OpenRaiser/Intern-Atlas huggingface dataset:
Improved Lower Bounds on the Total Variation Distance for the Poisson Approximation
Venue: arXiv cs.IT 2013
Year: 2013

New lower bounds on the total variation distance between the distribution of a sum of independent Bernoulli random variables and the Poisson random variable (with the same mean) are derived via the Chen-Stein method. The new bounds rely on a non-trivial modification of the analysis by Barbour and Hall (1984) which surprisingly gives a significant improvement. A use of the new lower bounds is addressed.
The Ciao clp(FD) Library. A Modular CLP Extension for Prolog
Venue: arXiv cs.PL 2013
Year: 2013

We present a new free library for Constraint Logic Programming over Finite Domains, included with the Ciao Prolog system. The library is entirely written in Prolog, leveraging on Ciao's module system and code transformation capabilities in order to achieve a highly modular design without compromising performance. We describe the interface, implementation, and design rationale of each modular component. The library meets several design goals: a high level of modularity, allowing the individual components to be replaced by different versions; high-efficiency, being competitive with other FD implementations; a glass-box approach, so the user can specify new constraints at different levels; and a Prolog implementation, in order to ease the integration with Ciao's code analysis components. The core is built upon two small libraries which implement integer ranges and closures. On top of that, a finite domain variable datatype is defined, taking care of constraint reexecution depending on range changes. These three libraries form what we call the FD kernel of the library. This FD kernel is used in turn to implement several higher-level finite domain constraints, specified using indexicals. Together with a labeling module this layer forms what we name \emph{the FD solver}. A final level integrates the clp(FD) paradigm with our FD solver. This is achieved using attributed variables and a compiler from the clp(FD) language to the set of constraints provided by the solver. It should be noted that the user of the library is encouraged to work in any of those levels as seen convenient: from writing a new range module to enriching the set of FD constraints by writing new indexicals.
PyPLN: a Distributed Platform for Natural Language Processing
Venue: arXiv cs.CL 2013
Year: 2013

This paper presents a distributed platform for Natural Language Processing called PyPLN. PyPLN leverages a vast array of NLP and text processing open source tools, managing the distribution of the workload on a variety of configurations: from a single server to a cluster of linux servers. PyPLN is developed using Python 2.7.3 but makes it very easy to incorporate other softwares for specific tasks as long as a linux version is available. PyPLN facilitates analyses both at document and corpus level, simplifying management and publication of corpora and analytical results through an easy to use web interface. In the current (beta) release, it supports English and Portuguese languages with support to other languages planned for future releases. To support the Portuguese language PyPLN uses the PALAVRAS parser\citep{Bick2000}. Currently PyPLN offers the following features: Text extraction with encoding normalization (to UTF-8), part-of-speech tagging, token frequency, semantic annotation, n-gram extraction, word and sentence repertoire, and full-text search across corpora. The platform is licensed as GPL-v3.
A coding approach to guarantee information integrity against a Byzantine relay
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a random coding scheme with which two nodes can exchange information with guaranteed integrity over a two-way Byzantine relay. This coding scheme is employed to obtain an inner bound on the capacity region with guaranteed information integrity. No pre-shared secret or secret transmission is needed for the proposed scheme. Hence the inner bound obtained is generally larger than those achieved based on secret transmission schemes. This approach advocates the separation of supporting information integrity and secrecy.
Maximum a posteriori estimation of piecewise arcs in tempo time-series
Venue: arXiv cs.SD 2013
Year: 2013

In musical performances with expressive tempo modulation, the tempo variation can be modelled as a sequence of tempo arcs. Previous authors have used this idea to estimate series of piecewise arc segments from data. In this paper we describe a probabilistic model for a time-series process of this nature, and use this to perform inference of single- and multi-level arc processes from data. We describe an efficient Viterbi-like process for MAP inference of arcs. Our approach is score-agnostic, and together with efficient inference allows for online analysis of performances including improvisations, and can predict immediate future tempo trajectories.
Routing for Energy Minimization with Discrete Cost Functions
Venue: arXiv cs.NI 2013
Year: 2013

Energy saving is becoming an important issue in the design and use of computer networks. In this work we propose a problem that considers the use of rate adaptation as the energy saving strategy in networks. The problem is modeled as an integral demand-routing problem in a network with discrete cost functions at the links. The discreteness of the cost function comes from the different states (bandwidths) at which links can operate and, in particular, from the energy consumed at each state. This in its turn leads to the non-convexity of the cost function, and thus adds complexity to solve this problem. We formulate this routing problem as an integer program, and we show that the general case of this problem is NP-hard, and even hard to approximate. For the special case when the step ratio of the cost function is bounded, we show that effective approximations can be obtained. Our main algorithm executes two processes in sequence: relaxation and rounding. The relaxation process eliminates the non-convexity of the cost function, so that the problem is transformed into a fractional convex program solvable in polynomial time. After that, a randomized rounding process is used to get a feasible solution for the original problem. This algorithm provides a constant approximation ratio for uniform demands and an approximation ratio of $O(\log^{β-1} d)$ for non-uniform demands, where $β$ is a constant and $d$ is the largest demand.
Sparse Multiple Kernel Learning with Geometric Convergence Rate
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we study the problem of sparse multiple kernel learning (MKL), where the goal is to efficiently learn a combination of a fixed small number of kernels from a large pool that could lead to a kernel classifier with a small prediction error. We develop an efficient algorithm based on the greedy coordinate descent algorithm, that is able to achieve a geometric convergence rate under appropriate conditions. The convergence rate is achieved by measuring the size of functional gradients by an empirical $\ell_2$ norm that depends on the empirical data distribution. This is in contrast to previous algorithms that use a functional norm to measure the size of gradients, which is independent from the data samples. We also establish a generalization error bound of the learned sparse kernel classifier using the technique of local Rademacher complexity.
Distributed simulation of city inundation by coupled surface and subsurface porous flow for urban flood decision support system
Venue: arXiv cs.CE 2013
Year: 2013

We present a decision support system for flood early warning and disaster management. It includes the models for data-driven meteorological predictions, for simulation of atmospheric pressure, wind, long sea waves and seiches; a module for optimization of flood barrier gates operation; models for stability assessment of levees and embankments, for simulation of city inundation dynamics and citizens evacuation scenarios. The novelty of this paper is a coupled distributed simulation of surface and subsurface flows that can predict inundation of low-lying inland zones far from the submerged waterfront areas, as observed in St. Petersburg city during the floods. All the models are wrapped as software services in the CLAVIRE platform for urgent computing, which provides workflow management and resource orchestration.
Class Algebra for Ontology Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Class algebra provides a natural framework for sharing of ISA hierarchies between users that may be unaware of each other's definitions. This permits data from relational databases, object-oriented databases, and tagged XML documents to be unioned into one distributed ontology, sharable by all users without the need for prior negotiation or the development of a "standard" ontology for each field. Moreover, class algebra produces a functional correspondence between a class's class algebraic definition (i.e. its "intent") and the set of all instances which satisfy the expression (i.e. its "extent"). The framework thus provides assistance in quickly locating examples and counterexamples of various definitions. This kind of information is very valuable when developing models of the real world, and serves as an invaluable tool assisting in the proof of theorems concerning these class algebra expressions. Finally, the relative frequencies of objects in the ISA hierarchy can produce a useful Boolean algebra of probabilities. The probabilities can be used by traditional information-theoretic classification methodologies to obtain optimal ways of classifying objects in the database.
Analisis laporan tugas akhir mahasiswa Diploma I dari sudut pandang kaidah ilmiah dan penggunaan teknologi informasi
Venue: arXiv cs.OH 2013
Year: 2013

The purposes of this research are: 1) to analyze final report from scientific role, 2) the use of information technology (IT), and 3) to conduct academic athmosphere in research area. This research gives contributions to study program of MI-DI, such as: 1) to know the pattern of student final report from scientific role and the use of IT, 2) give input to study program for next final report scheme, and 3) can be used for next research reference. If we look to the quality of final report, there are several focuses to be prepared on tittle, literature review, methodology, results of report, discussion and also conclusion. But for the use of IT is already good but the varian is decrease.
Fast Damage Recovery in Robotics with the T-Resilience Algorithm
Venue: arXiv cs.RO 2013
Year: 2013

Damage recovery is critical for autonomous robots that need to operate for a long time without assistance. Most current methods are complex and costly because they require anticipating each potential damage in order to have a contingency plan ready. As an alternative, we introduce the T-resilience algorithm, a new algorithm that allows robots to quickly and autonomously discover compensatory behaviors in unanticipated situations. This algorithm equips the robot with a self-model and discovers new behaviors by learning to avoid those that perform differently in the self-model and in reality. Our algorithm thus does not identify the damaged parts but it implicitly searches for efficient behaviors that do not use them. We evaluate the T-Resilience algorithm on a hexapod robot that needs to adapt to leg removal, broken legs and motor failures; we compare it to stochastic local search, policy gradient and the self-modeling algorithm proposed by Bongard et al. The behavior of the robot is assessed on-board thanks to a RGB-D sensor and a SLAM algorithm. Using only 25 tests on the robot and an overall running time of 20 minutes, T-Resilience consistently leads to substantially better results than the other approaches.
Generalization Guarantees for a Binary Classification Framework for Two-Stage Multiple Kernel Learning
Venue: arXiv cs.LG 2013
Year: 2013

We present generalization bounds for the TS-MKL framework for two stage multiple kernel learning. We also present bounds for sparse kernel learning formulations within the TS-MKL framework.
Learning to Rank for Expert Search in Digital Libraries of Academic Publications
Venue: arXiv cs.IR 2013
Year: 2013

The task of expert finding has been getting increasing attention in information retrieval literature. However, the current state-of-the-art is still lacking in principled approaches for combining different sources of evidence in an optimal way. This paper explores the usage of learning to rank methods as a principled approach for combining multiple estimators of expertise, derived from the textual contents, from the graph-structure with the citation patterns for the community of experts, and from profile information about the experts. Experiments made over a dataset of academic publications, for the area of Computer Science, attest for the adequacy of the proposed approaches.
Arthur-Merlin Streaming Complexity
Venue: arXiv cs.CC 2013
Year: 2013

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. As an application, we give an $\mathcal{AM}$ streaming algorithm for the \emph{Distinct Elements} problem. Given a data stream of length $m$ over alphabet of size $n$, the algorithm uses $\tilde O(s)$ space and a proof of size $\tilde O(w)$, for every $s,w$ such that $s \cdot w \ge n$ (where $\tilde O$ hides a $\polylog(m,n)$ factor). We also prove a lower bound, showing that every $\mathcal{MA}$ streaming algorithm for the \emph{Distinct Elements} problem that uses $s$ bits of space and a proof of size $w$, satisfies $s \cdot w = Ω(n)$. As a part of the proof of the lower bound for the \emph{Distinct Elements} problem, we show a new lower bound of $Ω(\sqrt n)$ on the $\mathcal{MA}$ communication complexity of the \emph{Gap Hamming Distance} problem, and prove its tightness.
Sparse Camera Network for Visual Surveillance -- A Comprehensive Survey
Venue: arXiv cs.CV 2013
Year: 2013

Technological advances in sensor manufacture, communication, and computing are stimulating the development of new applications that are transforming traditional vision systems into pervasive intelligent camera networks. The analysis of visual cues in multi-camera networks enables a wide range of applications, from smart home and office automation to large area surveillance and traffic surveillance. While dense camera networks - in which most cameras have large overlapping fields of view - are well studied, we are mainly concerned with sparse camera networks. A sparse camera network undertakes large area surveillance using as few cameras as possible, and most cameras have non-overlapping fields of view with one another. The task is challenging due to the lack of knowledge about the topological structure of the network, variations in the appearance and motion of specific tracking targets in different views, and the difficulties of understanding composite events in the network. In this review paper, we present a comprehensive survey of recent research results to address the problems of intra-camera tracking, topological structure learning, target appearance modeling, and global activity understanding in sparse camera networks. A number of current open research issues are discussed.
Local Structure Matching Driven by Joint-Saliency-Structure Adaptive Kernel Regression
Venue: arXiv cs.CV 2013
Year: 2013

For nonrigid image registration, matching the particular structures (or the outliers) that have missing correspondence and/or local large deformations, can be more difficult than matching the common structures with small deformations in the two images. Most existing works depend heavily on the outlier segmentation to remove the outlier effect in the registration. Moreover, these works do not handle simultaneously the missing correspondences and local large deformations. In this paper, we defined the nonrigid image registration as a local adaptive kernel regression which locally reconstruct the moving image's dense deformation vectors from the sparse deformation vectors in the multi-resolution block matching. The kernel function of the kernel regression adapts its shape and orientation to the reference image's structure to gather more deformation vector samples of the same structure for the iterative regression computation, whereby the moving image's local deformations could be compliant with the reference image's local structures. To estimate the local deformations around the outliers, we use joint saliency map that highlights the corresponding saliency structures (called Joint Saliency Structures, JSSs) in the two images to guide the dense deformation reconstruction by emphasizing those JSSs' sparse deformation vectors in the kernel regression. The experimental results demonstrate that by using local JSS adaptive kernel regression, the proposed method achieves almost the best performance in alignment of all challenging image pairs with outlier structures compared with other five state-of-the-art nonrigid registration algorithms.
Multi-Way Information Exchange Over Completely-Connected Interference Networks with a Multi-Antenna Relay
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers a fully-connected interference network with a relay in which multiple users equipped with a single antenna want to exchange multiple unicast messages with other users in the network by sharing the relay equipped with multiple antennas. For such a network, the degrees of freedom (DoF) are derived by considering various message exchange scenarios: a multi-user fully-connected Y channel, a two-pair two-way interference channel with the relay, and a two-pair two-way X channel with the relay. Further, considering distributed relays employing a single antenna in the two-way interference channel and the three-user fully-connected Y channel, achievable sum-DoF are also derived in the two-way interference channel and the three-user fully-connected Y channel. A major implication of the derived DoF results is that a relay with multiple antennas or multiple relays employing a single antenna increases the capacity scaling law of the multi-user interference network when multiple directional information flows are considered, even if the networks are fully-connected and all nodes operate in half-duplex. These results reveal that the relay is useful in the multi-way interference network with practical considerations.
Wheel of B2C E-commerce Development in Saudi Arabia
Venue: arXiv cs.CY 2013
Year: 2013

Online retailing (a model of B2C e-commerce) is growing world-wide, with companies in many countries showing increased sales and productivity as a result. It has great potential within the global economy. This paper looks at the current status of online retailing in Saudi Arabia, with particular focus on what inhibits or enables both the customers and retailers. It also analyses the status of Government involvement and proposes a layered model, known as the Wheel of Online Retailing which illustrates how Government intervention can benefit the e-commerce in Saudi Arabia.
Bootstrap Methods for the Empirical Study of Decision-Making and Information Flows in Social Systems
Venue: arXiv cs.IT 2013
Year: 2013

We characterize the statistical bootstrap for the estimation of information-theoretic quantities from data, with particular reference to its use in the study of large-scale social phenomena. Our methods allow one to preserve, approximately, the underlying axiomatic relationships of information theory---in particular, consistency under arbitrary coarse-graining---that motivate use of these quantities in the first place, while providing reliability comparable to the state of the art for Bayesian estimators. We show how information-theoretic quantities allow for rigorous empirical study of the decision-making capacities of rational agents and the time-asymmetric flows of information in distributed systems. We provide illustrative examples by reference to ongoing collaborative work on the semantic structure of the British Criminal Court system and the conflict dynamics of the contemporary Afghanistan insurgency.
A Comparison of Relaxations of Multiset Cannonical Correlation Analysis and Applications
Venue: arXiv cs.LG 2013
Year: 2013

Canonical correlation analysis is a statistical technique that is used to find relations between two sets of variables. An important extension in pattern analysis is to consider more than two sets of variables. This problem can be expressed as a quadratically constrained quadratic program (QCQP), commonly referred to Multi-set Canonical Correlation Analysis (MCCA). This is a non-convex problem and so greedy algorithms converge to local optima without any guarantees on global optimality. In this paper, we show that despite being highly structured, finding the optimal solution is NP-Hard. This motivates our relaxation of the QCQP to a semidefinite program (SDP). The SDP is convex, can be solved reasonably efficiently and comes with both absolute and output-sensitive approximation quality. In addition to theoretical guarantees, we do an extensive comparison of the QCQP method and the SDP relaxation on a variety of synthetic and real world data. Finally, we present two useful extensions: we incorporate kernel methods and computing multiple sets of canonical vectors.
The price of bandit information in multiclass online classification
Venue: arXiv cs.LG 2013
Year: 2013

We consider two scenarios of multiclass online learning of a hypothesis class $H\subseteq Y^X$. In the {\em full information} scenario, the learner is exposed to instances together with their labels. In the {\em bandit} scenario, the true label is not exposed, but rather an indication whether the learner's prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most $8\cdot|Y|\cdot \log(|Y|)$ in the realizable case, and $\tilde{O}(\sqrt{|Y|})$ in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle). We apply these results to the class of $γ$-margin multiclass linear classifiers in $\reals^d$. We show that the bandit error rate of this class is $\tildeΘ(\frac{|Y|}{γ^2})$ in the realizable case and $\tildeΘ(\frac{1}γ\sqrt{|Y|T})$ in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for online multiclass prediction).