OpenRaiser/Intern-Atlas huggingface dataset:
Application of Multi-core Parallel Programming to a Combination of Ant Colony Optimization and Genetic Algorithm
Venue: arXiv cs.NE 2014
Year: 2014

This Paper will deal with a combination of Ant Colony and Genetic Programming Algorithm to optimize Travelling Salesmen problem (NP-Hard). However, the complexity of the algorithm requires considerable computational time and resources. Parallel implementation can reduce the computational time. In this paper, emphasis in the parallelizing section is given to Multi-core architecture and Multi-Processor Systems which is developed and used almost everywhere today and hence, multi-core parallelization to the combination of algorithm is achieved by OpenMP library by Intel Corporation.
Verification of Relational Multiagent Systems with Data Types (Extended Version)
Venue: arXiv cs.AI 2014
Year: 2014

We study the extension of relational multiagent systems (RMASs), where agents manipulate full-fledged relational databases, with data types and facets equipped with domain-specific, rigid relations (such as total orders). Specifically, we focus on design-time verification of RMASs against rich first-order temporal properties expressed in a variant of first-order mu-calculus with quantification across states. We build on previous decidability results under the "state-bounded" assumption, i.e., in each single state only a bounded number of data objects is stored in the agent databases, while unboundedly many can be encountered over time. We recast this condition, showing decidability in presence of dense, linear orders, and facets defined on top of them. Our approach is based on the construction of a finite-state, sound and complete abstraction of the original system, in which dense linear orders are reformulated as non-rigid relations working on the active domain of the system only. We also show undecidability when including a data type equipped with the successor relation.
Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems
Venue: arXiv cs.DS 2014
Year: 2014

We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an $8.497$-approximation for the version where vehicles may be located at multiple depots and a $7.183$-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP-relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs---{\em configuration LPs} and {\em bidirected LP-relaxations}---that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP-relaxations for this class of problems. The $8.497$-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The $7.183$-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any $k$, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i.e., edge cost + number of uncovered nodes) as the best collection of $k$ rooted paths. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times.
Optimal Reduction of Multivariate Dirac Mixture Densities
Venue: arXiv cs.SY 2014
Year: 2014

This paper is concerned with the optimal approximation of a given multivariate Dirac mixture, i.e., a density comprising weighted Dirac distributions on a continuous domain, by an equally weighted Dirac mixture with a reduced number of components. The parameters of the approximating density are calculated by minimizing a smooth global distance measure, a generalization of the well-known Cramér-von Mises Distance to the multivariate case. This generalization is achieved by defining an alternative to the classical cumulative distribution, the Localized Cumulative Distribution (LCD), as a characterization of discrete random quantities (on continuous domains), which is unique and symmetric also in the multivariate case. The resulting approximation method provides the basis for various efficient nonlinear state and parameter estimation methods.
Using graph transformation algorithms to generate natural language equivalents of icons expressing medical concepts
Venue: arXiv cs.CL 2014
Year: 2014

A graphical language addresses the need to communicate medical information in a synthetic way. Medical concepts are expressed by icons conveying fast visual information about patients' current state or about the known effects of drugs. In order to increase the visual language's acceptance and usability, a natural language generation interface is currently developed. In this context, this paper describes the use of an informatics method ---graph transformation--- to prepare data consisting of concepts in an OWL-DL ontology for use in a natural language generation component. The OWL concept may be considered as a star-shaped graph with a central node. The method transforms it into a graph representing the deep semantic structure of a natural language phrase. This work may be of future use in other contexts where ontology concepts have to be mapped to half-formalized natural language expressions.
Aggregating partial rankings with applications to peer grading in massive online open courses
Venue: arXiv cs.AI 2014
Year: 2014

We investigate the potential of using ordinal peer grading for the evaluation of students in massive online open courses (MOOCs). According to such grading schemes, each student receives a few assignments (by other students) which she has to rank. Then, a global ranking (possibly translated into numerical scores) is produced by combining the individual ones. This is a novel application area for social choice concepts and methods where the important problem to be solved is as follows: how should the assignments be distributed so that the collected individual rankings can be easily merged into a global one that is as close as possible to the ranking that represents the relative performance of the students in the assignment? Our main theoretical result suggests that using very simple ways to distribute the assignments so that each student has to rank only $k$ of them, a Borda-like aggregation method can recover a $1-O(1/k)$ fraction of the true ranking when each student correctly ranks the assignments she receives. Experimental results strengthen our analysis further and also demonstrate that the same method is extremely robust even when students have imperfect capabilities as graders. We believe that our results provide strong evidence that ordinal peer grading can be a highly effective and scalable solution for evaluation in MOOCs.
Pseudo Dynamic Transitional Modeling of Building Heating Energy Demand Using Artificial Neural Network
Venue: arXiv cs.CE 2014
Year: 2014

This paper presents the building heating demand prediction model with occupancy profile and operational heating power level characteristics in short time horizon (a couple of days) using artificial neural network. In addition, novel pseudo dynamic transitional model is introduced, which consider time dependent attributes of operational power level characteristics and its effect in the overall model performance is outlined. Pseudo dynamic model is applied to a case study of French Institution building and compared its results with static and other pseudo dynamic neural network models. The results show the coefficients of correlation in static and pseudo dynamic neural network model of 0.82 and 0.89 (with energy consumption error of 0.02%) during the learning phase, and 0.61 and 0.85 during the prediction phase respectively. Further, orthogonal array design is applied to the pseudo dynamic model to check the schedule of occupancy profile and operational heating power level characteristics. The results show the new schedule and provide the robust design for pseudo dynamic model. Due to prediction in short time horizon, it finds application for Energy Services Company (ESCOs) to manage the heating load for dynamic control of heat production system.
Structured Hough Voting for Vision-based Highway Border Detection
Venue: arXiv cs.CV 2014
Year: 2014

We propose a vision-based highway border detection algorithm using structured Hough voting. Our approach takes advantage of the geometric relationship between highway road borders and highway lane markings. It uses a strategy where a number of trained road border and lane marking detectors are triggered, followed by Hough voting to generate corresponding detection of the border and lane marking. Since the initially triggered detectors usually result in large number of positives, conventional frame-wise Hough voting is not able to always generate robust border and lane marking results. Therefore, we formulate this problem as a joint detection-and-tracking problem under the structured Hough voting model, where tracking refers to exploiting inter-frame structural information to stabilize the detection results. Both qualitative and quantitative evaluations show the superiority of the proposed structured Hough voting model over a number of baseline methods.
Correlations of Interference and Link Successes in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

In heterogeneous cellular networks (HCNs), the interference received at a user is correlated over time slots since it comes from the same set of randomly located BSs. This results in the correlations of link successes, thus affecting network performance. Under the assumptions of a K-tier Poisson network, strongest-candidate based BS association, and independent Rayleigh fading, we first quantify the correlation coefficients of interference. We observe that the interference correlation is independent of the number of tiers, BS density, SIR threshold, and transmit power. Then, we study the correlations of link successes in terms of the joint success probability over multiple time slots. We show that the joint success probability is decided by the success probability in a single time slot and a diversity polynomial, which represents the temporal interference correlation. Moreover, the parameters of HCNs have an important influence on the joint success probability by affecting the success probability in a single time slot. Particularly, we obtain the condition under which the joint success probability increases with the BS density and transmit power. We further show that the conditional success probability given prior successes only depends on the path loss exponent and the number of time slots.
Automated Reasoning in Deontic Logic
Venue: arXiv cs.AI 2014
Year: 2014

Deontic logic is a very well researched branch of mathematical logic and philosophy. Various kinds of deontic logics are discussed for different application domains like argumentation theory, legal reasoning, and acts in multi-agent systems. In this paper, we show how standard deontic logic can be stepwise transformed into description logic and DL- clauses, such that it can be processed by Hyper, a high performance theorem prover which uses a hypertableau calculus. Two use cases, one from multi-agent research and one from the development of normative system are investigated.
Cognitive Systems and Question Answering
Venue: arXiv cs.AI 2014
Year: 2014

This paper briefly characterizes the field of cognitive computing. As an exemplification, the field of natural language question answering is introduced together with its specific challenges. A possibility to master these challenges is illustrated by a detailed presentation of the LogAnswer system, which is a successful representative of the field of natural language question answering.
Combinatorial Auctions via Posted Prices
Venue: arXiv cs.GT 2014
Year: 2014

We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in an arbitrary order, each purchasing her favorite bundle from among the unsold items at the posted prices. These mechanisms are simple, transparent and trivially dominant strategy incentive compatible (DSIC). We show that when agent preferences are fractionally subadditive (which includes all submodular functions), there always exist prices that, in expectation, obtain at least half of the optimal welfare. Our result is constructive: given black-box access to a combinatorial auction algorithm A, sample access to the prior distribution, and appropriate query access to the sampled valuations, one can compute, in polytime, prices that guarantee at least half of the expected welfare of A. As a corollary, we obtain the first polytime (in n and m) constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions, given access to demand query oracles. Our results also extend to valuations with complements, where the approximation factor degrades linearly with the level of complementarity.
Towards an objective ranking in online reputation systems: the effect of the rating projection
Venue: arXiv cs.IR 2014
Year: 2014

Online reputation systems are commonly used by e-commerce providers nowadays. In order to generate an objective ranking of online items' quality according to users' ratings, many sophisticated algorithms have been proposed in the literature. In this paper, instead of proposing new algorithms we focus on a more fundamental problem: the rating projection. The basic idea is that even though the rating values given by users are linearly separated, the real preference of users to items between different values gave is nonlinear. We thus design an approach to project the original ratings of users to more representative values. This approach can be regarded as a data pretreatment method. Simulation in both artificial and real networks shows that the performance of the ranking algorithms can be improved when the projected ratings are used.
Link Prediction in Social Networks: the State-of-the-Art
Venue: arXiv cs.SI 2014
Year: 2014

In social networks, link prediction predicts missing links in current networks and new or dissolution links in future networks, is important for mining and analyzing the evolution of social networks. In the past decade, many works have been done about the link prediction in social networks. The goal of this paper is to comprehensively review, analyze and discuss the state-of-the-art of the link prediction in social networks. A systematical category for link prediction techniques and problems is presented. Then link prediction techniques and problems are analyzed and discussed. Typical applications of link prediction are also addressed. Achievements and roadmaps of some active research groups are introduced. Finally, some future challenges of the link prediction in social networks are discussed.
PivotCompress: Compression by Sorting
Venue: arXiv cs.DS 2014
Year: 2014

Sorted data is usually easier to compress than unsorted permutations of the same data. This motivates a simple compression scheme: specify the sorted permutation of the data along with a representation of the sorted data compressed recursively. The sorted permutation can be specified by recording the decisions made by quicksort. If the size of the data is known, then the quicksort decisions describe the data at a rate that is nearly as efficient as the minimal prefix-free code for the distribution, which is bounded by the entropy of the distribution. This is possible even though the distribution is unknown ahead of time. Used in this way, quicksort acts as a universal code in that it is asymptotically optimal for any stationary source. The Shannon entropy is a lower bound when describing stochastic, independent symbols. However, it is possible to encode non-uniform, finite strings below the entropy of the sample distribution by also encoding symbol counts because the values in the sequence are no longer independent once the counts are known. The key insight is that sparse quicksort comparison vectors can also be compressed to achieve an even lower rate when data is highly non-uniform while incurring only a modest penalty when data is random.
Study of Gesture Recognition methods and augmented reality
Venue: arXiv cs.HC 2014
Year: 2014

With the growing technology, we humans always need something that stands out from the other thing. Gestures are most desirable source to Communicate with the Machines. Human Computer Interaction finds its importance when it comes to working with the Human gestures to control the computer applications. Usually we control the applications using mouse, keyboard, laser pointers etc. but, with the recent advent in the technology it has even left behind their usage by introducing more efficient techniques to control applications. There are many Gesture Recognition techniques that have been implemented using image processing in the past. However recognizing the gestures in the noisy background has always been a difficult task to achieve. In the proposed system, we are going to use one such technique called Augmentation in Image processing to control Media Player. We will recognize Gestures using which we are going to control the operations on Media player. Augmentation usually is one step ahead when it comes to virtual reality. It has no restrictions on the background. Moreover it also does not rely on certain things like gloves, color pointers etc. for recognizing the gesture. This system mainly appeals to those users who always looks out for a better option that makes their interaction with computer more simpler or easier.
Performance Limits of Segmented Compressive Sampling: Correlated Samples versus Bits
Venue: arXiv cs.IT 2014
Year: 2014

This paper gives performance limits of the segmented compressive sampling (CS) which collects correlated samples. It is shown that the effect of correlation among samples for the segmented CS can be characterized by a penalty term in the corresponding bounds on the sampling rate. Moreover, this penalty term is vanishing as the signal dimension increases. It means that the performance degradation due to the fixed correlation among samples obtained by the segmented CS (as compared to the standard CS with equivalent size sampling matrix) is negligible for a high-dimensional signal. In combination with the fact that the signal reconstruction quality improves with additional samples obtained by the segmented CS (as compared to the standard CS with sampling matrix of the size given by the number of original uncorrelated samples), the fact that the additional correlated samples also provide new information about a signal is a strong argument for the segmented CS.
Another proof of undecidability for the correspondence decision problem - Had I been Emil Post
Venue: arXiv cs.LO 2014
Year: 2014

In 1946 Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264 - 268) defined a famous correspondence decision problem which is nowadays called the Post Correspondence Problem, and he proved that the problem is undecidable. In this article we follow the steps of Post, and give another, simpler and more straightforward proof of the undecidability of the problem using the same source of reduction as Post original did, namely, the Post Normal Systems.
Can we build a conscious machine?
Venue: arXiv cs.ET 2014
Year: 2014

The underlying physiological mechanisms of generating conscious states are still unknown. To make progress on the problem of consciousness, we will need to experimentally design a system that evolves in a similar way our brains do. Recent experimental data show that the multiscale nature of the evolving human brain can be implemented by reprogramming human cells. A hybrid system can be designed to include an evolving brain equipped with digital computers that maintain homeostasis and provide the right amount of nutrients and oxygen for the brain growth. Shaping the structure of the evolving brain will be progressively achieved by controlling spatial organization of various types of cells. Following a specific program, the evolving brain can be trained using substitutional reality to learn and experience live scenes. We already know from neuroelectrodynamics that meaningful information in the brain is electrically (wirelessly) read out and written fast in neurons and synapses at the molecular (protein) level during the generation of action potentials and synaptic activities. Since with training, meaningful information accumulates and is electrically integrated in the brain, one can predict, that this gradual process of training will trigger a tipping point for conscious experience to emerge in the hybrid system.
Ontology Module Extraction via Datalog Reasoning
Venue: arXiv cs.AI 2014
Year: 2014

Module extraction - the task of computing a (preferably small) fragment M of an ontology T that preserves entailments over a signature S - has found many applications in recent years. Extracting modules of minimal size is, however, computationally hard, and often algorithmically infeasible. Thus, practical techniques are based on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations, however, ensure that M preserves all second-order entailments of T w.r.t. S, which is stronger than is required in many applications, and may lead to large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach not only generalises existing approximations in an elegant way, but it can also be tailored to preserve only specific kinds of entailments, which allows us to extract significantly smaller modules. An evaluation on widely-used ontologies has shown very encouraging results.
Type-Driven Incremental Semantic Parsing with Polymorphism
Venue: arXiv cs.CL 2014
Year: 2014

Semantic parsing has made significant progress, but most current semantic parsers are extremely slow (CKY-based) and rather primitive in representation. We introduce three new techniques to tackle these problems. First, we design the first linear-time incremental shift-reduce-style semantic parsing algorithm which is more efficient than conventional cubic-time bottom-up semantic parsers. Second, our parser, being type-driven instead of syntax-driven, uses type-checking to decide the direction of reduction, which eliminates the need for a syntactic grammar such as CCG. Third, to fully exploit the power of type-driven semantic parsing beyond simple types (such as entities and truth values), we borrow from programming language theory the concepts of subtype polymorphism and parametric polymorphism to enrich the type system in order to better guide the parsing. Our system learns very accurate parses in GeoQuery, Jobs and Atis domains.