OpenRaiser/Intern-Atlas huggingface dataset:
Assuring the Machine Learning Lifecycle: Desiderata, Methods, and Challenges
Venue: arXiv cs.LG 2019
Year: 2019

Machine learning has evolved into an enabling technology for a wide range of highly successful applications. The potential for this success to continue and accelerate has placed machine learning (ML) at the top of research, economic and political agendas. Such unprecedented interest is fuelled by a vision of ML applicability extending to healthcare, transportation, defence and other domains of great societal importance. Achieving this vision requires the use of ML in safety-critical applications that demand levels of assurance beyond those needed for current ML applications. Our paper provides a comprehensive survey of the state-of-the-art in the assurance of ML, i.e. in the generation of evidence that ML is sufficiently safe for its intended use. The survey covers the methods capable of providing such evidence at different stages of the machine learning lifecycle, i.e. of the complex, iterative process that starts with the collection of the data used to train an ML component for a system, and ends with the deployment of that component within the system. The paper begins with a systematic presentation of the ML lifecycle and its stages. We then define assurance desiderata for each stage, review existing methods that contribute to achieving these desiderata, and identify open challenges that require further research.
Graphs with the second and third maximum Wiener index over the 2-vertex connected graphs
Venue: arXiv cs.DM 2019
Year: 2019

Wiener index, defined as the sum of distances between all unordered pairs of vertices, is one of the most popular molecular descriptors. It is well known that among 2-vertex connected graphs on $n\ge 3$ vertices, the cycle $C_n$ attains the maximum value of Wiener index. We show that the second maximum graph is obtained from $C_n$ by introducing a new edge that connects two vertices at distance two on the cycle if $n\ne 6$. If $n\ge 11$, the third maximum graph is obtained from a $4$-cycle by connecting opposite vertices by a path of length $n-3$. We completely describe also the situation for $n\le 10$.
Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management
Venue: arXiv cs.LG 2019
Year: 2019

We consider a stochastic inventory control problem under censored demands, lost sales, and positive lead times. This is a fundamental problem in inventory management, with significant literature establishing near-optimality of a simple class of policies called ``base-stock policies'' for the underlying Markov Decision Process (MDP), as well as convexity of long run average-cost under those policies. We consider the relatively less studied problem of designing a learning algorithm for this problem when the underlying demand distribution is unknown. The goal is to bound regret of the algorithm when compared to the best base-stock policy. We utilize the convexity properties and a newly derived bound on bias of base-stock policies to establish a connection to stochastic convex bandit optimization. Our main contribution is a learning algorithm with a regret bound of $\tilde{O}(L\sqrt{T}+D)$ for the inventory control problem. Here $L$ is the fixed and known lead time, and $D$ is an unknown parameter of the demand distribution described roughly as the number of time steps needed to generate enough demand for depleting one unit of inventory. Notably, even though the state space of the underlying MDP is continuous and $L$-dimensional, our regret bounds depend linearly on $L$. Our results significantly improve the previously best known regret bounds for this problem where the dependence on $L$ was exponential and many further assumptions on demand distribution were required. The techniques presented here may be of independent interest for other settings that involve large structured MDPs but with convex cost functions.
Multiclass Language Identification using Deep Learning on Spectral Images of Audio Signals
Venue: arXiv cs.SD 2019
Year: 2019

The first step in any voice recognition software is to determine what language a speaker is using, and ideally this process would be automated. The technique described in this paper, language identification for audio spectrograms (LIFAS), uses spectrograms generated from audio signals as inputs to a convolutional neural network (CNN) to be used for language identification. LIFAS requires minimal pre-processing on the audio signals as the spectrograms are generated during each batch as they are input to the network during training. LIFAS utilizes deep learning tools that are shown to be successful on image processing tasks and applies it to audio signal classification. LIFAS performs binary language classification with an accuracy of 97\%, and multi-class classification with six languages at an accuracy of 89\% on 3.75 second audio clips.
Solving Irregular and Data-enriched Differential Equations using Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Recent work has introduced a simple numerical method for solving partial differential equations (PDEs) with deep neural networks (DNNs). This paper reviews and extends the method while applying it to analyze one of the most fundamental features in numerical PDEs and nonlinear analysis: irregular solutions. First, the Sod shock tube solution to compressible Euler equations is discussed, analyzed, and then compared to conventional finite element and finite volume methods. These methods are extended to consider performance improvements and simultaneous parameter space exploration. Next, a shock solution to compressible magnetohydrodynamics (MHD) is solved for, and used in a scenario where experimental data is utilized to enhance a PDE system that is \emph{a priori} insufficient to validate against the observed/experimental data. This is accomplished by enriching the model PDE system with source terms and using supervised training on synthetic experimental data. The resulting DNN framework for PDEs seems to demonstrate almost fantastical ease of system prototyping, natural integration of large data sets (be they synthetic or experimental), all while simultaneously enabling single-pass exploration of the entire parameter space.
User Association in Dense mmWave Networks based on Rate Requirements
Venue: arXiv cs.IT 2019
Year: 2019

Commonly considered user association frameworks in millimeter-wave communications are based on the sum rate maximization, and they essentially neglect user specific rate and service requirements. Furthermore, new features of millimeter-wave communications including spatial multiplexing, connectivity to multiple coordinated base stations and dense base station deployment are not considered. In this work, we propose a two-step optimization framework for single-shot user association in dense millimeter-wave networks which takes into account users' rate requirements, multi-connectivity, and hybrid transceiver architecture for spatial multiplexing. The proposed framework considers multiple RF chains at each base station and assigns them to different users that also have multiple RF chains for connectivity with more than one base station. In the first step, the objective of the user association is to maximize the number of users with satisfied rate requirements while minimizing network underutilization. In the second step, remaining RF chains are assigned to users, whose rate requirement has not been met, such that network sum rate is maximized. This is a novel problem formulation for user associate in millimeter-wave networks. We propose low complexity sub-optimal user association algorithms based on this formulation, numerically evaluate the optimal and sub-optimal solutions, and compare them to the conventional association approaches in terms of the number of associated users and network sum rate.
Optimizing Routerless Network-on-Chip Designs: An Innovative Learning-Based Framework
Venue: arXiv cs.AR 2019
Year: 2019

Machine learning applied to architecture design presents a promising opportunity with broad applications. Recent deep reinforcement learning (DRL) techniques, in particular, enable efficient exploration in vast design spaces where conventional design strategies may be inadequate. This paper proposes a novel deep reinforcement framework, taking routerless networks-on-chip (NoC) as an evaluation case study. The new framework successfully resolves problems with prior design approaches being either unreliable due to random searches or inflexible due to severe design space restrictions. The framework learns (near-)optimal loop placement for routerless NoCs with various design constraints. A deep neural network is developed using parallel threads that efficiently explore the immense routerless NoC design space with a Monte Carlo search tree. Experimental results show that, compared with conventional mesh, the proposed deep reinforcement learning (DRL) routerless design achieves a 3.25x increase in throughput, 1.6x reduction in packet latency, and 5x reduction in power. Compared with the state-of-the-art routerless NoC, DRL achieves a 1.47x increase in throughput, 1.18x reduction in packet latency, and 1.14x reduction in average hop count albeit with slightly more power overhead.
Machine Learning Approach for Device-Circuit Co-Optimization of Stochastic-Memristive-Device-Based Boltzmann Machine
Venue: arXiv cs.ET 2019
Year: 2019

A Boltzmann machine whose effective "temperature" can be dynamically "cooled" provides a stochastic neural network realization of simulated annealing, which is an important metaheuristic for solving combinatorial or global optimization problems with broad applications in machine intelligence and operations research. However, the hardware realization of the Boltzmann stochastic element with "cooling" capability has never been achieved within an individual semiconductor device. Here we demonstrate a new memristive device concept based on two-dimensional material heterostructures that enables this critical stochastic element in a Boltzmann machine. The dynamic cooling effect in simulated annealing can be emulated in this multi-terminal memristive device through electrostatic bias with sigmoidal thresholding distributions. We also show that a machine-learning-based method is efficient for device-circuit co-design of the Boltzmann machine based on the stochastic memristor devices in simulated annealing. The experimental demonstrations of the tunable stochastic memristors combined with the machine-learning-based device-circuit co-optimization approach for stochastic-memristor-based neural-network circuits chart a pathway for the efficient hardware realization of stochastic neural networks with applications in a broad range of electronics and computing disciplines.
Self-Supervised Visual Place Recognition Learning in Mobile Robots
Venue: arXiv cs.CV 2019
Year: 2019

Place recognition is a critical component in robot navigation that enables it to re-establish previously visited locations, and simultaneously use this information to correct the drift incurred in its dead-reckoned estimate. In this work, we develop a self-supervised approach to place recognition in robots. The task of visual loop-closure identification is cast as a metric learning problem, where the labels for positive and negative examples of loop-closures can be bootstrapped using a GPS-aided navigation solution that the robot already uses. By leveraging the synchronization between sensors, we show that we are able to learn an appropriate distance metric for arbitrary real-valued image descriptors (including state-of-the-art CNN models), that is specifically geared for visual place recognition in mobile robots. Furthermore, we show that the newly learned embedding can be particularly powerful in disambiguating visual scenes for the task of vision-based loop-closure identification in mobile robots.
Mining Hidden Populations through Attributed Search
Venue: arXiv cs.SI 2019
Year: 2019

Researchers often query online social platforms through their application programming interfaces (API) to find target populations such as people with mental illness~\cite{De-Choudhury2017} and jazz musicians~\cite{heckathorn2001finding}. Entities of such target population satisfy a property that is typically identified using an oracle (human or a pre-trained classifier). When the property of the target entities is not directly queryable via the API, we refer to the property as `hidden' and the population as a hidden population. Finding individuals who belong to these populations on social networks is hard because they are non-queryable, and the sampler has to explore from a combinatorial query space within a finite budget limit. By exploiting the correlation between queryable attributes and the population of interest and by hierarchically ordering the query space, we propose a Decision tree-based Thompson sampler (\texttt{DT-TMP}) that efficiently discovers the right combination of attributes to query. Our proposed sampler outperforms the state-of-the-art samplers in online experiments, for example by 54\% on Twitter. When the number of matching entities to a query is known in offline experiments, \texttt{DT-TMP} performs exceedingly well by a factor of 0.9-1.5$\times$ over the baseline samplers. In the future, we wish to explore the option of finding hidden populations by formulating more complex queries.
Accuracy Improvement of Neural Network Training using Particle Swarm Optimization and its Stability Analysis for Classification
Venue: arXiv cs.LG 2019
Year: 2019

Supervised classification is the most active and emerging research trends in today's scenario. In this view, Artificial Neural Network (ANN) techniques have been widely employed and growing interest to the researchers day by day. ANN training aims to find the proper setting of parameters such as weights ($\textbf{W}$) and biases ($b$) to properly classify the given data samples. The training process is formulated in an error minimization problem which consists of many local optima in the search landscape. In this paper, an enhanced Particle Swarm Optimization is proposed to minimize the error function for classifying real-life data sets. A stability analysis is performed to establish the efficiency of the proposed method for improving classification accuracy. The performance measurement such as confusion matrix, $F$-measure and convergence graph indicates the significant improvement in the classification accuracy.
PrivateJobMatch: A Privacy-Oriented Deferred Multi-Match Recommender System for Stable Employment
Venue: arXiv cs.DS 2019
Year: 2019

Coordination failure reduces match quality among employers and candidates in the job market, resulting in a large number of unfilled positions and/or unstable, short-term employment. Centralized job search engines provide a platform that connects directly employers with job-seekers. However, they require users to disclose a significant amount of personal data, i.e., build a user profile, in order to provide meaningful recommendations. In this paper, we present PrivateJobMatch -- a privacy-oriented deferred multi-match recommender system -- which generates stable pairings while requiring users to provide only a partial ranking of their preferences. PrivateJobMatch explores a series of adaptations of the game-theoretic Gale-Shapley deferred-acceptance algorithm which combine the flexibility of decentralized markets with the intelligence of centralized matching. We identify the shortcomings of the original algorithm when applied to a job market and propose novel solutions that rely on machine learning techniques. Experimental results on real and synthetic data confirm the benefits of the proposed algorithms across several quality measures. Over the past year, we have implemented a PrivateJobMatch prototype and deployed it in an active job market economy. Using the gathered real-user preference data, we find that the match-recommendations are superior to a typical decentralized job market---while requiring only a partial ranking of the user preferences.
Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we will present a new PoW consensus algorithm used in Seele's main-net, MPoW (Matrix-Proof-of-Work). Compared to Bitcoin's PoW consensus algorithm, MPoW requires miners to compute the determinants of submatrices from a matrix constructed with n hashes other than brute-force-hashing using a hash function to find the target. This paper will evaluate this algorithm's compatibility with difficulty adjustment. Then we will discuss its efficiency in countering machines with hashrate advantage, and its feasibility to personal computers. We believe more innovative consensus protocols can be developed based on this algorithm.
Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems
Venue: arXiv cs.DS 2019
Year: 2019

The 0-1 integer linear programming feasibility problem is an important NP-complete problem. This paper proposes a continuous-time dynamical system for solving that problem without getting trapped in non-solution local minima. First, the problem is transformed to an easier form in linear time. Then, we propose an "impulse algorithm" to escape from local traps and show its performance is better than randomization for escaping traps. Second, we present the time-to-solution distribution of the impulse algorithm and compare it with exhaustive search to see its advantages. Third, we show that the fractional size of the basin of attraction of the global minimum is significantly larger than $2^{-N}$, the corresponding discrete probability for exhaustive search. Finally, we conduct a case study to show that the location of the basin is independent of different dimensions. These findings reveal a better way to solve the 0-1 integer linear programming feasibility problem continuously and show that its cost could be less than discrete methods in average cases.
Kyrix: Interactive Visual Data Exploration at Scale
Venue: arXiv cs.HC 2019
Year: 2019

Scalable interactive visual data exploration is crucial in many domains due to increasingly large datasets generated at rapid rates. Details-on-demand provides a useful interaction paradigm for exploring large datasets, where users start at an overview, find regions of interest, zoom in to see detailed views, zoom out and then repeat. This paradigm is the primary user interaction mode of widely-used systems such as Google Maps, Aperture Tiles and ForeCache. These earlier systems, however, are highly customized with hardcoded visual representations and optimizations. A more general framework is needed to facilitate the development of visual data exploration systems at scale. In this paper, we present Kyrix, an end-to-end system for developing scalable details-on-demand data exploration applications. Kyrix provides developers with a declarative model for easy specification of general visualizations. Behind the scenes, Kyrix utilizes a suite of performance optimization techniques to achieve a response time within 500ms for various user interactions. We also report results from a performance study which shows that a novel dynamic fetching scheme adopted by Kyrix outperforms tile-based fetching used in earlier systems.
A Survey of Controller Placement Problem in Software Defined Networks
Venue: arXiv cs.NI 2019
Year: 2019

Software Defined Network (SDN) is an emerging network paradigm which provides a centralized view of the network by decoupling the network control plane from the data plane. This strategy of maintaining a global view of the network optimizes resource management. However, the implementation of SDN using a single physical controller lead to issues of scalability and robustness. A physically distributed but logically centralized SDN controller architecture promises to resolve both these issues. Distributed SDN along with its benefits brings along the problem of the number of controllers required and their placement in the network. This problem is referred to as the controller placement problem (CPP) and this paper is mainly concerned with the CPP solution techniques. The paper formally defines CPP, gives a comprehensive review of the various performance metrics and characteristics of the available CPP solutions. Finally, we point out the existing literature gap and discuss the future research direction in this domain.
List Decodable Learning via Sum of Squares
Venue: arXiv cs.DS 2019
Year: 2019

In the list-decodable learning setup, an overwhelming majority (say a $1-β$-fraction) of the input data consists of outliers and the goal of an algorithm is to output a small list $\mathcal{L}$ of hypotheses such that one of them agrees with inliers. We develop a framework for list-decodable learning via the Sum-of-Squares SDP hierarchy and demonstrate it on two basic statistical estimation problems {\it Linear regression:} Suppose we are given labelled examples $\{(X_i,y_i)\}_{i \in [N]}$ containing a subset $S$ of $βN$ {\it inliers} $\{X_i \}_{i \in S}$ that are drawn i.i.d. from standard Gaussian distribution $N(0,I)$ in $\mathbb{R}^d$, where the corresponding labels $y_i$ are well-approximated by a linear function $\ell$. We devise an algorithm that outputs a list $\mathcal{L}$ of linear functions such that there exists some $\hat{\ell} \in \mathcal{L}$ that is close to $\ell$. This yields the first algorithm for linear regression in a list-decodable setting. Our results hold for any distribution of examples whose concentration and anticoncentration can be certified by Sum-of-Squares proofs. {\it Mean Estimation:} Given data points $\{X_i\}_{i \in [N]}$ containing a subset $S$ of $βN$ {\it inliers} $\{X_i \}_{i \in S}$ that are drawn i.i.d. from a Gaussian distribution $N(μ,I)$ in $\mathbb{R}^d$, we devise an algorithm that generates a list $\mathcal{L}$ of means such that there exists $\hatμ \in \mathcal{L}$ close to $μ$. The recovery guarantees of the algorithm are analogous to the existing algorithms for the problem by Diakonikolas \etal and Kothari \etal. In an independent and concurrent work, Karmalkar \etal \cite{KlivansKS19} also obtain an algorithm for list-decodable linear regression using the Sum-of-Squares SDP hierarchy.
Sensor Defense In-Software (SDI):Practical Software Based Detection of Spoofing Attacks on Position Sensor
Venue: arXiv cs.CR 2019
Year: 2019

Position sensors, such as the gyroscope, the magnetometer and the accelerometer, are found in a staggering variety of devices, from smartphones and UAVs to autonomous robots. Several works have shown how adversaries can mount spoofing attacks to remotely corrupt or even completely control the outputs of these sensors. With more and more critical applications relying on sensor readings to make important decisions, defending sensors from these attacks is of prime importance. In this work we present practical software based defenses against attacks on two common types of position sensors, specifically the gyroscope and the magnetometer. We first characterize the sensitivity of these sensors to acoustic and magnetic adversaries. Next, we present two software-only defenses: a machine learning based single sensor defense, and a sensor fusion defense which makes use of the mathematical relationship between the two sensors. We performed a detailed theoretical analysis of our defenses, and implemented them on a variety of smartphones, as well as on a resource-constrained IoT sensor node. Our defenses do not require any hardware or OS-level modifications, making it possible to use them with existing hardware. Moreover, they provide a high detection accuracy, a short detection time and a reasonable power consumption.