OpenRaiser/Intern-Atlas huggingface dataset:
Continuous Regular Functions
Venue: arXiv cs.LO 2020
Year: 2020

Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1] \to [0,1]$ is $r$-regular if there is a Büchi automaton that accepts precisely the set of base $r \in \mathbb{N}$ representations of elements of the graph of $f$. We show that a continuous $r$-regular function $f$ is locally affine away from a nowhere dense, Lebesgue null, subset of $[0,1]$. As a corollary we establish that every differentiable $r$-regular function is affine. It follows that checking whether an $r$-regular function is differentiable is in $\operatorname{PSPACE}$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.
Longest Common Subsequence on Weighted Sequences
Venue: arXiv cs.CC 2020
Year: 2020

We consider the general problem of the Longest Common Subsequence (LCS) on weighted sequences. Weighted sequences are an extension of classical strings, where in each position every letter of the alphabet may occur with some probability. Previous results presented a PTAS and noticed that no FPTAS is possible unless P=NP. In this paper we essentially close the gap between upper and lower bounds by improving both. First of all, we provide an EPTAS for bounded alphabets (which is the most natural case), and prove that there does not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under the Exponential Time Hypothesis, we provide a lower bound which shows that no significantly better PTAS can exist for unbounded alphabets. As a side note, we prove that it is sufficient to work with only one threshold in the general variant of the problem.
Vehicular Edge Computing via Deep Reinforcement Learning
Venue: arXiv cs.NI 2020
Year: 2020

The smart vehicles construct Vehicle of Internet which can execute various intelligent services. Although the computation capability of the vehicle is limited, multi-type of edge computing nodes provide heterogeneous resources for vehicular services.When offloading the complicated service to the vehicular edge computing node, the decision should consider numerous factors.The offloading decision work mostly formulate the decision to a resource scheduling problem with single or multiple objective function and some constraints, and explore customized heuristics algorithms. However, offloading multiple data dependency tasks in a service is a difficult decision, as an optimal solution must understand the resource requirement, the access network, the user mobility, and importantly the data dependency. Inspired by recent advances in machine learning, we propose a knowledge driven (KD) service offloading decision framework for Vehicle of Internet, which provides the optimal policy directly from the environment. We formulate the offloading decision of multi-task in a service as a long-term planning problem, and explores the recent deep reinforcement learning to obtain the optimal solution. It considers the future data dependency of the following tasks when making decision for a current task from the learned offloading knowledge. Moreover, the framework supports the pre-training at the powerful edge computing node and continually online learning when the vehicular service is executed, so that it can adapt the environment changes and learns policy that are sensible in hindsight. The simulation results show that KD service offloading decision converges quickly, adapts to different conditions, and outperforms the greedy offloading decision algorithm.
Tightening Mutual Information Based Bounds on Generalization Error
Venue: arXiv cs.LG 2020
Year: 2020

An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm. The bound is derived under more general conditions on the loss function than in existing studies; nevertheless, it provides a tighter characterization of the generalization error. Examples of learning algorithms are provided to demonstrate the the tightness of the bound, and to show that it has a broad range of applicability. Application to noisy and iterative algorithms, e.g., stochastic gradient Langevin dynamics (SGLD), is also studied, where the constructed bound provides a tighter characterization of the generalization error than existing results. Finally, it is demonstrated that, unlike existing bounds, which are difficult to compute and evaluate empirically, the proposed bound can be estimated easily in practice.
The Smart$^2$ Speaker Blocker: An Open-Source Privacy Filter for Connected Home Speakers
Venue: arXiv cs.CR 2020
Year: 2020

The popularity and projected growth of in-home smart speaker assistants, such as Amazon's Echo, has raised privacy concerns among consumers and privacy advocates. Notable questions regarding the collection and storage of user data by for-profit organizations include: what data is being collected and how is it being used, who has or can obtain access to such data, and how can user privacy be maintained while providing useful services. In addition to concerns regarding what the speaker manufacturer will do with your data, there are also more fundamental concerns about the security of these devices, third-party plugins, and the servers where they store recorded data. To address these privacy and security concerns, we introduce an intermediary device to provide an additional layer of security, which we call the \textit{smart, smart speaker blocker} or Smart\textsuperscript{2} for short. By intelligently filtering sensitive conversations, and completely blocking this information from reaching a smart speaker's microphone(s), the Smart$^2$ Speaker Blocker is an open-source, network-local (offline) smart device that provides users with decisive control over what data leaves their living room.
Classification of load forecasting studies by forecasting problem to select load forecasting techniques and methodologies
Venue: arXiv cs.IR 2020
Year: 2020

The key contribution of this paper is to propose a classification into two dimensions of the load forecasting studies to decide which forecasting tools to use in which case. This classification aims to provide a synthetic view of the relevant forecasting techniques and methodologies by forecasting problem. In addition, the key principles of the main techniques and methodologies used are summarized along with the reviews of these papers. The classification process relies on two couples of parameters that define a forecasting problem. Each article is classified with key information about the dataset used and the forecasting tools implemented: the forecasting techniques (probabilistic or deterministic) and methodologies, the data cleansing techniques, and the error metrics. The process to select the articles reviewed in this paper was conducted into two steps. First, a set of load forecasting studies was built based on relevant load forecasting reviews and forecasting competitions. The second step consisted in selecting the most relevant studies of this set based on the following criteria: the quality of the description of the forecasting techniques and methodologies implemented, the description of the results, and the contributions. This paper can be read in two passes. The first one by identifying the forecasting problem of interest to select the corresponding class into one of the four classification tables. Each one references all the articles classified across a forecasting horizon. They provide a synthetic view of the forecasting tools used by articles addressing similar forecasting problems. Then, a second level composed of four Tables summarizes key information about the forecasting tools and the results of these studies. The second pass consists in reading the key principles of the main techniques and methodologies of interest and the reviews of the articles.
Encoding Candlesticks as Images for Patterns Classification Using Convolutional Neural Networks
Venue: arXiv cs.CE 2020
Year: 2020

Candlestick charts display the high, low, opening, and closing prices in a specific period. Candlestick patterns emerge because human actions and reactions are patterned and continuously replicate. These patterns capture information on the candles. According to Thomas Bulkowski's Encyclopedia of Candlestick Charts, there are 103 candlestick patterns. Traders use these patterns to determine when to enter and exit. Candlestick pattern classification approaches take the hard work out of visually identifying these patterns. To highlight its capabilities, we propose a two-steps approach to recognize candlestick patterns automatically. The first step uses the Gramian Angular Field (GAF) to encode the time series as different types of images. The second step uses the Convolutional Neural Network (CNN) with the GAF images to learn eight critical kinds of candlestick patterns. In this paper, we call the approach GAF-CNN. In the experiments, our method can identify the eight types of candlestick patterns with 90.7% average accuracy automatically in real-world data, outperforming the LSTM model.
Learning Credal Sum-Product Networks
Venue: arXiv cs.LG 2020
Year: 2020

Probabilistic representations, such as Bayesian and Markov networks, are fundamental to much of statistical machine learning. Thus, learning probabilistic representations directly from data is a deep challenge, the main computational bottleneck being inference that is intractable. Tractable learning is a powerful new paradigm that attempts to learn distributions that support efficient probabilistic querying. By leveraging local structure, representations such as sum-product networks (SPNs) can capture high tree-width models with many hidden layers, essentially a deep architecture, while still admitting a range of probabilistic queries to be computable in time polynomial in the network size. While the progress is impressive, numerous data sources are incomplete, and in the presence of missing data, structure learning methods nonetheless revert to single distributions without characterizing the loss in confidence. In recent work, credal sum-product networks, an imprecise extension of sum-product networks, were proposed to capture this robustness angle. In this work, we are interested in how such representations can be learnt and thus study how the computational machinery underlying tractable learning and inference can be generalized for imprecise probabilities.
Decomposition of games: some strategic considerations
Venue: arXiv cs.GT 2020
Year: 2020

Candogan et al. (2011) provide an orthogonal direct-sum decomposition of finite games into potential, harmonic and nonstrategic components. In this paper we study the issue of decomposing games that are strategically equivalent from a game-theoretical point of view, for instance games obtained via transformations such as duplications of strategies or positive affine mappings of of payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompositions.
Learning-Based Synthesis of Safety Controllers
Venue: arXiv cs.GT 2020
Year: 2020

We propose a machine learning framework to synthesize reactive controllers for systems whose interactions with their adversarial environment are modeled by infinite-duration, two-player games over (potentially) infinite graphs. Our framework targets safety games with infinitely many vertices, but it is also applicable to safety games over finite graphs whose size is too prohibitive for conventional synthesis techniques. The learning takes place in a feedback loop between a teacher component, which can reason symbolically about the safety game, and a learning algorithm, which successively learns an overapproximation of the winning region from various kinds of examples provided by the teacher. We develop a novel decision tree learning algorithm for this setting and show that our algorithm is guaranteed to converge to a reactive safety controller if a suitable overapproximation of the winning region can be expressed as a decision tree. Finally, we empirically compare the performance of a prototype implementation to existing approaches, which are based on constraint solving and automata learning, respectively.
A Deterministic Gradient-Based Approach to Avoid Saddle Points
Venue: arXiv cs.LG 2020
Year: 2020

Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning models efficiently. First-order methods such as gradient descent are usually the methods of choice for training machine learning models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent [Osher et al., arXiv:1806.06317], called modified Laplacian smoothing gradient descent (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region's dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is floor((n-1)/2), and hence it is significantly smaller than that of the gradient descent whose dimension is n-1.
Using a min-cut generalisation to go beyond Boolean surjective VCSPs
Venue: arXiv cs.DS 2020
Year: 2020

In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is to select a vertex subset such that the weight of the induced cut plus the set function value are minimised. In addition, a lower and upper bound is imposed on the solution size. We present a polynomial-time algorithm for enumerating all near-optimal solutions of this Bounded Generalised Min-Cut problem. Second, we apply this novel algorithm to surjective general-valued constraint satisfaction problems (VCSPs), i.e., VCSPs in which each label has to be used at least once. On the Boolean domain, Fulla, Uppman, and Zivny [ACM ToCT'18] have recently established a complete classification of surjective VCSPs based on an unbounded version of the Generalised Min-Cut problem. Their result features the discovery of a new non-trivial tractable case called EDS that does not appear in the non-surjective setting. As our main result, we extend the class EDS to arbitrary finite domains and provide a conditional complexity classification for surjective VCSPs of this type based on a reduction to smaller domains. On three-element domains, this leads to a complete classification of such VCSPs.
Convergence of the Non-Uniform Physarum Dynamics
Venue: arXiv cs.DS 2020
Year: 2020

Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in \mathbb{Z}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right) \] converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$, and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics \[ \dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),\] where $g_e$ is an increasing differentiable function with $g_e(1) = 1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.
Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees
Venue: arXiv cs.LG 2020
Year: 2020

We propose a novel nonparametric online predictor for discrete labels conditioned on multivariate continuous features. The predictor is based on a feature space discretization induced by a full-fledged k-d tree with randomly picked directions and a recursive Bayesian distribution, which allows to automatically learn the most relevant feature scales characterizing the conditional distribution. We prove its pointwise universality, i.e., it achieves a normalized log loss performance asymptotically as good as the true conditional entropy of the labels given the features. The time complexity to process the $n$-th sample point is $O(\log n)$ in probability with respect to the distribution generating the data points, whereas other exact nonparametric methods require to process all past observations. Experiments on challenging datasets show the computational and statistical efficiency of our algorithm in comparison to standard and state-of-the-art methods.
Deep Clustering with a Dynamic Autoencoder: From Reconstruction towards Centroids Construction
Venue: arXiv cs.LG 2020
Year: 2020

In unsupervised learning, there is no apparent straightforward cost function that can capture the significant factors of variations and similarities. Since natural systems have smooth dynamics, an opportunity is lost if an unsupervised objective function remains static during the training process. The absence of concrete supervision suggests that smooth dynamics should be integrated. Compared to classical static cost functions, dynamic objective functions allow to better make use of the gradual and uncertain knowledge acquired through pseudo-supervision. In this paper, we propose Dynamic Autoencoder (DynAE), a novel model for deep clustering that overcomes a clustering-reconstruction trade-off, by gradually and smoothly eliminating the reconstruction objective function in favor of a construction one. Experimental evaluations on benchmark datasets show that our approach achieves state-of-the-art results compared to the most relevant deep clustering methods.
Sequential Skip Prediction with Few-shot in Streamed Music Contents
Venue: arXiv cs.IR 2020
Year: 2020

This paper provides an outline of the algorithms submitted for the WSDM Cup 2019 Spotify Sequential Skip Prediction Challenge (team name: mimbres). In the challenge, complete information including acoustic features and user interaction logs for the first half of a listening session is provided. Our goal is to predict whether the individual tracks in the second half of the session will be skipped or not, only given acoustic features. We proposed two different kinds of algorithms that were based on metric learning and sequence learning. The experimental results showed that the sequence learning approach performed significantly better than the metric learning approach. Moreover, we conducted additional experiments to find that significant performance gain can be achieved using complete user log information.
Learning Space Partitions for Nearest Neighbor Search
Venue: arXiv cs.LG 2020
Year: 2020

Space partitions of $\mathbb{R}^d$ underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner [Sanders, Schulz SEA 2013] and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS, our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.
On the Existence of Telescopers for Rational Functions in Three Variables
Venue: arXiv cs.SC 2020
Year: 2020

Zeilberger's method of creative telescoping is crucial for the computer-generated proofs of combinatorial and special-function identities. Telescopers are linear differential or ($q$-)recurrence operators computed by algorithms for creative telescoping. For a given class of inputs, when telescopers exist and how to construct telescopers efficiently if they exist are two fundamental problems related to creative telescoping. In this paper, we solve the existence problem of telescopers for rational functions in three variables including 18 cases. We reduce the existence problem from the trivariate case to the bivariate case and some related problems. The existence criteria given in this paper enable us to determine the termination of algorithms for creative telescoping with trivariate rational inputs.
Bridging the Gap Between Computational Photography and Visual Recognition
Venue: arXiv cs.CV 2020
Year: 2020

What is the current state-of-the-art for image restoration and enhancement applied to degraded images acquired under less than ideal circumstances? Can the application of such algorithms as a pre-processing step to improve image interpretability for manual analysis or automatic visual recognition to classify scene content? While there have been important advances in the area of computational photography to restore or enhance the visual quality of an image, the capabilities of such techniques have not always translated in a useful way to visual recognition tasks. Consequently, there is a pressing need for the development of algorithms that are designed for the joint problem of improving visual appearance and recognition, which will be an enabling factor for the deployment of visual recognition tools in many real-world scenarios. To address this, we introduce the UG^2 dataset as a large-scale benchmark composed of video imagery captured under challenging conditions, and two enhancement tasks designed to test algorithmic impact on visual quality and automatic object recognition. Furthermore, we propose a set of metrics to evaluate the joint improvement of such tasks as well as individual algorithmic advances, including a novel psychophysics-based evaluation regime for human assessment and a realistic set of quantitative measures for object recognition performance. We introduce six new algorithms for image restoration or enhancement, which were created as part of the IARPA sponsored UG^2 Challenge workshop held at CVPR 2018. Under the proposed evaluation regime, we present an in-depth analysis of these algorithms and a host of deep learning-based and classic baseline approaches. From the observed results, it is evident that we are in the early days of building a bridge between computational photography and visual recognition, leaving many opportunities for innovation in this area.