OpenRaiser/Intern-Atlas huggingface dataset:
The Dynamic Geometry of Interaction Machine: A Token-Guided Graph Rewriter
Venue: arXiv cs.LO 2019
Year: 2019

In implementing evaluation strategies of the lambda-calculus, both correctness and efficiency of implementation are valid concerns. While the notion of correctness is determined by the evaluation strategy, regarding efficiency there is a larger design space that can be explored, in particular the trade-off between space versus time efficiency. Aiming at a unified framework that would enable the study of this trade-off, we introduce an abstract machine, inspired by Girard's Geometry of Interaction (GoI), a machine combining token passing and graph rewriting. We show soundness and completeness of our abstract machine, called the \emph{Dynamic GoI Machine} (DGoIM), with respect to three evaluations: call-by-need, left-to-right call-by-value, and right-to-left call-by-value. Analysing time cost of its execution classifies the machine as ``efficient'' in Accattoli's taxonomy of abstract machines.
Robust Repeated Auctions under Heterogeneous Buyer Behavior
Venue: arXiv cs.GT 2019
Year: 2019

We study revenue optimization in a repeated auction between a single seller and a single buyer. Traditionally, the design of repeated auctions requires strong modeling assumptions about the bidder behavior, such as it being myopic, infinite lookahead, or some specific form of learning behavior. Is it possible to design mechanisms which are simultaneously optimal against a multitude of possible buyer behaviors? We answer this question by designing a simple state-based mechanism that is simultaneously approximately optimal against a $k$-lookahead buyer for all $k$, a buyer who is a no-regret learner, and a buyer who is a policy-regret learner. Against each type of buyer our mechanism attains a constant fraction of the optimal revenue attainable against that type of buyer. We complement our positive results with almost tight impossibility results, showing that the revenue approximation tradeoffs achieved by our mechanism for different lookahead attitudes are near-optimal.
Convolutional Geometric Matrix Completion
Venue: arXiv cs.LG 2019
Year: 2019

Geometric matrix completion (GMC) has been proposed for recommendation by integrating the relationship (link) graphs among users/items into matrix completion (MC). Traditional GMC methods typically adopt graph regularization to impose smoothness priors for MC. Recently, geometric deep learning on graphs (GDLG) is proposed to solve the GMC problem, showing better performance than existing GMC methods including traditional graph regularization based methods. To the best of our knowledge, there exists only one GDLG method for GMC, which is called RMGCNN. RMGCNN combines graph convolutional network (GCN) and recurrent neural network (RNN) together for GMC. In the original work of RMGCNN, RMGCNN demonstrates better performance than pure GCN-based method. In this paper, we propose a new GMC method, called convolutional geometric matrix completion (CGMC), for recommendation with graphs among users/items. CGMC is a pure GCN-based method with a newly designed graph convolutional network. Experimental results on real datasets show that CGMC can outperform other state-of-the-art methods including RMGCNN in terms of both accuracy and speed.
Distributed Robust Output Regulation of Heterogeneous Uncertain Linear Agents by Adaptive Internal Model Principle
Venue: arXiv cs.SY 2019
Year: 2019

We study a multi-agent output regulation problem, where not all agents have access to the exosystem's dynamics. We propose a fully distributed controller that solves the problem for linear, heterogeneous, and uncertain agent dynamics as well as time-varying directed networks. The distributed controller consists of two parts: (1) an exosystem generator that locally estimates the exosystem dynamics, and (2) a dynamic compensator that, by locally approaching the internal model of the exosystem, achieves perfect output regulation. Moreover, we extend this distributed controller to solve an output synchronization problem where not all agents initially have the same internal model dynamics. Our approach leverages methods from internal model based controller synthesis and multi-agent consensus over time-varying directed networks; the derived result is a generalization of the (centralized) internal model principle to the distributed, networked setting.
A Many-Objective Evolutionary Algorithm With Two Interacting Processes: Cascade Clustering and Reference Point Incremental Learning
Venue: arXiv cs.NE 2019
Year: 2019

Researches have shown difficulties in obtaining proximity while maintaining diversity for many-objective optimization problems. Complexities of the true Pareto front pose challenges for the reference vector-based algorithms for their insufficient adaptability to the diverse characteristics with no priori. This paper proposes a many-objective optimization algorithm with two interacting processes: cascade clustering and reference point incremental learning (CLIA). In the population selection process based on cascade clustering (CC), using the reference vectors provided by the process based on incremental learning, the nondominated and the dominated individuals are clustered and sorted with different manners in a cascade style and are selected by round-robin for better proximity and diversity. In the reference vector adaptation process based on reference point incremental learning, using the feedbacks from the process based on CC, proper distribution of reference points is gradually obtained by incremental learning. Experimental studies on several benchmark problems show that CLIA is competitive compared with the state-of-the-art algorithms and has impressive efficiency and versatility using only the interactions between the two processes without incurring extra evaluations.
In-home and remote use of robotic body surrogates by people with profound motor deficits
Venue: arXiv cs.RO 2019
Year: 2019

By controlling robots comparable to the human body, people with profound motor deficits could potentially perform a variety of physical tasks for themselves, improving their quality of life. The extent to which this is achievable has been unclear due to the lack of suitable interfaces by which to control robotic body surrogates and a dearth of studies involving substantial numbers of people with profound motor deficits. We developed a novel, web-based augmented reality interface that enables people with profound motor deficits to remotely control a PR2 mobile manipulator from Willow Garage, which is a human-scale, wheeled robot with two arms. We then conducted two studies to investigate the use of robotic body surrogates. In the first study, 15 novice users with profound motor deficits from across the United States controlled a PR2 in Atlanta, GA to perform a modified Action Research Arm Test (ARAT) and a simulated self-care task. Participants achieved clinically meaningful improvements on the ARAT and 12 of 15 participants (80%) successfully completed the simulated self-care task. Participants agreed that the robotic system was easy to use, was useful, and would provide a meaningful improvement in their lives. In the second study, one expert user with profound motor deficits had free use of a PR2 in his home for seven days. He performed a variety of self-care and household tasks, and also used the robot in novel ways. Taking both studies together, our results suggest that people with profound motor deficits can improve their quality of life using robotic body surrogates, and that they can gain benefit with only low-level robot autonomy and without invasive interfaces. However, methods to reduce the rate of errors and increase operational speed merit further investigation.
Sub-Nyquist Radar: Principles and Prototypes
Venue: arXiv cs.IT 2019
Year: 2019

In the past few years, new approaches to radar signal processing have been introduced which allow the radar to perform signal detection and parameter estimation from much fewer measurements than that required by Nyquist sampling. These systems - referred to as sub-Nyquist radars - model the received signal as having finite rate of innovation and employ the Xampling framework to obtain low-rate samples of the signal. Sub-Nyquist radars exploit the fact that the target scene is sparse facilitating the use of compressed sensing (CS) methods in signal recovery. In this chapter, we review several pulse-Doppler radar systems based on these principles. Contrary to other CS-based designs, our formulations directly address the reduced-rate analog sampling in space and time, avoid a prohibitive dictionary size, and are robust to noise and clutter. We begin by introducing temporal sub-Nyquist processing for estimating the target locations using less bandwidth than conventional systems. This paves the way to cognitive radars which share their transmit spectrum with other communication services, thereby providing a robust solution for coexistence in spectrally crowded environments. Next, without impairing Doppler resolution, we reduce the dwell time by transmitting interleaved radar pulses in a scarce manner within a coherent processing interval or "slow time". Then, we consider multiple-input-multiple-output array radars and demonstrate spatial sub-Nyquist processing which allows the use of few antenna elements without degradation in angular resolution. Finally, we demonstrate application of sub-Nyquist and cognitive radars to imaging systems such as synthetic aperture radar. For each setting, we present a state-of-the-art hardware prototype designed to demonstrate the real-time feasibility of sub-Nyquist radars.
Testing the complexity of a valued CSP language
Venue: arXiv cs.CC 2019
Year: 2019

A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set $Γ$ of cost functions, called a language. Recent breakthrough results have established a complete complexity classification of such classes with respect to language $Γ$: if all cost functions in $Γ$ satisfy a certain algebraic condition then all $Γ$-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language $Γ$ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language $Γ$ can be tested in $O(\sqrt[3]{3}^{\,|D|}\cdot poly(size(Γ)))$ time, where $D$ is the domain of $Γ$ and $poly(\cdot)$ is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant $δ<1$ there is no $O(\sqrt[3]{3}^{\,δ|D|})$ algorithm, assuming that SETH holds.
Robust Multiple Kernel k-means Clustering using Min-Max Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Multiple kernel learning is a type of multiview learning that combines different data modalities by capturing view-specific patterns using kernels. Although supervised multiple kernel learning has been extensively studied, until recently, only a few unsupervised approaches have been proposed. In the meanwhile, adversarial learning has recently received much attention. Many works have been proposed to defend against adversarial examples. However, little is known about the effect of adversarial perturbation in the context of multiview learning, and even less in the unsupervised case. In this study, we show that adversarial features added to a view can make the existing approaches with the min-max formulation in multiple kernel clustering yield unfavorable clusters. To address this problem and inspired by recent works in adversarial learning, we propose a multiple kernel clustering method with the min-max framework that aims to be robust to such adversarial perturbation. We evaluate the robustness of our method on simulation data under different types of adversarial perturbations and show that it outperforms several compared existing methods. In the real data analysis, We demonstrate the utility of our method on a real-world problem.
Transfer Learning with Neural AutoML
Venue: arXiv cs.LG 2019
Year: 2019

We reduce the computational cost of Neural AutoML with transfer learning. AutoML relieves human effort by automating the design of ML algorithms. Neural AutoML has become popular for the design of deep learning architectures, however, this method has a high computation cost. To address this we propose Transfer Neural AutoML that uses knowledge from prior tasks to speed up network design. We extend RL-based architecture search methods to support parallel training on multiple tasks and then transfer the search strategy to new tasks. On language and image classification tasks, Transfer Neural AutoML reduces convergence time over single-task training by over an order of magnitude on many tasks.
Routing on the Visibility Graph
Venue: arXiv cs.CG 2019
Year: 2019

We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the \emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {\em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
A frequency-constrained geometric Pontryagin maximum principle on matrix Lie groups
Venue: arXiv cs.SY 2019
Year: 2019

In this article we present a geometric discrete-time Pontryagin maximum principle (PMP) on matrix Lie groups that incorporates frequency constraints on the controls in addition to pointwise constraints on the states and control actions directly at the stage of the problem formulation. This PMP gives first order necessary conditions for optimality, and leads to two-point boundary value problems that may be solved by shooting techniques to arrive at optimal trajectories. We validate our theoretical results with a numerical experiment on the attitude control of a spacecraft on the Lie group SO(3).
Multiple Instance Choquet Integral Classifier Fusion and Regression for Remote Sensing Applications
Venue: arXiv cs.CV 2019
Year: 2019

In classifier (or regression) fusion the aim is to combine the outputs of several algorithms to boost overall performance. Standard supervised fusion algorithms often require accurate and precise training labels. However, accurate labels may be difficult to obtain in many remote sensing applications. This paper proposes novel classification and regression fusion models that can be trained given ambiguosly and imprecisely labeled training data in which training labels are associated with sets of data points (i.e., "bags") instead of individual data points (i.e., "instances") following a multiple instance learning framework. Experiments were conducted based on the proposed algorithms on both synthetic data and applications such as target detection and crop yield prediction given remote sensing data. The proposed algorithms show effective classification and regression performance.
Detecting sequences of system states in temporal networks
Venue: arXiv cs.SI 2019
Year: 2019

Many time-evolving systems in nature, society and technology leave traces of the interactions within them. These interactions form temporal networks that reflect the states of the systems. In this work, we pursue a coarse-grained description of these systems by proposing a method to assign discrete states to the systems and inferring the sequence of such states from the data. Such states could, for example, correspond to a mental state (as inferred from neuroimaging data) or the operational state of an organization (as inferred by interpersonal communication). Our method combines a graph distance measure and hierarchical clustering. Using several empirical data sets of social temporal networks, we show that our method is capable of inferring the system's states such as distinct activities in a school and a weekday state as opposed to a weekend state. We expect the methods to be equally useful in other settings such as temporally varying protein interactions, ecological interspecific interactions, functional connectivity in the brain and adaptive social networks.
WISERNet: Wider Separate-then-reunion Network for Steganalysis of Color Images
Venue: arXiv cs.MM 2019
Year: 2019

Until recently, deep steganalyzers in spatial domain have been all designed for gray-scale images. In this paper, we propose WISERNet (the wider separate-then-reunion network) for steganalysis of color images. We provide theoretical rationale to claim that the summation in normal convolution is one sort of "linear collusion attack" which reserves strong correlated patterns while impairs uncorrelated noises. Therefore in the bottom convolutional layer which aims at suppressing correlated image contents, we adopt separate channel-wise convolution without summation instead. Conversely, in the upper convolutional layers we believe that the summation in normal convolution is beneficial. Therefore we adopt united normal convolution in those layers and make them remarkably wider to reinforce the effect of "linear collusion attack". As a result, our proposed wide-and-shallow, separate-then-reunion network structure is specifically suitable for color image steganalysis. We have conducted extensive experiments on color image datasets generated from BOSSBase raw images and another large-scale dataset which contains 100,000 raw images, with different demosaicking algorithms and down-sampling algorithms. The experimental results show that our proposed network outperforms other state-of-the-art color image steganalytic models either hand-crafted or learned using deep networks in the literature by a clear margin. Specifically, it is noted that the detection performance gain is achieved with less than half the complexity compared to the most advanced deep-learning steganalyzer as far as we know, which is scarce in the literature.
Comparing Task Simplifications to Learn Closed-Loop Object Picking Using Deep Reinforcement Learning
Venue: arXiv cs.RO 2019
Year: 2019

Enabling autonomous robots to interact in unstructured environments with dynamic objects requires manipulation capabilities that can deal with clutter, changes, and objects' variability. This paper presents a comparison of different reinforcement learning-based approaches for object picking with a robotic manipulator. We learn closed-loop policies mapping depth camera inputs to motion commands and compare different approaches to keep the problem tractable, including reward shaping, curriculum learning and using a policy pre-trained on a task with a reduced action set to warm-start the full problem. For efficient and more flexible data collection, we train in simulation and transfer the policies to a real robot. We show that using curriculum learning, policies learned with a sparse reward formulation can be trained at similar rates as with a shaped reward. These policies result in success rates comparable to the policy initialized on the simplified task. We could successfully transfer these policies to the real robot with only minor modifications of the depth image filtering. We found that using a heuristic to warm-start the training was useful to enforce desired behavior, while the policies trained from scratch using a curriculum learned better to cope with unseen scenarios where objects are removed.
Can Autism be Catered with Artificial Intelligence-Assisted Intervention Technology? A Literature Review
Venue: arXiv cs.HC 2019
Year: 2019

This article presents an extensive literature review of technology based intervention methodologies for individuals facing Autism Spectrum Disorder (ASD). Reviewed methodologies include: contemporary Computer Aided Systems (CAS), Computer Vision Assisted Technologies (CVAT) and Virtual Reality (VR) or Artificial Intelligence (AI)-Assisted interventions. The research over the past decade has provided enough demonstrations that individuals with ASD have a strong interest in technology based interventions, which are useful in both, clinical settings as well as at home and classrooms. Despite showing great promise, research in developing an advanced technology based intervention that is clinically quantitative for ASD is minimal. Moreover, the clinicians are generally not convinced about the potential of the technology based interventions due to non-empirical nature of published results. A major reason behind this lack of acceptability is that a vast majority of studies on distinct intervention methodologies do not follow any specific standard or research design. We conclude from our findings that there remains a gap between the research community of computer science, psychology and neuroscience to develop an AI assisted intervention technology for individuals suffering from ASD. Following the development of a standardized AI based intervention technology, a database needs to be developed, to devise effective AI algorithms.
Global Stabilization for Causally Consistent Partial Replication
Venue: arXiv cs.DC 2019
Year: 2019

Causally consistent distributed storage systems have received significant attention recently due to the potential for providing high throughput and causality guarantees. {\em Global stabilization} is a technique established for achieving causal consistency in distributed multi-version key-value store systems, adopted by the previous work such as GentleRain \cite{Du2014GentleRainCA} and Cure \cite{akkoorath2016cure}. Intuitively, this approach serializes all updates by their physical time and computes the ``Global Stable Time'' which is a time point $t$ such that versions with timestamp $\leq t$ can be returned to the client without violating causality. However, all previous designs with global stabilization assume {\em full replication}, where each data center stores a full copy of data, and each client is restricted to access servers within one data center. In this paper, we propose a theoretical framework to support {\em general partial replication} with causal consistency via global stabilization, where each server can store an arbitrary subset of the data, and each client is allowed to communicate with any subset of the servers and migrate among them without extra delays. We propose an algorithm that implements causal consistency for distributed multi-version key-value stores with general partially replication. We prove the optimality of the Global Stable Time computation in our algorithm regarding the remote update visibility latency, i.e. how fast update from a remote server is visible to the client, under general partial replication. We also provide trade-offs to further optimize the remote update visibility by introducing extra delays during client's migration. Simulation results on the performance of our algorithm compared to the previous work are also provided.