OpenRaiser/Intern-Atlas huggingface dataset:
Gender Prediction in English-Hindi Code-Mixed Social Media Content : Corpus and Baseline System
Venue: arXiv cs.CL 2018
Year: 2018

The rapid expansion in the usage of social media networking sites leads to a huge amount of unprocessed user generated data which can be used for text mining. Author profiling is the problem of automatically determining profiling aspects like the author's gender and age group through a text is gaining much popularity in computational linguistics. Most of the past research in author profiling is concentrated on English texts \cite{1,2}. However many users often change the language while posting on social media which is called code-mixing, and it develops some challenges in the field of text classification and author profiling like variations in spelling, non-grammatical structure and transliteration \cite{3}. There are very few English-Hindi code-mixed annotated datasets of social media content present online \cite{4}. In this paper, we analyze the task of author's gender prediction in code-mixed content and present a corpus of English-Hindi texts collected from Twitter which is annotated with author's gender. We also explore language identification of every word in this corpus. We present a supervised classification baseline system which uses various machine learning algorithms to identify the gender of an author using a text, based on character and word level features.
Immunization of networks with non-overlapping community structure
Venue: arXiv cs.SI 2018
Year: 2018

Although community structure is ubiquitous in complex networks, few works exploit this topological property to control epidemics. In this work, devoted to networks with non-overlapping community structure (i.e, a node belongs to a single community), we propose and investigate three deterministic immunization strategies. In order to characterize the influence of a node, various pieces of information are used such as the number of communities that the node can reach in one hop, the nature of the links (intra community links, inter community links), the size of the communities, and the interconnection density between communities. Numerical simulations with the Susceptible-Infected-Removed (SIR) epidemiological model are conducted on both real-world and synthetic networks. Experimental results show that the proposed strategies are more effective than classical deterministic alternatives that are agnostic of the community structure. Additionally, they outperform stochastic and deterministic strategies designed for modular networks.
Losing at Checkers is Hard
Venue: arXiv cs.CC 2018
Year: 2018

We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers where players must always be able to jump on their turn is PSPACE-complete; and (3) cooperative versions of (1) and (2) are NP-complete. We also give cooperative checkers puzzles whose solutions are the letters of the alphabet.
Evolving simple programs for playing Atari games
Venue: arXiv cs.NE 2018
Year: 2018

Cartesian Genetic Programming (CGP) has previously shown capabilities in image processing tasks by evolving programs with a function set specialized for computer vision. A similar approach can be applied to Atari playing. Programs are evolved using mixed type CGP with a function set suited for matrix operations, including image processing, but allowing for controller behavior to emerge. While the programs are relatively small, many controllers are competitive with state of the art methods for the Atari benchmark set and require less training time. By evaluating the programs of the best evolved individuals, simple but effective strategies can be found.
A Survey of Automatic Facial Micro-expression Analysis: Databases, Methods and Challenges
Venue: arXiv cs.CV 2018
Year: 2018

Over the last few years, automatic facial micro-expression analysis has garnered increasing attention from experts across different disciplines because of its potential applications in various fields such as clinical diagnosis, forensic investigation and security systems. Advances in computer algorithms and video acquisition technology have rendered machine analysis of facial micro-expressions possible today, in contrast to decades ago when it was primarily the domain of psychiatrists where analysis was largely manual. Indeed, although the study of facial micro-expressions is a well-established field in psychology, it is still relatively new from the computational perspective with many interesting problems. In this survey, we present a comprehensive review of state-of-the-art databases and methods for micro-expressions spotting and recognition. Individual stages involved in the automation of these tasks are also described and reviewed at length. In addition, we also deliberate on the challenges and future directions in this growing field of automatic facial micro-expression analysis.
Best sources forward: domain generalization through source-specific nets
Venue: arXiv cs.CV 2018
Year: 2018

A long standing problem in visual object categorization is the ability of algorithms to generalize across different testing conditions. The problem has been formalized as a covariate shift among the probability distributions generating the training data (source) and the test data (target) and several domain adaptation methods have been proposed to address this issue. While these approaches have considered the single source-single target scenario, it is plausible to have multiple sources and require adaptation to any possible target domain. This last scenario, named Domain Generalization (DG), is the focus of our work. Differently from previous DG methods which learn domain invariant representations from source data, we design a deep network with multiple domain-specific classifiers, each associated to a source domain. At test time we estimate the probabilities that a target sample belongs to each source domain and exploit them to optimally fuse the classifiers predictions. To further improve the generalization ability of our model, we also introduced a domain agnostic component supporting the final classifier. Experiments on two public benchmarks demonstrate the power of our approach.
Computing projective equivalences of special algebraic varieties
Venue: arXiv cs.CG 2018
Year: 2018

This paper is devoted to the investigation of selected situations when the computation of projective (and other) equivalences of algebraic varieties can be efficiently solved with the help of finding projective equivalences of finite sets on the projective line. In particular, we design a unifying approach that finds for two algebraic varieties $X,Y$ from special classes an associated set of automorphisms of the projective line (the so called good candidate set) consisting of candidates for the construction of possible mappings $X\rightarrow Y$. The functionality of the designed method is presented on computing projective equivalences of rational curves, on determining projective equivalences of rational ruled surfaces, on the detection of affine transformations between planar curves, and on computing similarities between two implicitly given algebraic surfaces. When possible, symmetries of given shapes are also discussed as special cases.
On the exact minimization of saturated loss functions for robust regression and subspace estimation
Venue: arXiv cs.LG 2018
Year: 2018

This paper deals with robust regression and subspace estimation and more precisely with the problem of minimizing a saturated loss function. In particular, we focus on computational complexity issues and show that an exact algorithm with polynomial time-complexity with respect to the number of data can be devised for robust regression and subspace estimation. This result is obtained by adopting a classification point of view and relating the problems to the search for a linear model that can approximate the maximal number of points with a given error. Approximate variants of the algorithms based on ramdom sampling are also discussed and experiments show that it offers an accuracy gain over the traditional RANSAC for a similar algorithmic simplicity.
Geometric Algorithms with Limited Workspace: A Survey
Venue: arXiv cs.CG 2018
Year: 2018

In the limited workspace model, we consider algorithms whose input resides in read-only memory and that use only a constant or sublinear amount of writable memory to accomplish their task. We survey recent results in computational geometry that fall into this model and that strive to achieve the lowest possible running time. In addition to discussing the state of the art, we give some illustrative examples and mention open problems for further research.
Beyond Metadata: Code-centric and Usage-based Analysis of Known Vulnerabilities in Open-source Software
Venue: arXiv cs.CR 2018
Year: 2018

The use of open-source software (OSS) is ever-increasing, and so is the number of open-source vulnerabilities being discovered and publicly disclosed. The gains obtained from the reuse of community-developed libraries may be offset by the cost of detecting, assessing, and mitigating their vulnerabilities in a timely fashion. In this paper we present a novel method to detect, assess and mitigate OSS vulnerabilities that improves on state-of-the-art approaches, which commonly depend on metadata to identify vulnerable OSS dependencies. Our solution instead is code-centric and combines static and dynamic analysis to determine the reachability of the vulnerable portion of libraries used (directly or transitively) by an application. Taking this usage into account, our approach then supports developers in choosing among the existing non-vulnerable library versions. VULAS, the tool implementing our code-centric and usage-based approach, is officially recommended by SAP to scan its Java software, and has been successfully used to perform more than 250000 scans of about 500 applications since December 2016. We report on our experience and on the lessons we learned when maturing the tool from a research prototype to an industrial-grade solution.
On Challenges of Cloud Monitoring
Venue: arXiv cs.SE 2018
Year: 2018

Cloud services are becoming increasingly popular: 60\% of information technology spending in 2016 was Cloud-based, and the size of the public Cloud service market will reach \$236B by 2020. To ensure reliable operation of the Cloud services, one must monitor their health. While a number of research challenges in the area of Cloud monitoring have been solved, problems are remaining. This prompted us to highlight three areas, which cause problems to practitioners and require further research. These three areas are as follows: A) defining health states of Cloud systems, B) creating unified monitoring environments, and C) establishing high availability strategies. In this paper we provide details of these areas and suggest a number of potential solutions to the challenges. We also show that Cloud monitoring presents exciting opportunities for novel research and practice.
Efficient Nearest Neighbors Search for Large-Scale Landmark Recognition
Venue: arXiv cs.CV 2018
Year: 2018

The problem of landmark recognition has achieved excellent results in small-scale datasets. When dealing with large-scale retrieval, issues that were irrelevant with small amount of data, quickly become fundamental for an efficient retrieval phase. In particular, computational time needs to be kept as low as possible, whilst the retrieval accuracy has to be preserved as much as possible. In this paper we propose a novel multi-index hashing method called Bag of Indexes (BoI) for Approximate Nearest Neighbors (ANN) search. It allows to drastically reduce the query time and outperforms the accuracy results compared to the state-of-the-art methods for large-scale landmark recognition. It has been demonstrated that this family of algorithms can be applied on different embedding techniques like VLAD and R-MAC obtaining excellent results in very short times on different public datasets: Holidays+Flickr1M, Oxford105k and Paris106k.
A Self-Replication Basis for Designing Complex Agents
Venue: arXiv cs.NE 2018
Year: 2018

In this work, we describe a self-replication-based mechanism for designing agents of increasing complexity. We demonstrate the validity of this approach by solving simple, standard evolutionary computation problems in simulation. In the context of these simulation results, we describe the fundamental differences of this approach when compared to traditional approaches. Further, we highlight the possible advantages of applying this approach to the problem of designing complex artificial agents, along with the potential drawbacks and issues to be addressed in the future.
Differential Evolution Algorithm Aided Turbo Channel Estimation and Multi-User Detection for G.Fast Systems in the Presence of FEXT
Venue: arXiv cs.IT 2018
Year: 2018

The ever-increasing demand for broadband Internet access has motivated the further development of the digital subscriber line to the G.fast standard in order to expand its operational band from 106 MHz to 212 MHz. Conventional far-end crosstalk (FEXT) based cancellers falter in the upstream transmission of this emerging G.fast system. In this paper, we propose a novel differential evolution algorithm (DEA) aided turbo channel estimation (CE) and multi-user detection (MUD) scheme for the G.fast upstream including the frequency band up to 212 MHz, which is capable of approaching the optimal Cramer-Rao lower bound of the channel estimate, whilst approaching the optimal maximum likelihood (ML) MUD's performance associated with perfect channel state information, and yet only imposing about 5% of its computational complexity. Explicitly, the turbo concept is exploited by iteratively exchanging information between the continuous value-based DEA assisted channel estimator and the discrete value-based DEA MUD. Our extensive simulations show that 18 dB normalized mean square error gain is attained by the channel estimator and 10 dB signal-to-noise ratio gain can be achieved by the MUD upon exploiting this iteration gain. We also quantify the influence of the CE error, of the copper length and of the impulse noise. Our study demonstrates that the proposed DEA aided turbo CE and MUD scheme is capable of offering near-capacity performance at an affordable complexity for the emerging G.fast systems.
Touching Data: A Discoverability-based Evaluation of a Visualization Interface for Tablet Computers
Venue: arXiv cs.HC 2018
Year: 2018

While a number of touch-based visualization systems have appeared in recent years, relatively little work has been done to evaluate these systems. The prevailing methods compare these systems to desktop-class applications or utilize traditional training-based usability studies. We argue that existing studies, while useful, fail to address a key aspect of mobile application usage - initial impression and discoverability-driven usability. Over the past few years, we have developed a tablet-based visualization system, Tangere, for analyzing tabular data in a multiple coordinated view configuration. This article describes a discoverability-based user study of Tangere in which the system is compared to a commercially available visualization system for tablets - Tableau's Vizable. The study highlights aspects of each system's design that resonate with study participants, and we reflect upon those findings to identify design principles for future tablet-based data visualization systems.
Stochastic WaveNet: A Generative Latent Variable Model for Sequential Data
Venue: arXiv cs.LG 2018
Year: 2018

How to model distribution of sequential data, including but not limited to speech and human motions, is an important ongoing research problem. It has been demonstrated that model capacity can be significantly enhanced by introducing stochastic latent variables in the hidden states of recurrent neural networks. Simultaneously, WaveNet, equipped with dilated convolutions, achieves astonishing empirical performance in natural speech generation task. In this paper, we combine the ideas from both stochastic latent variables and dilated convolutions, and propose a new architecture to model sequential data, termed as Stochastic WaveNet, where stochastic latent variables are injected into the WaveNet structure. We argue that Stochastic WaveNet enjoys powerful distribution modeling capacity and the advantage of parallel training from dilated convolutions. In order to efficiently infer the posterior distribution of the latent variables, a novel inference network structure is designed based on the characteristics of WaveNet architecture. State-of-the-art performances on benchmark datasets are obtained by Stochastic WaveNet on natural speech modeling and high quality human handwriting samples can be generated as well.
Selective Monitoring
Venue: arXiv cs.FL 2018
Year: 2018

We study selective monitors for labelled Markov chains. Monitors observe the outputs that are generated by a Markov chain during its run, with the goal of identifying runs as correct or faulty. A monitor is selective if it skips observations in order to reduce monitoring overhead. We are interested in monitors that minimize the expected number of observations. We establish an undecidability result for selectively monitoring general Markov chains. On the other hand, we show for non-hidden Markov chains (where any output identifies the state the Markov chain is in) that simple optimal monitors exist and can be computed efficiently, based on DFA language equivalence. These monitors do not depend on the precise transition probabilities in the Markov chain. We report on experiments where we compute these monitors for several open-source Java projects.
TrQuery: An Embedding-based Framework for Recommanding SPARQL Queries
Venue: arXiv cs.DB 2018
Year: 2018

In this paper, we present an embedding-based framework (TrQuery) for recommending solutions of a SPARQL query, including approximate solutions when exact querying solutions are not available due to incompleteness or inconsistencies of real-world RDF data. Within this framework, embedding is applied to score solutions together with edit distance so that we could obtain more fine-grained recommendations than those recommendations via edit distance. For instance, graphs of two querying solutions with a similar structure can be distinguished in our proposed framework while the edit distance depending on structural difference becomes unable. To this end, we propose a novel score model built on vector space generated in embedding system to compute the similarity between an approximate subgraph matching and a whole graph matching. Finally, we evaluate our approach on large RDF datasets DBpedia and YAGO, and experimental results show that TrQuery exhibits an excellent behavior in terms of both effectiveness and efficiency.
Nonsmooth Aggregative Games with Coupling Constraints and Infinitely Many Classes of Players
Venue: arXiv cs.GT 2018
Year: 2018

After defining a pure-action profile in a nonatomic aggregative game, where players have specific compact convex pure-action sets and nonsmooth convex cost functions, as a square-integrable function, we characterize a Wardrop equilibrium as a solution to an infinite-dimensional generalized variational inequality. We show the existence of Wardrop equilibrium and variational Wardrop equilibrium, a concept of equilibrium adapted to the presence of coupling constraints, in monotone nonatomic aggregative games. The uniqueness of (variational) Wardrop equilibrium is proved for strictly or aggregatively strictly monotone nonatomic aggregative games. We then show that, for a sequence of finite-player aggregative games with aggregative constraints, if the players' pure-action sets converge to those of a strongly (resp. aggregatively strongly) monotone nonatomic aggregative game, and the aggregative constraints in the finite-player games converge to the aggregative constraint of the nonatomic game, then a sequence of so-called variational Nash equilibria in these finite-player games converge to the variational Wardrop equilibrium in pure-action profile (resp. aggregate-action profile). In particular, it allows the construction of an auxiliary sequence of games with finite-dimensional equilibria to approximate the infinite-dimensional equilibrium in such a nonatomic game. Finally, we show how to construct auxiliary finite-player games for two general classes of nonatomic games.
Applying Autonomy with Bandwidth Allocation Models
Venue: arXiv cs.NI 2018
Year: 2018

Bandwidth Allocation Models (BAMs) are resource allocation methods used for networks in general. BAMs are currently applied for handling resources such as bandwidth allocation in MPLS DS-TE networks (LSP setup). In general, BAMs defines resource restrictions by class and allocate the available resources on demand. This is frequently necessary to manage large and complex systems like routing networks. GBAM is a new generalized BAM that, by configuration, incorporates the behavior of existing BAMs (MAM, RDM, G-RDM and AllocTC-Sharing). In effect, any current available BAM behavior is reproduced by G-BAM by simply adjusting its configuration parameters. This paper focuses on investigating the applicability of using autonomy together with Bandwidth Allocation Models (BAMs) for improve performance and facilitating the management of MPLS DS-TE networks. It is investigated the applicability of BAM switching using a framework with autonomic characteristics. In brief, it is investigated the switching among BAM behaviors and BAM reconfiguration with distinct network traffic scenarios by using GBAM. Simulation results suggest that the autonomic switching of BAM behaviors based on high-level management rules (SLAs, QoS or other police) may result in improving overall network management and operational parameters such as link utilization and preemption.
Evaluation of sentence embeddings in downstream and linguistic probing tasks
Venue: arXiv cs.CL 2018
Year: 2018

Despite the fast developmental pace of new sentence embedding methods, it is still challenging to find comprehensive evaluations of these different techniques. In the past years, we saw significant improvements in the field of sentence embeddings and especially towards the development of universal sentence encoders that could provide inductive transfer to a wide variety of downstream tasks. In this work, we perform a comprehensive evaluation of recent methods using a wide variety of downstream and linguistic feature probing tasks. We show that a simple approach using bag-of-words with a recently introduced language model for deep context-dependent word embeddings proved to yield better results in many tasks when compared to sentence encoders trained on entailment datasets. We also show, however, that we are still far away from a universal encoder that can perform consistently across several downstream tasks.