OpenRaiser/Intern-Atlas huggingface dataset:
Impacts of Dirty Data: and Experimental Evaluation
Venue: arXiv cs.DB 2021
Year: 2021

Data quality issues have attracted widespread attention due to the negative impacts of dirty data on data mining and machine learning results. The relationship between data quality and the accuracy of results could be applied on the selection of the appropriate algorithm with the consideration of data quality and the determination of the data share to clean. However, rare research has focused on exploring such relationship. Motivated by this, this paper conducts an experimental comparison for the effects of missing, inconsistent and conflicting data on classification and clustering algorithms. Based on the experimental findings, we provide guidelines for algorithm selection and data cleaning.
Coordinating users of shared facilities via data-driven predictive assistants and game theory
Venue: arXiv cs.GT 2021
Year: 2021

We study data-driven assistants that provide congestion forecasts to users of shared facilities (roads, cafeterias, etc.), to support coordination between them, and increase efficiency of such collective systems. Key questions are: (1) when and how much can (accurate) predictions help for coordination, and (2) which assistant algorithms reach optimal predictions? First we lay conceptual ground for this setting where user preferences are a priori unknown and predictions influence outcomes. Addressing (1), we establish conditions under which self-fulfilling prophecies, i.e., "perfect" (probabilistic) predictions of what will happen, solve the coordination problem in the game-theoretic sense of selecting a Bayesian Nash equilibrium (BNE). Next we prove that such prophecies exist even in large-scale settings where only aggregated statistics about users are available. This entails a new (nonatomic) BNE existence result. Addressing (2), we propose two assistant algorithms that sequentially learn from users' reactions, together with optimality/convergence guarantees. We validate one of them in a large real-world experiment.
Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
Venue: arXiv cs.DS 2021
Year: 2021

The transversal hypergraph problem is the task of enumerating the minimal hitting sets of a hypergraph. It is a long-standing open question whether this can be done in output-polynomial time. For hypergraphs whose solutions have bounded size, Eiter and Gottlob [SICOMP 1995] gave an algorithm that runs in output-polynomial time, but whose space requirement also scales with the output size. We improve this to polynomial delay and polynomial space. More generally, we present an algorithm that on $n$-vertex, $m$-edge hypergraphs has delay $O(m^{k^*+1} n^2)$ and uses $O(mn)$ space, where $k^*$ is the maximum size of any minimal hitting set. Our algorithm is oblivious to $k^*$, a quantity that is hard to compute or even approximate. Central to our approach is the extension problem for minimal hitting sets, deciding for a set $X$ of vertices whether it is contained in any solution. With $|X|$ as parameter, we show that this is one of the first natural problems to be complete for the complexity class $W[3]$. We give an algorithm for the extension problem running in time $O(m^{|X|+1} n)$. We also prove a conditional lower bound under the Strong Exponential Time Hypothesis, showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
Facial Landmarks Localization using Cascaded Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

The accurate localization of facial landmarks is at the core of face analysis tasks, such as face recognition and facial expression analysis, to name a few. In this work, we propose a novel localization approach based on a deep learning architecture that utilizes cascaded subnetworks with convolutional neural network units. The cascaded units of the first subnetwork estimate heatmap-based encodings of the landmarks locations, while the cascaded units of the second subnetwork receive as input the output of the corresponding heatmap estimation units, and refine them through regression. The proposed scheme is experimentally shown to compare favorably with contemporary state-of-the-art schemes, especially when applied to images depicting challenging localization conditions.
Developing parsimonious ensembles using ensemble diversity within a reinforcement learning framework
Venue: arXiv cs.LG 2021
Year: 2021

Heterogeneous ensembles built from the predictions of a wide variety and large number of diverse base predictors represent a potent approach to building predictive models for problems where the ideal base/individual predictor may not be obvious. Ensemble selection is an especially promising approach here, not only for improving prediction performance, but also because of its ability to select a collectively predictive subset, often a relatively small one, of the base predictors. In this paper, we present a set of algorithms that explicitly incorporate ensemble diversity, a known factor influencing predictive performance of ensembles, into a reinforcement learning framework for ensemble selection. We rigorously tested these approaches on several challenging problems and associated data sets, yielding that several of them produced more accurate ensembles than those that don't explicitly consider diversity. More importantly, these diversity-incorporating ensembles were much smaller in size, i.e., more parsimonious, than the latter types of ensembles. This can eventually aid the interpretation or reverse engineering of predictive models assimilated into the resultant ensemble(s).
Presentable signatures and initial semantics
Venue: arXiv cs.LO 2021
Year: 2021

We present a device for specifying and reasoning about syntax for datatypes, programming languages, and logic calculi. More precisely, we study a notion of "signature" for specifying syntactic constructions. In the spirit of Initial Semantics, we define the "syntax generated by a signature" to be the initial object -- if it exists -- in a suitable category of models. In our framework, the existence of an associated syntax to a signature is not automatically guaranteed. We identify, via the notion of presentation of a signature, a large class of signatures that do generate a syntax. Our (presentable) signatures subsume classical algebraic signatures (i.e., signatures for languages with variable binding, such as the pure lambda calculus) and extend them to include several other significant examples of syntactic constructions. One key feature of our notions of signature, syntax, and presentation is that they are highly compositional, in the sense that complex examples can be obtained by gluing simpler ones. Moreover, through the Initial Semantics approach, our framework provides, beyond the desired algebra of terms, a well-behaved substitution and the induction and recursion principles associated to the syntax. This paper builds upon ideas from a previous attempt by Hirschowitz-Maggesi, which, in turn, was directly inspired by some earlier work of Ghani-Uustalu-Hamana and Matthes-Uustalu. The main results presented in the paper are computer-checked within the UniMath system.
Supersingular Isogeny Oblivious Transfer (SIOT)
Venue: arXiv cs.CR 2021
Year: 2021

We present an oblivious transfer (OT) protocol that combines the OT scheme of Chou and Orlandi together with thesupersingular isogeny Diffie-Hellman (SIDH) primitive of De Feo, Jao, and Plût. Our construction is a candidate for post-quantum secure OT and demonstrates that SIDH naturally supports OT functionality. We consider the protocol in the simplest configuration of $\binom{2}{1}$-OT and analyze the protocol to verify its security.
Bandit-Based Monte Carlo Optimization for Nearest Neighbors
Venue: arXiv cs.LG 2021
Year: 2021

The celebrated Monte Carlo method estimates an expensive-to-compute quantity by random sampling. Bandit-based Monte Carlo optimization is a general technique for computing the minimum of many such expensive-to-compute quantities by adaptive random sampling. The technique converts an optimization problem into a statistical estimation problem which is then solved via multi-armed bandits. We apply this technique to solve the problem of high-dimensional $k$-nearest neighbors, developing an algorithm which we prove is able to identify exact nearest neighbors with high probability. We show that under regularity assumptions on a dataset of $n$ points in $d$-dimensional space, the complexity of our algorithm scales logarithmically with the dimension of the data as $O\left((n+d)\log^2 \left(\frac{nd}δ\right)\right)$ for error probability $δ$, rather than linearly as in exact computation requiring $O(nd)$. We corroborate our theoretical results with numerical simulations, showing that our algorithm outperforms both exact computation and state-of-the-art algorithms such as kGraph, NGT, and LSH on real datasets.
Learning convex polyhedra with margin
Venue: arXiv cs.LG 2021
Year: 2021

We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about $t \log t$ halfspaces with constant-size margins in time polynomial in $t$ (where $t$ is the number of halfspaces forming an optimal polyhedron). We also identify distinct generalizations of the notion of margin from hyperplanes to polyhedra and investigate how they relate geometrically; this result may have ramifications beyond the learning setting.
Invariant Representation of Mathematical Expressions
Venue: arXiv cs.AI 2021
Year: 2021

While there exist many methods in machine learning for comparison of letter string data, most are better equipped to handle strings that represent natural language, and their performance will not hold up when presented with strings that correspond to mathematical expressions. Based on the graphical representation of the expression tree, here we propose a simple method for encoding such expressions that is only sensitive to their structural properties, and invariant to the specifics which can vary between two seemingly different, but semantically similar mathematical expressions.
JTAV: Jointly Learning Social Media Content Representation by Fusing Textual, Acoustic, and Visual Features
Venue: arXiv cs.CL 2021
Year: 2021

Learning social media content is the basis of many real-world applications, including information retrieval and recommendation systems, among others. In contrast with previous works that focus mainly on single modal or bi-modal learning, we propose to learn social media content by fusing jointly textual, acoustic, and visual information (JTAV). Effective strategies are proposed to extract fine-grained features of each modality, that is, attBiGRU and DCRNN. We also introduce cross-modal fusion and attentive pooling techniques to integrate multi-modal information comprehensively. Extensive experimental evaluation conducted on real-world datasets demonstrates our proposed model outperforms the state-of-the-art approaches by a large margin.
Automated Image Data Preprocessing with Deep Reinforcement Learning
Venue: arXiv cs.CV 2021
Year: 2021

Data preparation, i.e. the process of transforming raw data into a format that can be used for training effective machine learning models, is a tedious and time-consuming task. For image data, preprocessing typically involves a sequence of basic transformations such as cropping, filtering, rotating or flipping images. Currently, data scientists decide manually based on their experience which transformations to apply in which particular order to a given image data set. Besides constituting a bottleneck in real-world data science projects, manual image data preprocessing may yield suboptimal results as data scientists need to rely on intuition or trial-and-error approaches when exploring the space of possible image transformations and thus might not be able to discover the most effective ones. To mitigate the inefficiency and potential ineffectiveness of manual data preprocessing, this paper proposes a deep reinforcement learning framework to automatically discover the optimal data preprocessing steps for training an image classifier. The framework takes as input sets of labeled images and predefined preprocessing transformations. It jointly learns the classifier and the optimal preprocessing transformations for individual images. Experimental results show that the proposed approach not only improves the accuracy of image classifiers, but also makes them substantially more robust to noisy inputs at test time.
Representative families for matroid intersections, with applications to location, packing, and covering problems
Venue: arXiv cs.DS 2021
Year: 2021

We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
Popular Matchings in Complete Graphs
Venue: arXiv cs.DM 2021
Year: 2021

Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our goal is to construct a matching in $G$ that is popular. A matching $M$ is popular if $M$ does not lose a head-to-head election against any matching $M'$, where each vertex casts a vote for the matching in $\{M,M'\}$ where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in $G$ is easy to solve for odd $n$. Surprisingly, the problem becomes NP-hard for even $n$, as we show here.
Online exploration outside a convex obstacle
Venue: arXiv cs.CG 2021
Year: 2021

A watchman path is a path such that a direct line of sight exists between each point in some region and some point along the path. Here, we study the online watchman path problem outside a convex polygon, i.e., in $\mathbb{R}^2\setminus Ω$, where $Ω$ is a convex polygon that is not known in advance. We present an algorithm for the exploration of the region outside the polygon. We prove that the presented algorithms guarantees a $\approx 22.77$ competitive ratio compared to the optimal offline watchman path.
Mean Isoperimetry with Control on Outliers: Exact and Approximation Algorithms
Venue: arXiv cs.DS 2021
Year: 2021

Given a weighted graph $G=(V,E)$ with weight functions $c:E\to \mathbb{R}_+$ and $π:V\to \mathbb{R}_+$, and a subset $U\subseteq V$, the normalized cut value for $U$ is defined as the sum of the weights of edges exiting $U$ divided by the weight of vertices in $U$. The {\it mean isoperimetry problem}, $\mathsf{ISO}^1(G,k)$, for a weighted graph $G$ is a generalization of the classical uniform sparsest cut problem in which, given a parameter $k$, the objective is to find $k$ disjoint nonempty subsets of $V$ minimizing the average normalized cut value of the parts. The robust version of the problem seeks an optimizer where the number of vertices that fall out of the subpartition is bounded by some given integer $0 \leq ρ\leq |V|$. Our main result states that $\mathsf{ISO}^1(G,k)$, as well as its robust version, $\mathsf{CRISO}^1(G,k,ρ)$, subjected to the condition that each part of the subpartition induces a connected subgraph, are solvable in time $O(k^2 ρ^2\ π(V(T)^3)$ on any weighted tree $T$, in which $π(V(T))$ is the sum of the vertex-weights. This result implies that $\mathsf{ISO}^1(G,k)$ is strongly polynomial-time solvable on weighted trees when the vertex-weights are polynomially bounded and may be compared to the fact that the problem is NP-Hard for weighted trees in general. Also, using this, we show that both mentioned problems, $\mathsf{ISO}^1(G,k)$ and $\mathsf{CRISO}^1(G,k,ρ)$ as well as the ordinary robust mean isoperimetry problem $\mathsf{RISO}^1(G,k,ρ)$, admit polynomial-time $O(\log^{1.5}|V| \log\log |V|)$-approximation algorithms for weighted graphs with polynomially bounded weights, using the R{ä}cke-Shah tree cut sparsifier.
Triangle-Free Equimatchable Graphs
Venue: arXiv cs.DM 2021
Year: 2021

A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et al. [8] provided a characterization of equimatchable graphs with girth at least $5$. In this paper, we extend this result by providing a complete structural characterization of equimatchable graphs with girth at least $4$, i.e., equimatchable graphs with no triangle, by identifying the equimatchable triangle-free graph families. Our characterization also extends the result given by Akbari et al. in [1], which proves that the only connected triangle-free equimatchable $r$-regular graphs are $C_5$, $C_7$ and $K_{r,r}$, where $r$ is a positive integer. Given a non-bipartite graph, our characterization implies a linear time recognition algorithm for triangle-free equimatchable graphs.
Security and Privacy Issues in Deep Learning
Venue: arXiv cs.CR 2021
Year: 2021

To promote secure and private artificial intelligence (SPAI), we review studies on the model security and data privacy of DNNs. Model security allows system to behave as intended without being affected by malicious external influences that can compromise its integrity and efficiency. Security attacks can be divided based on when they occur: if an attack occurs during training, it is known as a poisoning attack, and if it occurs during inference (after training) it is termed an evasion attack. Poisoning attacks compromise the training process by corrupting the data with malicious examples, while evasion attacks use adversarial examples to disrupt entire classification process. Defenses proposed against such attacks include techniques to recognize and remove malicious data, train a model to be insensitive to such data, and mask the model's structure and parameters to render attacks more challenging to implement. Furthermore, the privacy of the data involved in model training is also threatened by attacks such as the model-inversion attack, or by dishonest service providers of AI applications. To maintain data privacy, several solutions that combine existing data-privacy techniques have been proposed, including differential privacy and modern cryptography techniques. In this paper, we describe the notions of some of methods, e.g., homomorphic encryption, and review their advantages and challenges when implemented in deep-learning models.
On Nonnegative Integer Matrices and Short Killing Words
Venue: arXiv cs.FL 2021
Year: 2021

Let $n$ be a natural number and $\mathcal{M}$ a set of $n \times n$-matrices over the nonnegative integers such that the joint spectral radius of $\mathcal{M}$ is at most one. We show that if the zero matrix $0$ is a product of matrices in $\mathcal{M}$, then there are $M_1, \ldots, M_{n^5} \in \mathcal{M}$ with $M_1 \cdots M_{n^5} = 0$. This result has applications in automata theory and the theory of codes. Specifically, if $X \subset Σ^*$ is a finite incomplete code, then there exists a word $w \in Σ^*$ of length polynomial in $\sum_{x \in X} |x|$ such that $w$ is not a factor of any word in $X^*$. This proves a weak version of Restivo's conjecture.
Polymorphic Iterable Sequential Effect Systems
Venue: arXiv cs.PL 2021
Year: 2021

Effect systems are lightweight extensions to type systems that can verify a wide range of important properties with modest developer burden. But our general understanding of effect systems is limited primarily to systems where the order of effects is irrelevant. Understanding such systems in terms of a semilattice of effects grounds understanding of the essential issues, and provides guidance when designing new effect systems. By contrast, sequential effect systems -- where the order of effects is important -- lack an established algebraic structure on effects. We present an abstract polymorphic effect system parameterized by an effect quantale -- an algebraic structure with well-defined properties that can model the effects of a range of existing sequential effect systems. We define effect quantales, derive useful properties, and show how they cleanly model a variety of known sequential effect systems. We show that for most effect quantales, there is an induced notion of iterating a sequential effect; that for systems we consider the derived iteration agrees with the manually designed iteration operators in prior work; and that this induced notion of iteration is as precise as possible when defined. We also position effect quantales with respect to work on categorical semantics for sequential effect systems, clarifying the distinctions between these systems and our own in the course of giving a thorough survey of these frameworks. Our derived iteration construct should generalize to these semantic structures, addressing limitations of that work. Finally, we consider the relationship between sequential effects and Kleene Algebras, where the latter may be used as instances of the former.
Cross-App Interference Threats in Smart Homes: Categorization, Detection and Handling
Venue: arXiv cs.CR 2021
Year: 2021

A number of Internet of Things (IoTs) platforms have emerged to enable various IoT apps developed by third-party developers to automate smart homes. Prior research mostly concerns the overprivilege problem in the permission model. Our work, however, reveals that even IoT apps that follow the principle of least privilege, when they interplay, can cause unique types of threats, named Cross-App Interference (CAI) threats. We describe and categorize the new threats, showing that unexpected automation, security and privacy issues may be caused by such threats, which cannot be handled by existing IoT security mechanisms. To address this problem, we present HOMEGUARD, a system for appified IoT platforms to detect and cope with CAI threats. A symbolic executor module is built to precisely extract the automation semantics from IoT apps. The semantics of different IoT apps are then considered collectively to evaluate their interplay and discover CAI threats systematically. A user interface is presented to users during IoT app installation, interpreting the discovered threats to help them make decisions. We evaluate HOMEGUARD via a proof-of-concept implementation on Samsung SmartThings and discover many threat instances among apps in the SmartThings public repository. The evaluation shows that it is precise, effective and efficient.