OpenRaiser/Intern-Atlas huggingface dataset:
Applying Deep Learning to the Newsvendor Problem
Venue: arXiv cs.LG 2018
Year: 2018

The newsvendor problem is one of the most basic and widely applied inventory models. There are numerous extensions of this problem. If the probability distribution of the demand is known, the problem can be solved analytically. However, approximating the probability distribution is not easy and is prone to error; therefore, the resulting solution to the newsvendor problem may be not optimal. To address this issue, we propose an algorithm based on deep learning that optimizes the order quantities for all products based on features of the demand data. Our algorithm integrates the forecasting and inventory-optimization steps, rather than solving them separately, as is typically done, and does not require knowledge of the probability distributions of the demand. Numerical experiments on real-world data suggest that our algorithm outperforms other approaches, including data-driven and machine learning approaches, especially for demands with high volatility. Finally, in order to show how this approach can be used for other inventory optimization problems, we provide an extension for (r,Q) policies.
Consensus Attention-based Neural Networks for Chinese Reading Comprehension
Venue: arXiv cs.CL 2018
Year: 2018

Reading comprehension has embraced a booming in recent NLP research. Several institutes have released the Cloze-style reading comprehension data, and these have greatly accelerated the research of machine comprehension. In this work, we firstly present Chinese reading comprehension datasets, which consist of People Daily news dataset and Children's Fairy Tale (CFT) dataset. Also, we propose a consensus attention-based neural network architecture to tackle the Cloze-style reading comprehension problem, which aims to induce a consensus attention over every words in the query. Experimental results show that the proposed neural network significantly outperforms the state-of-the-art baselines in several public datasets. Furthermore, we setup a baseline for Chinese reading comprehension task, and hopefully this would speed up the process for future research.
Estimation of KL Divergence: Optimal Minimax Rate
Venue: arXiv cs.IT 2018
Year: 2018

The problem of estimating the Kullback-Leibler divergence $D(P\|Q)$ between two unknown distributions $P$ and $Q$ is studied, under the assumption that the alphabet size $k$ of the distributions can scale to infinity. The estimation is based on $m$ independent samples drawn from $P$ and $n$ independent samples drawn from $Q$. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function $f(k)$ is further considered. {An augmented plug-in estimator is proposed, and its worst-case quadratic risk is shown to be within a constant factor of $(\frac{k}{m}+\frac{kf(k)}{n})^2+\frac{\log ^2 f(k)}{m}+\frac{f(k)}{n}$, if $m$ and $n$ exceed a constant factor of $k$ and $kf(k)$, respectively.} Moreover, the minimax quadratic risk is characterized to be within a constant factor of $(\frac{k}{m\log k}+\frac{kf(k)}{n\log k})^2+\frac{\log ^2 f(k)}{m}+\frac{f(k)}{n}$, if $m$ and $n$ exceed a constant factor of $k/\log(k)$ and $kf(k)/\log k$, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.
Classifier Risk Estimation under Limited Labeling Resources
Venue: arXiv cs.LG 2018
Year: 2018

In this paper we propose strategies for estimating performance of a classifier when labels cannot be obtained for the whole test set. The number of test instances which can be labeled is very small compared to the whole test data size. The goal then is to obtain a precise estimate of classifier performance using as little labeling resource as possible. Specifically, we try to answer, how to select a subset of the large test set for labeling such that the performance of a classifier estimated on this subset is as close as possible to the one on the whole test set. We propose strategies based on stratified sampling for selecting this subset. We show that these strategies can reduce the variance in estimation of classifier accuracy by a significant amount compared to simple random sampling (over 65% in several cases). Hence, our proposed methods are much more precise compared to random sampling for accuracy estimation under restricted labeling resources. The reduction in number of samples required (compared to random sampling) to estimate the classifier accuracy with only 1% error is high as 60% in some cases.
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges, the textbook algorithm takes $O(n+m)$ time to construct a DFS tree. In this paper, we study the problem of maintaining a DFS tree when the graph is undergoing incremental updates. Formally, we show: Given an arbitrary online sequence of edge or vertex insertions, there is an algorithm that reports a DFS tree in $O(n)$ worst case time per operation, and requires $O\left(\min\{m \log n, n^2\}\right)$ preprocessing time. Our result improves the previous $O(n \log^3 n)$ worst case update time algorithm by Baswana et al. and the $O(n \log n)$ time by Nakamura and Sadakane, and matches the trivial $Ω(n)$ lower bound when it is required to explicitly output a DFS tree. Our result builds on the framework introduced in the breakthrough work by Baswana et al., together with a novel use of a tree-partition lemma by Duan and Zhan, and the celebrated fractional cascading technique by Chazelle and Guibas.
Number Theoretic Transforms for Secure Signal Processing
Venue: arXiv cs.CR 2018
Year: 2018

Multimedia contents are inherently sensitive signals that must be protected whenever they are outsourced to an untrusted environment. This problem becomes a challenge when the untrusted environment must perform some processing on the sensitive signals; a paradigmatic example is Cloud-based signal processing services. Approaches based on Secure Signal Processing (SSP) address this challenge by proposing novel mechanisms for signal processing in the encrypted domain and interactive secure protocols to achieve the goal of protecting signals without disclosing the sensitive information they convey. This work presents a novel and comprehensive set of approaches and primitives to efficiently process signals in an encrypted form, by using Number Theoretic Transforms (NTTs) in innovative ways. This usage of NTTs paired with appropriate signal pre- and post-coding enables a whole range of easily composable signal processing operations comprising, among others, filtering, generalized convolutions, matrix-based processing or error correcting codes. The main focus is on unattended processing, in which no interaction from the client is needed; for implementation purposes, efficient lattice-based somewhat homomorphic cryptosystems are used. We exemplify these approaches and evaluate their performance and accuracy, proving that the proposed framework opens up a wide variety of new applications for secured outsourced-processing of multimedia contents.
Environmental Information Improves Robotic Search Performance
Venue: arXiv cs.RO 2018
Year: 2018

We address the problem where a mobile search agent seeks to find an unknown number of stationary objects distributed in a bounded search domain, and the search mission is subject to time/distance constraint. Our work accounts for false positives, false negatives and environmental uncertainty. We consider the case that the performance of a search sensor is dependent on the environment (e.g., clutter density), and therefore sensor performance is better in some locations than in others. We specifically consider applications where environmental information can be acquired either by a separate vehicle or by the same vehicle that performs the search task. Our main contribution in this study is to formally derive a decision-theoretic cost function to compute the locations where the environmental information should be acquired. For the cases where computing the optimal locations to sample the environment is computationally expensive, we offer an approximation approach that yields provable near-optimal paths. We show that our decision-theoretic cost function outperforms the information-maximization approach, which is often employed in similar applications.
On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
Venue: arXiv cs.DS 2018
Year: 2018

In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given $m \times n$ matrix $A$ and an $m$-vector $b=(b_1,\dots, b_m)$, there is a non-negative integer $n$-vector $x$ such that $Ax=b$. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IP) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ArXiv 2018]. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal. We also show that when the matrix $A$ is assumed to be non-negative, a component of Papadimitriou's original algorithm is already nearly optimal under ETH. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IP) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IP) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant.
Stability, convergence and Hopf bifurcation analyses of the classical car-following model
Venue: arXiv cs.SY 2018
Year: 2018

Reaction delays play an important role in determining the qualitative dynamical properties of a platoon of vehicles traversing a straight road. In this paper, we investigate the impact of delayed feedback on the dynamics of the Classical Car-Following Model (CCFM). Specifically, we analyze the CCFM in no delay, small delay and arbitrary delay regimes. First, we derive a sufficient condition for local stability of the CCFM in no-delay and small-delay regimes using. Next, we derive the necessary and sufficient condition for local stability of the CCFM for an arbitrary delay. We then demonstrate that the transition of traffic flow from the locally stable to the unstable regime occurs via a Hopf bifurcation, thus resulting in limit cycles in system dynamics. Physically, these limit cycles manifest as back-propagating congestion waves on highways. In the context of human-driven vehicles, our work provides phenomenological insight into the impact of reaction delays on the emergence and evolution of traffic congestion. In the context of self-driven vehicles, our work has the potential to provide design guidelines for control algorithms running in self-driven cars to avoid undesirable phenomena. Specifically, designing control algorithms that avoid jerky vehicular movements is essential. Hence, we derive the necessary and sufficient condition for non-oscillatory convergence of the CCFM. Next, we characterize the rate of convergence of the CCFM, and bring forth the interplay between local stability, non-oscillatory convergence and the rate of convergence of the CCFM. Further, to better understand the oscillations in the system dynamics, we characterize the type of the Hopf bifurcation and the asymptotic orbital stability of the limit cycles using Poincare normal forms and the center manifold theory. The analysis is complemented with stability charts, bifurcation diagrams and MATLAB simulations.
Demand Control Management in Micro-grids: The Impact of Different Policies and Communication Network Topologies
Venue: arXiv cs.MA 2018
Year: 2018

This work studies how the communication network between proactive consumers affects the power utilization and fairness in a simplified direct-current micro-grid model, composed by three coupled layers: physical (an electric circuit that represents a micro-grid), communication (a peer-to-peer network within the micro-grid) and regulatory (individual decision strategies). Our results show that, for optimal power utilization and fairness, a global knowledge about the system is needed, demonstrating the importance of a micro-grid aggregator to inform about the power consumption for different time periods.
The Language of Generalization
Venue: arXiv cs.CL 2018
Year: 2018

Language provides simple ways of communicating generalizable knowledge to each other (e.g., "Birds fly", "John hikes", "Fire makes smoke"). Though found in every language and emerging early in development, the language of generalization is philosophically puzzling and has resisted precise formalization. Here, we propose the first formal account of generalizations conveyed with language that makes quantitative predictions about human understanding. We test our model in three diverse domains: generalizations about categories (generic language), events (habitual language), and causes (causal language). The model explains the gradience in human endorsement through the interplay between a simple truth-conditional semantic theory and diverse beliefs about properties, formalized in a probabilistic model of language understanding. This work opens the door to understanding precisely how abstract knowledge is learned from language.
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks -- Extended version with an Improved Upper Bound --
Venue: arXiv cs.DS 2018
Year: 2018

CSTNs is a constraint-based graph-formalism for conditional temporal planning. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced epsilon-DC (a refined, more realistic, notion of DC), and provided an algorithmic solution to it. The epsilon-DC notion is interesting per se, and the epsilon-DC-Checking algorithm in [Comin and Rizzi, TIME 2015] rests on the assumption that the reaction-time satisfies epsilon > 0; leaving unsolved the question of what happens when epsilon = 0. In this work, we introduce and study pi-DC, a sound notion of DC with an instantaneous reaction-time (i.e. one in which the planner can react to any observation at the same instant of time in which the observation is made). Firstly, we demonstrate by a counter-example that pi-DC is not equivalent to 0-DC, and that 0-DC is actually inadequate for modeling DC with an instantaneous reaction-time. This shows that the main results obtained in our previous work do not apply directly, as they were formulated, to the case of epsilon=0. Motivated by this observation, as a second contribution, our previous tools are extended in order to handle pi-DC, and the notion of ps-tree is introduced, also pointing out a relationship between pi-DC and HyTN-Consistency. Thirdly, a simple reduction from pi-DC-Checking to DC-Checking is identified. This allows us to design and to analyze the first sound-and-complete pi-DC-Checking procedure. Remarkably, the time complexity of the proposed algorithm remains (pseudo) singly-exponential in the number of propositional letters. Finally, it is observed that the technique can be leveraged to actually reduce from pi-DC to 1-DC, this allows us to further improve the exponents in the time complexity of pi-DC-Checking.
Naming a Channel with Beeps
Venue: arXiv cs.DC 2018
Year: 2018

We consider a communication channel in which the only possible communication mode is transmitting beeps, which reach all the nodes instantaneously. Nodes are anonymous, in that they do not have any individual identifiers. The algorithmic goal is to randomly assign names to the nodes in such a manner that the names make a contiguous segment of positive integers starting from $1$. We give a Las Vegas naming algorithm for the case when the number of nodes $n$ is known, and a Monte Carlo algorithm for the case when the number of nodes $n$ is not known. The algorithms are provably optimal with respect to the expected time $O(n\log n)$, the number of used random bits $O(n\log n)$, and the probability of error.
The Distortion-Rate Function of Sampled Wiener Processes
Venue: arXiv cs.IT 2018
Year: 2018

We consider the recovery of a continuous-time Wiener process from a quantized or lossy compressed version of its uniform samples under limited bitrate and sampling rate. We derive a closed form expression for the optimal tradeoff among sampling rate, bitrate, and quadratic distortion in this setting. This expression is given in terms of a reverse waterfilling formula over the asymptotic spectral distribution of a sequence of finite-rank operators associated with the optimal estimator of the Wiener process from its samples. We show that the ratio between this expression and the standard distortion rate function of the Wiener process, describing the optimal tradeoff between bitrate and distortion without a sampling constraint, is only a function of the number of bits per sample. For example using one bit per sample on average, the expected distortion is approximately 1.2 times the standard distortion rate function, indicating a performance loss of about 20% due to sampling. We next consider the distortion when the continuous-time process is estimated from the output of an encoder that is optimal with respect to the discrete-time samples. We show that while the latter is strictly greater than the distortion under optimal encoding, the ratio between the two does not exceed 1.027. We therefore conclude that nearly optimal performance is attained even if the encoder is unaware of the sampling rate and encodes the samples without taking into account the continuous-time underlying process.
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
Venue: arXiv cs.DM 2018
Year: 2018

Nowhere dense classes of graphs are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this paper, we use tools from logic, in particular from a subfield of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerful method in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed value of $r$ a polynomial kernel for the distance-$r$ dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class $\mathcal{C}$ of graphs which is closed under subgraphs, the distance-$r$ dominating set problem admits a kernel on $\mathcal{C}$ for every value of $r$ if, and only if, it admits a polynomial kernel for every value of $r$ (under the standard assumption of parameterized complexity theory that $\mathrm{FPT} \neq W[2]$).
Coded Caching and Content Delivery with Heterogeneous Distortion Requirements
Venue: arXiv cs.IT 2018
Year: 2018

Cache-aided coded content delivery is studied for devices with diverse quality-of-service (QoS) requirements, specified by a different average distortion target. The network consists of a server holding a database of independent contents, and users equipped with local caches of different capacities. User caches are filled by the server during a low traffic period without the knowledge of particular user demands. As opposed to the current literature, which assumes that the users request files in their entirety, it is assumed that the users in the system have distinct distortion requirements; and therefore, each user requests a single file from the database to be served at a different distortion level. Our goal in this work is to characterize the minimum delivery rate the server needs to transmit over an error-free shared link to satisfy all possible demand combinations at the requested distortion levels, considering both centralized and decentralized cache placement.
FEMOSAA: Feature Guided and Knee Driven Multi-Objective Optimization for Self-Adaptive Software
Venue: arXiv cs.SE 2018
Year: 2018

Self-adaptive software (SAS) can reconfigure itself to adapt to the changing environment at runtime, aiming for continually optimizing conflicted non-functional objectives, e.g., response time, energy consumption, throughput and cost etc. In this paper, we present Feature guided and knEe driven Multi-Objective optimization for Self-Adaptive softwAre (FEMOSAA), a novel framework that automatically synergizes the feature model and Multi-Objective Evolutionary Algorithm (MOEA), to optimize SAS at runtime. FEMOSAA operates in two phases: at design time, FEMOSAA automatically transposes the engineers' design of SAS, expressed as a feature model, to fit the MOEA, creating new chromosome representation and reproduction operators. At runtime, FEMOSAA utilizes the feature model as domain knowledge to guide the search and further extend the MOEA, providing a larger chance for finding better solutions. In addition, we have designed a new method to search for the knee solutions, which can achieve a balanced trade-off. We comprehensively evaluated FEMOSAA on two running SAS: one is a highly complex SAS with various adaptable real-world software under the realistic workload trace, another is a service-oriented SAS that can be dynamically composed from services. In particular, we compared the effectiveness and overhead of FEMOSAA against four of its variants and three other search-based frameworks for SAS under various scenarios, including three commonly applied MOEAs, two workload patterns and diverse conflicting quality objectives. The results reveal the effectiveness of FEMOSAA and its superiority over the others with high statistical significance and non-trivial effect sizes.
Practical sketching algorithms for low-rank matrix approximation
Venue: arXiv cs.NA 2018
Year: 2018

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.