OpenRaiser/Intern-Atlas huggingface dataset:
An Ensemble Method to Produce High-Quality Word Embeddings (2016)
Venue: arXiv cs.CL 2019
Year: 2019

A currently successful approach to computational semantics is to represent words as embeddings in a machine-learned vector space. We present an ensemble method that combines embeddings produced by GloVe (Pennington et al., 2014) and word2vec (Mikolov et al., 2013) with structured knowledge from the semantic networks ConceptNet (Speer and Havasi, 2012) and PPDB (Ganitkevitch et al., 2013), merging their information into a common representation with a large, multilingual vocabulary. The embeddings it produces achieve state-of-the-art performance on many word-similarity evaluations. Its score of $ρ= .596$ on an evaluation of rare words (Luong et al., 2013) is 16% higher than the previous best known system.
Robust Estimators in High Dimensions without the Computational Intractability
Venue: arXiv cs.DS 2019
Year: 2019

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question:Is high-dimensional agnostic distribution learning even possible, algorithmically? In this work, we obtain the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly-linearly with the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions, that may be applicable to many other problems.
Quantitative Automata under Probabilistic Semantics
Venue: arXiv cs.FL 2019
Year: 2019

Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider.
Formal Verification of Obstacle Avoidance and Navigation of Ground Robots
Venue: arXiv cs.SY 2019
Year: 2019

The safety of mobile robots in dynamic environments is predicated on making sure that they do not collide with obstacles. In support of such safety arguments, we analyze and formally verify a series of increasingly powerful safety properties of controllers for avoiding both stationary and moving obstacles: (i) static safety, which ensures that no collisions can happen with stationary obstacles, (ii) passive safety, which ensures that no collisions can happen with stationary or moving obstacles while the robot moves, (iii) the stronger passive friendly safety in which the robot further maintains sufficient maneuvering distance for obstacles to avoid collision as well, and (iv) passive orientation safety, which allows for imperfect sensor coverage of the robot, i. e., the robot is aware that not everything in its environment will be visible. We complement these provably correct safety properties with liveness properties: we prove that provably safe motion is flexible enough to let the robot still navigate waypoints and pass intersections. We use hybrid system models and theorem proving techniques that describe and formally verify the robot's discrete control decisions along with its continuous, physical motion. Moreover, we formally prove that safety can still be guaranteed despite sensor uncertainty and actuator perturbation, and when control choices for more aggressive maneuvers are introduced. Our verification results are generic in the sense that they are not limited to the particular choices of one specific control algorithm but identify conditions that make them simultaneously apply to a broad class of control algorithms.
Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We consider the $k$-Center problem and some generalizations. For $k$-Center a set of $k$ center vertices needs to be found in a graph $G$ with edge lengths, such that the distance from any vertex of $G$ to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by Abraham et al. [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any $\varepsilon>0$ computing a $(2-\varepsilon)$-approximation is W[2]-hard for parameter $k$ and NP-hard for graphs with highway dimension $O(\log^2 n)$. The latter does not rule out fixed-parameter $(2-\varepsilon)$-approximations for the highway dimension parameter $h$, but implies that such an algorithm must have at least doubly exponential running time in $h$ if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of $2$ by combining the parameters $k$ and $h$: we develop a fixed-parameter $3/2$-approximation with running time $2^{O(kh\log h)}\cdot n^{O(1)}$. Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter $(2-\varepsilon)$-approximations for only the parameter $h$. We also provide similar fixed-parameter approximations for the weighted $k$-Center and $(k,\mathcal{F})$-Partition problems, which generalize $k$-Center.
On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About Its Nonsmooth Loss Function
Venue: arXiv cs.LG 2019
Year: 2019

Many machine learning techniques sacrifice convenient computational structures to gain estimation robustness and modeling flexibility. However, by exploring the modeling structures, we find these "sacrifices" do not always require more computational efforts. To shed light on such a "free-lunch" phenomenon, we study the square-root-Lasso (SQRT-Lasso) type regression problem. Specifically, we show that the nonsmooth loss functions of SQRT-Lasso type regression ease tuning effort and gain adaptivity to inhomogeneous noise, but is not necessarily more challenging than Lasso in computation. We can directly apply proximal algorithms (e.g. proximal gradient descent, proximal Newton, and proximal Quasi-Newton algorithms) without worrying the nonsmoothness of the loss function. Theoretically, we prove that the proximal algorithms combined with the pathwise optimization scheme enjoy fast convergence guarantees with high probability. Numerical results are provided to support our theory.
Stochastic Function Norm Regularization of Deep Networks
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural networks have had an enormous impact on image analysis. State-of-the-art training methods, based on weight decay and DropOut, result in impressive performance when a very large training set is available. However, they tend to have large problems overfitting to small data sets. Indeed, the available regularization methods deal with the complexity of the network function only indirectly. In this paper, we study the feasibility of directly using the $L_2$ function norm for regularization. Two methods to integrate this new regularization in the stochastic backpropagation are proposed. Moreover, the convergence of these new algorithms is studied. We finally show that they outperform the state-of-the-art methods in the low sample regime on benchmark datasets (MNIST and CIFAR10). The obtained results demonstrate very clear improvement, especially in the context of small sample regimes with data laying in a low dimensional manifold. Source code of the method can be found at \url{https://github.com/AmalRT/DNN_Reg}.
Sparse Bayesian Inference of Multivariable ARX Networks
Venue: arXiv cs.SY 2019
Year: 2019

Increasing attention has recently been given to the inference of sparse networks. In biology, for example, most molecules only bind to a small number of other molecules, leading to sparse molecular interaction networks. To achieve sparseness, a common approach consists of applying weighted penalties to the number of links between nodes in the network and the complexity of the dynamics of existing links. The selection of proper weights, however, is non-trivial. Alternatively, this paper proposes a novel data-driven method, called GESBL, that is able to penalise both network sparsity and model complexity without any tuning. GESBL combines Sparse Bayesian Learning (SBL) and Group Sparse Bayesian Learning (GSBL) to introduce penalties for complexity, both in terms of element (system order of nonzero connections) and group sparsity (network topology). The paper considers a class of sparse linear time-invariant networks where the dynamics are represented by multivariable ARX models. Data generated from sparse random ARX networks and synthetic gene regulatory networks indicate that our method, on average, considerably outperforms existing state-of-the-art methods. The proposed method can be applied to a wide range of fields, from systems biology applications in signalling and genetic regulatory networks to power systems.
Scene Grammars, Factor Graphs, and Belief Propagation
Venue: arXiv cs.CV 2019
Year: 2019

We describe a general framework for probabilistic modeling of complex scenes and inference from ambiguous observations. The approach is motivated by applications in image analysis and is based on the use of priors defined by stochastic grammars. We define a class of grammars that capture relationships between the objects in a scene and provide important contextual cues for statistical inference. The distribution over scenes defined by a probabilistic scene grammar can be represented by a graphical model and this construction can be used for efficient inference with loopy belief propagation. We show experimental results with two different applications. One application involves the reconstruction of binary contour maps. Another application involves detecting and localizing faces in images. In both applications the same framework leads to robust inference algorithms that can effectively combine local information to reason about a scene.
Continuous Transmission of Spatially-Coupled LDPC Code Chains
Venue: arXiv cs.IT 2019
Year: 2019

We propose a novel encoding/transmission scheme called continuous chain (CC) transmission that is able to improve the finite-length performance of a system using spatially-coupled low-density parity-check (SC-LDPC) codes. In CC transmission, instead of transmitting a sequence of independent codewords from a terminated SC-LDPC code chain, we connect multiple chains in a layered format, where encoding, transmission, and decoding are now performed in a continuous fashion. The connections between chains are created at specific points, chosen to improve the finite-length performance of the code structure under iterative decoding. We describe the design of CC schemes for different SC-LDPC code ensembles constructed from protographs: a (J,K)-regular SC-LDPC code chain, a spatially-coupled repeat-accumulate (SC-RA) code, and a spatially-coupled accumulate-repeat-jagged-accumulate (SC- ARJA) code. In all cases, significant performance improvements are reported and, in addition, it is shown that using CC transmission only requires a small increase in decoding complexity and decoding delay with respect to a system employing a single SC-LDPC code chain for transmission.
Community Structure in Industrial SAT Instances
Venue: arXiv cs.AI 2019
Year: 2019

Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there are few works trying to exactly characterize the main features of this structure. The research community on complex networks has developed techniques of analysis and algorithms to study real-world graphs that can be used by the SAT community. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them. In this paper, inspired by the results on complex networks, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. In our analysis, we represent SAT instances as graphs, and we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver. In particular, we use the community structure to detect that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. This is, learned clauses tend to contain variables of distinct communities.
Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
Venue: arXiv cs.LG 2019
Year: 2019

Submodular continuous functions are a category of (generally) non-convex/non-concave functions with a wide spectrum of applications. We characterize these functions and demonstrate that they can be maximized efficiently with approximation guarantees. Specifically, i) We introduce the weak DR property that gives a unified characterization of submodularity for all set, integer-lattice and continuous functions; ii) for maximizing monotone DR-submodular continuous functions under general down-closed convex constraints, we propose a Frank-Wolfe variant with $(1-1/e)$ approximation guarantee, and sub-linear convergence rate; iii) for maximizing general non-monotone submodular continuous functions subject to box constraints, we propose a DoubleGreedy algorithm with $1/3$ approximation guarantee. Submodular continuous functions naturally find applications in various real-world settings, including influence and revenue maximization with continuous assignments, sensor energy management, multi-resolution data summarization, facility location, etc. Experimental results show that the proposed algorithms efficiently generate superior solutions compared to baseline algorithms.
Unbiased Inversion-Based Fault Estimation of Systems with Non-Minimum Phase Fault-to-Output Dynamics
Venue: arXiv cs.SY 2019
Year: 2019

We propose a framework for inversion-based estimation of certain categories of faults in discrete-time linear systems. The fault signal, as an unknown input, is reconstructed from its projections onto two subspaces. One projection is achieved through an algebraic operation, whereas the other is given by a dynamic filter whose poles coincide with the transmission zeros of the system. A feedback is then introduced to stabilize the above filter as well as to provide an unbiased estimate of the unknown input. Our solution has two distinctive and practical advantages. First, it represents a unified approach to the problem of inversion of both minimum and non-minimum phase systems as well as systems having transmission zeros on the unit circle. Second, the feedback structure makes the proposed scheme robust to noise. We have shown that the proposed inversion filter is unbiased for certain categories of faults. Finally, we have illustrated the performance of our proposed methodologies through numerous simulation studies.
Two Measures of Dependence
Venue: arXiv cs.IT 2019
Year: 2019

Two families of dependence measures between random variables are introduced. They are based on the Rényi divergence of order $α$ and the relative $α$-entropy, respectively, and both dependence measures reduce to Shannon's mutual information when their order $α$ is one. The first measure shares many properties with the mutual information, including the data-processing inequality, and can be related to the optimal error exponents in composite hypothesis testing. The second measure does not satisfy the data-processing inequality, but appears naturally in the context of distributed task encoding.
Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach
Venue: arXiv cs.GT 2019
Year: 2019

This paper studies repeated games where two players play multiple duopolistic games simultaneously (multimarket contact). A key assumption is that each player receives a noisy and private signal about the other's actions (private monitoring or observation errors). There has been no game-theoretic support that multimarket contact facilitates collusion or not, in the sense that more collusive equilibria in terms of per-market profits exist than those under a benchmark case of one market. An equilibrium candidate under the benchmark case is belief-free strategies. We are the first to construct a non-trivial class of strategies that exhibits the effect of multimarket contact from the perspectives of simplicity and mild punishment. Strategies must be simple because firms in a cartel must coordinate each other with no communication. Punishment must be mild to an extent that it does not hurt even the minimum required profits in the cartel. We thus focus on two-state automaton strategies such that the players are cooperative in at least one market even when he or she punishes a traitor. Furthermore, we identify an additional condition (partial indifference), under which the collusive equilibrium yields the optimal payoff.
Probabilistic call by push value
Venue: arXiv cs.LO 2019
Year: 2019

We introduce a probabilistic extension of Levy's Call-By-Push-Value. This extension consists simply in adding a " flipping coin " boolean closed atomic expression. This language can be understood as a major generalization of Scott's PCF encompassing both call-by-name and call-by-value and featuring recursive (possibly lazy) data types. We interpret the language in the previously introduced denotational model of probabilistic coherence spaces, a categorical model of full classical Linear Logic, interpreting data types as coalgebras for the resource comonad. We prove adequacy and full abstraction, generalizing earlier results to a much more realistic and powerful programming language.
Adaptive Nonnegative Matrix Factorization and Measure Comparisons for Recommender Systems
Venue: arXiv cs.LG 2019
Year: 2019

The Nonnegative Matrix Factorization (NMF) of the rating matrix has shown to be an effective method to tackle the recommendation problem. In this paper we propose new methods based on the NMF of the rating matrix and we compare them with some classical algorithms such as the SVD and the regularized and unregularized non-negative matrix factorization approach. In particular a new algorithm is obtained changing adaptively the function to be minimized at each step, realizing a sort of dynamic prior strategy. Another algorithm is obtained modifying the function to be minimized in the NMF formulation by enforcing the reconstruction of the unknown ratings toward a prior term. We then combine different methods obtaining two mixed strategies which turn out to be very effective in the reconstruction of missing observations. We perform a thoughtful comparison of different methods on the basis of several evaluation measures. We consider in particular rating, classification and ranking measures showing that the algorithm obtaining the best score for a given measure is in general the best also when different measures are considered, lowering the interest in designing specific evaluation measures. The algorithms have been tested on different datasets, in particular the 1M, and 10M MovieLens datasets containing ratings on movies, the Jester dataset with ranting on jokes and Amazon Fine Foods dataset with ratings on foods. The comparison of the different algorithms, shows the good performance of methods employing both an explicit and an implicit regularization scheme. Moreover we can get a boost by mixed strategies combining a fast method with a more accurate one.
Wiretap Channels with Random States Non-Causally Available at the Encoder
Venue: arXiv cs.IT 2019
Year: 2019

We study the state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes all other instances of CSI availability as special cases, and calls for an efficient utilization of the state sequence for both reliability and security purposes. A lower bound on the secrecy-capacity, that improves upon the previously best known result published by Prabhakaran et al., is derived based on a novel superposition coding scheme. Our achievability gives rise to the exact secrecy-capacity characterization of a class of SD-WTCs that decompose into a product of two WTCs, where one is independent of the state and the other one depends only on the state. The results are derived under the strict semantic-security metric that requires negligible information leakage for all message distributions.
Password Cracking: The Effect of Hash Function Bias on the Average Guesswork
Venue: arXiv cs.CR 2019
Year: 2019

Modern authentication systems store hashed values of passwords of users using cryptographic hash functions. Therefore, to crack a password an attacker needs to guess a hash function input that is mapped to the hashed value, as opposed to the password itself. We call a hash function that maps the same number of inputs to each bin, as \textbf{unbiased}. However, cryptographic hash functions in use have not been proven to be unbiased (i.e., they may have an unequal number of inputs mapped to different bins). A cryptographic hash function has the property that it is computationally difficult to find an input mapped to a bin. In this work we introduce a structured notion of biased hash functions for which we analyze the average guesswork under certain types of brute force attacks. This work shows that the level of security depends on the set of hashed values of valid users as well as the statistical profile of a hash function, resulting from bias. We examine the average guesswork conditioned on the set of hashed values, and model the statistical profile through the empirical distribution of the number of inputs that are mapped to a bin. In particular, we focus on a class of statistical profiles (capturing the bias) , which we call type-class statistical profiles, that has an empirical distribution related to the probability of the type classes defined in the method of types. For such profiles, we show that the average guesswork is related to basic measures in information theory such as entropy and divergence. We use this to show that the effect of bias on the conditional average guesswork is limited compared to other system parameters such as the number of valid users who store their hashed passwords in the system.