OpenRaiser/Intern-Atlas huggingface dataset:
IoT Data Analytics Using Deep Learning
Venue: arXiv cs.NI 2021
Year: 2021

Deep learning is a popular machine learning approach which has achieved a lot of progress in all traditional machine learning areas. Internet of thing (IoT) and Smart City deployments are generating large amounts of time-series sensor data in need of analysis. Applying deep learning to these domains has been an important topic of research. The Long-Short Term Memory (LSTM) network has been proven to be well suited for dealing with and predicting important events with long intervals and delays in the time series. LTSM networks have the ability to maintain long-term memory. In an LTSM network, a stacked LSTM hidden layer also makes it possible to learn a high level temporal feature without the need of any fine tuning and preprocessing which would be required by other techniques. In this paper, we construct a long-short term memory (LSTM) recurrent neural network structure, use the normal time series training set to build the prediction model. And then we use the predicted error from the prediction model to construct a Gaussian naive Bayes model to detect whether the original sample is abnormal. This method is called LSTM-Gauss-NBayes for short. We use three real-world data sets, each of which involve long-term time-dependence or short-term time-dependence, even very weak time dependence. The experimental results show that LSTM-Gauss-NBayes is an effective and robust model.
A Comparison of Audio Signal Preprocessing Methods for Deep Neural Networks on Music Tagging
Venue: arXiv cs.SD 2021
Year: 2021

In this paper, we empirically investigate the effect of audio preprocessing on music tagging with deep neural networks. We perform comprehensive experiments involving audio preprocessing using different time-frequency representations, logarithmic magnitude compression, frequency weighting, and scaling. We show that many commonly used input preprocessing techniques are redundant except magnitude compression.
Subspace Clustering using Ensembles of $K$-Subspaces
Venue: arXiv cs.CV 2021
Year: 2021

Subspace clustering is the unsupervised grouping of points lying near a union of low-dimensional linear subspaces. Algorithms based directly on geometric properties of such data tend to either provide poor empirical performance, lack theoretical guarantees, or depend heavily on their initialization. We present a novel geometric approach to the subspace clustering problem that leverages ensembles of the K-subspaces (KSS) algorithm via the evidence accumulation clustering framework. Our algorithm, referred to as ensemble K-subspaces (EKSS), forms a co-association matrix whose (i,j)th entry is the number of times points i and j are clustered together by several runs of KSS with random initializations. We prove general recovery guarantees for any algorithm that forms an affinity matrix with entries close to a monotonic transformation of pairwise absolute inner products. We then show that a specific instance of EKSS results in an affinity matrix with entries of this form, and hence our proposed algorithm can provably recover subspaces under similar conditions to state-of-the-art algorithms. The finding is, to the best of our knowledge, the first recovery guarantee for evidence accumulation clustering and for KSS variants. We show on synthetic data that our method performs well in the traditionally challenging settings of subspaces with large intersection, subspaces with small principal angles, and noisy data. Finally, we evaluate our algorithm on six common benchmark datasets and show that unlike existing methods, EKSS achieves excellent empirical performance when there are both a small and large number of points per subspace.
Preconditioners for Saddle Point Problems on Truncated Domains in Phase Separation Modelling
Venue: arXiv cs.NA 2021
Year: 2021

The discretization of Cahn-Hilliard equation with obstacle potential leads to a block 2 by 2 non-linear system, where the p1, 1q block has a non-linear and non-smooth term. Recently a globally convergent Newton Schur method was proposed for the non-linear Schur complement corresponding to this non-linear system. The solver may be seen as an inexact Uzawa method which has the falvour of an active set method in the sense that the active sets are first identified by solving a quadratic obstacle problem corresponding to the p1, 1q block of the block 2 by 2 nonlinear system, and a new decent direction is obtained after discarding the active set region. The problem becomes linear on nonactive set, and corresponds to solving a linear saddle point problem on truncated domains. For solving the quadratic obstacle problem, various optimal multigrid like methods have been proposed. In this paper solvers for the truncated saddle point problem is considered. Three preconditioners are considered, two of them have block diagonal structure, and the third one has block tridiagonal structure. One of the block diagonal preconditioners is obtained by adding certain scaling of stiffness and mass matrices, whereas, the remaining two involves Schur complement. Eigenvalue bound and condition number estimates are derived for the preconditioned untruncated problem. It is shown that the extreme eigenvalues of the preconditioned truncated system remain bounded by the extreme eigenvalues of the preconditioned untruncated system. Numerical experiments confirm the optimality of the solvers.
Flow: A Modular Learning Framework for Mixed Autonomy Traffic
Venue: arXiv cs.AI 2021
Year: 2021

The rapid development of autonomous vehicles (AVs) holds vast potential for transportation systems through improved safety, efficiency, and access to mobility. However, the progression of these impacts, as AVs are adopted, is not well understood. Numerous technical challenges arise from the goal of analyzing the partial adoption of autonomy: partial control and observation, multi-vehicle interactions, and the sheer variety of scenarios represented by real-world networks. To shed light into near-term AV impacts, this article studies the suitability of deep reinforcement learning (RL) for overcoming these challenges in a low AV-adoption regime. A modular learning framework is presented, which leverages deep RL to address complex traffic dynamics. Modules are composed to capture common traffic phenomena (stop-and-go traffic jams, lane changing, intersections). Learned control laws are found to improve upon human driving performance, in terms of system-level velocity, by up to 57% with only 4-7% adoption of AVs. Furthermore, in single-lane traffic, a small neural network control law with only local observation is found to eliminate stop-and-go traffic - surpassing all known model-based controllers to achieve near-optimal performance - and generalize to out-of-distribution traffic densities.
On Lower Bounds on Sub-Packetization Level of MSR codes and On The Structure of Optimal-Access MSR Codes Achieving The Bound
Venue: arXiv cs.IT 2021
Year: 2021

We present two lower bounds on sub-packetization level $α$ of MSR codes with parameters $(n, k, d=n-1, α)$ where $n$ is the block length, $k$ dimension, $d$ number of helper nodes contacted during single node repair and $α$ the sub-packetization level. The first bound we present is for any MSR code and is given by $α\ge e^{\frac{(k-1)(r-1)}{2r^2}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by $α\ge \min \{ r^{\frac{n-1}{r}}, r^{k-1} \}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR codes to have optimal sub-packetization level under the constraint that the indices of helper symbols are dependant only on the failed node, it is needed that the support of the parity check matrix is same as the support structure of several other optimal constructions in literature.
Finding branch-decompositions of matroids, hypergraphs, and more
Venue: arXiv cs.DM 2021
Year: 2021

Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field $\mathbb F$, we wish to find a "branch-decomposition" of these subspaces of width at most $k$ that is a subcubic tree $T$ with $n$ leaves mapped bijectively to the subspaces such that for every edge $e$ of $T$, the sum of subspaces associated to the leaves in one component of $T-e$ and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most $k$. This problem includes the problems of computing branch-width of $\mathbb F$-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most $k$, if it exists, for input subspaces of a finite-dimensional vector space over $\mathbb F$. Our algorithm is analogous to the algorithm of Bodlaender and Kloks (1996) on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of $\mathbb F$-represented matroids was due to Hliněný and Oum (2008) that runs in time $O(n^3)$ where $n$ is the number of elements of the input $\mathbb F$-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. (2003) that the number of forbidden minors is finite and uses the algorithm of Hliněný (2006) on checking monadic second-order formulas on $\mathbb F$-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed $k$.
Projection Theorems Using Effective Dimension
Venue: arXiv cs.CC 2021
Year: 2021

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which shows that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.
Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,m\}}f_i(A)$. While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, Krause et al.\ (2008) showed that when the number of objectives $m$ grows as the cardinality $k$ i.e., $m=Ω(k)$, the problem is inapproximable (unless $P=NP$). On the other hand, when $m$ is constant Chekuri et al.\ (2010) showed a randomized $(1-1/e)-ε$ approximation with runtime (number of queries to function oracle) $n^{m/ε^3}$. %In fact, the result of Chekuri et al.\ (2010) is for the far more general case of matroid constant. We focus on finding a fast and practical algorithm that has (asymptotic) approximation guarantees even when $m$ is super constant. We first modify the algorithm of Chekuri et al.\ (2010) to achieve a $(1-1/e)$ approximation for $m=o(\frac{k}{\log^3 k})$. This demonstrates a steep transition from constant factor approximability to inapproximability around $m=Ω(k)$. Then using Multiplicative-Weight-Updates (MWU), we find a much faster $\tilde{O}(n/δ^3)$ time asymptotic $(1-1/e)^2-δ$ approximation. While the above results are all randomized, we also give a simple deterministic $(1-1/e)-ε$ approximation with runtime $kn^{m/ε^4}$. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.
Asymptotically Minimax Robust Hypothesis Testing
Venue: arXiv cs.IT 2021
Year: 2021

The design of asymptotically minimax robust hypothesis testing is formalized for the Bayesian and Neyman-Pearson tests of Type-I and Type-II. The uncertainty classes based on the KL-divergence, $α$-divergence, symmetrized $α$-divergence, total variation distance, as well as the band model, moment classes and p-point classes are considered. Implications between single-sample-, all-sample- and asymptotic minimax robustness are derived. Existence and uniqueness of asymptotically minimax robust tests are proven using Sion's minimax theorem and the Karush-Kuhn-Tucker multipliers. The least favorable distributions and the corresponding robust likelihood ratio functions are derived in parametric forms, which can then be determined by solving a system of equations. The proposed theory proves that Dabak's design does not produce any asymptotically minimax robust test. Furthermore, it also generalizes the earlier works by Huber and Kassam by allowing analytical derivations, hence, providing answers to the questions 'how?', which were left unanswered. Simulations are provided to exemplify and evaluate the theoretical derivations.
Learning Fast and Slow: PROPEDEUTICA for Real-time Malware Detection
Venue: arXiv cs.CR 2021
Year: 2021

Existing malware detectors on safety-critical devices have difficulties in runtime detection due to the performance overhead. In this paper, we introduce PROPEDEUTICA, a framework for efficient and effective real-time malware detection, leveraging the best of conventional machine learning (ML) and deep learning (DL) techniques. In PROPEDEUTICA, all software start execution are considered as benign and monitored by a conventional ML classifier for fast detection. If the software receives a borderline classification from the ML detector (e.g. the software is 50% likely to be benign and 50% likely to be malicious), the software will be transferred to a more accurate, yet performance demanding DL detector. To address spatial-temporal dynamics and software execution heterogeneity, we introduce a novel DL architecture (DEEPMALWARE) for PROPEDEUTICA with multi-stream inputs. We evaluated PROPEDEUTICA with 9,115 malware samples and 1,338 benign software from various categories for the Windows OS. With a borderline interval of [30%-70%], PROPEDEUTICA achieves an accuracy of 94.34% and a false-positive rate of 8.75%, with 41.45% of the samples moved for DEEPMALWARE analysis. Even using only CPU, PROPEDEUTICA can detect malware within less than 0.1 seconds.
Character-Based Handwritten Text Transcription with Attention Networks
Venue: arXiv cs.CV 2021
Year: 2021

The paper approaches the task of handwritten text recognition (HTR) with attentional encoder-decoder networks trained on sequences of characters, rather than words. We experiment on lines of text from popular handwriting datasets and compare different activation functions for the attention mechanism used for aligning image pixels and target characters. We find that softmax attention focuses heavily on individual characters, while sigmoid attention focuses on multiple characters at each step of the decoding. When the sequence alignment is one-to-one, softmax attention is able to learn a more precise alignment at each step of the decoding, whereas the alignment generated by sigmoid attention is much less precise. When a linear function is used to obtain attention weights, the model predicts a character by looking at the entire sequence of characters and performs poorly because it lacks a precise alignment between the source and target. Future research may explore HTR in natural scene images, since the model is capable of transcribing handwritten text without the need for producing segmentations or bounding boxes of text in images.
New and Improved Algorithms for Unordered Tree Inclusion
Venue: arXiv cs.DS 2021
Year: 2021

The tree inclusion problem is, given two node-labeled trees $P$ and $T$ (the ``pattern tree'' and the ``target tree''), to locate every minimal subtree in $T$ (if any) that can be obtained by applying a sequence of node insertion operations to $P$. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpeläinen and Mannila from 1995 that runs in $O(2^{2d} mn)$ time, where $m$ and $n$ are the sizes of the pattern and target trees, respectively, and $d$ is the degree of the pattern tree. Here, we develop a new algorithm that runs in $O(2^{d} mn^2)$ time, improving the exponential factor from $2^{2d}$ to $2^d$ by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem.
Taking Visual Motion Prediction To New Heightfields
Venue: arXiv cs.CV 2021
Year: 2021

While the basic laws of Newtonian mechanics are well understood, explaining a physical scenario still requires manually modeling the problem with suitable equations and estimating the associated parameters. In order to be able to leverage the approximation capabilities of artificial intelligence techniques in such physics related contexts, researchers have handcrafted the relevant states, and then used neural networks to learn the state transitions using simulation runs as training data. Unfortunately, such approaches are unsuited for modeling complex real-world scenarios, where manually authoring relevant state spaces tend to be tedious and challenging. In this work, we investigate if neural networks can implicitly learn physical states of real-world mechanical processes only based on visual data while internally modeling non-homogeneous environment and in the process enable long-term physical extrapolation. We develop a recurrent neural network architecture for this task and also characterize resultant uncertainties in the form of evolving variance estimates. We evaluate our setup to extrapolate motion of rolling ball(s) on bowls of varying shape and orientation, and on arbitrary heightfields using only images as input. We report significant improvements over existing image-based methods both in terms of accuracy of predictions and complexity of scenarios; and report competitive performance with approaches that, unlike us, assume access to internal physical states.
Stabbing Pairwise Intersecting Disks by Five Points
Venue: arXiv cs.CG 2021
Year: 2021

Suppose we are given a set $\mathcal{D}$ of $n$ pairwise intersecting disks in the plane. A planar point set $P$ stabs $\mathcal{D}$ if and only if each disk in $\mathcal{D}$ contains at least one point from $P$. We present a deterministic algorithm that takes $O(n)$ time to find five points that stab $\mathcal{D}$. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. Moreover, we present a simple argument showing that eight disks can be stabbed by at most three points. This provides a simple-albeit slightly weaker-algorithmic version of a classical result by Danzer that such a set $\mathcal{D}$ can always be stabbed by four points.
Online Maximum Matching with Recourse
Venue: arXiv cs.DS 2021
Year: 2021

We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter $k$. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most $k$ such actions per edge take place, where $k$ is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Information Processing Letters, 2013], whereas the special case $k=2$ was studied by Boyar et al. [WADS 2017]. In the first part of this paper we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP of Avitabile et al., by exploiting the structure of the matching problem. In addition, we show that the greedy algorithm has competitive ratio $3/2$ for every even $k$ and ratio $2$ for every odd $k$. Moreover, we present and analyze an improvement of the greedy algorithm which we call $L$-Greedy, and we show that for small values of $k$ it outperforms the algorithm AMP. In terms of lower bounds, we show that no deterministic algorithm better than $1+1/(k-1)$ exists, improving upon the known lower bound of $1+1/k$. The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of $L$-Greedy and AMP carry through in this model; moreover we show a lower bound of $(k^2-3k+6) / (k^2-4k+7)$ for all even $k \ge 4$. For $k\in\{2,3\}$, the competitive ratio is $3/2$.
Dugundji systems and a retract characterization of effective zero-dimensionality
Venue: arXiv cs.LO 2021
Year: 2021

In this paper (as in [Ken15]), we consider an effective version of the characterization of separable metric spaces as zero-dimensional iff every nonempty closed subset is a retract of the space (actually, it is a relative result for closed zero-dimensional subspaces of a fixed space that we have proved). This uses (in the converse direction) local compactness & bilocated sets as in [Ken15], but in the forward direction the newer version has a simpler proof and no compactness assumption. Furthermore, the proof of the forward implication relates to so-called Dugundji systems: we elaborate both a general construction of such systems for a proper nonempty closed subspace (using a computable form of countable paracompactness), and modifications -- to make the sets pairwise disjoint if the subspace is zero-dimensional, or to avoid the restriction to proper subspaces. In a different direction, a second theorem applies in $p$-adic analysis the ideas of the first theorem to compute a more general form of retraction, given a Dugundji system (possibly without disjointness). Finally, we complement the effective retract characterization of zero-dimensional subspaces mentioned above by improving to equivalence the implications (or Weihrauch reductions in some cases), for closed at-most-zero-dimensional subsets with some negative information, among separate conditions of computability of operations $N,M,B,S$ introduced in [Ken15,§4] and corresponding to vanishing large inductive dimension, vanishing small inductive dimension, existence of a countable basis of relatively clopen sets, and the reduction principle for sequences of open sets. Thus, similarly to the robust notion of effective zero-dimensionality of computable metric spaces in [Ken15], there is a robust notion of `uniform effective zero-dimensionality' for a represented pointclass consisting of at-most-zero-dimensional closed subsets.