OpenRaiser/Intern-Atlas huggingface dataset:
A theory of the phenomenology of multipopulation genetic algorithm with an application to the Ising model
Venue: arXiv cs.NE 2018
Year: 2018

Genetic algorithm (GA) is a stochastic metaheuristic process consisting on the evolution of a population of candidate solutions for a given optimization problem. By extension, multipopulation genetic algorithm (MPGA) aims for efficiency by evolving many populations, or islands, in parallel and performing migrations between them periodically. The connectivity between islands constrains the directions of migration and characterizes MPGA as a dynamic process over a network. As such, predicting the evolution of the quality of the solutions is a difficult challenge, implying in the waste of computer resources and energy when the parameters are inadequate. By using models derived from statistical mechanics, this work aims to estimate equations for the study of dynamics in relation to the connectivity in MPGA. To illustrate the importance of understanding MPGA, we show its application as an efficient alternative to the thermalization phase of Metropolis-Hastings algorithm applied to the Ising model.
The Geometry of Culture: Analyzing Meaning through Word Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

We demonstrate the utility of a new methodological tool, neural-network word embedding models, for large-scale text analysis, revealing how these models produce richer insights into cultural associations and categories than possible with prior methods. Word embeddings represent semantic relations between words as geometric relationships between vectors in a high-dimensional space, operationalizing a relational model of meaning consistent with contemporary theories of identity and culture. We show that dimensions induced by word differences (e.g. man - woman, rich - poor, black - white, liberal - conservative) in these vector spaces closely correspond to dimensions of cultural meaning, and the projection of words onto these dimensions reflects widely shared cultural connotations when compared to surveyed responses and labeled historical data. We pilot a method for testing the stability of these associations, then demonstrate applications of word embeddings for macro-cultural investigation with a longitudinal analysis of the coevolution of gender and class associations in the United States over the 20th century and a comparative analysis of historic distinctions between markers of gender and class in the U.S. and Britain. We argue that the success of these high-dimensional models motivates a move towards "high-dimensional theorizing" of meanings, identities and cultural processes.
Logistic Regression: The Importance of Being Improper
Venue: arXiv cs.LG 2018
Year: 2018

Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (2014) showed that this is unfortunately unimprovable. Starting with the simple observation that the logistic loss is $1$-mixable, we design a new efficient improper learning algorithm for online logistic regression that circumvents the aforementioned lower bound with a regret bound exhibiting a doubly-exponential improvement in dependence on the predictor norm. This provides a positive resolution to a variant of the COLT 2012 open problem of McMahan and Streeter (2012) when improper learning is allowed. This improvement is obtained both in the online setting and, with some extra work, in the batch statistical setting with high probability. We also show that the improved dependence on predictor norm is near-optimal. Leveraging this improved dependency on the predictor norm yields the following applications: (a) we give algorithms for online bandit multiclass learning with the logistic loss with an $\tilde{O}(\sqrt{n})$ relative mistake bound across essentially all parameter ranges, thus providing a solution to the COLT 2009 open problem of Abernethy and Rakhlin (2009), and (b) we give an adaptive algorithm for online multiclass boosting with optimal sample complexity, thus partially resolving an open problem of Beygelzimer et al. (2015) and Jung et al. (2017). Finally, we give information-theoretic bounds on the optimal rates for improper logistic regression with general function classes, thereby characterizing the extent to which our improvement for linear classes extends to other parametric and even nonparametric settings.
A Face Recognition Signature Combining Patch-based Features with Soft Facial Attributes
Venue: arXiv cs.CV 2018
Year: 2018

This paper focuses on improving face recognition performance with a new signature combining implicit facial features with explicit soft facial attributes. This signature has two components: the existing patch-based features and the soft facial attributes. A deep convolutional neural network adapted from state-of-the-art networks is used to learn the soft facial attributes. Then, a signature matcher is introduced that merges the contributions of both patch-based features and the facial attributes. In this matcher, the matching scores computed from patch-based features and the facial attributes are combined to obtain a final matching score. The matcher is also extended so that different weights are assigned to different facial attributes. The proposed signature and matcher have been evaluated with the UR2D system on the UHDB31 and IJB-A datasets. The experimental results indicate that the proposed signature achieve better performance than using only patch-based features. The Rank-1 accuracy is improved significantly by 4% and 0.37% on the two datasets when compared with the UR2D system.
Automatic Identification of Closely-related Indian Languages: Resources and Experiments
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we discuss an attempt to develop an automatic language identification system for 5 closely-related Indo-Aryan languages of India, Awadhi, Bhojpuri, Braj, Hindi and Magahi. We have compiled a comparable corpora of varying length for these languages from various resources. We discuss the method of creation of these corpora in detail. Using these corpora, a language identification system was developed, which currently gives state of the art accuracy of 96.48\%. We also used these corpora to study the similarity between the 5 languages at the lexical level, which is the first data-based study of the extent of closeness of these languages.
Efficient File Delivery for Coded Prefetching in Shared Cache Networks with Multiple Requests Per User
Venue: arXiv cs.IT 2018
Year: 2018

We consider a centralized caching network, where a server serves several groups of users, each having a common shared homogeneous fixed-size cache and requesting arbitrary multiple files. An existing coded prefetching scheme is employed where each file is broken into multiple fragments and each cache stores multiple coded packets each formed by XORing fragments from different files. For such a system, we propose an efficient file delivery scheme with explicit constructions by the server to meet the arbitrary multi-requests of all user-groups. Specifically, the stored coded packets of each cache are classified into four types based on the composition of the file fragments encoded. A delivery strategy is developed, which separately delivers part of each packet type first and then combinatorially delivers the remaining different packet types in the last stage. The rate as well as the worst rate of the proposed delivery scheme are analyzed. We show that our caching model and delivery scheme can incorporate some existing coded caching schemes as special cases. Moreover, for the special case of uniform requests and uncoded prefetching, we make a comparison with existing results, and show that our approach can achieve a lower delivery rate. We also provide numerical results on the delivery rate for the proposed scheme.
A Switch to the Concern of User: Importance Coefficient in Utility Distribution and Message Importance Measure
Venue: arXiv cs.IT 2018
Year: 2018

This paper mainly focuses on the utilization frequency in receiving end of communication systems, which shows the inclination of the user about different symbols. When the average number of use is limited, a specific utility distribution is proposed on the best effort in term of fairness, which is also the closest one to occurring probability in the relative entropy. Similar to a switch, its parameter can be selected to make it satisfy different users' requirements: negative parameter means the user focus on high-probability events and positive parameter means the user is interested in small-probability events. In fact, the utility distribution is a measure of message importance in essence. It illustrates the meaning of message importance measure (MIM), and extend it to the general case by selecting the parameter. Numerical results show that this utility distribution characterizes the message importance like MIM and its parameter determines the concern of users.
A comparative study above two self-tuning controllers with application to the control of synchronous generator excitation system
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents two self-tuning control structures synthesized through the minimization of two criterion functions. It is described the computation methodology of the control laws, both being particularized for the case of the synchronous generator's excitation control. The parameters estimator is considered the recursive least square error (RLSE) algorithm. In order to validate the considered control structures, two comparative study cases by computer simulation are presented.
A Low-Resolution ADC Module Assisted Hybrid Beamforming Architecture for mmWave Communications
Venue: arXiv cs.IT 2018
Year: 2018

We propose a low-resolution analog-to-digital converter (ADC) module assisted hybrid beamforming architecture for millimeter-wave (mmWave) communications. We prove that the proposed low-cost and flexible architecture can reduce the beam training time and complexity dramatically without degradation in the data transmission performance. In addition, we design a fast beam training method which is suitable for the proposed system architecture. The proposed beam training method requires only L + 1 (where L is the number of paths) time slots which is smaller compared to the state-of-the-art.
Connectionist Recommendation in the Wild: On the utility and scrutability of neural networks for personalized course guidance
Venue: arXiv cs.AI 2018
Year: 2018

The aggregate behaviors of users can collectively encode deep semantic information about the objects with which they interact. In this paper, we demonstrate novel ways in which the synthesis of these data can illuminate the terrain of users' environment and support them in their decision making and wayfinding. A novel application of Recurrent Neural Networks and skip-gram models, approaches popularized by their application to modeling language, are brought to bear on student university enrollment sequences to create vector representations of courses and map out traversals across them. We present demonstrations of how scrutability from these neural networks can be gained and how the combination of these techniques can be seen as an evolution of content tagging and a means for a recommender to balance user preferences inferred from data with those explicitly specified. From validation of the models to the development of a UI, we discuss additional requisite functionality informed by the results of a usability study leading to the ultimate deployment of the system at a university.
Local verification of global proofs
Venue: arXiv cs.DC 2018
Year: 2018

In this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof for the correctness of the state of the system, and the nodes need to verify this proof by looking at only their local neighborhood in the system. Previous works have studied the model where each node is given its own, possibly unique, part of the proof as input. The cost of a proof is the maximum size of an individual label. We compare this model to a model where each node has access to the same global proof, and the cost is the size of this global proof. It is easy to see that a global proof can always include all of the local proofs, and every local proof can be a copy of the global proof. We show that there exists properties that exhibit these relative proof sizes, and also properties that are somewhere in between. In addition, we introduce a new lower bound technique and use it to prove a tight lower bound on the complexity of reversing distributed decision and establish a link between communication complexity and distributed proof complexity.
On Expansion and Resolution in CEGAR Based QBF Solving
Venue: arXiv cs.LO 2018
Year: 2018

A quantified Boolean formula (QBF) is a propositional formula extended with universal and existential quantification over propositions. There are two methodologies in CEGAR based QBF solving techniques, one that is based on a refinement loop that builds partial expansions and a more recent one that is based on the communication of satisfied clauses. Despite their algorithmic similarity, their performance characteristics in experimental evaluations are very different and in many cases orthogonal. We compare those CEGAR approaches using proof theory developed around QBF solving and present a unified calculus that combines the strength of both approaches. Lastly, we implement the new calculus and confirm experimentally that the theoretical improvements lead to improved performance.
Sparse Recovery over Graph Incidence Matrices
Venue: arXiv cs.IT 2018
Year: 2018

Classical results in sparse recovery guarantee the exact reconstruction of $s$-sparse signals under assumptions on the dictionary that are either too strong or NP-hard to check. Moreover, such results may be pessimistic in practice since they are based on a worst-case analysis. In this paper, we consider the sparse recovery of signals defined over a graph, for which the dictionary takes the form of an incidence matrix. We derive necessary and sufficient conditions for sparse recovery, which depend on properties of the cycles of the graph that can be checked in polynomial time. We also derive support-dependent conditions for sparse recovery that depend only on the intersection of the cycles of the graph with the support of the signal. Finally, we exploit sparsity properties on the measurements and the structure of incidence matrices to propose a specialized sub-graph-based recovery algorithm that outperforms the standard $\ell_1$-minimization approach.
Proactive Received Power Prediction Using Machine Learning and Depth Images for mmWave Networks
Venue: arXiv cs.NI 2018
Year: 2018

This study demonstrates the feasibility of the proactive received power prediction by leveraging spatiotemporal visual sensing information toward the reliable millimeter-wave (mmWave) networks. Since the received power on a mmWave link can attenuate aperiodically due to a human blockage, the long-term series of the future received power cannot be predicted by analyzing the received signals before the blockage occurs. We propose a novel mechanism that predicts a time series of the received power from the next moment to even several hundred milliseconds ahead. The key idea is to leverage the camera imagery and machine learning (ML). The time-sequential images can involve the spatial geometry and the mobility of obstacles representing the mmWave signal propagation. ML is used to build the prediction model from the dataset of sequential images labeled with the received power in several hundred milliseconds ahead of when each image is obtained. The simulation and experimental evaluations using IEEE 802.11ad devices and a depth camera show that the proposed mechanism employing convolutional LSTM predicted a time series of the received power in up to 500 ms ahead at an inference time of less than 3 ms with a root-mean-square error of 3.5 dB.
Predicting the Future with Transformational States
Venue: arXiv cs.CV 2018
Year: 2018

An intelligent observer looks at the world and sees not only what is, but what is moving and what can be moved. In other words, the observer sees how the present state of the world can transform in the future. We propose a model that predicts future images by learning to represent the present state and its transformation given only a sequence of images. To do so, we introduce an architecture with a latent state composed of two components designed to capture (i) the present image state and (ii) the transformation between present and future states, respectively. We couple this latent state with a recurrent neural network (RNN) core that predicts future frames by transforming past states into future states by applying the accumulated state transformation with a learned operator. We describe how this model can be integrated into an encoder-decoder convolutional neural network (CNN) architecture that uses weighted residual connections to integrate representations of the past with representations of the future. Qualitatively, our approach generates image sequences that are stable and capture realistic motion over multiple predicted frames, without requiring adversarial training. Quantitatively, our method achieves prediction results comparable to state-of-the-art results on standard image prediction benchmarks (Moving MNIST, KTH, and UCF101).
A Common Framework for Natural Gradient and Taylor based Optimisation using Manifold Theory
Venue: arXiv cs.LG 2018
Year: 2018

This technical report constructs a theoretical framework to relate standard Taylor approximation based optimisation methods with Natural Gradient (NG), a method which is Fisher efficient with probabilistic models. Such a framework will be shown to also provide mathematical justification to combine higher order methods with the method of NG.
Heat Kernel analysis of Syntactic Structures
Venue: arXiv cs.CL 2018
Year: 2018

We consider two different data sets of syntactic parameters and we discuss how to detect relations between parameters through a heat kernel method developed by Belkin-Niyogi, which produces low dimensional representations of the data, based on Laplace eigenfunctions, that preserve neighborhood information. We analyze the different connectivity and clustering structures that arise in the two datasets, and the regions of maximal variance in the two-parameter space of the Belkin-Niyogi construction, which identify preferable choices of independent variables. We compute clustering coefficients and their variance.
Generative Design in Minecraft (GDMC), Settlement Generation Competition
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces the settlement generation competition for Minecraft, the first part of the Generative Design in Minecraft challenge. The settlement generation competition is about creating Artificial Intelligence (AI) agents that can produce functional, aesthetically appealing and believable settlements adapted to a given Minecraft map - ideally at a level that can compete with human created designs. The aim of the competition is to advance procedural content generation for games, especially in overcoming the challenges of adaptive and holistic PCG. The paper introduces the technical details of the challenge, but mostly focuses on what challenges this competition provides and why they are scientifically relevant.
WebSeg: Learning Semantic Segmentation from Web Searches
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we improve semantic segmentation by automatically learning from Flickr images associated with a particular keyword, without relying on any explicit user annotations, thus substantially alleviating the dependence on accurate annotations when compared to previous weakly supervised methods. To solve such a challenging problem, we leverage several low-level cues (such as saliency, edges, etc.) to help generate a proxy ground truth. Due to the diversity of web-crawled images, we anticipate a large amount of 'label noise' in which other objects might be present. We design an online noise filtering scheme which is able to deal with this label noise, especially in cluttered images. We use this filtering strategy as an auxiliary module to help assist the segmentation network in learning cleaner proxy annotations. Extensive experiments on the popular PASCAL VOC 2012 semantic segmentation benchmark show surprising good results in both our WebSeg (mIoU = 57.0%) and weakly supervised (mIoU = 63.3%) settings.
A Classification Model for Sensing Human Trust in Machines Using EEG and GSR
Venue: arXiv cs.HC 2018
Year: 2018

Today, intelligent machines \emph{interact and collaborate} with humans in a way that demands a greater level of trust between human and machine. A first step towards building intelligent machines that are capable of building and maintaining trust with humans is the design of a sensor that will enable machines to estimate human trust level in real-time. In this paper, two approaches for developing classifier-based empirical trust sensor models are presented that specifically use electroencephalography (EEG) and galvanic skin response (GSR) measurements. Human subject data collected from 45 participants is used for feature extraction, feature selection, classifier training, and model validation. The first approach considers a general set of psychophysiological features across all participants as the input variables and trains a classifier-based model for each participant, resulting in a trust sensor model based on the general feature set (i.e., a "general trust sensor model"). The second approach considers a customized feature set for each individual and trains a classifier-based model using that feature set, resulting in improved mean accuracy but at the expense of an increase in training time. This work represents the first use of real-time psychophysiological measurements for the development of a human trust sensor. Implications of the work, in the context of trust management algorithm design for intelligent machines, are also discussed.
A Decision Tree Approach to Predicting Recidivism in Domestic Violence
Venue: arXiv cs.LG 2018
Year: 2018

Domestic violence (DV) is a global social and public health issue that is highly gendered. Being able to accurately predict DV recidivism, i.e., re-offending of a previously convicted offender, can speed up and improve risk assessment procedures for police and front-line agencies, better protect victims of DV, and potentially prevent future re-occurrences of DV. Previous work in DV recidivism has employed different classification techniques, including decision tree (DT) induction and logistic regression, where the main focus was on achieving high prediction accuracy. As a result, even the diagrams of trained DTs were often too difficult to interpret due to their size and complexity, making decision-making challenging. Given there is often a trade-off between model accuracy and interpretability, in this work our aim is to employ DT induction to obtain both interpretable trees as well as high prediction accuracy. Specifically, we implement and evaluate different approaches to deal with class imbalance as well as feature selection. Compared to previous work in DV recidivism prediction that employed logistic regression, our approach can achieve comparable area under the ROC curve results by using only 3 of 11 available features and generating understandable decision trees that contain only 4 leaf nodes.