OpenRaiser/Intern-Atlas huggingface dataset:
The Resistance to Label Noise in K-NN and DNN Depends on its Concentration
Venue: arXiv cs.LG 2020
Year: 2020

We investigate the classification performance of K-nearest neighbors (K-NN) and deep neural networks (DNNs) in the presence of label noise. We first show empirically that a DNN's prediction for a given test example depends on the labels of the training examples in its local neighborhood. This motivates us to derive a realizable analytic expression that approximates the multi-class K-NN classification error in the presence of label noise, which is of independent importance. We then suggest that the expression for K-NN may serve as a first-order approximation for the DNN error. Finally, we demonstrate empirically the proximity of the developed expression to the observed performance of K-NN and DNN classifiers. Our result may explain the already observed surprising resistance of DNN to some types of label noise. It also characterizes an important factor of it showing that the more concentrated the noise the greater is the degradation in performance.
Incremental and Modular Context-sensitive Analysis
Venue: arXiv cs.PL 2020
Year: 2020

Context-sensitive global analysis of large code bases can be expensive, which can make its use impractical during software development. However, there are many situations in which modifications are small and isolated within a few components, and it is desirable to reuse as much as possible previous analysis results. This has been achieved to date through incremental global analysis fixpoint algorithms that achieve cost reductions at fine levels of granularity, such as changes in program lines. However, these fine-grained techniques are not directly applicable to modular programs, nor are they designed to take advantage of modular structures. This paper describes, implements, and evaluates an algorithm that performs efficient context-sensitive analysis incrementally on modular partitions of programs. The experimental results show that the proposed modular algorithm shows significant improvements, in both time and memory consumption, when compared to existing non-modular, fine-grain incremental analysis techniques. Furthermore, thanks to the proposed inter-modular propagation of analysis information, our algorithm also outperforms traditional modular analysis even when analyzing from scratch.
A Framework for Searching in Graphs in the Presence of Errors
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of searching for an unknown target vertex $t$ in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex $v$ and the response either admits $v$ is the target or provides any neighbor $s\not=v$ that lies on a shortest path from $v$ to $t$. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability $p<1/2$ and a correct one with probability $1-p$). We study this problem in both adversarial errors and independent noise models. First, we show an algorithm that needs $\frac{\log_2 n}{1 - H(r)}$ queries against \emph{adversarial} errors, where adversary is bounded with its rate of errors by a known constant $r<1/2$. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking amortization argument. We then show that our algorithm coupled with Chernoff bound argument leads to an algorithm for independent noise that is simpler and with a query complexity that is both simpler and asymptotically better to one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies Robust Interactive Learning framework proposed by Emamjomeh-Zadeh et al. [NIPS 2017]. Secondly, performing analogous analysis for \emph{edge-queries} (where query to edge $e$ returns its endpoint that is closer to target) we actually recover (as a special case) noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon existing algorithm for searching of \emph{unbounded} domains due to Aslam and Dhagat [STOC 1991].
Learning a Text-Video Embedding from Incomplete and Heterogeneous Data
Venue: arXiv cs.CV 2020
Year: 2020

Joint understanding of video and language is an active research area with many applications. Prior work in this domain typically relies on learning text-video embeddings. One difficulty with this approach, however, is the lack of large-scale annotated video-caption datasets for training. To address this issue, we aim at learning text-video embeddings from heterogeneous data sources. To this end, we propose a Mixture-of-Embedding-Experts (MEE) model with ability to handle missing input modalities during training. As a result, our framework can learn improved text-video embeddings simultaneously from image and video datasets. We also show the generalization of MEE to other input modalities such as face descriptors. We evaluate our method on the task of video retrieval and report results for the MPII Movie Description and MSR-VTT datasets. The proposed MEE model demonstrates significant improvements and outperforms previously reported methods on both text-to-video and video-to-text retrieval tasks. Code is available at: https://github.com/antoine77340/Mixture-of-Embedding-Experts
Abelian networks IV. Dynamics of nonhalting networks
Venue: arXiv cs.FL 2020
Year: 2020

An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend the theory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order. We give an intrinsic definition of the \emph{torsion group} of a finite irreducible (halting or nonhalting) abelian network, and show that it coincides with the critical group of Bond and Levine (2016) if the network is halting. We show that the torsion group acts freely on the set of invertible recurrent components of the trajectory digraph, and identify when this action is transitive. This perspective leads to new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any number of chips. We give formulas for generating series such as \[ \sum_{n \geq 1} r_n z^n = \det (\frac{1}{1-z}D - A ) \] where $r_n$ is the number of recurrent chip-and-rotor configurations with $n$ chips; $D$ is the diagonal matrix of outdegrees, and $A$ is the adjacency matrix. A consequence is that the sequence $(r_n)_{n \geq 1}$ completely determines the spectrum of the simple random walk on the network.
Learning Deep Gradient Descent Optimization for Image Deconvolution
Venue: arXiv cs.CV 2020
Year: 2020

As an integral component of blind image deblurring, non-blind deconvolution removes image blur with a given blur kernel, which is essential but difficult due to the ill-posed nature of the inverse problem. The predominant approach is based on optimization subject to regularization functions that are either manually designed, or learned from examples. Existing learning based methods have shown superior restoration quality but are not practical enough due to their restricted and static model design. They solely focus on learning a prior and require to know the noise level for deconvolution. We address the gap between the optimization-based and learning-based approaches by learning a universal gradient descent optimizer. We propose a Recurrent Gradient Descent Network (RGDN) by systematically incorporating deep neural networks into a fully parameterized gradient descent scheme. A hyper-parameter-free update unit shared across steps is used to generate updates from the current estimates, based on a convolutional neural network. By training on diverse examples, the Recurrent Gradient Descent Network learns an implicit image prior and a universal update rule through recursive supervision. The learned optimizer can be repeatedly used to improve the quality of diverse degenerated observations. The proposed method possesses strong interpretability and high generalization. Extensive experiments on synthetic benchmarks and challenging real-world images demonstrate that the proposed deep optimization method is effective and robust to produce favorable results as well as practical for real-world image deblurring applications.
A clustering-based reinforcement learning approach for tailored personalization of e-Health interventions
Venue: arXiv cs.AI 2020
Year: 2020

Personalization is very powerful in improving the effectiveness of health interventions. Reinforcement learning (RL) algorithms are suitable for learning these tailored interventions from sequential data collected about individuals. However, learning can be very fragile. The time to learn intervention policies is limited as disengagement from the user can occur quickly. Also, in e-Health intervention timing can be crucial before the optimal window passes. We present an approach that learns tailored personalization policies for groups of users by combining RL and clustering. The benefits are two-fold: speeding up the learning to prevent disengagement while maintaining a high level of personalization. Our clustering approach utilizes dynamic time warping to compare user trajectories consisting of states and rewards. We apply online and batch RL to learn policies over clusters of individuals and introduce our self-developed and publicly available simulator for e-Health interventions to evaluate our approach. We compare our methods with an e-Health intervention benchmark. We demonstrate that batch learning outperforms online learning for our setting. Furthermore, our proposed clustering approach for RL finds near-optimal clusterings which lead to significantly better policies in terms of cumulative reward compared to learning a policy per individual or learning one non-personalized policy across all individuals. Our findings also indicate that the learned policies accurately learn to send interventions at the right moments and that the users workout more and at the right times of the day.
Design of Polar Codes in 5G New Radio
Venue: arXiv cs.IT 2020
Year: 2020

Polar codes have attracted the attention of academia and industry alike in the past decade, such that the 5$^\text{th}$ generation wireless systems (5G) standardization process of the 3$^\text{th}$ generation partnership project (3GPP) chose polar codes as a channel coding scheme. In this tutorial, we provide a description of the encoding process of polar codes adopted by the 5G standard. We illustrate the struggles of designing a family of polar codes able to satisfy the demands of 5G systems, with particular attention to rate flexibility and low decoding latency. The result of these efforts is an elaborate framework that applies novel coding techniques to provide a solid channel code for NR requirements.
A Feedback Information-Theoretic Transmission Scheme (FITTS) for Modeling Trajectory Variability in Aimed Movements
Venue: arXiv cs.HC 2020
Year: 2020

Trajectories in human aimed movements are inherently variable. Using the concept of positional variance profiles, such trajectories are shown to be decomposable into two phases: In a first phase, the variance of the limb position over many trajectories increases rapidly; in a second phase, it then decreases steadily. A new theoretical model, where the aiming task is seen as a Shannon-like communication problem, is developed to describe the second phase: Information is transmitted from a source (determined by the position at the end of the first phase), to a destination (the movement's end-point) over a channel perturbed by Gaussian noise, with the presence of a noiseless feedback link. Information-theoretic considerations show that the positional variance decreases exponentially with a rate equal to the channel capacity C. Two existing datasets for simple pointing tasks are re-analyzed and observations on real data confirm our model. The first phase has constant duration and C is found constant across instructions and task parameters, which thus characterizes the participant's performance. Our model provides a clear understanding of the speed-accuracy tradeoff in aimed movements: Since the participant's capacity is fixed, a higher prescribed accuracy necessarily requires a longer second phase resulting in an increased overall movement time. The well-known Fitts' law is also recovered using this approach.
On Gradient-Based Learning in Continuous Games
Venue: arXiv cs.LG 2020
Year: 2020

We formulate a general framework for competitive gradient-based learning that encompasses a wide breadth of multi-agent learning algorithms, and analyze the limiting behavior of competitive gradient-based learning algorithms using dynamical systems theory. For both general-sum and potential games, we characterize a non-negligible subset of the local Nash equilibria that will be avoided if each agent employs a gradient-based learning algorithm. We also shed light on the issue of convergence to non-Nash strategies in general- and zero-sum games, which may have no relevance to the underlying game, and arise solely due to the choice of algorithm. The existence and frequency of such strategies may explain some of the difficulties encountered when using gradient descent in zero-sum games as, e.g., in the training of generative adversarial networks. To reinforce the theoretical contributions, we provide empirical results that highlight the frequency of linear quadratic dynamic games (a benchmark for multi-agent reinforcement learning) that admit global Nash equilibria that are almost surely avoided by policy gradient.
Optimal Scheduling of Multiple Sensors over Lossy and Bandwidth Limited Channels
Venue: arXiv cs.SY 2020
Year: 2020

This work considers the sensor scheduling for multiple dynamic processes. We consider $n$ linear dynamic processes, the state of each process is measured by a sensor, which transmits their local state estimates over wireless channels to a remote estimator with certain communication costs. In each time step, only a portion of the sensors is allowed to transmit data to the remote estimator and the packet might be lost due to unreliability of the wireless channels. Our goal is to find a scheduling policy which coordinates the sensors in a centralized manner to minimize the total expected estimation error of the remote estimator and the communication costs. We formulate the problem as a Markov decision process. We develop an algorithm to check whether there exists a deterministic stationary optimal policy. We show the optimality of monotone policies, which saves computational effort of finding an optimal policy and facilitates practical implementation. Nevertheless, obtaining an exact optimal policy still suffers from curse of dimensionality when the number of processes are large. We further provide an index-based heuristics to avoid brute force computation. Numerical examples are presented to illustrate our theoretical results.
Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks
Venue: arXiv cs.SI 2020
Year: 2020

Consider the following process on a network: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two have the same opinion, the agent adopts it. This process is known as the 2-Choices dynamics and is arguably the most basic non-trivial opinion dynamics modeling voting behavior on social networks. Despite its apparent simplicity, 2-Choices has been analytically characterized only on restricted network classes---under assumptions on the initial configuration that establish it as a fast majority consensus protocol. In this work, we aim at contributing to the understanding of the 2-Choices dynamics by considering its behavior on a class of networks with core-periphery structure, a well-known topological assumption in social networks. In a nutshell, assume that a densely-connected subset of agents, the core, holds a different opinion from the rest of the network, the periphery. Then, depending on the strength of the cut between the core and the periphery, a phase-transition phenomenon occurs: Either the core's opinion rapidly spreads among the rest of the network, or a metastability phase takes place, in which both opinions coexist in the network for superpolynomial time. The interest of our result is twofold. On the one hand, by looking at the 2-Choices dynamics as a simplistic model of competition among opinions in social networks, our theorem sheds light on the influence of the core on the rest of the network, as a function of the core's connectivity toward the latter. On the other hand, we provide one of the first analytical results which shows a heterogeneous behavior of a simple dynamics as a function of structural parameters of the network. Finally, we validate our theoretical predictions with extensive experiments on real networks.
An Executable Operational Semantics for Rust with the Formalization of Ownership and Borrowing
Venue: arXiv cs.PL 2020
Year: 2020

Rust is an emergent systems programming language highlighting memory safety by its Ownership and Borrowing System (OBS). The existing formal semantics for Rust only covers limited subsets of the major language features of Rust. Moreover, they formalize OBS as type systems at the language-level, which can only be used to conservatively analyze programs against the OBS invariants at compile-time. That is, they are not executable, and thus cannot be used for automated verification of runtime behavior. In this paper, we propose RustSEM, a new executable operational semantics for Rust. RustSEM covers a much larger subset of the major language features than existing semantics. Moreover, RustSEM provides an operational semantics for OBS at the memory-level, which can be used to verify the runtime behavior of Rust programs against the OBS invariants. We have implemented RustSEM in the executable semantics modeling tool K-Framework. We have evaluated the semantics correctness of RustSEM wrt. the Rust compiler using around 700 tests. In particular, we have proposed a new technique for testing semantic consistency to ensure the absence of semantic ambiguities on all possible execution selections. We have also evaluated the potential applications of RustSEM in automated runtime and formal verification for both functional and memory properties. Experimental results show that RustSEM can enhance the memory safety mechanism of Rust, as it is more powerful than OBS in detecting memory errors.
Mobile Edge Computing-Enabled Heterogeneous Networks
Venue: arXiv cs.IT 2020
Year: 2020

The mobile edge computing (MEC) has been introduced for providing computing capabilities at the edge of networks to improve the latency performance of wireless networks. In this paper, we provide the novel framework for MEC-enabled heterogeneous networks (HetNets), composed of the multi-tier networks with access points (APs) (i.e., MEC servers), which have different transmission power and different computing capabilities. In this framework, we also consider multiple-type mobile users with different sizes of computation tasks, and they offload the tasks to a MEC server, and receive the computation resulting data from the server. We derive the successful edge computing probability (SECP), defined as the probability that a user offloads and finishes its computation task at the MEC server within the target latency. We provide a closed-form expression of the approximated SECP for general case, and closed-form expressions of the exact SECP for special cases. This paper then provides the design insights for the optimal configuration of MEC-enabled HetNets by analyzing the effects of network parameters and bias factors, used in MEC server association, on the SECP. Specifically, it shows how the optimal bias factors in terms of SECP can be changed according to the numbers of user types and tiers of MEC servers, and how they are different to the conventional ones that did not consider the computing capabilities and task sizes.
Using Aspect Extraction Approaches to Generate Review Summaries and User Profiles
Venue: arXiv cs.CL 2020
Year: 2020

Reviews of products or services on Internet marketplace websites contain a rich amount of information. Users often wish to survey reviews or review snippets from the perspective of a certain aspect, which has resulted in a large body of work on aspect identification and extraction from such corpora. In this work, we evaluate a newly-proposed neural model for aspect extraction on two practical tasks. The first is to extract canonical sentences of various aspects from reviews, and is judged by human evaluators against alternatives. A $k$-means baseline does remarkably well in this setting. The second experiment focuses on the suitability of the recovered aspect distributions to represent users by the reviews they have written. Through a set of review reranking experiments, we find that aspect-based profiles can largely capture notions of user preferences, by showing that divergent users generate markedly different review rankings.
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms
Venue: arXiv cs.CG 2020
Year: 2020

We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, $S$, of $n$ point sites in the plane determines a stable matching between the points in $\mathbb{R}^2$ and the sites in $S$ such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota or "appetite" indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the well-known post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work on the stable-matching Voronoi diagram provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. In this paper, we show that a stable-matching Voronoi diagram of $n$ point sites has $O(n^{2+\varepsilon})$ faces and edges, for any $\varepsilon>0$, and show that this bound is almost tight by giving a family of diagrams with $Θ(n^2)$ faces and edges. We also provide a discrete algorithm for constructing it in $O(n^3\log n+n^2f(n))$ time in the real-RAM model of computation, where $f(n)$ is the runtime of a geometric primitive (which we define) that can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation. We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions.