OpenRaiser/Intern-Atlas huggingface dataset:
Estimation Efficiency Under Privacy Constraints
Venue: arXiv cs.IT 2018
Year: 2018

We investigate the problem of estimating a random variable $Y\in \mathcal{Y}$ under a privacy constraint dictated by another random variable $X\in \mathcal{X}$, where estimation efficiency and privacy are assessed in terms of two different loss functions. In the discrete case, we use the Hamming loss function and express the corresponding utility-privacy tradeoff in terms of the privacy-constrained guessing probability $h(P_{XY}, ε)$, the maximum probability $\mathsf{P}_\mathsf{c}(Y|Z)$ of correctly guessing $Y$ given an auxiliary random variable $Z\in \mathcal{Z}$, where the maximization is taken over all $P_{Z|Y}$ ensuring that $\mathsf{P}_\mathsf{c}(X|Z)\leq ε$ for a given privacy threshold $ε\geq 0$. We prove that $h(P_{XY}, \cdot)$ is concave and piecewise linear, which allows us to derive its expression in closed form for any $ε$ when $X$ and $Y$ are binary. In the non-binary case, we derive $h(P_{XY}, ε)$ in the high utility regime (i.e., for sufficiently large values of $ε$) under the assumption that $Z$ takes values in $\mathcal{Y}$. We also analyze the privacy-constrained guessing probability for two binary vector scenarios. When $X$ and $Y$ are continuous random variables, we use the squared-error loss function and express the corresponding utility-privacy tradeoff in terms of $\mathsf{sENSR}(P_{XY}, ε)$, which is the smallest normalized minimum mean squared-error (mmse) incurred in estimating $Y$ from its Gaussian perturbation $Z$, such that the mmse of $f(X)$ given $Z$ is within $ε$ of the variance of $f(X)$ for any non-constant real-valued function $f$. We derive tight upper and lower bounds for $\mathsf{sENSR}$ when $Y$ is Gaussian. We also obtain a tight lower bound for $\mathsf{sENSR}(P_{XY}, ε)$ for general absolutely continuous random variables when $ε$ is sufficiently small.
Complete Cyclic Proof Systems for Inductive Entailments
Venue: arXiv cs.LO 2018
Year: 2018

In this paper we develop cyclic proof systems for the problem of inclusion between the least sets of models of mutually recursive predicates, when the ground constraints in the inductive definitions belong to the quantifier-free fragments of (i) First Order Logic with the canonical Herbrand interpretation and (ii) Separation Logic, respectively. Inspired by classical automata-theoretic techniques of proving language inclusion between tree automata, we give a small set of inference rules, that are proved to be sound and complete, under certain semantic restrictions, involving the set of constraints in the inductive system. Moreover, we investigate the decidability and computational complexity of these restrictions for all the logical fragments considered and provide a proof search semi-algorithm that becomes a decision procedure for the entailment problem, for those systems that fulfill the restrictions.
Assortment Optimization under the Sequential Multinomial Logit Model
Venue: arXiv cs.DM 2018
Year: 2018

We study the assortment optimization problem under the Sequential Multinomial Logit (SML), a discrete choice model that generalizes the multinomial logit (MNL). Under the SML model, products are partitioned into two levels, to capture differences in attractiveness, brand awareness and, or visibility of the products in the market. When a consumer is presented with an assortment of products, she first considers products in the first level and, if none of them is purchased, products in the second level are considered. This model is a special case of the Perception-Adjusted Luce Model (PALM) recently proposed by Echenique et al (2018). It can explain many behavioural phenomena such as the attraction, compromise, similarity effects and choice overload which cannot be explained by the MNL model or any discrete choice model based on random utility. In particular, the SML model allows violations to regularity which states that the probability of choosing a product cannot increase if the offer set is enlarged. This paper shows that the seminal concept of revenue-ordered assortment sets, which contain an optimal assortment under the MNL model, can be generalized to the SML model. More precisely, the paper proves that all optimal assortments under the SML are revenue-ordered by level, a natural generalization of revenue-ordered assortments that contains, at most, a quadratic number of assortments. As a corollary, assortment optimization under the SML is polynomial-time solvable. This result is particularly interesting given that the SML model does not satisfy the regularity condition and, therefore, it can explain choice behaviours that cannot be explained by any choice model based on random utility.
Best-Effort Inductive Logic Programming via Fine-grained Cost-based Hypothesis Generation
Venue: arXiv cs.AI 2018
Year: 2018

We describe the Inspire system which participated in the first competition on Inductive Logic Programming (ILP). Inspire is based on Answer Set Programming (ASP). The distinguishing feature of Inspire is an ASP encoding for hypothesis space generation: given a set of facts representing the mode bias, and a set of cost configuration parameters, each answer set of this encoding represents a single rule that is considered for finding a hypothesis that entails the given examples. Compared with state-of-the-art methods that use the length of the rule body as a metric for rule complexity, our approach permits a much more fine-grained specification of the shape of hypothesis candidate rules. The Inspire system iteratively increases the rule cost limit and thereby increases the search space until it finds a suitable hypothesis. The system searches for a hypothesis that entails a single example at a time, utilizing an ASP encoding derived from the encoding used in XHAIL. We perform experiments with the development and test set of the ILP competition. For comparison we also adapted the ILASP system to process competition instances. Experimental results show that the cost parameters for the hypothesis search space are an important factor for finding hypotheses to competition instances within tight resource bounds.
Probabilistic Program Equivalence for NetKAT
Venue: arXiv cs.PL 2018
Year: 2018

We tackle the problem of deciding whether two probabilistic programs are equivalent in Probabilistic NetKAT, a formal language for specifying and reasoning about the behavior of packet-switched networks. We show that the problem is decidable for the history-free fragment of the language by developing an effective decision procedure based on stochastic matrices. The main challenge lies in reasoning about iteration, which we address by designing an encoding of the program semantics as a finite-state absorbing Markov chain, whose limiting distribution can be computed exactly. In an extended case study on a real-world data center network, we automatically verify various quantitative properties of interest, including resilience in the presence of failures, by analyzing the Markov chain semantics.
An Analysis of Human-centered Geolocation
Venue: arXiv cs.CV 2018
Year: 2018

Online social networks contain a constantly increasing amount of images - most of them focusing on people. Due to cultural and climate factors, fashion trends and physical appearance of individuals differ from city to city. In this paper we investigate to what extent such cues can be exploited in order to infer the geographic location, i.e. the city, where a picture was taken. We conduct a user study, as well as an evaluation of automatic methods based on convolutional neural networks. Experiments on the Fashion 144k and a Pinterest-based dataset show that the automatic methods succeed at this task to a reasonable extent. As a matter of fact, our empirical results suggest that automatic methods can surpass human performance by a large margin. Further inspection of the trained models shows that human-centered characteristics, like clothing style, physical features, and accessories, are informative for the task at hand. Moreover, it reveals that also contextual features, e.g. wall type, natural environment, etc., are taken into account by the automatic methods.
Unsupervised Body Part Regression via Spatially Self-ordering Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Automatic body part recognition for CT slices can benefit various medical image applications. Recent deep learning methods demonstrate promising performance, with the requirement of large amounts of labeled images for training. The intrinsic structural or superior-inferior slice ordering information in CT volumes is not fully exploited. In this paper, we propose a convolutional neural network (CNN) based Unsupervised Body part Regression (UBR) algorithm to address this problem. A novel unsupervised learning method and two inter-sample CNN loss functions are presented. Distinct from previous work, UBR builds a coordinate system for the human body and outputs a continuous score for each axial slice, representing the normalized position of the body part in the slice. The training process of UBR resembles a self-organization process: slice scores are learned from inter-slice relationships. The training samples are unlabeled CT volumes that are abundant, thus no extra annotation effort is needed. UBR is simple, fast, and accurate. Quantitative and qualitative experiments validate its effectiveness. In addition, we show two applications of UBR in network initialization and anomaly detection.
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
Venue: arXiv cs.IT 2018
Year: 2018

We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly generalize the usual symbol corruption errors and are much harder to protect against. We show how to hide the complications of synchronization errors in many applications by introducing very general channel simulations which efficiently transform an insertion-deletion channel into a regular symbol corruption channel with an error rate larger by a constant factor and a slightly smaller alphabet. We generalize synchronization string based methods which were recently introduced as a tool to design essentially optimal error correcting codes for insertion-deletion channels. Our channel simulations depend on the fact that, at the cost of increasing the error rate by a constant factor, synchronization strings can be decoded in a streaming manner that preserves linearity of time. We also provide a lower bound showing that this constant factor cannot be improved to $1+ε$, in contrast to what is achievable for error correcting codes. Our channel simulations drastically generalize the applicability of synchronization strings. We provide new interactive coding schemes which simulate any interactive two-party protocol over an insertion-deletion channel. Our results improve over the interactive coding schemes of Braverman et al. [TransInf 2017] and Sherstov and Wu [FOCS 2017], which achieve a small constant rate and require exponential time computations, with respect to computational and communication complexities. We provide the first computationally efficient interactive coding schemes for synchronization errors, the first coding scheme with a rate approaching one for small noise rates, and also the first coding scheme that works over arbitrarily small alphabet sizes.
How hard is it to satisfy (almost) all roommates?
Venue: arXiv cs.CC 2018
Year: 2018

The classic Stable Roommates problem (which is the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners. Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost γ, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called Min-Block-Pair Stable Roommates, which seeks to find a matching with a minimum number β of blocking pairs. Our main result is that Egal Stable Roommates parameterized by γ is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by β is W[1]-hard, even if the length of each preference list is at most five.
Uncertainty principles and optimally sparse wavelet transforms
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we introduce a new localization framework for wavelet transforms, such as the 1D wavelet transform and the Shearlet transform. Our goal is to design nonadaptive window functions that promote sparsity in some sense. For that, we introduce a framework for analyzing localization aspects of window functions. Our localization theory diverges from the conventional theory in two ways. First, we distinguish between the group generators, and the operators that measure localization (called observables). Second, we define the uncertainty of a signal transform based on a window as a whole, instead of defining the uncertainty of an individual window. We show that the uncertainty of a window function, in the signal space, is closely related to the localization of the reproducing kernel of the wavelet transform, in phase space. As a result, we show that using uncertainty minimizing window functions, results in representations which are optimally sparse in some sense.
Coding sets with asymmetric information
Venue: arXiv cs.DS 2018
Year: 2018

We study the following one-way asymmetric transmission problem, also a variant of model-based compressed sensing: a resource-limited encoder has to report a small set $S$ from a universe of $N$ items to a more powerful decoder (server). The distinguishing feature is asymmetric information: the subset $S$ is comprised of i.i.d. samples from a prior distribution $μ$, and $μ$ is only known to the decoder. The goal for the encoder is to encode $S$ obliviously, while achieving the information-theoretic bound of $|S| \cdot H(μ)$, i.e., the Shannon entropy bound. We first show that any such compression scheme must be {\em randomized}, if it gains non-trivially from the prior $μ$. This stands in contrast to the symmetric case (when both the encoder and decoder know $μ$), where the Huffman code provides a near-optimal deterministic solution. On the other hand, a rather simple argument shows that, when $|S|=k$, a random linear code achieves near-optimal communication rate of about $k\cdot H(μ)$ bits. Alas, the resulting scheme has prohibitive decoding time: about ${N\choose k} \approx (N/k)^k$. Our main result is a computationally efficient and linear coding scheme, which achieves an $O(\lg\lg N)$-competitive communication ratio compared to the optimal benchmark, and runs in $\text{poly}(N,k)$ time. Our "multi-level" coding scheme uses a combination of hashing and syndrome-decoding of Reed-Solomon codes, and relies on viewing the (unknown) prior $μ$ as a rather small convex combination of uniform ("flat") distributions.
Improving Naive Bayes for Regression with Optimised Artificial Surrogate Data
Venue: arXiv cs.AI 2018
Year: 2018

Can we evolve better training data for machine learning algorithms? To investigate this question we use population-based optimisation algorithms to generate artificial surrogate training data for naive Bayes for regression. We demonstrate that the generalisation performance of naive Bayes for regression models is enhanced by training them on the artificial data as opposed to the real data. These results are important for two reasons. Firstly, naive Bayes models are simple and interpretable but frequently underperform compared to more complex "black box" models, and therefore new methods of enhancing accuracy are called for. Secondly, the idea of using the real training data indirectly in the construction of the artificial training data, as opposed to directly for model training, is a novel twist on the usual machine learning paradigm.
Cheap or Robust? The Practical Realization of Self-Driving Wheelchair Technology
Venue: arXiv cs.RO 2018
Year: 2018

To date, self-driving experimental wheelchair technologies have been either inexpensive or robust, but not both. Yet, in order to achieve real-world acceptance, both qualities are fundamentally essential. We present a unique approach to achieve inexpensive and robust autonomous and semi-autonomous assistive navigation for existing fielded wheelchairs, of which there are approximately 5 million units in Canada and United States alone. Our prototype wheelchair platform is capable of localization and mapping, as well as robust obstacle avoidance, using only a commodity RGB-D sensor and wheel odometry. As a specific example of the navigation capabilities, we focus on the single most common navigation problem: the traversal of narrow doorways in arbitrary environments. The software we have developed is generalizable to corridor following, desk docking, and other navigation tasks that are either extremely difficult or impossible for people with upper-body mobility impairments.
One-shot Face Recognition by Promoting Underrepresented Classes
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we study the problem of training large-scale face identification model with imbalanced training data. This problem naturally exists in many real scenarios including large-scale celebrity recognition, movie actor annotation, etc. Our solution contains two components. First, we build a face feature extraction model, and improve its performance, especially for the persons with very limited training samples, by introducing a regularizer to the cross entropy loss for the multi-nomial logistic regression (MLR) learning. This regularizer encourages the directions of the face features from the same class to be close to the direction of their corresponding classification weight vector in the logistic regression. Second, we build a multi-class classifier using MLR on top of the learned face feature extraction model. Since the standard MLR has poor generalization capability for the one-shot classes even if these classes have been oversampled, we propose a novel supervision signal called underrepresented-classes promotion loss, which aligns the norms of the weight vectors of the one-shot classes (a.k.a. underrepresented-classes) to those of the normal classes. In addition to the original cross entropy loss, this new loss term effectively promotes the underrepresented classes in the learned model and leads to a remarkable improvement in face recognition performance. We test our solution on the MS-Celeb-1M low-shot learning benchmark task. Our solution recognizes 94.89% of the test images at the precision of 99\% for the one-shot classes. To the best of our knowledge, this is the best performance among all the published methods using this benchmark task with the same setup, including all the participants in the recent MS-Celeb-1M challenge at ICCV 2017.
On the covering radius of small codes versus dual distance
Venue: arXiv cs.IT 2018
Year: 2018

Tietäväinen's upper and lower bounds assert that for block-length-$n$ linear codes with dual distance $d$, the covering radius $R$ is at most $\frac{n}{2}-(\frac{1}{2}-o(1))\sqrt{dn}$ and typically at least $\frac{n}{2}-Θ(\sqrt{dn\log{\frac{n}{d}}})$. The gap between those bounds on $R -\frac{n}{2}$ is an $Θ(\sqrt{\log{\frac{n}{d}}})$ factor related to the gap between the worst covering radius given $d$ and the sphere-covering bound. Our focus in this paper is on the case when $d = o(n)$, i.e., when the code size is subexponential and the gap is $w(1)$. We show that up to a constant, the gap can be eliminated by relaxing the covering requirement to allow for missing $o(1)$ fraction of points. Namely, if the dual distance $d = o(n)$, then for sufficiently large $d$, almost all points can be covered with radius $R\leq\frac{n}{2}-Θ(\sqrt{dn\log{\frac{n}{d}}})$. Compared to random linear codes, our bound on $R-\frac{n}{2}$ is asymptotically tight up to a factor less than $3$. We give applications to dual BCH codes. The proof builds on the author's previous work on the weight distribution of cosets of linear codes, which we simplify in this paper and extend from codes to probability distributions on $\{0,1\}^n$, thus enabling the extension of the above result to $(d-1)$-wise independent distributions.
DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning
Venue: arXiv cs.CL 2018
Year: 2018

We study the problem of learning to reason in large scale knowledge graphs (KGs). More specifically, we describe a novel reinforcement learning framework for learning multi-hop relational paths: we use a policy-based agent with continuous states based on knowledge graph embeddings, which reasons in a KG vector space by sampling the most promising relation to extend its path. In contrast to prior work, our approach includes a reward function that takes the accuracy, diversity, and efficiency into consideration. Experimentally, we show that our proposed method outperforms a path-ranking based algorithm and knowledge graph embedding methods on Freebase and Never-Ending Language Learning datasets.
Learning Task Priorities from Demonstrations
Venue: arXiv cs.RO 2018
Year: 2018

Bimanual operations in humanoids offer the possibility to carry out more than one manipulation task at the same time, which in turn introduces the problem of task prioritization. We address this problem from a learning from demonstration perspective, by extending the Task-Parameterized Gaussian Mixture Model (TP-GMM) to Jacobian and null space structures. The proposed approach is tested on bimanual skills but can be applied in any scenario where the prioritization between potentially conflicting tasks needs to be learned. We evaluate the proposed framework in: two different tasks with humanoids requiring the learning of priorities and a loco-manipulation scenario, showing that the approach can be exploited to learn the prioritization of multiple tasks in parallel.
What Looks Good with my Sofa: Multimodal Search Engine for Interior Design
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a multi-modal search engine for interior design that combines visual and textual queries. The goal of our engine is to retrieve interior objects, e.g. furniture or wall clocks, that share visual and aesthetic similarities with the query. Our search engine allows the user to take a photo of a room and retrieve with a high recall a list of items identical or visually similar to those present in the photo. Additionally, it allows to return other items that aesthetically and stylistically fit well together. To achieve this goal, our system blends the results obtained using textual and visual modalities. Thanks to this blending strategy, we increase the average style similarity score of the retrieved items by 11%. Our work is implemented as a Web-based application and it is planned to be opened to the public.