OpenRaiser/Intern-Atlas huggingface dataset:
On Sets of Words of Rank Two
Venue: arXiv cs.FL 2019
Year: 2019

Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X \subseteq F^*$. A submonoid $M$ generated by $k$ elements of $A^*$ is $k$-maximal if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X \subseteq A^*$ primitive if it is the basis of a $|X|$-maximal submonoid. This extends the notion of primitive word: indeed, $\{w\}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X \subseteq Y^*$. The set $Y$ is therefore called a primitive root of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2. For a single word $w$, we say that the set $\{x,y\}$ is a {\em binary root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and $\{x,y\}$ is a primitive set. We prove that every primitive word $w$ has at most one binary root $\{x,y\}$ such that $|x|+|y|<\sqrt{|w|}$. That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $θ$ is defined on $A^*$. In this setting, the notions of $θ$-power, $θ$-primitive and $θ$-root are defined, and it is shown that any word has a unique $θ$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $θ$-primitive if and only if $\{w, θ(w)\}$ is a primitive set.
Prefix-Free Code Distribution Matching for Probabilistic Constellation Shaping
Venue: arXiv cs.IT 2019
Year: 2019

In this work, we construct energy-efficient variable-to-fixed length (V2F), fixed-to-variable length (F2V), and variable-to-variable length (V2V) prefix-free codes, which are optimal (or near-optimal) in the sense that no (or few) other codes with the size can achieve a smaller energy per code letter for the same entropy rate. Under stringent constraints of 4096 entries or below per codebook, the constructed codes yield an energy per code letter within a few tenths of a dB of the unconstrained theoretic lower bound, across a wide range of entropy rates with a very fine granularity. We also propose a framing method that allows variable-length codes to be transmitted using a fixed-length frame. The penalty caused by framing is studied using simulations and analysis, showing that the energy per code letter is kept within 0.2 dB of the unconstrained theoretic limit for some tested codes with a large frame length. When framed prefix-free codes are used to implement probabilistic constellation shaping (PCS) for communications in the additive white Gaussian noise channel, simulations show that 1.1 dB and 0.65 dB of shaping gains are achieved relative to uniform 8- and 16-quadrature amplitude modulation (QAM), respectively.
Generalizing the theory of cooperative inference
Venue: arXiv cs.LG 2019
Year: 2019

Cooperation information sharing is important to theories of human learning and has potential implications for machine learning. Prior work derived conditions for achieving optimal Cooperative Inference given strong, relatively restrictive assumptions. We relax these assumptions by demonstrating convergence for any discrete joint distribution, robustness through equivalence classes and stability under perturbation, and effectiveness by deriving bounds from structural properties of the original joint distribution. We provide geometric interpretations, connections to and implications for optimal transport, and connections to importance sampling, and conclude by outlining open questions and challenges to realizing the promise of Cooperative Inference.
Learning To Simulate
Venue: arXiv cs.LG 2019
Year: 2019

Simulation is a useful tool in situations where training data for machine learning models is costly to annotate or even hard to acquire. In this work, we propose a reinforcement learning-based method for automatically adjusting the parameters of any (non-differentiable) simulator, thereby controlling the distribution of synthesized data in order to maximize the accuracy of a model trained on that data. In contrast to prior art that hand-crafts these simulation parameters or adjusts only parts of the available parameters, our approach fully controls the simulator with the actual underlying goal of maximizing accuracy, rather than mimicking the real data distribution or randomly generating a large volume of data. We find that our approach (i) quickly converges to the optimal simulation parameters in controlled experiments and (ii) can indeed discover good sets of parameters for an image rendering simulator in actual computer vision applications.
A Fast Text Similarity Measure for Large Document Collections using Multi-reference Cosine and Genetic Algorithm
Venue: arXiv cs.IR 2019
Year: 2019

One of the important factors that make a search engine fast and accurate is a concise and duplicate free index. In order to remove duplicate and near-duplicate documents from the index, a search engine needs a swift and reliable duplicate and near-duplicate text document detection system. Traditional approaches to this problem, such as brute force comparisons or simple hash-based algorithms are not suitable as they are not scalable and are not capable of detecting near-duplicate documents effectively. In this paper, a new signature-based approach to text similarity detection is introduced which is fast, scalable, reliable and needs less storage space. The proposed method is examined on popular text document data-sets such as CiteseerX, Enron, Gold Set of Near-duplicate News Articles and etc. The results are promising and comparable with the best cutting-edge algorithms, considering the accuracy and performance. The proposed method is based on the idea of using reference texts to generate signatures for text documents. The novelty of this paper is the use of genetic algorithms to generate better reference texts.
European Court of Human Right Open Data project
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents thirteen datasets for binary, multiclass and multilabel classification based on the European Court of Human Rights judgments since its creation. The interest of such datasets is explained through the prism of the researcher, the data scientist, the citizen and the legal practitioner. Contrarily to many datasets, the creation process, from the collection of raw data to the feature transformation, is provided under the form of a collection of fully automated and open-source scripts. It ensures reproducibility and a high level of confidence in the processed data, which is some of the most important issues in data governance nowadays. A first experimental campaign is performed to study some predictability properties and to establish baseline results on popular machine learning algorithms. The results are consistently good across the binary datasets with an accuracy comprised between 75.86% and 98.32% for an average accuracy of 96.45%.
A Query System for Efficiently Investigating Complex Attack Behaviors for Enterprise Security
Venue: arXiv cs.CR 2019
Year: 2019

The need for countering Advanced Persistent Threat (APT) attacks has led to the solutions that ubiquitously monitor system activities in each enterprise host, and perform timely attack investigation over the monitoring data for uncovering the attack sequence. However, existing general-purpose query systems lack explicit language constructs for expressing key properties of major attack behaviors, and their semantics-agnostic design often produces inefficient execution plans for queries. To address these limitations, we build AIQL, a novel query system that is designed with novel types of domain-specific optimizations to enable efficient attack investigation. AIQL provides (1) domain-specific data model and storage for storing the massive system monitoring data, (2) a domain-specific query language, Attack Investigation Query Language (AIQL) that integrates critical primitives for expressing major attack behaviors, and (3) an optimized query engine based on the characteristics of the data and the semantics of the query to efficiently schedule the execution. We have deployed AIQL in NEC Labs America comprising 150 hosts. In our demo, we aim to show the complete usage scenario of AIQL by (1) performing an APT attack in a controlled environment, and (2) using AIQL to investigate such attack by querying the collected system monitoring data that contains the attack traces. The audience will have the option to perform the APT attack themselves under our guidance, and interact with the system and investigate the attack via issuing queries and checking the query results through our web UI.
On the Benefits of Network-Level Cooperation in Millimeter-Wave Communications
Venue: arXiv cs.NI 2019
Year: 2019

Relaying techniques for millimeter-wave wireless networks represent a powerful solution for improving the transmission performance. In this work, we quantify the benefits in terms of delay and throughput for a random-access multi-user millimeter-wave wireless network, assisted by a full-duplex network cooperative relay. The relay is equipped with a queue for which we analyze the performance characteristics (e.g., arrival rate, service rate, average size, and stability condition). Moreover, we study two possible transmission schemes: fully directional and broadcast. In the former, the source nodes transmit a packet either to the relay or to the destination by using narrow beams, whereas, in the latter, the nodes transmit to both the destination and the relay in the same timeslot by using a wider beam, but with lower beamforming gain. In our analysis, we also take into account the beam alignment phase that occurs every time a transmitter node changes the destination node. We show how the beam alignment duration, as well as position and number of transmitting nodes, significantly affect the network performance. Moreover, we illustrate the optimal transmission scheme (i.e., broadcast or fully directional) for several system parameters and show that a fully directional transmission is not always beneficial, but, in some scenarios, broadcasting and relaying can improve the performance in terms of throughput and delay.
Proximal Online Gradient is Optimum for Dynamic Regret
Venue: arXiv cs.LG 2019
Year: 2019

In online learning, the dynamic regret metric chooses the reference (optimal) solution that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications such as online recommendation (since the customers' preference always evolves over time). While the online gradient method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this paper, we show that proximal online gradient (a general version of online gradient) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound that slightly improves existing upper bound.
Domain Transfer for 3D Pose Estimation from Color Images without Manual Annotations
Venue: arXiv cs.CV 2019
Year: 2019

We introduce a novel learning method for 3D pose estimation from color images. While acquiring annotations for color images is a difficult task, our approach circumvents this problem by learning a mapping from paired color and depth images captured with an RGB-D camera. We jointly learn the pose from synthetic depth images that are easy to generate, and learn to align these synthetic depth images with the real depth images. We show our approach for the task of 3D hand pose estimation and 3D object pose estimation, both from color images only. Our method achieves performances comparable to state-of-the-art methods on popular benchmark datasets, without requiring any annotations for the color images.
Model Cards for Model Reporting
Venue: arXiv cs.LG 2019
Year: 2019

Trained machine learning models are increasingly used to perform high-impact tasks in areas such as law enforcement, medicine, education, and employment. In order to clarify the intended use cases of machine learning models and minimize their usage in contexts for which they are not well suited, we recommend that released models be accompanied by documentation detailing their performance characteristics. In this paper, we propose a framework that we call model cards, to encourage such transparent model reporting. Model cards are short documents accompanying trained machine learning models that provide benchmarked evaluation in a variety of conditions, such as across different cultural, demographic, or phenotypic groups (e.g., race, geographic location, sex, Fitzpatrick skin type) and intersectional groups (e.g., age and race, or sex and Fitzpatrick skin type) that are relevant to the intended application domains. Model cards also disclose the context in which models are intended to be used, details of the performance evaluation procedures, and other relevant information. While we focus primarily on human-centered machine learning models in the application fields of computer vision and natural language processing, this framework can be used to document any trained machine learning model. To solidify the concept, we provide cards for two supervised models: One trained to detect smiling faces in images, and one trained to detect toxic comments in text. We propose model cards as a step towards the responsible democratization of machine learning and related AI technology, increasing transparency into how well AI technology works. We hope this work encourages those releasing trained machine learning models to accompany model releases with similar detailed evaluation numbers and other relevant documentation.
Computationally Efficient Deep Neural Network for Computed Tomography Image Reconstruction
Venue: arXiv cs.CV 2019
Year: 2019

Deep-neural-network-based image reconstruction has demonstrated promising performance in medical imaging for under-sampled and low-dose scenarios. However, it requires large amount of memory and extensive time for the training. It is especially challenging to train the reconstruction networks for three-dimensional computed tomography (CT) because of the high resolution of CT images. The purpose of this work is to reduce the memory and time consumption of the training of the reconstruction networks for CT to make it practical for current hardware, while maintaining the quality of the reconstructed images. We unrolled the proximal gradient descent algorithm for iterative image reconstruction to finite iterations and replaced the terms related to the penalty function with trainable convolutional neural networks (CNN). The network was trained greedily iteration by iteration in the image-domain on patches, which requires reasonable amount of memory and time on mainstream graphics processing unit (GPU). To overcome the local-minimum problem caused by greedy learning, we used deep UNet as the CNN and incorporated separable quadratic surrogate with ordered subsets for data fidelity, so that the solution could escape from easy local minimums and achieve better image quality. The proposed method achieved comparable image quality with state-of-the-art neural network for CT image reconstruction on 2D sparse-view and limited-angle problems on the low-dose CT challenge dataset.
Bridging the gap between regret minimization and best arm identification, with application to A/B tests
Venue: arXiv cs.LG 2019
Year: 2019

State of the art online learning procedures focus either on selecting the best alternative ("best arm identification") or on minimizing the cost (the "regret"). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also delta-PAC (with a proven guaranteed bound on the decision time), hence fulfilling at the same time regret minimization and best arm identification. This analysis sheds light on the common observation that ill-callibrated UCB-algorithms minimize regret while still identifying quickly the best arm. We also extend these results to the non-iid case faced by many practitioners. This provides a technique to make cost versus decision time compromise when doing adaptive tests with applications ranging from website A/B testing to clinical trials.
Learning One-hidden-layer Neural Networks under General Input Distributions
Venue: arXiv cs.LG 2019
Year: 2019

Significant advances have been made recently on training neural networks, where the main challenge is in solving an optimization problem with abundant critical points. However, existing approaches to address this issue crucially rely on a restrictive assumption: the training data is drawn from a Gaussian distribution. In this paper, we provide a novel unified framework to design loss functions with desirable landscape properties for a wide range of general input distributions. On these loss functions, remarkably, stochastic gradient descent theoretically recovers the true parameters with global initializations and empirically outperforms the existing approaches. Our loss function design bridges the notion of score functions with the topic of neural network optimization. Central to our approach is the task of estimating the score function from samples, which is of basic and independent interest to theoretical statistics. Traditional estimation methods (example: kernel based) fail right at the outset; we bring statistical methods of local likelihood to design a novel estimator of score functions, that provably adapts to the local geometry of the unknown density.
Deep clustering: On the link between discriminative models and K-means
Venue: arXiv cs.LG 2019
Year: 2019

In the context of recent deep clustering studies, discriminative models dominate the literature and report the most competitive performances. These models learn a deep discriminative neural network classifier in which the labels are latent. Typically, they use multinomial logistic regression posteriors and parameter regularization, as is very common in supervised learning. It is generally acknowledged that discriminative objective functions (e.g., those based on the mutual information or the KL divergence) are more flexible than generative approaches (e.g., K-means) in the sense that they make fewer assumptions about the data distributions and, typically, yield much better unsupervised deep learning results. On the surface, several recent discriminative models may seem unrelated to K-means. This study shows that these models are, in fact, equivalent to K-means under mild conditions and common posterior models and parameter regularization. We prove that, for the commonly used logistic regression posteriors, maximizing the $L_2$ regularized mutual information via an approximate alternating direction method (ADM) is equivalent to a soft and regularized K-means loss. Our theoretical analysis not only connects directly several recent state-of-the-art discriminative models to K-means, but also leads to a new soft and regularized deep K-means algorithm, which yields competitive performance on several image clustering benchmarks.
On Tracking the Physicality of Wi-Fi: A Subspace Approach
Venue: arXiv cs.IT 2019
Year: 2019

Wi-Fi channel state information (CSI) has emerged as a plausible modality for sensing different human activities as a function of modulations in the wireless signal that travels between wireless devices. Until now, most research has taken a statistical approach and/or purpose-built inference pipeline. Although interesting, these approaches struggle to sustain sensing performances beyond experimental conditions. As such, the full potential of CSI as a general-purpose sensing modality is yet to be realised. We argue a universal approach with well-grounded formalisation is necessary to characterise the relationship between wireless channel modulations (spatial and temporal) and human movement. To this end, we present a formalism for quantifying the changing part of the wireless signal modulated by human motion. Grounded in this formalisation, we then present a new subspace tracking technique to describe the channel statistics in an interpretable way, which succinctly contains the human modulated part of the channel. We characterise the signal and noise subspaces for the case of uncontrolled human movement, and show that these subspaces are dynamic. Our results demonstrate that proposed channel statistics alone can robustly reproduce state-of-the-art application-specific feature engineering baseline, however, across multiple usage scenarios. We expect, our universal channel statistics will yield an effective general-purpose featurisation of wireless channel measurements and will uncover opportunities for applying CSI for a variety of human sensing applications in a robust way.
GraphMP: I/O-Efficient Big Graph Analytics on a Single Commodity Machine
Venue: arXiv cs.DC 2019
Year: 2019

Recent studies showed that single-machine graph processing systems can be as highly competitive as cluster-based approaches on large-scale problems. While several out-of-core graph processing systems and computation models have been proposed, the high disk I/O overhead could significantly reduce performance in many practical cases. In this paper, we propose GraphMP to tackle big graph analytics on a single machine. GraphMP achieves low disk I/O overhead with three techniques. First, we design a vertex-centric sliding window (VSW) computation model to avoid reading and writing vertices on disk. Second, we propose a selective scheduling method to skip loading and processing unnecessary edge shards on disk. Third, we use a compressed edge cache mechanism to fully utilize the available memory of a machine to reduce the amount of disk accesses for edges. Extensive evaluations have shown that GraphMP could outperform existing single-machine out-of-core systems such as GraphChi, X-Stream and GridGraph by up to 51, and can be as highly competitive as distributed graph engines like Pregel+, PowerGraph and Chaos.
A new rank-order clustering algorithm for prolonging the lifetime of wireless sensor networks
Venue: arXiv cs.DC 2019
Year: 2019

Energy efficient resource management is critical for prolonging the lifetime of wireless sensor networks (WSN). Clustering of sensor nodes with the aim of distributing the traffic loads in the network is a proven approach for balanced energy consumption in WSN. The main body of literature in this topic can be classified as hierarchical and distance-based clustering techniques in which multi-hop, multi-level forwarding and distance-based criteria, respectively, are utilized for categorization of sensor nodes. In this study, we propose the Approximate Rank-Order Wireless Sensor Networks (ARO-WSN) clustering algorithm as a combined hierarchical and distance-based clustering approach. ARO-WSN algorithm which has been extensively used in the field of image processing, runs in the order of O(n) for a large data set, therefore it can be applied on WSN. The results shows that ARO-WSN outperforms the classical LEACH, LEACH-C and K-means clustering algorithms in the terms of energy consumption and network lifetime.
Path matrix and path energy of graphs
Venue: arXiv cs.DS 2019
Year: 2019

Given a graph $G$, we associate a path matrix $P$ whose $(i, j)$ entry represents the maximum number of vertex disjoint paths between the vertices $i$ and $j$, with zeros on the main diagonal. In this note, we resolve four conjectures from [M. M. Shikare, P. P. Malavadkar, S. C. Patekar, I. Gutman, \emph{On Path Eigenvalues and Path Energy of Graphs}, MATCH Commun. Math. Comput. Chem. {\bf 79} (2018), 387--398.] on the path energy of graphs and finally present efficient $O(|E| |V|^3)$ algorithm for computing the path matrix used for verifying computational results.