OpenRaiser/Intern-Atlas huggingface dataset:
On monotone circuits with local oracles and clique lower bounds
Venue: arXiv cs.CC 2019
Year: 2019

We investigate monotone circuits with local oracles [K., 2016], i.e., circuits containing additional inputs $y_i = y_i(\vec{x})$ that can perform unstructured computations on the input string $\vec{x}$. Let $μ\in [0,1]$ be the locality of the circuit, a parameter that bounds the combined strength of the oracle functions $y_i(\vec{x})$, and $U_{n,k}, V_{n,k} \subseteq \{0,1\}^m$ be the set of $k$-cliques and the set of complete $(k-1)$-partite graphs, respectively (similarly to [Razborov, 1985]). Our results can be informally stated as follows. 1. For an appropriate extension of depth-$2$ monotone circuits with local oracles, we show that the size of the smallest circuits separating $U_{n,3}$ (triangles) and $V_{n,3}$ (complete bipartite graphs) undergoes two phase transitions according to $μ$. 2. For $5 \leq k(n) \leq n^{1/4}$, arbitrary depth, and $μ\leq 1/50$, we prove that the monotone circuit size complexity of separating the sets $U_{n,k}$ and $V_{n,k}$ is $n^{Θ(\sqrt{k})}$, under a certain restrictive assumption on the local oracle gates. The second result, which concerns monotone circuits with restricted oracles, extends and provides a matching upper bound for the exponential lower bounds on the monotone circuit size complexity of $k$-clique obtained by Alon and Boppana (1987).
Axiomatizing Epistemic Logic of Friendship via Tree Sequent Calculus
Venue: arXiv cs.LO 2019
Year: 2019

This paper positively solves an open problem if it is possible to provide a Hilbert system to Epistemic Logic of Friendship (EFL) by Seligman, Girard and Liu. To find a Hilbert system, we first introduce a sound, complete and cut-free tree (or nested) sequent calculus for EFL, which is an integrated combination of Seligman's sequent calculus for basic hybrid logic and a tree sequent calculus for modal logic. Then we translate a tree sequent into an ordinary formula to specify a Hilbert system of EFL and finally show that our Hilbert system is sound and complete for the intended two-dimensional semantics.
Optimizing Automata Learning via Monads
Venue: arXiv cs.FL 2019
Year: 2019

Automata learning has been successfully applied in the verification of hardware and software. The size of the automaton model learned is a bottleneck for scalability, and hence optimizations that enable learning of compact representations are important. This paper exploits monads, both as a mathematical structure and a programming construct, to design, prove correct, and implement a wide class of such optimizations. The former perspective on monads allows us to develop a new algorithm and accompanying correctness proofs, building upon a general framework for automata learning based on category theory. The new algorithm is parametric on a monad, which provides a rich algebraic structure to capture non-determinism and other side-effects. We show that our approach allows us to uniformly capture existing algorithms, develop new ones, and add optimizations. The latter perspective allows us to effortlessly translate the theory into practice: we provide a Haskell library implementing our general framework, and we show experimental results for two specific instances: non-deterministic and weighted automata.
Effective scaling registration approach by imposing the emphasis on the scale factor
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes an effective approach for the scaling registration of $m$-D point sets. Different from the rigid transformation, the scaling registration can not be formulated into the common least square function due to the ill-posed problem caused by the scale factor. Therefore, this paper designs a novel objective function for the scaling registration problem. The appearance of this objective function is a rational fraction, where the numerator item is the least square error and the denominator item is the square of the scale factor. By imposing the emphasis on scale factor, the ill-posed problem can be avoided in the scaling registration. Subsequently, the new objective function can be solved by the proposed scaling iterative closest point (ICP) algorithm, which can obtain the optimal scaling transformation. For the practical applications, the scaling ICP algorithm is further extended to align partially overlapping point sets. Finally, the proposed approach is tested on public data sets and applied to merging grid maps of different resolutions. Experimental results demonstrate its superiority over previous approaches on efficiency and robustness.
Smart Routing of Electric Vehicles for Load Balancing in Smart Grids
Venue: arXiv cs.GT 2019
Year: 2019

Electric vehicles (EVs) are expected to be a major component of the smart grid. The rapid proliferation of EVs will introduce an unprecedented load on the existing electric grid due to the charging/discharging behavior of the EVs, thus motivating the need for novel approaches for routing EVs across the grid. In this paper, a novel gametheoretic framework for smart routing of EVs within the smart grid is proposed. The goal of this framework is to balance the electricity load across the grid while taking into account the traffic congestion and the waiting time at charging stations. The EV routing problem is formulated as a noncooperative game. For this game, it is shown that selfish behavior of EVs will result in a pure-strategy Nash equilibrium with the price of anarchy upper bounded by the variance of the ground load induced by the residential, industrial, or commercial users. Moreover, the results are extended to capture the stochastic nature of induced ground load as well as the subjective behavior of the owners of EVs as captured by using notions from the behavioral framework of prospect theory. Simulation results provide new insights on more efficient energy pricing at charging stations and under more realistic grid conditions.
Pitfalls and Best Practices in Algorithm Configuration
Venue: arXiv cs.AI 2019
Year: 2019

Good parameter settings are crucial to achieve high performance in many areas of artificial intelligence (AI), such as propositional satisfiability solving, AI planning, scheduling, and machine learning (in particular deep learning). Automated algorithm configuration methods have recently received much attention in the AI community since they replace tedious, irreproducible and error-prone manual parameter tuning and can lead to new state-of-the-art performance. However, practical applications of algorithm configuration are prone to several (often subtle) pitfalls in the experimental design that can render the procedure ineffective. We identify several common issues and propose best practices for avoiding them. As one possibility for automatically handling as many of these as possible, we also propose a tool called GenericWrapper4AC.
Two-temperature logistic regression based on the Tsallis divergence
Venue: arXiv cs.LG 2019
Year: 2019

We develop a variant of multiclass logistic regression that is significantly more robust to noise. The algorithm has one weight vector per class and the surrogate loss is a function of the linear activations (one per class). The surrogate loss of an example with linear activation vector $\mathbf{a}$ and class $c$ has the form $-\log_{t_1} \exp_{t_2} (a_c - G_{t_2}(\mathbf{a}))$ where the two temperatures $t_1$ and $t_2$ ''temper'' the $\log$ and $\exp$, respectively, and $G_{t_2}(\mathbf{a})$ is a scalar value that generalizes the log-partition function. We motivate this loss using the Tsallis divergence. Our method allows transitioning between non-convex and convex losses by the choice of the temperature parameters. As the temperature $t_1$ of the logarithm becomes smaller than the temperature $t_2$ of the exponential, the surrogate loss becomes ''quasi convex''. Various tunings of the temperatures recover previous methods and tuning the degree of non-convexity is crucial in the experiments. In particular, quasi-convexity and boundedness of the loss provide significant robustness to the outliers. We explain this by showing that $t_1 < 1$ caps the surrogate loss and $t_2 >1$ makes the predictive distribution have a heavy tail. We show that the surrogate loss is Bayes-consistent, even in the non-convex case. Additionally, we provide efficient iterative algorithms for calculating the log-partition value only in a few number of iterations. Our compelling experimental results on large real-world datasets show the advantage of using the two-temperature variant in the noisy as well as the noise free case.
Generalized Degrees Freedom of Noncoherent MIMO Channels with Asymmetric Link Strengths
Venue: arXiv cs.IT 2019
Year: 2019

We study the generalized degrees of freedom (gDoF) of block-fading noncoherent multiple input multiple output (MIMO) channels with asymmetric distributions of link strengths and a coherence time of T symbol durations. We derive the optimal signaling structure for communication for the asymmetric MIMO channel, which is distinct from that for the MIMO channel with independent and identically distributed (i.i.d.) links. We extend the existing results for the single input multiple output (SIMO) channel with i.i.d. links to the asymmetric case, proving that selecting the statistically best antenna is gDoF-optimal. Using the gDoF result for the SIMO channel, we prove that for T=1, the gDoF is zero for MIMO channels with arbitrary link strengths., extending the result for MIMO with i.i.d. links We show that selecting the statistically best antenna is gDoF-optimal for the multiple input single output (MISO) channel. We also derive the gDoF for the 2X2 MIMO channel with different exponents in the direct and cross links. In this setting, we show that it is always necessary to use both the antennas to achieve the gDoF, in contrast to the results for the 2X2 MIMO channel with i.i.d. links. We show that having weaker crosslinks, gives gDoF gain compared to the case with i.i.d. links. For the noncoherent MIMO channel with i.i.d. links, the traditional method of training each transmit antenna independently is degrees of freedom (DoF) optimal, whereas we observe that for the asymmetric 2X2 MIMO channel, the traditional training is not gDoF-optimal. We extend this observation to a larger MX M MIMO channel by demonstrating a strategy that can achieve larger gDoF than a traditional training-based method.
Large-Scale Classification of Structured Objects using a CRF with Deep Class Embedding
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel deep learning architecture to classify structured objects in datasets with a large number of visually similar categories. We model sequences of images as linear-chain CRFs, and jointly learn the parameters from both local-visual features and neighboring classes. The visual features are computed by convolutional layers, and the class embeddings are learned by factorizing the CRF pairwise potential matrix. This forms a highly nonlinear objective function which is trained by optimizing a local likelihood approximation with batch-normalization. This model overcomes the difficulties of existing CRF methods to learn the contextual relationships thoroughly when there is a large number of classes and the data is sparse. The performance of the proposed method is illustrated on a huge dataset that contains images of retail-store product displays, taken in varying settings and viewpoints, and shows significantly improved results compared to linear CRF modeling and unnormalized likelihood optimization.
Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions
Venue: arXiv cs.LG 2019
Year: 2019

We examine the Bayes-consistency of a recently proposed 1-nearest-neighbor-based multiclass learning algorithm. This algorithm is derived from sample compression bounds and enjoys the statistical advantages of tight, fully empirical generalization bounds, as well as the algorithmic advantages of a faster runtime and memory savings. We prove that this algorithm is strongly Bayes-consistent in metric spaces with finite doubling dimension --- the first consistency result for an efficient nearest-neighbor sample compression scheme. Rather surprisingly, we discover that this algorithm continues to be Bayes-consistent even in a certain infinite-dimensional setting, in which the basic measure-theoretic conditions on which classic consistency proofs hinge are violated. This is all the more surprising, since it is known that $k$-NN is not Bayes-consistent in this setting. We pose several challenging open problems for future research.
Interpreting Blackbox Models via Model Extraction
Venue: arXiv cs.LG 2019
Year: 2019

Interpretability has become incredibly important as machine learning is increasingly used to inform consequential decisions. We propose to construct global explanations of complex, blackbox models in the form of a decision tree approximating the original model---as long as the decision tree is a good approximation, then it mirrors the computation performed by the blackbox model. We devise a novel algorithm for extracting decision tree explanations that actively samples new training points to avoid overfitting. We evaluate our algorithm on a random forest to predict diabetes risk and a learned controller for cart-pole. Compared to several baselines, our decision trees are both substantially more accurate and equally or more interpretable based on a user study. Finally, we describe several insights provided by our interpretations, including a causal issue validated by a physician.
Uncovering the Flop of the EU Cookie Law
Venue: arXiv cs.CY 2019
Year: 2019

In 2002, the European Union (EU) introduced the ePrivacy Directive to regulate the usage of online tracking technologies. Its aim is to make tracking mechanisms explicit while increasing privacy awareness in users. It mandates websites to ask for explicit consent before using any kind of profiling methodology, e.g., cookies. Starting from 2013 the Directive is mandatory, and now most of European websites embed a "Cookie Bar" to explicitly ask user's consent. To the best of our knowledge, no study focused in checking whether a website respects the Directive. For this, we engineer CookieCheck, a simple tool that makes this check automatic. We use it to run a measurement campaign on more than 35,000 websites. Results depict a dramatic picture: 65% of websites do not respect the Directive and install tracking cookies before the user is even offered the accept button. In few words, we testify the failure of the ePrivacy Directive. Among motivations, we identify the absence of rules enabling systematic auditing procedures, the lack of tools to verify its implementation by the deputed agencies, and the technical difficulties of webmasters in implementing it.
Distributed Dominating Set Approximations beyond Planar Graphs
Venue: arXiv cs.DC 2019
Year: 2019

The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, there has been much progress on computing local approximations on sparse graphs, and in particular planar graphs. In this paper we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bounds for planar graphs can be lifted to bounded genus graphs, and present (1) a local constant-time, constant-factor MDS approximation algorithm and (2) a local $\mathcal{O}(\log^*{n})$-time approximation scheme. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments.
Multi-Focus Image Fusion Using Sparse Representation and Coupled Dictionary Learning
Venue: arXiv cs.CV 2019
Year: 2019

We address the multi-focus image fusion problem, where multiple images captured with different focal settings are to be fused into an all-in-focus image of higher quality. Algorithms for this problem necessarily admit the source image characteristics along with focused and blurred features. However, most sparsity-based approaches use a single dictionary in focused feature space to describe multi-focus images, and ignore the representations in blurred feature space. We propose a multi-focus image fusion approach based on sparse representation using a coupled dictionary. It exploits the observations that the patches from a given training set can be sparsely represented by a couple of overcomplete dictionaries related to the focused and blurred categories of images and that a sparse approximation based on such coupled dictionary leads to a more flexible and therefore better fusion strategy than the one based on just selecting the sparsest representation in the original image estimate. In addition, to improve the fusion performance, we employ a coupled dictionary learning approach that enforces pairwise correlation between atoms of dictionaries learned to represent the focused and blurred feature spaces. We also discuss the advantages of the fusion approach based on coupled dictionary learning, and present efficient algorithms for fusion based on coupled dictionary learning. Extensive experimental comparisons with state-of-the-art multi-focus image fusion algorithms validate the effectiveness of the proposed approach.
Experience Replay Using Transition Sequences
Venue: arXiv cs.AI 2019
Year: 2019

Experience replay is one of the most commonly used approaches to improve the sample efficiency of reinforcement learning algorithms. In this work, we propose an approach to select and replay sequences of transitions in order to accelerate the learning of a reinforcement learning agent in an off-policy setting. In addition to selecting appropriate sequences, we also artificially construct transition sequences using information gathered from previous agent-environment interactions. These sequences, when replayed, allow value function information to trickle down to larger sections of the state/state-action space, thereby making the most of the agent's experience. We demonstrate our approach on modified versions of standard reinforcement learning tasks such as the mountain car and puddle world problems and empirically show that it enables better learning of value functions as compared to other forms of experience replay. Further, we briefly discuss some of the possible extensions to this work, as well as applications and situations where this approach could be particularly useful.
Thompson Sampling for the MNL-Bandit
Venue: arXiv cs.LG 2019
Year: 2019

We consider a sequential subset selection problem under parameter uncertainty, where at each time step, the decision maker selects a subset of cardinality $K$ from $N$ possible items (arms), and observes a (bandit) feedback in the form of the index of one of the items in said subset, or none. Each item in the index set is ascribed a certain value (reward), and the feedback is governed by a Multinomial Logit (MNL) choice model whose parameters are a priori unknown. The objective of the decision maker is to maximize the expected cumulative rewards over a finite horizon $T$, or alternatively, minimize the regret relative to an oracle that knows the MNL parameters. We refer to this as the MNL-Bandit problem. This problem is representative of a larger family of exploration-exploitation problems that involve a combinatorial objective, and arise in several important application domains. We present an approach to adapt Thompson Sampling to this problem and show that it achieves near-optimal regret as well as attractive numerical performance.
DeepKey: An EEG and Gait Based Dual-Authentication System
Venue: arXiv cs.LG 2019
Year: 2019

Biometric authentication involves various technologies to identify individuals by exploiting their unique, measurable physiological and behavioral characteristics. However, traditional biometric authentication systems (e.g., face recognition, iris, retina, voice, and fingerprint) are facing an increasing risk of being tricked by biometric tools such as anti-surveillance masks, contact lenses, vocoder, or fingerprint films. In this paper, we design a multimodal biometric authentication system named Deepkey, which uses both Electroencephalography (EEG) and gait signals to better protect against such risk. Deepkey consists of two key components: an Invalid ID Filter Model to block unauthorized subjects and an identification model based on attention-based Recurrent Neural Network (RNN) to identify a subject`s EEG IDs and gait IDs in parallel. The subject can only be granted access while all the components produce consistent evidence to match the user`s proclaimed identity. We implement Deepkey with a live deployment in our university and conduct extensive empirical experiments to study its technical feasibility in practice. DeepKey achieves the False Acceptance Rate (FAR) and the False Rejection Rate (FRR) of 0 and 1.0%, respectively. The preliminary results demonstrate that Deepkey is feasible, show consistent superior performance compared to a set of methods, and has the potential to be applied to the authentication deployment in real world settings.
Multi-Modal Obstacle Detection in Unstructured Environments with Conditional Random Fields
Venue: arXiv cs.RO 2019
Year: 2019

Reliable obstacle detection and classification in rough and unstructured terrain such as agricultural fields or orchards remains a challenging problem. These environments involve large variations in both geometry and appearance, challenging perception systems that rely on only a single sensor modality. Geometrically, tall grass, fallen leaves, or terrain roughness can mistakenly be perceived as nontraversable or might even obscure actual obstacles. Likewise, traversable grass or dirt roads and obstacles such as trees and bushes might be visually ambiguous. In this paper, we combine appearance- and geometry-based detection methods by probabilistically fusing lidar and camera sensing with semantic segmentation using a conditional random field. We apply a state-of-the-art multimodal fusion algorithm from the scene analysis domain and adjust it for obstacle detection in agriculture with moving ground vehicles. This involves explicitly handling sparse point cloud data and exploiting both spatial, temporal, and multimodal links between corresponding 2D and 3D regions. The proposed method was evaluated on a diverse data set, comprising a dairy paddock and different orchards gathered with a perception research robot in Australia. Results showed that for a two-class classification problem (ground and nonground), only the camera leveraged from information provided by the other modality with an increase in the mean classification score of 0.5%. However, as more classes were introduced (ground, sky, vegetation, and object), both modalities complemented each other with improvements of 1.4% in 2D and 7.9% in 3D. Finally, introducing temporal links between successive frames resulted in improvements of 0.2% in 2D and 1.5% in 3D.
A proof theoretic study of abstract termination principles
Venue: arXiv cs.LO 2019
Year: 2019

We carry out a proof theoretic analysis of the wellfoundedness of recursive path orders in an abstract setting. We outline a very general termination principle and extract from its wellfoundedness proof subrecursive bounds on the size of derivation trees which can be defined in Gödel's system T plus bar recursion. We then carry out a complexity analysis of these terms, and demonstrate how this can be applied to bound the derivational complexity of term rewrite systems.