OpenRaiser/Intern-Atlas huggingface dataset:
Detecting Correlations with Little Memory and Communication
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of identifying correlations in multivariate data, under information constraints: Either on the amount of memory that can be used by the algorithm, or the amount of communication when the data is distributed across several machines. We prove a tight trade-off between the memory/communication complexity and the sample complexity, implying (for example) that to detect pairwise correlations with optimal sample complexity, the number of required memory/communication bits is at least quadratic in the dimension. Our results substantially improve those of Shamir [2014], which studied a similar question in a much more restricted setting. To the best of our knowledge, these are the first provable sample/memory/communication trade-offs for a practical estimation problem, using standard distributions, and in the natural regime where the memory/communication budget is larger than the size of a single data point. To derive our theorems, we prove a new information-theoretic result, which may be relevant for studying other information-constrained learning problems.
Improving QED-Tutrix by Automating the Generation of Proofs
Venue: arXiv cs.AI 2018
Year: 2018

The idea of assisting teachers with technological tools is not new. Mathematics in general, and geometry in particular, provide interesting challenges when developing educative softwares, both in the education and computer science aspects. QED-Tutrix is an intelligent tutor for geometry offering an interface to help high school students in the resolution of demonstration problems. It focuses on specific goals: 1) to allow the student to freely explore the problem and its figure, 2) to accept proofs elements in any order, 3) to handle a variety of proofs, which can be customized by the teacher, and 4) to be able to help the student at any step of the resolution of the problem, if the need arises. The software is also independent from the intervention of the teacher. QED-Tutrix offers an interesting approach to geometry education, but is currently crippled by the lengthiness of the process of implementing new problems, a task that must still be done manually. Therefore, one of the main focuses of the QED-Tutrix' research team is to ease the implementation of new problems, by automating the tedious step of finding all possible proofs for a given problem. This automation must follow fundamental constraints in order to create problems compatible with QED-Tutrix: 1) readability of the proofs, 2) accessibility at a high school level, and 3) possibility for the teacher to modify the parameters defining the "acceptability" of a proof. We present in this paper the result of our preliminary exploration of possible avenues for this task. Automated theorem proving in geometry is a widely studied subject, and various provers exist. However, our constraints are quite specific and some adaptation would be required to use an existing prover. We have therefore implemented a prototype of automated prover to suit our needs. The future goal is to compare performances and usability in our specific use-case between the existing provers and our implementation.
A new stereo formulation not using pixel and disparity models
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a new stereo formulation which does not use pixel and disparity models. Many problems in vision are treated as assigning each pixel a label. Disparities are labels for stereo. Such pixel-labeling problems are naturally represented in terms of energy minimization, where the energy function has two terms: one term penalizes solutions that inconsistent with the observed data, the other term enforces spatial smoothness. Graph cuts are one of the effi- cient methods for solving energy minimization. However, exact minimization of multi labeling problems can be performed by graph cuts only for the case with convex smoothness terms. In pixel-disparity formulation, convex smoothness terms do not generate well reconstructed 3D results. Thus, truncated linear or quadratic smoothness terms, etc. are used, where approximate energy minimization is necessary. In this paper, we introduce a new site-labeling formulation, where the sites are not pixels but lines in 3D space, labels are not disparities but depth numbers. For this formulation, visibility reasoning is naturally included in the energy function. In addition, this formulation allows us to use a small smoothness term, which does not affect the 3D results much. This makes the optimization step very simple, so we could develop an approximation method for graph cut itself (not for energy minimization) and a high performance GPU graph cut program. For Tsukuba stereo pair in Middlebury data set, we got the result in 5ms using GTX1080GPU, 19ms using GTX660GPU.
Network Phenotyping for Network Traffic Classification and Anomaly Detection
Venue: arXiv cs.NI 2018
Year: 2018

This paper proposes to develop a network phenotyping mechanism based on network resource usage analysis and identify abnormal network traffic. The network phenotyping may use different metrics in the cyber physical system (CPS), including resource and network usage monitoring, physical state estimation. The set of devices will collectively decide a holistic view of the entire system through advanced image processing and machine learning methods. In this paper, we choose the network traffic pattern as a study case to demonstrate the effectiveness of the proposed method, while the methodology may similarly apply to classification and anomaly detection based on other resource metrics. We apply image processing and machine learning on the network resource usage to extract and recognize communication patterns. The phenotype method is experimented on four real-world decentralized applications. With proper length of sampled continuous network resource usage, the overall recognition accuracy is about 99%. Additionally, the recognition error is used to detect the anomaly network traffic. We simulate the anomaly network resource usage that equals to 10%, 20% and 30% of the normal network resource usage. The experiment results show the proposed anomaly detection method is efficient in detecting each intensity of anomaly network resource usage.
Finger Grip Force Estimation from Video using Two Stream Approach
Venue: arXiv cs.RO 2018
Year: 2018

Estimation of a hand grip force is essential for the understanding of force pattern during the execution of assembly or disassembly operations. Human demonstration of a correct way of doing an operation is a powerful source of information which can be used for guided robot teaching. Typically to assess this problem instrumented approach is used, which requires hand or object mounted devices and poses an inconvenience for an operator or limits the scope of addressable objects. The work demonstrates that contact force may be estimated using a noninvasive contactless method with the help of vision system alone. We propose a two-stream approach for video processing, which utilizes both spatial information of each frame and dynamic information of frame change. In this work, image processing and machine learning techniques are used along with dense optical flow for frame change tracking and Kalman filter is used for stream fusion. Our studies show that the proposed method can successfully estimate contact grip force with RMSE < 10% of sensor range (RMSE $\approx 0.2$ N), the performances of each stream and overall method performance are reported. The proposed method has a wide range of applications, including robot teaching through demonstration, haptic force feedback, and validation of human- performed operations.
Excitable London: Street map analysis with Oregonator model
Venue: arXiv cs.ET 2018
Year: 2018

We explore geometry of London's streets using computational mode of an excitable chemical system, Belousov-Zhabotinsky (BZ) medium. We virtually fill in the streets with a BZ medium and study propagation of excitation waves for a range of excitability parameters, gradual transition from excitable to sub-excitable to non-excitable. We demonstrate a pruning strategy adopted by the medium with decreasing excitability when wider and ballistically appropriate streets are selected. We explain mechanics of streets selection and pruning. The results of the paper will be used in future studies of studying dynamics of cities with living excitable substrates.
On the Use of Computational Paths in Path Spaces of Homotopy Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

The treatment of equality as a type in type theory gives rise to an interesting type-theoretic structure known as `identity type'. The idea is that, given terms $a,b$ of a type $A$, one may form the type $Id_{A}(a,b)$, whose elements are proofs that $a$ and $b$ are equal elements of type $A$. A term of this type, $p : Id_{A}(a,b)$, makes up for the grounds (or proof) that establishes that $a$ is indeed equal to $b$. Based on that, a proof of equality can be seen as a sequence of substitutions and rewrites, also known as a `computational path'. One interesting fact is that it is possible to rewrite computational paths using a set of reduction rules arising from an analysis of redundancies in paths. These rules were mapped by De Oliveira in 1994 in a term rewrite system known as $LND_{EQ}-TRS$. Here we use computational paths and this term rewrite system to work with path spaces. In homotopy type theory, the main technique used to define path spaces is the code-encode-decode approach. Our objective is to propose an alternative approach based on the theory of computational paths. We believe this new approach is simpler and more straightforward than the code-encode-decode one. We then use our approach to obtain two important results of homotopy type theory: the construction of the path space of the naturals and the calculation of the fundamental group of the circle.
Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
Venue: arXiv cs.DM 2018
Year: 2018

The pancake problem is concerned with sorting a permutation (a stack of pancakes of different diameter) using only prefix reversals (spatula flips). Although the problem description belies simplicity, an exact formula for the maximum number of flips needed to sort $n$ pancakes has been elusive. In this paper we present a different approach to the pancake problem, as a word problem on the symmetric group and hyperoctahedral group. Pancake flips are considered as generators and we study the relations satisfied by them. We completely describe the order of the product of any two of these generators, and provide some partial results on the order of the product of any three generators. Connections to the pancake graph of the hyperoctahedral group are also drawn.
An Analysis of the t-SNE Algorithm for Data Visualization
Venue: arXiv cs.LG 2018
Year: 2018

A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually identifiable. Standard Johnson-Lindenstrauss dimensionality reduction does not produce data visualizations. The t-SNE heuristic of van der Maaten and Hinton, which is based on non-convex optimization, has become the de facto standard for visualization in a wide range of applications. This work gives a formal framework for the problem of data visualization - finding a 2-dimensional embedding of clusterable data that correctly separates individual clusters to make them visually identifiable. We then give a rigorous analysis of the performance of t-SNE under a natural, deterministic condition on the "ground-truth" clusters (similar to conditions assumed in earlier analyses of clustering) in the underlying data. These are the first provable guarantees on t-SNE for constructing good data visualizations. We show that our deterministic condition is satisfied by considerably general probabilistic generative models for clusterable data such as mixtures of well-separated log-concave distributions. Finally, we give theoretical evidence that t-SNE provably succeeds in partially recovering cluster structure even when the above deterministic condition is not met.
Dynamic Competition Networks: detecting alliances and leaders
Venue: arXiv cs.SI 2018
Year: 2018

We consider social networks of competing agents that evolve dynamically over time. Such dynamic competition networks are directed, where a directed edge from nodes $u$ to $v$ corresponds a negative social interaction. We present a novel hypothesis that serves as a predictive tool to uncover alliances and leaders within dynamic competition networks. Our focus is in the present study is to validate it on competitive networks arising from social game shows such as Survivor and Big Brother.
Towards Automatic & Personalised Mobile Health Interventions: An Interactive Machine Learning Perspective
Venue: arXiv cs.CY 2018
Year: 2018

Machine learning (ML) is the fastest growing field in computer science and healthcare, providing future benefits in improved medical diagnoses, disease analyses and prevention. In this paper, we introduce an application of interactive machine learning (iML) in a telemedicine system, to enable automatic and personalised interventions for lifestyle promotion. We first present the high level architecture of the system and the components forming the overall architecture. We then illustrate the interactive machine learning process design. Prediction models are expected to be trained through the participants' profiles, activity performance, and feedback from the caregiver. Finally, we show some preliminary results during the system implementation and discuss future directions. We envisage the proposed system to be digitally implemented, and behaviourally designed to promote healthy lifestyle and activities, and hence prevent users from the risk of chronic diseases.
Accumulate Then Transmit: Multi-user Scheduling in Full-Duplex Wireless-Powered IoT Systems
Venue: arXiv cs.IT 2018
Year: 2018

This paper develops and evaluates an accumulate-then-transmit framework for multi-user scheduling in a full-duplex (FD) wireless-powered Internet-of-Things system, consisting of multiple energy harvesting (EH) IoT devices (IoDs) and one FD hybrid access point (HAP). All IoDs have no embedded energy supply and thus need to perform EH before transmitting their data to the HAP. Thanks to its FD capability, the HAP can simultaneously receive data uplink and broadcast energy-bearing signals downlink to charge IoDs. The instantaneous channel information is assumed unavailable throughout this paper. To maximize the system average throughput, we design a new throughput-oriented scheduling scheme, in which a single IoD with the maximum weighted residual energy is selected to transmit information to the HAP, while the other IoDs harvest and accumulate energy from the signals broadcast by the HAP. However, similar to most of the existing throughput-oriented schemes, the proposed throughout-oriented scheme also leads to unfair inter-user throughput because IoDs with better channel performance will be granted more transmission opportunities. To strike a balance between the system throughput and user fairness, we then propose a fairness-oriented scheduling scheme based on the normalized accumulated energy. To evaluate the system performance, we model the dynamic charging/discharging processes of each IoD as a finite-state Markov Chain. Analytical expressions of the system outage probability and average throughput are derived over Rician fading channels for both proposed schemes. Simulation results validate the performance analysis and demonstrate the performance superiority of both proposed schemes over the existing schemes.
Online Deep Learning: Growing RBM on the fly
Venue: arXiv cs.NE 2018
Year: 2018

We propose a novel online learning algorithm for Restricted Boltzmann Machines (RBM), namely, the Online Generative Discriminative Restricted Boltzmann Machine (OGD-RBM), that provides the ability to build and adapt the network architecture of RBM according to the statistics of streaming data. The OGD-RBM is trained in two phases: (1) an online generative phase for unsupervised feature representation at the hidden layer and (2) a discriminative phase for classification. The online generative training begins with zero neurons in the hidden layer, adds and updates the neurons to adapt to statistics of streaming data in a single pass unsupervised manner, resulting in a feature representation best suited to the data. The discriminative phase is based on stochastic gradient descent and associates the represented features to the class labels. We demonstrate the OGD-RBM on a set of multi-category and binary classification problems for data sets having varying degrees of class-imbalance. We first apply the OGD-RBM algorithm on the multi-class MNIST dataset to characterize the network evolution. We demonstrate that the online generative phase converges to a stable, concise network architecture, wherein individual neurons are inherently discriminative to the class labels despite unsupervised training. We then benchmark OGD-RBM performance to other machine learning, neural network and ClassRBM techniques for credit scoring applications using 3 public non-stationary two-class credit datasets with varying degrees of class-imbalance. We report that OGD-RBM improves accuracy by 2.5-3% over batch learning techniques while requiring at least 24%-70% fewer neurons and fewer training samples. This online generative training approach can be extended greedily to multiple layers for training Deep Belief Networks in non-stationary data mining applications without the need for a priori fixed architectures.
Explain Yourself: A Natural Language Interface for Scrutable Autonomous Robots
Venue: arXiv cs.CL 2018
Year: 2018

Autonomous systems in remote locations have a high degree of autonomy and there is a need to explain what they are doing and why in order to increase transparency and maintain trust. Here, we describe a natural language chat interface that enables vehicle behaviour to be queried by the user. We obtain an interpretable model of autonomy through having an expert 'speak out-loud' and provide explanations during a mission. This approach is agnostic to the type of autonomy model and as expert and operator are from the same user-group, we predict that these explanations will align well with the operator's mental model, increase transparency and assist with operator training.
Optimal Grassmann Manifold Eavesdropping: A Huge Security Disaster for M-1-2 Wiretap Channels
Venue: arXiv cs.CR 2018
Year: 2018

We in this paper introduce an advanced eavesdropper that aims to paralyze the artificial-noise-aided secure communications. We consider the M-1-2 Gaussian MISO wiretap channel, which consists of a M-antenna transmitter, a single-antenna receiver, and a two-antenna eavesdropper. This type of eavesdropper, by adopting an optimal Grassmann manifold (OGM) filtering structure, can reduce the maximum achievable secrecy rate (MASR) to be zero by using only two receive antennas, regardless of the number of antennas at the transmitter. Specifically, the eavesdropper exploits linear filters to serially recover the legitimate information symbols and intends to find the optimal filter that minimizes the meansquare error (MSE) in estimating the symbols. During the process, a convex semidefinite programming (SDP) problem with constraints on the filter matrix can be formulated and solved. Interestingly, the resulted optimal filters constitute a complex Grassmann manifold on the matrix space. Based on the filters, a novel expression of MASR is derived and further verified to be zero under the noiseless environment. Besides this, an achievable variable region (AVR) that induces zero MASR is presented analytically in the noisy case. Numerical results are provided to illustrate the huge disaster in the respect of secrecy rate.
Smartphone-based Home Robotics
Venue: arXiv cs.RO 2018
Year: 2018

Humanoid robotics is a promising field because the strong human preference to interact with anthropomorphic interfaces. Despite this, humanoid robots are far from reaching main stream adoption and the features available in such robots seem to lag that of the latest smartphones. A fragmented robot ecosystem and low incentives to developers do not help to foster the creation of Robot-Apps either. In contrast, smartphones enjoy high adoption rates and a vibrant app ecosystem (4M apps published). Given this, it seems logical to apply the mobile SW and HW development model to humanoid robots. One way is to use a smartphone to power the robot. Smartphones have been embedded in toys and drones before. However, they have never been used as the main compute unit in a humanoid embodiment. Here, we introduce a novel robot architecture based on smartphones that demonstrates x3 cost reduction and that is compatible with iOS/Android.
Towards Mission-Critical Control at the Edge and Over 5G
Venue: arXiv cs.SY 2018
Year: 2018

With the emergence of industrial IoT and cloud computing, and the advent of 5G and edge clouds, there are ambitious expectations on elasticity, economies of scale, and fast time to market for demanding use cases in the next generation of ICT networks. Responsiveness and reliability of wireless communication links and services in the cloud are set to improve significantly as the concept of edge clouds is becoming more prevalent. To enable industrial uptake we must provide cloud capacity in the networks but also a sufficient level of simplicity and self-sustainability in the software platforms. In this paper, we present a research test-bed built to study mission-critical control over the distributed edge cloud. We evaluate system properties using a conventional control application in the form of a Model Predictive Controller. Our cloud platform provides the means to continuously operate our mission-critical application while seamlessly relocating computations across geographically dispersed compute nodes. Through our use of 5G wireless radio, we allow for mobility and reliably provide compute resources with low latency, at the edge. The primary contribution of this paper is a state-of-the art, fully operational test-bed showing the potential for merged IoT, 5G, and cloud. We also provide an evaluation of the system while operating a mission-critical application and provide an outlook on a novel research direction.
On Simple Back-Off in Unreliable Radio Networks
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with a preliminary investigation of the performance of these strategies when we include additional generality to the model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.