OpenRaiser/Intern-Atlas huggingface dataset:
Achieving Maximum Distance Separable Private Information Retrieval Capacity With Linear Codes
Venue: arXiv cs.IT 2019
Year: 2019

We propose three private information retrieval (PIR) protocols for distributed storage systems (DSSs) where data is stored using an arbitrary linear code. The first two protocols, named Protocol 1 and Protocol 2, achieve privacy for the scenario with noncolluding nodes. Protocol 1 requires a file size that is exponential in the number of files in the system, while Protocol 2 requires a file size that is independent of the number of files and is hence simpler. We prove that, for certain linear codes, Protocol 1 achieves the maximum distance separable (MDS) PIR capacity, i.e., the maximum PIR rate (the ratio of the amount of retrieved stored data per unit of downloaded data) for a DSS that uses an MDS code to store any given (finite and infinite) number of files, and Protocol 2 achieves the asymptotic MDS-PIR capacity (with infinitely large number of files in the DSS). In particular, we provide a necessary and a sufficient condition for a code to achieve the MDS-PIR capacity with Protocols 1 and 2 and prove that cyclic codes, Reed-Muller (RM) codes, and a class of distance-optimal local reconstruction codes achieve both the finite MDS-PIR capacity (i.e., with any given number of files) and the asymptotic MDS-PIR capacity with Protocols 1 and 2, respectively. Furthermore, we present a third protocol, Protocol 3, for the scenario with multiple colluding nodes, which can be seen as an improvement of a protocol recently introduced by Freij-Hollanti et al.. Similar to the noncolluding case, we provide a necessary and a sufficient condition to achieve the maximum possible PIR rate of Protocol 3. Moreover, we provide a particular class of codes that is suitable for this protocol and show that RM codes achieve the maximum possible PIR rate for the protocol. For all three protocols, we present an algorithm to optimize their PIR rates.
Optimal Construction of Compressed Indexes for Highly Repetitive Texts
Venue: arXiv cs.DS 2019
Year: 2019

We propose algorithms that, given the input string of length $n$ over integer alphabet of size $σ$, construct the Burrows-Wheeler transform (BWT), the permuted longest-common-prefix (PLCP) array, and the LZ77 parsing in $O(n/\log_σn+r\,{\rm polylog}\,n)$ time and working space, where $r$ is the number of runs in the BWT of the input. These are the essential components of many compressed indexes such as compressed suffix tree, FM-index, and grammar and LZ77-based indexes, but also find numerous applications in sequence analysis and data compression. The value of $r$ is a common measure of repetitiveness that is significantly smaller than $n$ if the string is highly repetitive. Since just accessing every symbol of the string requires $Ω(n/\log_σn)$ time, the presented algorithms are time and space optimal for inputs satisfying the assumption $n/r\inΩ({\rm polylog}\,n)$ on the repetitiveness. For such inputs our result improves upon the currently fastest general algorithms of Belazzougui (STOC 2014) and Munro et al. (SODA 2017) which run in $O(n)$ time and use $O(n/\log_σ n)$ working space. We also show how to use our techniques to obtain optimal solutions on highly repetitive data for other fundamental string processing problems such as: Lyndon factorization, construction of run-length compressed suffix arrays, and some classical "textbook" problems such as computing the longest substring occurring at least some fixed number of times.
Enhancing Symbolic Execution of Heap-based Programs with Separation Logic for Test Input Generation
Venue: arXiv cs.SE 2019
Year: 2019

Symbolic execution is a well established method for test input generation. Despite of having achieved tremendous success over numerical domains, existing symbolic execution techniques for heap-based programs are limited due to the lack of a succinct and precise description for symbolic values over unbounded heaps. In this work, we present a new symbolic execution method for heap-based programs based on separation logic. The essence of our proposal is context-sensitive lazy initialization, a novel approach for efficient test input generation. Our approach differs from existing approaches in two ways. Firstly, our approach is based on separation logic, which allows us to precisely capture preconditions of heap-based programs so that we avoid generating invalid test inputs. Secondly, we generate only fully initialized test inputs, which are more useful in practice compared to those partially initialized test inputs generated by the state-of-the-art tools. We have implemented our approach as a tool, called Java StarFinder, and evaluated it on a set of programs with complex heap inputs. The results show that our approach significantly reduces the number of invalid test inputs and improves the test coverage.
Measurement-based Efficient Resource Allocation with Demand-Side Adjustments
Venue: arXiv cs.SY 2019
Year: 2019

The problem of efficient resource allocation has drawn significant attention in many scientific disciplines due to its direct societal benefits, such as energy savings. Traditional approaches in addressing online resource allocation problems neglect the potential benefit of feedback information available from the running tasks/loads as well as the potential flexibility of a task to adjust its operation/service-level in order to increase efficiency. The present paper builds upon recent developments in the area of bandwidth allocation in computing systems and proposes a generalized design approach for resource allocation when only performance measurements of the running tasks are available, possibly corrupted by noise. We demonstrate through analysis and simulations the potential of the proposed scheme in providing fair and efficient allocation of resources in a large class of resource allocation problems.
The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
Venue: arXiv cs.IT 2019
Year: 2019

Sparse superposition codes, or sparse regression codes (SPARCs), are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviations bound on the probability of AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(\log n)^{2T}$, where $T$, the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity.
On the Universality of Memcomputing Machines
Venue: arXiv cs.NE 2019
Year: 2019

Universal memcomputing machines (UMMs) [IEEE Trans. Neural Netw. Learn. Syst. 26, 2702 (2015)] represent a novel computational model in which memory (time non-locality) accomplishes both tasks of storing and processing of information. UMMs have been shown to be Turing-complete, namely they can simulate any Turing machine. In this paper, using set theory and cardinality arguments, we compare them with liquid-state machines (or "reservoir computing") and quantum machines ("quantum computing"). We show that UMMs can simulate both types of machines, hence they are both "liquid-" or "reservoir-complete" and "quantum-complete". Of course, these statements pertain only to the type of problems these machines can solve, and not to the amount of resources required for such simulations. Nonetheless, the method presented here provides a general framework in which to describe the relation between UMMs and any other type of computational model.
Finding Submodularity Hidden in Symmetric Difference
Venue: arXiv cs.DM 2019
Year: 2019

A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ for any pair $X, Y \subseteq V$. The symmetric difference transformation (SD-transformation) of $f$ by a canonical set $S \subseteq V$ is a set function $g$ given by $g(X) = f(X \vartriangle S)$ for $X \subseteq V$,where $X \vartriangle S = (X \setminus S) \cup (S \setminus X)$ denotes the symmetric difference between $X$ and $S$. Submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-stransformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set $S$, given the SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$ is given by a function value oracle. A submodular function $f$ on $V$ is said to be strict if $f(X) + f(Y) > f(X \cup Y) + f(X \cap Y)$ holds whenever both $X \setminus Y$ and $Y \setminus X$ are nonempty. We show that the problem is solved by using ${\rm O}(|V|)$ oracle calls when $f$ is strictly submodular, although it requires exponentially many oracle calls in general.
Letter-Based Speech Recognition with Gated ConvNets
Venue: arXiv cs.CL 2019
Year: 2019

In the recent literature, "end-to-end" speech systems often refer to letter-based acoustic models trained in a sequence-to-sequence manner, either via a recurrent model or via a structured output learning approach (such as CTC). In contrast to traditional phone (or senone)-based approaches, these "end-to-end'' approaches alleviate the need of word pronunciation modeling, and do not require a "forced alignment" step at training time. Phone-based approaches remain however state of the art on classical benchmarks. In this paper, we propose a letter-based speech recognition system, leveraging a ConvNet acoustic model. Key ingredients of the ConvNet are Gated Linear Units and high dropout. The ConvNet is trained to map audio sequences to their corresponding letter transcriptions, either via a classical CTC approach, or via a recent variant called ASG. Coupled with a simple decoder at inference time, our system matches the best existing letter-based systems on WSJ (in word error rate), and shows near state of the art performance on LibriSpeech.
Classical System of Martin-Lof's Inductive Definitions is not Equivalent to Cyclic Proofs
Venue: arXiv cs.LO 2019
Year: 2019

A cyclic proof system, called CLKID-omega, gives us another way of representing inductive definitions and efficient proof search. The 2005 paper by Brotherston showed that the provability of CLKID-omega includes the provability of LKID, first order classical logic with inductive definitions in Martin-Löf's style, and conjectured the equivalence. The equivalence has been left an open question since 2011. This paper shows that CLKID-omega and LKID are indeed not equivalent. This paper considers a statement called 2-Hydra in these two systems with the first-order language formed by 0, the successor, the natural number predicate, and a binary predicate symbol used to express 2-Hydra. This paper shows that the 2-Hydra statement is provable in CLKID-omega, but the statement is not provable in LKID, by constructing some Henkin model where the statement is false.
Object-Oriented Theorem Proving (OOTP): First Thoughts
Venue: arXiv cs.PL 2019
Year: 2019

Automatic (i.e., computer-assisted) theorem proving (ATP) can come in many flavors. This document presents early steps in our effort towards defining object-oriented theorem proving (OOTP) as a new style of ATP. Traditional theorem proving (TTP) is the only well-known flavor of ATP so far. OOTP is a generalization of TTP. While TTP is strongly based on functional programming (FP), OOTP is strongly based on object-oriented programming (OOP) instead. We believe OOTP is a style of theorem proving that is no less powerful and no less natural than TTP and thus likely will be no less practically useful than TTP.
Objective evaluation metrics for automatic classification of EEG events
Venue: arXiv cs.LG 2019
Year: 2019

The evaluation of machine learning algorithms in biomedical fields for applications involving sequential data lacks standardization. Common quantitative scalar evaluation metrics such as sensitivity and specificity can often be misleading depending on the requirements of the application. Evaluation metrics must ultimately reflect the needs of users yet be sufficiently sensitive to guide algorithm development. Feedback from critical care clinicians who use automated event detection software in clinical applications has been overwhelmingly emphatic that a low false alarm rate, typically measured in units of the number of errors per 24 hours, is the single most important criterion for user acceptance. Though using a single metric is not often as insightful as examining performance over a range of operating conditions, there is a need for a single scalar figure of merit. In this paper, we discuss the deficiencies of existing metrics for a seizure detection task and propose several new metrics that offer a more balanced view of performance. We demonstrate these metrics on a seizure detection task based on the TUH EEG Corpus. We show that two promising metrics are a measure based on a concept borrowed from the spoken term detection literature, Actual Term-Weighted Value (ATWV), and a new metric, Time-Aligned Event Scoring (TAES), that accounts for the temporal alignment of the hypothesis to the reference annotation. We also demonstrate that state of the art technology based on deep learning, though impressive in its performance, still needs significant improvement before it meets very strict user acceptance criteria.
Deep Reinforcement Learning for List-wise Recommendations
Venue: arXiv cs.LG 2019
Year: 2019

Recommender systems play a crucial role in mitigating the problem of information overload by suggesting users' personalized items or services. The vast majority of traditional recommender systems consider the recommendation procedure as a static process and make recommendations following a fixed strategy. In this paper, we propose a novel recommender system with the capability of continuously improving its strategies during the interactions with users. We model the sequential interactions between users and a recommender system as a Markov Decision Process (MDP) and leverage Reinforcement Learning (RL) to automatically learn the optimal strategies via recommending trial-and-error items and receiving reinforcements of these items from users' feedbacks. In particular, we introduce an online user-agent interacting environment simulator, which can pre-train and evaluate model parameters offline before applying the model online. Moreover, we validate the importance of list-wise recommendations during the interactions between users and agent, and develop a novel approach to incorporate them into the proposed framework LIRD for list-wide recommendations. The experimental results based on a real-world e-commerce dataset demonstrate the effectiveness of the proposed framework.
A General Framework for Adversarial Examples with Objectives
Venue: arXiv cs.CV 2019
Year: 2019

Images perturbed subtly to be misclassified by neural networks, called adversarial examples, have emerged as a technically deep challenge and an important concern for several application domains. Most research on adversarial examples takes as its only constraint that the perturbed images are similar to the originals. However, real-world application of these ideas often requires the examples to satisfy additional objectives, which are typically enforced through custom modifications of the perturbation process. In this paper, we propose adversarial generative nets (AGNs), a general methodology to train a generator neural network to emit adversarial examples satisfying desired objectives. We demonstrate the ability of AGNs to accommodate a wide range of objectives, including imprecise ones difficult to model, in two application domains. In particular, we demonstrate physical adversarial examples---eyeglass frames designed to fool face recognition---with better robustness, inconspicuousness, and scalability than previous approaches, as well as a new attack to fool a handwritten-digit classifier.
Sequential Decision Making with Limited Observation Capability: Application to Wireless Networks
Venue: arXiv cs.SY 2019
Year: 2019

This work studies a generalized class of restless multi-armed bandits with hidden states and allow cumulative feedback, as opposed to the conventional instantaneous feedback. We call them lazy restless bandits (LRB) as the events of decision-making are sparser than events of state transition. Hence, feedback after each decision event is the cumulative effect of the following state transition events. The states of arms are hidden from the decision-maker and rewards for actions are state dependent. The decision-maker needs to choose one arm in each decision interval, such that long term cumulative reward is maximized. As the states are hidden, the decision-maker maintains and updates its belief about them. It is shown that LRBs admit an optimal policy which has threshold structure in belief space. The Whittle-index policy for solving LRB problem is analyzed; indexability of LRBs is shown. Further, closed-form index expressions are provided for two sets of special cases; for more general cases, an algorithm for index computation is provided. An extensive simulation study is presented; Whittle-index, modified Whittle-index and myopic policies are compared. Lagrangian relaxation of the problem provides an upper bound on the optimal value function; it is used to assess the degree of sub-optimality various policies.
Deep Bidirectional and Unidirectional LSTM Recurrent Neural Network for Network-wide Traffic Speed Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Short-term traffic forecasting based on deep learning methods, especially long short-term memory (LSTM) neural networks, has received much attention in recent years. However, the potential of deep learning methods in traffic forecasting has not yet fully been exploited in terms of the depth of the model architecture, the spatial scale of the prediction area, and the predictive power of spatial-temporal data. In this paper, a deep stacked bidirectional and unidirectional LSTM (SBU- LSTM) neural network architecture is proposed, which considers both forward and backward dependencies in time series data, to predict network-wide traffic speed. A bidirectional LSTM (BDLSM) layer is exploited to capture spatial features and bidirectional temporal dependencies from historical data. To the best of our knowledge, this is the first time that BDLSTMs have been applied as building blocks for a deep architecture model to measure the backward dependency of traffic data for prediction. The proposed model can handle missing values in input data by using a masking mechanism. Further, this scalable model can predict traffic speed for both freeway and complex urban traffic networks. Comparisons with other classical and state-of-the-art models indicate that the proposed SBU-LSTM neural network achieves superior prediction performance for the whole traffic network in both accuracy and robustness.
The Explicit Coding Rate Region of Symmetric Multilevel Diversity Coding
Venue: arXiv cs.IT 2019
Year: 2019

It is well known that {\em superposition coding}, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In this paper, we first obtain closed-form expressions of these uncountably many inequalities. Then we identify a finite subset of inequalities that is sufficient for characterizing the coding rate region. This gives an explicit characterization of the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding.
DeepStyle: Multimodal Search Engine for Fashion and Interior Design
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a multimodal search engine that combines visual and textual cues to retrieve items from a multimedia database aesthetically similar to the query. The goal of our engine is to enable intuitive retrieval of fashion merchandise such as clothes or furniture. Existing search engines treat textual input only as an additional source of information about the query image and do not correspond to the real-life scenario where the user looks for 'the same shirt but of denim'. Our novel method, dubbed DeepStyle, mitigates those shortcomings by using a joint neural network architecture to model contextual dependencies between features of different modalities. We prove the robustness of this approach on two different challenging datasets of fashion items and furniture where our DeepStyle engine outperforms baseline methods by 18-21% on the tested datasets. Our search engine is commercially deployed and available through a Web-based application.
On the Reliability Function of Distributed Hypothesis Testing Under Optimal Detection
Venue: arXiv cs.IT 2019
Year: 2019

The distributed hypothesis testing problem with full side-information is studied. The trade-off (reliability function) between the two types of error exponents under limited rate is studied in the following way. First, the problem is reduced to the problem of determining the reliability function of channel codes designed for detection (in analogy to a similar result which connects the reliability function of distributed lossless compression and ordinary channel codes). Second, a single-letter random-coding bound based on a hierarchical ensemble, as well as a single-letter expurgated bound, are derived for the reliability of channel-detection codes. Both bounds are derived for a system which employs the optimal detection rule. We conjecture that the resulting random-coding bound is ensemble-tight, and consequently optimal within the class of quantization-and-binning schemes.