OpenRaiser/Intern-Atlas huggingface dataset:
Inequality Constraints in Causal Models with Hidden Variables
Venue: arXiv cs.AI 2012
Year: 2012

We present a class of inequality constraints on the set of distributions induced by local interventions on variables governed by a causal Bayesian network, in which some of the variables remain unmeasured. We derive bounds on causal effects that are not directly measured in randomized experiments. We derive instrumental inequality type of constraints on nonexperimental distributions. The results have applications in testing causal models with observational or experimental data.
Convex Structure Learning for Bayesian Networks: Polynomial Feature Selection and Approximate Ordering
Venue: arXiv cs.LG 2012
Year: 2012

We present a new approach to learning the structure and parameters of a Bayesian network based on regularized estimation in an exponential family representation. Here we show that, given a fixed variable order, the optimal structure and parameters can be learned efficiently, even without restricting the size of the parent sets. We then consider the problem of optimizing the variable order for a given set of features. This is still a computationally hard problem, but we present a convex relaxation that yields an optimal 'soft' ordering in polynomial time. One novel aspect of the approach is that we do not perform a discrete search over DAG structures, nor over variable orders, but instead solve a continuous relaxation that can then be rounded to obtain a valid network structure. We conduct an experimental comparison against standard structure search procedures over standard objectives, which cope with local minima, and evaluate the advantages of using convex relaxations that reduce the effects of local minima.
Visualization of Collaborative Data
Venue: arXiv cs.GR 2012
Year: 2012

Collaborative data consist of ratings relating two distinct sets of objects: users and items. Much of the work with such data focuses on filtering: predicting unknown ratings for pairs of users and items. In this paper we focus on the problem of visualizing the information. Given all of the ratings, our task is to embed all of the users and items as points in the same Euclidean space. We would like to place users near items that they have rated (or would rate) high, and far away from those they would give a low rating. We pose this problem as a real-valued non-linear Bayesian network and employ Markov chain Monte Carlo and expectation maximization to find an embedding. We present a metric by which to judge the quality of a visualization and compare our results to local linear embedding and Eigentaste on three real-world datasets.
Propagation of Delays in the National Airspace System
Venue: arXiv cs.AI 2012
Year: 2012

The National Airspace System (NAS) is a large and complex system with thousands of interrelated components: administration, control centers, airports, airlines, aircraft, passengers, etc. The complexity of the NAS creates many difficulties in management and control. One of the most pressing problems is flight delay. Delay creates high cost to airlines, complaints from passengers, and difficulties for airport operations. As demand on the system increases, the delay problem becomes more and more prominent. For this reason, it is essential for the Federal Aviation Administration to understand the causes of delay and to find ways to reduce delay. Major contributing factors to delay are congestion at the origin airport, weather, increasing demand, and air traffic management (ATM) decisions such as the Ground Delay Programs (GDP). Delay is an inherently stochastic phenomenon. Even if all known causal factors could be accounted for, macro-level national airspace system (NAS) delays could not be predicted with certainty from micro-level aircraft information. This paper presents a stochastic model that uses Bayesian Networks (BNs) to model the relationships among different components of aircraft delay and the causal factors that affect delays. A case study on delays of departure flights from Chicago O'Hare international airport (ORD) to Hartsfield-Jackson Atlanta International Airport (ATL) reveals how local and system level environmental and human-caused factors combine to affect components of delay, and how these components contribute to the final arrival delay at the destination airport.
A Non-Parametric Bayesian Method for Inferring Hidden Causes
Venue: arXiv cs.LG 2012
Year: 2012

We present a non-parametric Bayesian approach to structure learning with hidden causes. Previous Bayesian treatments of this problem define a prior over the number of hidden causes and use algorithms such as reversible jump Markov chain Monte Carlo to move between solutions. In contrast, we assume that the number of hidden causes is unbounded, but only a finite number influence observable variables. This makes it possible to use a Gibbs sampler to approximate the distribution over causal structures. We evaluate the performance of both approaches in discovering hidden causes in simulated data, and use our non-parametric approach to discover hidden causes in a real medical dataset.
Identifying Topical Twitter Communities via User List Aggregation
Venue: arXiv cs.SI 2012
Year: 2012

A particular challenge in the area of social media analysis is how to find communities within a larger network of social interactions. Here a community may be a group of microblogging users who post content on a coherent topic, or who are associated with a specific event or news story. Twitter provides the ability to curate users into lists, corresponding to meaningful topics or themes. Here we describe an approach for crowdsourcing the list building efforts of many different Twitter users, in order to identify topical communities. This approach involves the use of ensemble community finding to produce stable groupings of user lists, and by extension, individual Twitter users. We examine this approach in the context of a case study surrounding the detection of communities on Twitter relating to the London 2012 Olympics.
Subspace System Identification via Weighted Nuclear Norm Optimization
Venue: arXiv cs.SY 2012
Year: 2012

We present a subspace system identification method based on weighted nuclear norm approximation. The weight matrices used in the nuclear norm minimization are the same weights as used in standard subspace identification methods. We show that the inclusion of the weights improves the performance in terms of fit on validation data. As a second benefit, the weights reduce the size of the optimization problems that need to be solved. Experimental results from randomly generated examples as well as from the Daisy benchmark collection are reported. The key to an efficient implementation is the use of the alternating direction method of multipliers to solve the optimization problem.
The Complexity of Learning Principles and Parameters Grammars
Venue: arXiv cs.FL 2012
Year: 2012

We investigate models for learning the class of context-free and context-sensitive languages (CFLs and CSLs). We begin with a brief discussion of some early hardness results which show that unrestricted language learning is impossible, and unrestricted CFL learning is computationally infeasible; we then briefly survey the literature on algorithms for learning restricted subclasses of the CFLs. Finally, we introduce a new family of subclasses, the principled parametric context-free grammars (and a corresponding family of principled parametric context-sensitive grammars), which roughly model the "Principles and Parameters" framework in psycholinguistics. We present three hardness results: first, that the PPCFGs are not efficiently learnable given equivalence and membership oracles, second, that the PPCFGs are not efficiently learnable from positive presentations unless P = NP, and third, that the PPCSGs are not efficiently learnable from positive presentations unless integer factorization is in P.
Density-Difference Estimation
Venue: arXiv cs.LG 2012
Year: 2012

We address the problem of estimating the difference between two probability densities. A naive approach is a two-step procedure of first estimating two densities separately and then computing their difference. However, such a two-step procedure does not necessarily work well because the first step is performed without regard to the second step and thus a small error incurred in the first stage can cause a big error in the second stage. In this paper, we propose a single-shot procedure for directly estimating the density difference without separately estimating two densities. We derive a non-parametric finite-sample error bound for the proposed single-shot density-difference estimator and show that it achieves the optimal convergence rate. The usefulness of the proposed method is also demonstrated experimentally.
Answering Table Queries on the Web using Column Keywords
Venue: arXiv cs.DB 2012
Year: 2012

We present the design of a structured search engine which returns a multi-column table in response to a query consisting of keywords describing each of its columns. We answer such queries by exploiting the millions of tables on the Web because these are much richer sources of structured knowledge than free-format text. However, a corpus of tables harvested from arbitrary HTML web pages presents huge challenges of diversity and redundancy not seen in centrally edited knowledge bases. We concentrate on one concrete task in this paper. Given a set of Web tables T1, . . ., Tn, and a query Q with q sets of keywords Q1, . . ., Qq, decide for each Ti if it is relevant to Q and if so, identify the mapping between the columns of Ti and query columns. We represent this task as a graphical model that jointly maps all tables by incorporating diverse sources of clues spanning matches in different parts of the table, corpus-wide co-occurrence statistics, and content overlap across table columns. We define a novel query segmentation model for matching keywords to table columns, and a robust mechanism of exploiting content overlap across table columns. We design efficient inference algorithms based on bipartite matching and constrained graph cuts to solve the joint labeling task. Experiments on a workload of 59 queries over a 25 million web table corpus shows significant boost in accuracy over baseline IR methods.
Early Accurate Results for Advanced Analytics on MapReduce
Venue: arXiv cs.DB 2012
Year: 2012

Approximate results based on samples often provide the only way in which advanced analytical applications on very massive data sets can satisfy their time and resource constraints. Unfortunately, methods and tools for the computation of accurate early results are currently not supported in MapReduce-oriented systems although these are intended for `big data'. Therefore, we proposed and implemented a non-parametric extension of Hadoop which allows the incremental computation of early results for arbitrary work-flows, along with reliable on-line estimates of the degree of accuracy achieved so far in the computation. These estimates are based on a technique called bootstrapping that has been widely employed in statistics and can be applied to arbitrary functions and data distributions. In this paper, we describe our Early Accurate Result Library (EARL) for Hadoop that was designed to minimize the changes required to the MapReduce framework. Various tests of EARL of Hadoop are presented to characterize the frequent situations where EARL can provide major speed-ups over the current version of Hadoop.
Mining Statistically Significant Substrings using the Chi-Square Statistic
Venue: arXiv cs.DB 2012
Year: 2012

The problem of identification of statistically significant patterns in a sequence of data has been applied to many domains such as intrusion detection systems, financial models, web-click records, automated monitoring systems, computational biology, cryptology, and text analysis. An observed pattern of events is deemed to be statistically significant if it is unlikely to have occurred due to randomness or chance alone. We use the chi-square statistic as a quantitative measure of statistical significance. Given a string of characters generated from a memoryless Bernoulli model, the problem is to identify the substring for which the empirical distribution of single letters deviates the most from the distribution expected from the generative Bernoulli model. This deviation is captured using the chi-square measure. The most significant substring (MSS) of a string is thus defined as the substring having the highest chi-square value. Till date, to the best of our knowledge, there does not exist any algorithm to find the MSS in better than O(n^2) time, where n denotes the length of the string. In this paper, we propose an algorithm to find the most significant substring, whose running time is O(n^{3/2}) with high probability. We also study some variants of this problem such as finding the top-t set, finding all substrings having chi-square greater than a fixed threshold and finding the MSS among substrings greater than a given length. We experimentally demonstrate the asymptotic behavior of the MSS on varying the string size and alphabet size. We also describe some applications of our algorithm on cryptology and real world data from finance and sports. Finally, we compare our technique with the existing heuristics for finding the MSS.
On the Complexity of Equivalence of Specifications of Infinite Objects
Venue: arXiv cs.LO 2012
Year: 2012

We study the complexity of deciding the equality of infinite objects specified by systems of equations, and of infinite objects specified by lambda-terms. For equational specifications there are several natural notions of equality: equality in all models, equality of the sets of solutions, and equality of normal forms for productive specifications. For lambda-terms we investigate Boehm-tree equality and various notions of observational equality. We pinpoint the complexity of each of these notions in the arithmetical or analytical hierarchy. We show that the complexity of deciding equality in all models subsumes the entire analytical hierarchy. This holds already for the most simple infinite objects, viz. streams over {0,1}, and stands in sharp contrast to the low arithmetical Pi^0_2-completeness of equality of equationally specified streams derived in [Rosu 2006] employing a different notion of equality.
Randomized Distributed Decision
Venue: arXiv cs.DC 2012
Year: 2012

The paper tackles the power of randomization in the context of locality by analyzing the ability to`boost' the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. Informally, a (p,q)-decider for a language L is a distributed randomized algorithm which accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p,q)-decider, where p^2+q>1, can actually be decided deterministically in O(t) rounds. In one of our results we give evidence supporting the conjecture that the above statement holds for all distributed languages. This is achieved by considering the restricted case of path topologies. We then turn our attention to the range below the aforementioned threshold, namely, the case where p^2+q\leq1. We define B_k(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p^{1+1/k}+q>1. It is easy to see that every language is decidable (in zero rounds) by a (p,q)-decider satisfying p+q=1. Hence, the hierarchy B_k provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k\geq 1, there exists a language L satisfying L\in B_{k+1}(0) but L\notin B_k(t) for any t=o(n). In addition, we show that B_\infty(t) does not contain all languages, for any t=o(n). Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null.
Biochemical Oscillations in Delayed Negative Cyclic Feedback: Harmonic Balance Analysis with Applications
Venue: arXiv cs.SY 2012
Year: 2012

Oscillatory chemical reactions often serve as a timing clock of cellular processes in living cells. The temporal dynamics of protein concentration levels is thus of great interest in biology. Here we propose a theoretical framework to analyze the frequency, phase and amplitude of oscillatory protein concentrations in gene regulatory networks with negative cyclic feedback. We first formulate the analysis framework of oscillation profiles based on multivariable harmonic balance. With this framework, the frequency, phase and amplitude are obtained analytically in terms of kinetic constants of the reactions despite the nonlinearity of the dynamics. These results are demonstrated with the Pentilator and Hes7 self-repression network, and it is shown that the developed analysis method indeed predicts the profiles of the oscillations. A distinctive feature of the presented result is that the waveform of oscillations is analytically obtained for a broad class of biochemical systems. Thus, it is easy to see how the waveform is determined from the system's parameters and structures. We present general biological insights that are applicable for any gene regulatory networks with negative cyclic feedback.
Topological model for machining of parts with complex shapes
Venue: arXiv cs.OH 2012
Year: 2012

Complex shapes are widely used to design products in several industries such as aeronautics, automotive and domestic appliances. Several variations of their curvatures and orientations generate difficulties during their manufacturing or the machining of dies used in moulding, injection and forging. Analysis of several parts highlights two levels of difficulties between three types of shapes: prismatic parts with simple geometrical shapes, aeronautic structure parts composed of several shallow pockets and forging dies composed of several deep cavities which often contain protrusions. This paper mainly concerns High Speed Machining (HSM) of these dies which represent the highest complexity level because of the shapes' geometry and their topology. Five axes HSM is generally required for such complex shaped parts but 3 axes machining can be sufficient for dies. Evolutions in HSM CAM software and machine tools lead to an important increase in time for machining preparation. Analysis stages of the CAD model particularly induce this time increase which is required for a wise choice of cutting tools and machining strategies. Assistance modules for prismatic parts machining features identification in CAD models are widely implemented in CAM software. In spite of the last CAM evolutions, these kinds of CAM modules are undeveloped for aeronautical structure parts and forging dies. Development of new CAM modules for the extraction of relevant machining areas as well as the definition of the topological relations between these areas must make it possible for the machining assistant to reduce the machining preparation time. In this paper, a model developed for the description of complex shape parts topology is presented. It is based on machining areas extracted for the construction of geometrical features starting from CAD models of the parts. As topology is described in order to assist machining assistant during machining process generation, the difficulties associated with tasks he carried out are analyzed at first. The topological model presented after is based on the basic geometrical features extracted. Topological relations which represent the framework of the model are defined between the basic geometrical features which are gathered afterwards in macro-features. Approach used for the identification of these macro-features is also presented in this paper. Detailed application on the construction of the topological model of forging dies is presented in the last part of the paper.
Code-Expanded Random Access for Machine-Type Communications
Venue: arXiv cs.IT 2012
Year: 2012

The random access methods used for support of machine-type communications (MTC) in current cellular standards are derivatives of traditional framed slotted ALOHA and therefore do not support high user loads efficiently. Motivated by the random access method employed in LTE, we propose a novel approach that is able to sustain a wide random access load range, while preserving the physical layer unchanged and incurring minor changes in the medium access control layer. The proposed scheme increases the amount of available contention resources, without resorting to the increase of system resources, such as contention sub-frames and preambles. This increase is accomplished by expanding the contention space to the code domain, through the creation of random access codewords. Specifically, in the proposed scheme, users perform random access by transmitting one or none of the available LTE orthogonal preambles in multiple random access sub-frames, thus creating access codewords that are used for contention. In this way, for the same number of random access sub-frames and orthogonal preambles, the amount of available contention resources is drastically increased, enabling the support of an increased number of MTC users. We present the framework and analysis of the proposed code-expanded random access method and show that our approach supports load regions that are beyond the reach of current systems.
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
Venue: arXiv cs.CC 2012
Year: 2012

For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differs from the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved by Krajicek (2011) that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction relevant to proof complexity.
Applying Deep Belief Networks to Word Sense Disambiguation
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, we applied a novel learning algorithm, namely, Deep Belief Networks (DBN) to word sense disambiguation (WSD). DBN is a probabilistic generative model composed of multiple layers of hidden units. DBN uses Restricted Boltzmann Machine (RBM) to greedily train layer by layer as a pretraining. Then, a separate fine tuning step is employed to improve the discriminative power. We compared DBN with various state-of-the-art supervised learning algorithms in WSD such as Support Vector Machine (SVM), Maximum Entropy model (MaxEnt), Naive Bayes classifier (NB) and Kernel Principal Component Analysis (KPCA). We used all words in the given paragraph, surrounding context words and part-of-speech of surrounding words as our knowledge sources. We conducted our experiment on the SENSEVAL-2 data set. We observed that DBN outperformed all other learning algorithms.