OpenRaiser/Intern-Atlas huggingface dataset:
Near-optimal Bayesian Active Learning with Correlated and Noisy Tests
Venue: arXiv cs.LG 2016
Year: 2016

We consider the Bayesian active learning and experimental design problem, where the goal is to learn the value of some unknown target variable through a sequence of informative, noisy tests. In contrast to prior work, we focus on the challenging, yet practically relevant setting where test outcomes can be conditionally dependent given the hidden target variable. Under such assumptions, common heuristics, such as greedily performing tests that maximize the reduction in uncertainty of the target, often perform poorly. In this paper, we propose ECED, a novel, computationally efficient active learning algorithm, and prove strong theoretical guarantees that hold with correlated, noisy tests. Rather than directly optimizing the prediction error, at each step, ECED picks the test that maximizes the gain in a surrogate objective, which takes into account the dependencies between tests. Our analysis relies on an information-theoretic auxiliary function to track the progress of ECED, and utilizes adaptive submodularity to attain the near-optimal bound. We demonstrate strong empirical performance of ECED on two problem instances, including a Bayesian experimental design task intended to distinguish among economic theories of how people make risky decisions, and an active preference learning task via pairwise comparisons.
Bubbles: a data management approach to create an advanced industrial interoperability layer for critical systems development applying reuse techniques
Venue: arXiv cs.SE 2016
Year: 2016

The development of critical systems is becoming more and more complex. The overall tendency is that development costs raise. In order to cut cost of development, companies are forced to build systems from proven components and larger new systems from smaller older ones. Respective reuse activities involve good number of people, tools and processes along different stages of the development lifecycle which involve large numbers of tools. Some development is directly planned for reuse. Planned reuse implies excellent knowledge management and firm governance of reusable items. According to the current state of the art, there are still practical problems in the two fields, mainly because the governance and knowledge management is fragmented over the tools of the toolchain. In our experience, the practical effect of this fragmentation is that involved ancestor and derivation relationships are often undocumented or not exploitable. Additionally, useful reuse is almost always dealing with heterogeneous content which must be transferred from older to newer development environments. In this process, interoperability proves either as biggest obstacle or greatest help. In this paper, authors connect the topics interoperability and knowledge management and propose to seek for ubiquitous reuse via advanced interoperability features. A single concept from a larger Technical Interoperability Concept (TIC) with the name bubble is presented. Bubbles are expected to overcome existing barriers to cost-efficient reuse in systems and software development lifecycles. That is why, the present paper introduces and defines bubbles by showing how they simplify application of repairs and changes and hence contribute to expansion of reuse at reduced cost.
Multi-Level Analysis and Annotation of Arabic Corpora for Text-to-Sign Language MT
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we present an ongoing effort in lexical semantic analysis and annotation of Modern Standard Arabic (MSA) text, a semi automatic annotation tool concerned with the morphologic, syntactic, and semantic levels of description.
Non-Gaussian Random Generators in Bacteria Foraging Algorithm for Multiobjective Optimization
Venue: arXiv cs.AI 2016
Year: 2016

Random generators or stochastic engines are a key component in the structure of metaheuristic algorithms. This work investigates the effects of non-Gaussian stochastic engines on the performance of metaheuristics when solving a real-world optimization problem. In this work, the bacteria foraging algorithm (BFA) was employed in tandem with four random generators (stochastic engines). The stochastic engines operate using the Weibull distribution, Gamma distribution, Gaussian distribution and a chaotic mechanism. The two non-Gaussian distributions are the Weibull and Gamma distributions. In this work, the approaches developed were implemented on the real-world multi-objective resin bonded sand mould problem. The Pareto frontiers obtained were benchmarked using two metrics; the hyper volume indicator (HVI) and the proposed Average Explorative Rate (AER) metric. Detail discussions from various perspectives on the effects of non-Gaussian random generators in metaheuristics are provided.
Quickest Moving Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

We present a general framework and method for simultaneous detection and segmentation of an object in a video that moves (or comes into view of the camera) at some unknown time in the video. The method is an online approach based on motion segmentation, and it operates under dynamic backgrounds caused by a moving camera or moving nuisances. The goal of the method is to detect and segment the object as soon as it moves. Due to stochastic variability in the video and unreliability of the motion signal, several frames are needed to reliably detect the object. The method is designed to detect and segment with minimum delay subject to a constraint on the false alarm rate. The method is derived as a problem of Quickest Change Detection. Experiments on a dataset show the effectiveness of our method in minimizing detection delay subject to false alarm constraints.
When should an expert make a prediction?
Venue: arXiv cs.GT 2016
Year: 2016

We consider a setting where in a known future time, a certain continuous random variable will be realized. There is a public prediction that gradually converges to its realized value, and an expert that has access to a more accurate prediction. Our goal is to study {\em when} should the expert reveal his information, assuming that his reward is based on a logarithmic market scoring rule (i.e., his reward is proportional to the gain in log-likelihood of the realized value). Our contributions are: (1) we characterize the expert's optimal policy and show that it is threshold based. (2) we analyze the expert's asymptotic expected optimal reward and show a tight connection to the Law of the Iterated Logarithm, and (3) we give an efficient dynamic programming algorithm to compute the optimal policy.
Impact of General Channel Aging Conditions on the Downlink Performance of Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

Recent works have identified massive multiple-input-multiple-output (MIMO) as a key technology for achieving substantial gains in spectral and energy efficiency. Additionally, the turn to low-cost transceivers, being prone to hardware impairments is the most effective and attractive way for cost-efficient applications concerning massive MIMO systems. In this context, the impact of channel aging, which severely affects the performance, is investigated herein by considering a generalized model. Specifically, we show that both Doppler shift because of the users' relative movement as well as phase noise due to noisy local oscillators (LOs) contribute to channel aging. To this end, we first propose a joint model, encompassing both effects, in order to investigate the performance of a massive MIMO system based on the inevitable time-varying nature of realistic mobile communications. Then, we derive the deterministic equivalents (DEs) for the signal-to-noise-and-interference ratios (SINRs) with maximum ratio transmission (MRT) and regularized zero-forcing precoding (RZF). Our analysis not only demonstrates a performance comparison between MRT and RZF under these conditions, but most importantly, it reveals interesting properties regarding the effects of user mobility and phase noise. In particular, the large antenna limit behavior depends profoundly on both effects, but the burden due to user mobility is much more detrimental than phase noise even for moderate user velocities ($\approx30$ km/h), while the negative impact of phase noise is noteworthy at lower mobility conditions.
Requirements for storing electrophysiology data
Venue: arXiv cs.OH 2016
Year: 2016

The purpose of this document is to specify the basic data types required for storing electrophysiology and optical imaging data to facilitate computer-based neuroscience studies and data sharing. These requirements are being developed within a working group of the Electrophysiology Task Force in the International Neuroinformatics Coordinating Facility (INCF) Program on Standards for Data Sharing. While this document describes the requirements of the standard independent of the actual storage technology, the Task Force has recommended basing a standard on HDF5. This is in line with a number of groups who are already using HDF5 to store electrophysiology data, although currently without being based on a standard.
On Non-Orthogonal Multiple Access in Downlink
Venue: arXiv cs.IT 2016
Year: 2016

Non orthogonal multiple access (NOMA) in the downlink is discussed in this letter. When combined with soft frequency reuse, NOMA is detrimental to user fairness by increasing the data rate of a near user at the cost of data rate of a far user.
Local Perturb-and-MAP for Structured Prediction
Venue: arXiv cs.CV 2016
Year: 2016

Conditional random fields (CRFs) provide a powerful tool for structured prediction, but cast significant challenges in both the learning and inference steps. Approximation techniques are widely used in both steps, which should be considered jointly to guarantee good performance (a.k.a. "inferning"). Perturb-and-MAP models provide a promising alternative to CRFs, but require global combinatorial optimization and hence they are usable only on specific models. In this work, we present a new Local Perturb-and-MAP (locPMAP) framework that replaces the global optimization with a local optimization by exploiting our observed connection between locPMAP and the pseudolikelihood of the original CRF model. We test our approach on three different vision tasks and show that our method achieves consistently improved performance over other approximate inference techniques optimized to a pseudolikelihood objective. Additionally, we demonstrate that we can integrate our method in the fully convolutional network framework to increase our model's complexity. Finally, our observed connection between locPMAP and the pseudolikelihood leads to a novel perspective for understanding and using pseudolikelihood.
Generalized Mirror Descents in Congestion Games
Venue: arXiv cs.GT 2016
Year: 2016

Different types of dynamics have been studied in repeated game play, and one of them which has received much attention recently consists of those based on "no-regret" algorithms from the area of machine learning. It is known that dynamics based on generic no-regret algorithms may not converge to Nash equilibria in general, but to a larger set of outcomes, namely coarse correlated equilibria. Moreover, convergence results based on generic no-regret algorithms typically use a weaker notion of convergence: the convergence of the average plays instead of the actual plays. Some work has been done showing that when using a specific no-regret algorithm, the well-known multiplicative updates algorithm, convergence of actual plays to equilibria can be shown and better quality of outcomes in terms of the price of anarchy can be reached for atomic congestion games and load balancing games. Are there more cases of natural no-regret dynamics that perform well in suitable classes of games in terms of convergence and quality of outcomes that the dynamics converge to? We answer this question positively in the bulletin-board model by showing that when employing the mirror-descent algorithm, a well-known generic no-regret algorithm, the actual plays converge quickly to equilibria in nonatomic congestion games. Furthermore, the bandit model considers a probably more realistic and prevalent setting with only partial information, in which at each time step each player only knows the cost of her own currently played strategy, but not any costs of unplayed strategies. For the class of atomic congestion games, we propose a family of bandit algorithms based on the mirror-descent algorithms previously presented, and show that when each player individually adopts such a bandit algorithm, their joint (mixed) strategy profile quickly converges with implications.
Learning Moore Machines from Input-Output Traces
Venue: arXiv cs.FL 2016
Year: 2016

The problem of learning automata from example traces (but no equivalence or membership queries) is fundamental in automata learning theory and practice. In this paper we study this problem for finite state machines with inputs and outputs, and in particular for Moore machines. We develop three algorithms for solving this problem: (1) the PTAP algorithm, which transforms a set of input-output traces into an incomplete Moore machine and then completes the machine with self-loops; (2) the PRPNI algorithm, which uses the well-known RPNI algorithm for automata learning to learn a product of automata encoding a Moore machine; and (3) the MooreMI algorithm, which directly learns a Moore machine using PTAP extended with state merging. We prove that MooreMI has the fundamental identification in the limit property. We also compare the algorithms experimentally in terms of the size of the learned machine and several notions of accuracy, introduced in this paper. Finally, we compare with OSTIA, an algorithm that learns a more general class of transducers, and find that OSTIA generally does not learn a Moore machine, even when fed with a characteristic sample.
Dynamic analysis of simultaneous adaptation of force, impedance and trajectory
Venue: arXiv cs.RO 2016
Year: 2016

When carrying out tasks in contact with the environment, humans are found to concurrently adapt force, impedance and trajectory. Here we develop a robotic model of this mechanism in humans and analyse the underlying dynamics. We derive a general adaptive controller for the interaction of a robot with an environment solely characterised by its stiffness and damping, using Lyapunov theory.
How Many Real Attractive Fixed Points Can A Polynomial Have?
Venue: arXiv cs.NA 2016
Year: 2016

We prove a complex polynomial of degree $n$ has at most $\lceil n/2 \rceil$ attractive fixed points lying on a line. We also consider the general case.
Consensus in the Presence of Multiple Opinion Leaders: Effect of Bounded Confidence
Venue: arXiv cs.SI 2016
Year: 2016

The problem of analyzing the performance of networked agents exchanging evidence in a dynamic network has recently grown in importance. This problem has relevance in signal and data fusion network applications and in studying opinion and consensus dynamics in social networks. Due to its capability of handling a wider variety of uncertainties and ambiguities associated with evidence, we use the framework of Dempster-Shafer (DS) theory to capture the opinion of an agent. We then examine the consensus among agents in dynamic networks in which an agent can utilize either a cautious or receptive updating strategy. In particular, we examine the case of bounded confidence updating where an agent exchanges its opinion only with neighboring nodes possessing 'similar' evidence. In a fusion network, this captures the case in which nodes only update their state based on evidence consistent with the node's own evidence. In opinion dynamics, this captures the notions of Social Judgment Theory (SJT) in which agents update their opinions only with other agents possessing opinions closer to their own. Focusing on the two special DS theoretic cases where an agent state is modeled as a Dirichlet body of evidence and a probability mass function (p.m.f.), we utilize results from matrix theory, graph theory, and networks to prove the existence of consensus agent states in several time-varying network cases of interest. For example, we show the existence of a consensus in which a subset of network nodes achieves a consensus that is adopted by follower network nodes. Of particular interest is the case of multiple opinion leaders, where we show that the agents do not reach a consensus in general, but rather converge to 'opinion clusters'. Simulation results are provided to illustrate the main results.
Generalized phase retrieval : measurement number, matrix recovery and beyond
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we develop a framework of generalized phase retrieval in which one aims to reconstruct a vector ${\mathbf x}$ in ${\mathbb R}^d$ or ${\mathbb C}^d$ through quadratic samples ${\mathbf x}^*A_1{\mathbf x}, \dots, {\mathbf x}^*A_N{\mathbf x}$. The generalized phase retrieval includes as special cases the standard phase retrieval as well as the phase retrieval by orthogonal projections. We first explore the connections among generalized phase retrieval, low-rank matrix recovery and nonsingular bilinear form. Motivated by the connections, we present results on the minimal measurement number needed for recovering a matrix that lies in a set $W\in {\mathbb C}^{d\times d}$. Applying the results to phase retrieval, we show that generic $d \times d$ matrices $A_1,\ldots, A_N$ have the phase retrieval property if $N\geq 2d-1$ in the real case and $N \geq 4d-4$ in the complex case for very general classes of $A_1,\ldots,A_N$, e.g. matrices with prescribed ranks or orthogonal projections. Our method also leads to a novel proof for the classical Stiefel-Hopf condition on nonsingular bilinear form. We also give lower bounds on the minimal measurement number required for generalized phase retrieval. For several classes of dimensions $d$ we obtain the precise values of the minimal measurement number. Our work unifies and enhances results from the standard phase retrieval, phase retrieval by projections and low-rank matrix recovery.
Automatic Action Annotation in Weakly Labeled Videos
Venue: arXiv cs.CV 2016
Year: 2016

Manual spatio-temporal annotation of human action in videos is laborious, requires several annotators and contains human biases. In this paper, we present a weakly supervised approach to automatically obtain spatio-temporal annotations of an actor in action videos. We first obtain a large number of action proposals in each video. To capture a few most representative action proposals in each video and evade processing thousands of them, we rank them using optical flow and saliency in a 3D-MRF based framework and select a few proposals using MAP based proposal subset selection method. We demonstrate that this ranking preserves the high quality action proposals. Several such proposals are generated for each video of the same action. Our next challenge is to iteratively select one proposal from each video so that all proposals are globally consistent. We formulate this as Generalized Maximum Clique Graph problem using shape, global and fine grained similarity of proposals across the videos. The output of our method is the most action representative proposals from each video. Our method can also annotate multiple instances of the same action in a video. We have validated our approach on three challenging action datasets: UCF Sport, sub-JHMDB and THUMOS'13 and have obtained promising results compared to several baseline methods. Moreover, on UCF Sports, we demonstrate that action classifiers trained on these automatically obtained spatio-temporal annotations have comparable performance to the classifiers trained on ground truth annotation.
Towards large-scale deliberative decision-making: small groups and the importance of triads
Venue: arXiv cs.GT 2016
Year: 2016

Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a model in which large-scale decision-making takes place through a sequence of small group interactions. Our model considers a group of participants, each having an opinion which together form a graph. We show that for median graphs, a class of graphs including grids and trees, it is possible to use a small number of three-person interactions to tightly approximate the wisdom of the crowd, defined here to be the generalized median of participant opinions, even when agents are strategic. Interestingly, we also show that this sharply contrasts with small groups of size two, for which we prove an impossibility result. Specifically, we show that it is impossible to use sequences of two-person interactions satisfying natural axioms to find a tight approximation of the generalized median, even when agents are non-strategic. Our results demonstrate the potential of small group interactions for reaching global decision-making properties.
Highly-Smooth Zero-th Order Online Optimization Vianney Perchet
Venue: arXiv cs.LG 2016
Year: 2016

The minimization of convex functions which are only available through partial and noisy information is a key methodological problem in many disciplines. In this paper we consider convex optimization with noisy zero-th order information, that is noisy function evaluations at any desired point. We focus on problems with high degrees of smoothness, such as logistic regression. We show that as opposed to gradient-based algorithms, high-order smoothness may be used to improve estimation rates, with a precise dependence of our upper-bounds on the degree of smoothness. In particular, we show that for infinitely differentiable functions, we recover the same dependence on sample size as gradient-based algorithms, with an extra dimension-dependent factor. This is done for both convex and strongly-convex functions, with finite horizon and anytime algorithms. Finally, we also recover similar results in the online optimization setting.
Analysis of Resparsification
Venue: arXiv cs.DS 2016
Year: 2016

We show that schemes for sparsifying matrices based on iteratively resampling rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman and Srivastava [STOC 2008]). In particular, this gives a formal analysis of a scheme very similar to the one proposed by Kelner and Levin [TCS 2013].