OpenRaiser/Intern-Atlas huggingface dataset:
Learning in Repeated Games: Human Versus Machine
Venue: arXiv cs.CY 2014
Year: 2014

While Artificial Intelligence has successfully outperformed humans in complex combinatorial games (such as chess and checkers), humans have retained their supremacy in social interactions that require intuition and adaptation, such as cooperation and coordination games. Despite significant advances in learning algorithms, most algorithms adapt at times scales which are not relevant for interactions with humans, and therefore the advances in AI on this front have remained of a more theoretical nature. This has also hindered the experimental evaluation of how these algorithms perform against humans, as the length of experiments needed to evaluate them is beyond what humans are reasonably expected to endure (max 100 repetitions). This scenario is rapidly changing, as recent algorithms are able to converge to their functional regimes in shorter time-scales. Additionally, this shift opens up possibilities for experimental investigation: where do humans stand compared with these new algorithms? We evaluate humans experimentally against a representative element of these fast-converging algorithms. Our results indicate that the performance of at least one of these algorithms is comparable to, and even exceeds, the performance of people.
Writing on a Dirty Paper in the presence of Jamming
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the problem of writing on a dirty paper in the presence of jamming is examined. We consider an AWGN channel with an additive white Gaussian state and an additive adversarial jammer. The state is assumed to be known non-causally to the encoder and the jammer but not to the decoder. The capacity of the channel in the presence of a jammer is determined. A surprising result that this capacity is equal to the capacity of a relaxed version of the problem, where the state is also known non-causally to the decoder, is proved.
SleepScale: Runtime Joint Speed Scaling and Sleep States Management for Power Efficient Data Centers
Venue: arXiv cs.PF 2014
Year: 2014

Power consumption in data centers has been growing significantly in recent years. To reduce power, servers are being equipped with increasingly sophisticated power management mechanisms. Different mechanisms offer dramatically different trade-offs between power savings and performance penalties. Considering the complexity, variety, and temporally varying nature of the applications hosted in a typical data center, intelligently determining which power management policy to use and when is a complicated task. In this paper we analyze a system model featuring both performance scaling and low-power states. We reveal the interplay between performance scaling and low-power states via intensive simulation and analytic verification. Based on the observations, we present SleepScale, a runtime power management tool designed to efficiently exploit existing power control mechanisms. At run time, SleepScale characterizes power consumption and quality-of-service (QoS) for each low-power state and frequency setting, and selects the best policy for a given QoS constraint. We evaluate SleepScale using workload traces from data centers and achieve significant power savings relative to conventional power management strategies.
Analytical Assessment of Coordinated Overlay D2D Communications
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, analytical assessment of overlay-inband device-to-device (D2D) communications is investigated, under cellular-network-assisted (coordinated) scheduling. To this end, a simple scheduling scheme is assumed that takes into account only local (per cell) topological information of the D2D links. Stochastic geometry tools are utilized in order to obtain analytical expressions for the interferers density as well as the D2D link signal-to-interference-ratio distribution. The analytical results accuracy is validated by comparison with simulations. In addition, the analytical expressions are employed for efficiently optimizing the parameters of a cellular system with overlay D2D communications. It is shown that coordinated scheduling of D2D transmissions enhances system performance both in terms of average user rate as well as maximum allowable D2D link distance.
Sequential Resource Allocation with Positional Costs
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of minimizing the total cost to run a sequence of $n$ tasks in the given order by $k$ agents under the positional cost model. The cost to run a task not only depends on the intrinsic cost of the task itself, but also monotonically related to the position this task is in the working list of the agent assigned. Such a positional effect can naturally arise from the classic sum-of-completion-time minimization problems, and is also well motivated by the varying efficiency when an agent works in reality (such as due to the learning effects or deteriorating effects). Also, it can be seen as a deterministic variant of the classic Baysian sequential decision making problems. This paper presents a simple and practical algorithm that runs in $O(k^2 n)$ time and minimizes the total cost of any problem instance consisting of two task types. The algorithm works by making greedy decision for each task sequentially based on some stopping thresholds in a "greedy-like" allocation simulation -- a working style coinciding with Gittins' optimal-stopping based algorithm for the classic Baysian multi-armed bandit problem.
Analysis and Design of Two-Hop Diffusion-Based Molecular Communication Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a two-hop molecular communication network consisting of one nanotransmitter, one nanoreceiver, and one nanotransceiver acting as a relay. We consider two different schemes for relaying to improve the range of diffusion-based molecular communication. In the first scheme, two different types of messenger molecules are utilized at the relay node for transmission and detection. In the second scheme, we assume that there is only one type of molecule available to be used as an information carrier. We identify self-interference as the performance-limiting effect for the second relaying scheme. Self-interference occurs when the relay must detect the same type of molecule that it also emits. Furthermore, we consider two relaying modes analogous to those used in wireless communication systems, i.e., full-duplex and half-duplex. In particular, while our main focus is on full-duplex relaying, half-duplex relaying is employed as a means to mitigate self-interference. In addition, we propose the adaptation of the decision threshold as an effective mechanism to mitigate self-interference at the relay for full-duplex transmission. We derive closed-form expressions for the expected error probability of the network for both considered relaying schemes.
Tolerating Silent Data Corruption in Opaque Preconditioners
Venue: arXiv cs.DC 2014
Year: 2014

We demonstrate algorithm-based fault tolerance for silent, transient data corruption in "black-box" preconditioners. We consider both additive Schwarz domain decomposition with an ILU(k) subdomain solver, and algebraic multigrid, both implemented in the Trilinos library. We evaluate faults that corrupt preconditioner results in both single and multiple MPI ranks. We then analyze how our approach behaves when then application is scaled. Our technique is based on a Selective Reliability approach that performs most operations in an unreliable mode, with only a few operations performed reliably. We also investigate two responses to faults and discuss the performance overheads imposed by each. For a non-symmetric problem solved using GMRES and ILU, we show that at scale our fault tolerance approach incurs only 22% overhead for the worst case. With detection techniques, we are able to reduce this overhead to 1.8% in the worst case.
Large Margin Image Set Representation and Classification
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose a novel image set representation and classification method by maximizing the margin of image sets. The margin of an image set is defined as the difference of the distance to its nearest image set from different classes and the distance to its nearest image set of the same class. By modeling the image sets by using both their image samples and their affine hull models, and maximizing the margins of the images sets, the image set representation parameter learning problem is formulated as an minimization problem, which is further optimized by an expectation -maximization (EM) strategy with accelerated proximal gradient (APG) optimization in an iterative algorithm. To classify a given test image set, we assign it to the class which could provide the largest margin. Experiments on two applications of video-sequence-based face recognition demonstrate that the proposed method significantly outperforms state-of-the-art image set classification methods in terms of both effectiveness and efficiency.
Motion planning and Collision Avoidance using Non-Gradient Vector Fields. Technical Report
Venue: arXiv cs.RO 2014
Year: 2014

This paper presents a novel feedback method on the motion planning for unicycle robots in environments with static obstacles, along with an extension to the distributed planning and coordination in multi-robot systems. The method employs a family of 2-dimensional analytic vector fields, whose integral curves exhibit various patterns depending on the value of a parameter lambda. More specifically, for an a priori known value of lambda, the vector field has a unique singular point of dipole type and can be used to steer the unicycle to a goal configuration. Furthermore, for the unique value of lambda that the vector field has a continuum of singular points, the integral curves are used to define flows around obstacles. An almost global feedback motion plan can then be constructed by suitably blending attractive and repulsive vector fields in a static obstacle environment. The method does not suffer from the appearance of sinks (stable nodes) away from goal point. Compared to other similar methods which are free of local minima, the proposed approach does not require any parameter tuning to render the desired convergence properties. The paper also addresses the extension of the method to the distributed coordination and control of multiple robots, where each robot needs to navigate to a goal configuration while avoiding collisions with the remaining robots, and while using local information only. More specifically, based on the results which apply to the single-robot case, a motion coordination protocol is presented which guarantees the safety of the multi-robot system and the almost global convergence of the robots to their goal configurations. The efficacy of the proposed methodology is demonstrated via simulation results in static and dynamic environments.
A Fast Multiple Attractor Cellular Automata with Modified Clonal Classifier for Splicing Site Prediction in Human Genome
Venue: arXiv cs.CE 2014
Year: 2014

Bioinformatics encompass storing, analyzing and interpreting the biological data. Most of the challenges for Machine Learning methods like Cellular Automata is to furnish the functional information with the corresponding biological sequences. In eukaryotes DNA is divided into introns and exons. The introns will be removed to make the coding region by a process called splicing. By indentifying a splice site we can easily specify the DNA sequence category (Donor/Accepter/Neither).Splicing sites play an important role in understanding the genes. A class of CA which can handle fuzzy logic is employed with modified clonal algorithm is proposed to identify the splicing site. This classifier is tested with Irvine Primate Splice Junction Database. It is compared with NNspIICE, GENIO, HSPL and SPIICE VIEW. The reported accuracy and efficiency of prediction is quite promising.
List and Unique Error-Erasure Decoding of Interleaved Gabidulin Codes with Interpolation Techniques
Venue: arXiv cs.IT 2014
Year: 2014

A new interpolation-based decoding principle for interleaved Gabidulin codes is presented. The approach consists of two steps: First, a multi-variate linearized polynomial is constructed which interpolates the coefficients of the received word and second, the roots of this polynomial have to be found. Due to the specific structure of the interpolation polynomial, both steps (interpolation and root-finding) can be accomplished by solving a linear system of equations. This decoding principle can be applied as a list decoding algorithm (where the list size is not necessarily bounded polynomially) as well as an efficient probabilistic unique decoding algorithm. For the unique decoder, we show a connection to known unique decoding approaches and give an upper bound on the failure probability. Finally, we generalize our approach to incorporate not only errors, but also row and column erasures.
Classifying pairs with trees for supervised biological network inference
Venue: arXiv cs.LG 2014
Year: 2014

Networks are ubiquitous in biology and computational approaches have been largely investigated for their inference. In particular, supervised machine learning methods can be used to complete a partially known network by integrating various measurements. Two main supervised frameworks have been proposed: the local approach, which trains a separate model for each network node, and the global approach, which trains a single model over pairs of nodes. Here, we systematically investigate, theoretically and empirically, the exploitation of tree-based ensemble methods in the context of these two approaches for biological network inference. We first formalize the problem of network inference as classification of pairs, unifying in the process homogeneous and bipartite graphs and discussing two main sampling schemes. We then present the global and the local approaches, extending the later for the prediction of interactions between two unseen network nodes, and discuss their specializations to tree-based ensemble methods, highlighting their interpretability and drawing links with clustering techniques. Extensive computational experiments are carried out with these methods on various biological networks that clearly highlight that these methods are competitive with existing methods.
SimpleTrack:Adaptive Trajectory Compression with Deterministic Projection Matrix for Mobile Sensor Networks
Venue: arXiv cs.IT 2014
Year: 2014

Some mobile sensor network applications require the sensor nodes to transfer their trajectories to a data sink. This paper proposes an adaptive trajectory (lossy) compression algorithm based on compressive sensing. The algorithm has two innovative elements. First, we propose a method to compute a deterministic projection matrix from a learnt dictionary. Second, we propose a method for the mobile nodes to adaptively predict the number of projections needed based on the speed of the mobile nodes. Extensive evaluation of the proposed algorithm using 6 datasets shows that our proposed algorithm can achieve sub-metre accuracy. In addition, our method of computing projection matrices outperforms two existing methods. Finally, comparison of our algorithm against a state-of-the-art trajectory compression algorithm show that our algorithm can reduce the error by 10-60 cm for the same compression ratio.
Deepening the Relationship between SEFE and C-Planarity
Venue: arXiv cs.CC 2014
Year: 2014

In this paper we deepen the understanding of the connection between two long-standing Graph Drawing open problems, that is, Simultaneous Embedding with Fixed Edges (SEFE) and Clustered Planarity (C-PLANARITY). In his GD'12 paper Marcus Schaefer presented a reduction from C-PLANARITY to SEFE of two planar graphs (SEFE-2). We prove that a reduction exists also in the opposite direction, if we consider instances of SEFE-2 in which the intersection graph is connected. We pose as an open question whether the two problems are polynomial-time equivalent.
Mathoid: Robust, Scalable, Fast and Accessible Math Rendering for Wikipedia
Venue: arXiv cs.DL 2014
Year: 2014

Wikipedia is the first address for scientists who want to recap basic mathematical and physical laws and concepts. Today, formulae in those pages are displayed as Portable Network Graphics images. Those images do not integrate well into the text, can not be edited after copying, are inaccessible to screen readers for people with special needs, do not support line breaks for small screens and do not scale for high resolution devices. Mathoid improves this situation and converts formulae specified by Wikipedia editors in a TeX-like input format to MathML, with Scalable Vector Graphics images as a fallback solution.
A Unified Ordering for Termination Proving
Venue: arXiv cs.LO 2014
Year: 2014

We introduce a reduction order called the weighted path order (WPO) that subsumes many existing reduction orders. WPO compares weights of terms as in the Knuth-Bendix order (KBO), while WPO allows weights to be computed by a wide class of interpretations. We investigate summations, polynomials and maximums for such interpretations. We show that KBO is a restricted case of WPO induced by summations, the polynomial order (POLO) is subsumed by WPO induced by polynomials, and the lexicographic path order (LPO) is a restricted case of WPO induced by maximums. By combining these interpretations, we obtain an instance of WPO that unifies KBO, LPO and POLO. In order to fit WPO in the modern dependency pair framework, we further provide a reduction pair based on WPO and partial statuses. As a reduction pair, WPO also subsumes matrix interpretations. We finally present SMT encodings of our techniques, and demonstrate the significance of our work through experiments.
Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
Venue: arXiv cs.SC 2014
Year: 2014

Cylindrical algebraic decomposition(CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. When using CAD, there is often a choice for the ordering placed on the variables. This can be important, with some problems infeasible with one variable ordering but easy with another. Machine learning is the process of fitting a computer model to a complex function based on properties learned from measured data. In this paper we use machine learning (specifically a support vector machine) to select between heuristics for choosing a variable ordering, outperforming each of the separate heuristics.
Math Indexer and Searcher Web Interface: Towards Fulfillment of Mathematicians' Information Needs
Venue: arXiv cs.DL 2014
Year: 2014

We are designing and developing a web user interface for digital mathematics libraries called WebMIaS. It allows queries to be expressed by mathematicians through a faceted search interface. Users can combine standard textual autocompleted keywords with keywords in the form of mathematical formulae in LaTeX or MathML formats. Formulae are shown rendered by the web browser on-the-fly for users' feedback. We describe WebMIaS design principles and our experiences deploying in the European Digital Mathematics Library (EuDML). We further describe the issues addressed by formulae canonicalization and by extending the MIaS indexing engine with Content MathML support.
On the Non-Monotonic Description Logic $\mathcal{ALC}$+T$_{\mathsf{min}}$
Venue: arXiv cs.AI 2014
Year: 2014

In the last 20 years many proposals have been made to incorporate non-monotonic reasoning into description logics, ranging from approaches based on default logic and circumscription to those based on preferential semantics. In particular, the non-monotonic description logic $\mathcal{ALC}$+T$_{\mathsf{min}}$ uses a combination of the preferential semantics with minimization of a certain kind of concepts, which represent atypical instances of a class of elements. One of its drawbacks is that it suffers from the problem known as the \emph{property blocking inheritance}, which can be seen as a weakness from an inferential point of view. In this paper we propose an extension of $\mathcal{ALC}$+T$_{\mathsf{min}}$, namely $\mathcal{ALC}$+T$^+_{\mathsf{min}}$, with the purpose to solve the mentioned problem. In addition, we show the close connection that exists between $\mathcal{ALC}$+T$^+_{\mathsf{min}}$ and concept-circumscribed knowledge bases. Finally, we study the complexity of deciding the classical reasoning tasks in $\mathcal{ALC}$+T$^+_{\mathsf{min}}$.
Une approche CSP pour l'aide à la localisation d'erreurs
Venue: arXiv cs.AI 2014
Year: 2014

We introduce in this paper a new CP-based approach to support errors location in a program for which a counter-example is available, i.e. an instantiation of the input variables that violates the post-condition. To provide helpful information for error location, we generate a constraint system for the paths of the CFG (Control Flow Graph) for which at most k conditional statements may be erroneous. Then, we calculate Minimal Correction Sets (MCS) of bounded size for each of these paths. The removal of one of these sets of constraints yields a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the post condition. We extend the algorithm proposed by Liffiton and Sakallah \cite{LiS08} to handle programs with numerical statements more efficiently. We present preliminary experimental results that are quite encouraging.
EAGr: Supporting Continuous Ego-centric Aggregate Queries over Large Dynamic Graphs
Venue: arXiv cs.DB 2014
Year: 2014

In this work, we present EAGr, a system for supporting large numbers of continuous neighborhood-based ("ego-centric") aggregate queries over large, highly dynamic, and rapidly evolving graphs. Examples of such queries include computation of personalized, tailored trends in social networks, anomaly/event detection in financial transaction networks, local search and alerts in spatio-temporal networks, to name a few. Key challenges in supporting such continuous queries include high update rates typically seen in these situations, large numbers of queries that need to be executed simultaneously, and stringent low latency requirements. We propose a flexible, general, and extensible in-memory framework for executing different types of ego-centric aggregate queries over large dynamic graphs with low latencies. Our framework is built around the notion of an aggregation overlay graph, a pre-compiled data structure that encodes the computations to be performed when an update/query is received. The overlay graph enables sharing of partial aggregates across multiple ego-centric queries (corresponding to the nodes in the graph), and also allows partial pre-computation of the aggregates to minimize the query latencies. We present several highly scalable techniques for constructing an overlay graph given an aggregation function, and also design incremental algorithms for handling structural changes to the underlying graph. We also present an optimal, polynomial-time algorithm for making the pre-computation decisions given an overlay graph, and evaluate an approach to incrementally adapt those decisions as the workload changes. Although our approach is naturally parallelizable, we focus on a single-machine deployment and show that our techniques can easily handle graphs of size up to 320 million nodes and edges, and achieve update/query throughputs of over 500K/s using a single, powerful machine.
Equating the achievable exponent region to the achievable entropy region by partitioning the source
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we investigate the image size characterization problem. We show that any arbitrary source set may be decomposed into sets whose image size characterization is the same as its entropy characterization. We also show that the number of these sets required is small enough that one may consider that from a coding perspective the achievable entropy region and achievable exponent region are equal. This has an impact on many source networks and network problems whose solution heretofore could not have the image size characterization applied to them.