OpenRaiser/Intern-Atlas huggingface dataset:
Combining local search techniques and path following for bimatrix games
Venue: arXiv cs.GT 2012
Year: 2012

Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).
Crowdsourcing Control: Moving Beyond Multiple Choice
Venue: arXiv cs.AI 2012
Year: 2012

To ensure quality results from crowdsourced tasks, requesters often aggregate worker responses and use one of a plethora of strategies to infer the correct answer from the set of noisy responses. However, all current models assume prior knowledge of all possible outcomes of the task. While not an unreasonable assumption for tasks that can be posited as multiple-choice questions (e.g. n-ary classification), we observe that many tasks do not naturally fit this paradigm, but instead demand a free-response formulation where the outcome space is of infinite size (e.g. audio transcription). We model such tasks with a novel probabilistic graphical model, and design and implement LazySusan, a decision-theoretic controller that dynamically requests responses as necessary in order to infer answers to these tasks. We also design an EM algorithm to jointly learn the parameters of our model while inferring the correct answers to multiple tasks at a time. Live experiments on Amazon Mechanical Turk demonstrate the superiority of LazySusan at solving SAT Math questions, eliminating 83.2% of the error and achieving greater net utility compared to the state-ofthe-art strategy, majority-voting. We also show in live experiments that our EM algorithm outperforms majority-voting on a visualization task that we design.
Nested Dictionary Learning for Hierarchical Organization of Imagery and Text
Venue: arXiv cs.LG 2012
Year: 2012

A tree-based dictionary learning model is developed for joint analysis of imagery and associated text. The dictionary learning may be applied directly to the imagery from patches, or to general feature vectors extracted from patches or superpixels (using any existing method for image feature extraction). Each image is associated with a path through the tree (from root to a leaf), and each of the multiple patches in a given image is associated with one node in that path. Nodes near the tree root are shared between multiple paths, representing image characteristics that are common among different types of images. Moving toward the leaves, nodes become specialized, representing details in image classes. If available, words (text) are also jointly modeled, with a path-dependent probability over words. The tree structure is inferred via a nested Dirichlet process, and a retrospective stick-breaking sampler is used to infer the tree depth and width.
Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we present a new approach for tightening upper bounds on the partition function. Our upper bounds are based on fractional covering bounds on the entropy function, and result in a concave program to compute these bounds and a convex program to tighten them. To solve these programs effectively for general region graphs we utilize the entropy barrier method, thus decomposing the original programs by their dual programs and solve them with dual block optimization scheme. The entropy barrier method provides an elegant framework to generalize the message-passing scheme to high-order region graph, as well as to solve the block dual steps in closed-form. This is a key for computational relevancy for large problems with thousands of regions.
Unsupervised Joint Alignment and Clustering using Bayesian Nonparametrics
Venue: arXiv cs.LG 2012
Year: 2012

Joint alignment of a collection of functions is the process of independently transforming the functions so that they appear more similar to each other. Typically, such unsupervised alignment algorithms fail when presented with complex data sets arising from multiple modalities or make restrictive assumptions about the form of the functions or transformations, limiting their generality. We present a transformed Bayesian infinite mixture model that can simultaneously align and cluster a data set. Our model and associated learning scheme offer two key advantages: the optimal number of clusters is determined in a data-driven fashion through the use of a Dirichlet process prior, and it can accommodate any transformation function parameterized by a continuous parameter vector. As a result, it is applicable to a wide range of data types, and transformation functions. We present positive results on synthetic two-dimensional data, on a set of one-dimensional curves, and on various image data sets, showing large improvements over previous work. We discuss several variations of the model and conclude with directions for future work.
Probability and Asset Updating using Bayesian Networks for Combinatorial Prediction Markets
Venue: arXiv cs.AI 2012
Year: 2012

A market-maker-based prediction market lets forecasters aggregate information by editing a consensus probability distribution either directly or by trading securities that pay off contingent on an event of interest. Combinatorial prediction markets allow trading on any event that can be specified as a combination of a base set of events. However, explicitly representing the full joint distribution is infeasible for markets with more than a few base events. A factored representation such as a Bayesian network (BN) can achieve tractable computation for problems with many related variables. Standard BN inference algorithms, such as the junction tree algorithm, can be used to update a representation of the entire joint distribution given a change to any local conditional probability. However, in order to let traders reuse assets from prior trades while never allowing assets to become negative, a BN based prediction market also needs to update a representation of each user's assets and find the conditional state in which a user has minimum assets. Users also find it useful to see their expected assets given an edit outcome. We show how to generalize the junction tree algorithm to perform all these computations.
Latent Structured Ranking
Venue: arXiv cs.LG 2012
Year: 2012

Many latent (factorized) models have been proposed for recommendation tasks like collaborative filtering and for ranking tasks like document or image retrieval and annotation. Common to all those methods is that during inference the items are scored independently by their similarity to the query in the latent embedding space. The structure of the ranked list (i.e. considering the set of items returned as a whole) is not taken into account. This can be a problem because the set of top predictions can be either too diverse (contain results that contradict each other) or are not diverse enough. In this paper we introduce a method for learning latent structured rankings that improves over existing methods by providing the right blend of predictions at the top of the ranked list. Particular emphasis is put on making this method scalable. Empirical results on large scale image annotation and music recommendation tasks show improvements over existing approaches.
Semi-Definite Programming Relaxation for Non-Line-of-Sight Localization
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of estimating the locations of a set of points in a k-dimensional euclidean space given a subset of the pairwise distance measurements between the points. We focus on the case when some fraction of these measurements can be arbitrarily corrupted by large additive noise. Given that the problem is highly non-convex, we propose a simple semidefinite programming relaxation that can be efficiently solved using standard algorithms. We define a notion of non-contractibility and show that the relaxation gives the exact point locations when the underlying graph is non-contractible. The performance of the algorithm is evaluated on an experimental data set obtained from a network of 44 nodes in an indoor environment and is shown to be robust to non-line-of-sight errors.
Optimal Computational Trade-Off of Inexact Proximal Methods
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we investigate the trade-off between convergence rate and computational cost when minimizing a composite functional with proximal-gradient methods, which are popular optimisation tools in machine learning. We consider the case when the proximity operator is computed via an iterative procedure, which provides an approximation of the exact proximity operator. In that case, we obtain algorithms with two nested loops. We show that the strategy that minimizes the computational cost to reach a solution with a desired accuracy in finite time is to set the number of inner iterations to a constant, which differs from the strategy indicated by a convergence rate analysis. In the process, we also present a new procedure called SIP (that is Speedy Inexact Proximal-gradient algorithm) that is both computationally efficient and easy to implement. Our numerical experiments confirm the theoretical findings and suggest that SIP can be a very competitive alternative to the standard procedure.
Tracking Group Evolution in Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

Easy access and vast amount of data, especially from long period of time, allows to divide social network into timeframes and create temporal social network. Such network enables to analyse its dynamics. One aspect of the dynamics is analysis of social communities evolution, i.e., how particular group changes over time. To do so, the complete group evolution history is needed. That is why in this paper the new method for group evolution extraction called GED is presented.
Maximum Likelihood Algorithms for Joint Estimation of Synchronization Impairments and Channel in MIMO-OFDM System
Venue: arXiv cs.IT 2012
Year: 2012

Maximum Likelihood (ML) algorithms, for the joint estimation of synchronization impairments and channel in Multiple Input Multiple Output-Orthogonal Frequency Division Multiplexing (MIMO-OFDM) system, are investigated in this work. A system model that takes into account the effects of carrier frequency offset, sampling frequency offset, symbol timing error, and channel impulse response is formulated. Cramér-Rao Lower Bounds for the estimation of continuous parameters are derived, which show the coupling effect among different impairments and the significance of the joint estimation. We propose an ML algorithm for the estimation of synchronization impairments and channel together, using grid search method. To reduce the complexity of the joint grid search in ML algorithm, a Modified ML (MML) algorithm with multiple one-dimensional searches is also proposed. Further, a Stage-wise ML (SML) algorithm using existing algorithms, which estimate fewer number of parameters, is also proposed. Performance of the estimation algorithms is studied through numerical simulations and it is found that the proposed ML and MML algorithms exhibit better performance than SML algorithm.
Bayesian Estimation for Continuous-Time Sparse Stochastic Processes
Venue: arXiv cs.LG 2012
Year: 2012

We consider continuous-time sparse stochastic processes from which we have only a finite number of noisy/noiseless samples. Our goal is to estimate the noiseless samples (denoising) and the signal in-between (interpolation problem). By relying on tools from the theory of splines, we derive the joint a priori distribution of the samples and show how this probability density function can be factorized. The factorization enables us to tractably implement the maximum a posteriori and minimum mean-square error (MMSE) criteria as two statistical approaches for estimating the unknowns. We compare the derived statistical methods with well-known techniques for the recovery of sparse signals, such as the $\ell_1$ norm and Log ($\ell_1$-$\ell_0$ relaxation) regularization methods. The simulation results show that, under certain conditions, the performance of the regularization techniques can be very close to that of the MMSE estimator.
Hamiltonian Tetrahedralizations with Steiner Points
Venue: arXiv cs.CG 2012
Year: 2012

Let $S$ be a set of $n$ points in 3-dimensional space. A tetrahedralization $\mathcal{T}$ of $S$ is a set of interior disjoint tetrahedra with vertices on $S$, not containing points of $S$ in their interior, and such that their union is the convex hull of $S$. Given $\mathcal{T}$, $D_\mathcal{T}$ is defined as the graph having as vertex set the tetrahedra of $\mathcal{T}$, two of which are adjacent if they share a face. We say that $\mathcal{T}$ is Hamiltonian if $D_\mathcal{T}$ has a Hamiltonian path. Let $m$ be the number of convex hull vertices of $S$. We prove that by adding at most $\lfloor \frac{m-2}{2} \rfloor$ Steiner points to interior of the convex hull of $S$, we can obtain a point set that admits a Hamiltonian tetrahedralization. An $O(m^{3/2}) + O(n \log n)$ time algorithm to obtain these points is given. We also show that all point sets with at most 20 convex hull points admit a Hamiltonian tetrahedralization without the addition of any Steiner points. Finally we exhibit a set of 84 points that does not admit a Hamiltonian tetrahedralization in which all tetrahedra share a vertex.
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Venue: arXiv cs.CC 2012
Year: 2012

We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with $(16/17 + \eps)$ of the edges bichromatic. In a related result, we show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
The construction of characteristic matrixes of dynamic coverings using an incremental approach
Venue: arXiv cs.IT 2012
Year: 2012

The covering approximation space evolves in time due to the explosion of the information, and the characteristic matrixes of coverings viewed as an effective approach to approximating the concept should update with time for knowledge discovery. This paper further investigates the construction of characteristic matrixes without running the matrix acquisition algorithm repeatedly. First, we present two approaches to computing the characteristic matrixes of the covering with lower time complexity. Then, we investigate the construction of the characteristic matrixes of the dynamic covering using the incremental approach. We mainly address the characteristic matrix updating from three aspects: the variations of elements in the covering, the immigration and emigration of objects and the changes of attribute values. Afterwards, several illustrative examples are employed to show that the proposed approach can effectively compute the characteristic matrixes of the dynamic covering for approximations of concepts.
Coding for the Lee and Manhattan Metrics with Weighing Matrices
Venue: arXiv cs.IT 2012
Year: 2012

This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics. Two related packing problems will be considered. The first is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second is to transform the space in a way that volumes are preserved and each Lee sphere (or conscribed cross-polytope), in the space, will be transformed to a shape inscribed in a small cube.
Developing ICC Profile Using Gray Level Control In Offset Printing Process
Venue: arXiv cs.CV 2012
Year: 2012

In prepress department RGB image has to be converted to CMYK image. To control that amount of black, cyan, magenta and yellow has to be controlled by using color separation method. Graycolor separation method is selected to control the amounts of these colors because it increase the quality of printing also. A single printer used for printing the same image on different paper also results in different printed images. To remove this problem a different ICC profile based on gray level control is developedand a sheet offset printer is calibrated using that profile and a subjective evaluation shows satisfactory results for different quality papers.
Classification Analysis Of Authorship Fiction Texts in The Space Of Semantic Fields
Venue: arXiv cs.CL 2012
Year: 2012

The use of naive Bayesian classifier (NB) and the classifier by the k nearest neighbors (kNN) in classification semantic analysis of authors' texts of English fiction has been analysed. The authors' works are considered in the vector space the basis of which is formed by the frequency characteristics of semantic fields of nouns and verbs. Highly precise classification of authors' texts in the vector space of semantic fields indicates about the presence of particular spheres of author's idiolect in this space which characterizes the individual author's style.
A Simple and Reliable Touch Sensitive Security System
Venue: arXiv cs.CR 2012
Year: 2012

This research focuses on detection of unauthorized access to residential and commercial buildings when the residents are far away from the access gate of the house. The system is a simple and reliable touch activated security system and uses sensor technology to revolutionize the standards of living. The system provides a best solution to most of the problems faced by house owners in their daily life. Due to its simple electronic components nature, it is more adaptable and cost-effective. The system is divided into three units; the power supply unit which employs the use of both DC battery and mains supply to ensure constant power supply to the circuit, the trigger unit which is responsible for activating the alarm unit and designed to have much time and period and moderate sensitivity in order to reduce the rate of false alarm, and the alarm amplitude unit which main function is to produce amplitude alarm sound when triggered by the trigger unit with the aim of producing a large audible sound that can alert the entire neighborhood or scare an intruder away. The design of the system was achieved by considering some factors such as economy, availability of components and research materials, efficiency, compatibility and portability and also durability in the design process. The performance of the system after test met design specifications. This system works on the principle of touch sensor. The general operation of the system and performance is dependent on the presence of an intruder entering through the door and touching any part of the door. The overall system was constructed and tested and it work perfectly.
An MML-based tool for evaluating the complexity of (stochastic) logic theories
Venue: arXiv cs.LO 2012
Year: 2012

Theory evaluation is a key problem in many areas: machine learning, scientific discovery, inverse engineering, decision making, software engineering, design, human sciences, etc. If we have a set of theories that are able to explain the same set of phenomena, we need a criterion to choose which one is best. There are, of course, many possible criteria. Model simplicity is one of the most common criteria in theory evaluation. The Minimum Message Length (MML) is a solid approach to evaluate theories relative to a given evidence or data. Theories can be expressed in specific or general (Turing-complete) languages. First-order logic, and logic programming in particular, is a Turing-complete language. Evaluating the simplicity of a theory or program described in a Turing-complete language is much more difficult than just counting the number of lines or bits. It is, in fact, the problem of calculating its Kolmogorov complexity, which is uncomputable. Few works in the literature have been able to present accurate and effective approximations for a Turing-complete language. In this work, we present the first general MML coding scheme for logic programs. With this scheme, we can quantify the bits of information required to code (or send) a theory, a set of data or the same data given the theory. As a realization of the above-mentioned schemes, we present a software tool which is able to code and evaluate a set of alternative (stochastic) theories (programs) against a set of examples. We illustrate the application of the tool to a variety of non-probabilistic and probabilistic scenarios.
In-Network Estimation of Frequency Moments
Venue: arXiv cs.NI 2012
Year: 2012

We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of non-linear functions of the distributed data which is over a large alphabet. We consider three types of networks: point-to-point networks with gossip based communication, random planar networks in the connectivity regime and random planar networks in the percolating regime both of which use the slotted Aloha communication protocol. For each network type, we estimate the scaled $k$-th frequency moments, for $k \geq 2$. Specifically, for every $k \geq 2,$ we give a distributed randomized algorithm that computes, with probability $(1-δ),$ an $ε$-approximation of the scaled $k$-th frequency moment, $F_k/N^k$, using time $O(M^{1-\frac{1}{k-1}} T)$ and $O(M^{1-\frac{1}{k-1}} \log N \log (δ^{-1})/ε^2)$ bits of transmission per communication step. Here, $N$ is the number of nodes in the network, $T$ is the information spreading time and $M=o(N)$ is the alphabet size.