OpenRaiser/Intern-Atlas huggingface dataset:
Linear Transformations for Cross-lingual Semantic Textual Similarity
Venue: arXiv cs.CL 2018
Year: 2018

Cross-lingual semantic textual similarity systems estimate the degree of the meaning similarity between two sentences, each in a different language. State-of-the-art algorithms usually employ machine translation and combine vast amount of features, making the approach strongly supervised, resource rich, and difficult to use for poorly-resourced languages. In this paper, we study linear transformations, which project monolingual semantic spaces into a shared space using bilingual dictionaries. We propose a novel transformation, which builds on the best ideas from prior works. We experiment with unsupervised techniques for sentence similarity based only on semantic spaces and we show they can be significantly improved by the word weighting. Our transformation outperforms other methods and together with word weighting leads to very promising results on several datasets in different languages.
Cross-lingual Word Analogies using Linear Transformations between Semantic Spaces
Venue: arXiv cs.CL 2018
Year: 2018

We generalize the word analogy task across languages, to provide a new intrinsic evaluation method for cross-lingual semantic spaces. We experiment with six languages within different language families, including English, German, Spanish, Italian, Czech, and Croatian. State-of-the-art monolingual semantic spaces are transformed into a shared space using dictionaries of word translations. We compare several linear transformations and rank them for experiments with monolingual (no transformation), bilingual (one semantic space is transformed to another), and multilingual (all semantic spaces are transformed onto English space) versions of semantic spaces. We show that tested linear transformations preserve relationships between words (word analogies) and lead to impressive results. We achieve average accuracy of 51.1%, 43.1%, and 38.2% for monolingual, bilingual, and multilingual semantic spaces, respectively.
On error representation in exact-decisions number types
Venue: arXiv cs.CG 2018
Year: 2018

Accuracy-driven computation is a strategy widely used in exact-decisions number types for robust geometric algorithms. This work provides an overview on the usage of error bounds in accuracy-driven computation, compares different approaches on the representation and computation of these error bounds and points out some caveats. The stated claims are supported by experiments.
Rank of weighted digraphs with blocks
Venue: arXiv cs.DM 2018
Year: 2018

Let $G$ be a digraph and $r(G)$ be its rank. Many interesting results on the rank of an undirected graph appear in the literature, but not much information about the rank of a digraph is available. In this article, we study the rank of a digraph using the ranks of its blocks. In particular, we define classes of digraphs, namely $r_2$-digraph, and $r_0$-digraph, for which the rank can be exactly determined in terms of the ranks of subdigraphs of the blocks. Furthermore, the rank of directed trees, simple biblock graphs, and some simple block graphs are studied.
A Collaborative Ranking Model with Multiple Location-based Similarities for Venue Suggestion
Venue: arXiv cs.IR 2018
Year: 2018

Recommending venues plays a critical rule in satisfying users' needs on location-based social networks. Recent studies have explored the idea of adopting collaborative ranking (CR) for recommendation, combining the idea of learning to rank and collaborative filtering. However, CR suffers from the sparsity problem, mainly because it associates similar users based on exact matching of the venues in their check-in history. Even though research in collaborative filtering has shown that considering auxiliary information such as geographical influence, helps the model to alleviate the sparsity problem, the same direction still needs to be explored in CR. In this work, we present a CR framework that focuses on the top of the ranked list while integrating an arbitrary number of similarity functions between venues as it learns the model's parameters. We further introduce three example similarity measures based on venues' contents and locations. Incorporating cross-venue similarity measures into the model enhances the latent associations between users as similar venues are also taken into account while associating users with each other. Our experiments on the TREC Contextual Suggestion dataset show that our proposed CR model beats other state-of-the-art venue suggestion methods.
Knowledge Compilation, Width and Quantification
Venue: arXiv cs.CC 2018
Year: 2018

We generalize many results concerning the tractability of SAT and #SAT on bounded treewidth CNF-formula in the context of Quantified Boolean Formulas (QBF). To this end, we start by studying the notion of width for OBDD and observe that the blow up in size while existentially or universally projecting a block of variables in an OBDD only affects its width. We then generalize this notion of width to the more general representation of structured (deterministic) DNNF and give a similar algorithm to existentially or universally project a block of variables. Using a well-known algorithm transforming bounded treewidth CNF formula into deterministic DNNF, we are able to generalize this connection to quantified CNF which gives us as a byproduct that one can count the number of models of a bounded treewidth and bounded quantifier alternation quantified CNF in FPT time. We also give an extensive study of bounded width d-DNNF and proves the optimality of several of our results.
A Formal Account of Effectiveness Evaluation and Ranking Fusion
Venue: arXiv cs.IR 2018
Year: 2018

This paper proposes a theoretical framework which models the information provided by retrieval systems in terms of Information Theory. The proposed framework allows to formalize: (i) system effectiveness as an information theoretic similarity between system outputs and human assessments, and (ii) ranking fusion as an information quantity measure. As a result, the proposed effectiveness metric improves popular metrics in terms of formal constraints. In addition, our empirical experiments suggest that it captures quality aspects from traditional metrics, while the reverse is not true. Our work also advances the understanding of theoretical foundations of the empirically known phenomenon of effectiveness increase when combining retrieval system outputs in an unsupervised manner.
Verification and Calibration of Antenna Cross-Polarization Discrimination and Penetration Loss for Millimeter Wave Communications
Venue: arXiv cs.IT 2018
Year: 2018

This article presents measurement guidelines and verification procedures for antenna cross-polarization discrimination (XPD) and penetration loss measurements for millimeter wave (mmWave) channel sounder systems. These techniques are needed to ensure accurate and consistent measurements by different researchers at different frequencies and bandwidths. Measurements at 73 GHz are used to demonstrate and verify the guidelines, and show the consistency of the antenna XPD factor and the penetration loss at different transmitter-receiver (T-R) separation distances, thus providing a systematic method that may be used at any frequency for reliable field measurements.
Improved Query Reformulation for Concept Location using CodeRank and Document Structures
Venue: arXiv cs.SE 2018
Year: 2018

During software maintenance, developers usually deal with a significant number of software change requests. As a part of this, they often formulate an initial query from the request texts, and then attempt to map the concepts discussed in the request to relevant source code locations in the software system (a.k.a., concept location). Unfortunately, studies suggest that they often perform poorly in choosing the right search terms for a change task. In this paper, we propose a novel technique --ACER-- that takes an initial query, identifies appropriate search terms from the source code using a novel term weight --CodeRank, and then suggests effective reformulation to the initial query by exploiting the source document structures, query quality analysis and machine learning. Experiments with 1,675 baseline queries from eight subject systems report that our technique can improve 71% of the baseline queries which is highly promising. Comparison with five closely related existing techniques in query reformulation not only validates our empirical findings but also demonstrates the superiority of our technique.
Achieving Connectivity Between Wide Areas Through Self-Organising Robot Swarm Using Embodied Evolution
Venue: arXiv cs.NE 2018
Year: 2018

Abruptions to the communication infrastructure happens occasionally, where manual dedicated personnel will go out to fix the interruptions, restoring communication abilities. However, sometimes this can be dangerous to the personnel carrying out the task, which can be the case in war situations, environmental disasters like earthquakes or toxic spills or in the occurrence of fire. Therefore, human casualties can be minimised if autonomous robots are deployed that can achieve the same outcome: to establish a communication link between two previously distant but connected sites. In this paper we investigate the deployment of mobile ad hoc robots which relay traffic between them. In order to get the robots to locate themselves appropriately, we take inspiration from self-organisation and emergence in artificial life, where a common overall goal may be achieved if the correct local rules on the agents in system are invoked. We integrate the aspect of connectivity between two sites into the multirobot simulation platform known as JBotEvolver. The robot swarm is composed of Thymio II robots. In addition, we compare three heuristics, of which one uses neuroevolution (evolution of neural networks) to show how self-organisation and embodied evolution can be used within the integration. Our use of embodiment in robotic controllers shows promising results and provide solid knowledge and guidelines for further investigations.
Algorithmic Meta-Theorems for Monotone Submodular Maximization
Venue: arXiv cs.DS 2018
Year: 2018

We consider a monotone submodular maximization problem whose constraint is described by a logic formula on a graph. Formally, we prove the following three `algorithmic metatheorems.' (1) If the constraint is specified by a monadic second-order logic on a graph of bounded treewidth, the problem is solved in $n^{O(1)}$ time with an approximation factor of $O(\log n)$. (2) If the constraint is specified by a first-order logic on a graph of low degree, the problem is solved in $O(n^{1 + ε})$ time for any $ε> 0$ with an approximation factor of $2$. (3) If the constraint is specified by a first-order logic on a graph of bounded expansion, the problem is solved in $n^{O(\log k)}$ time with an approximation factor of $O(\log k)$, where $k$ is the number of variables and $O(\cdot)$ suppresses only constants independent of $k$.
Derivation of the closed-form BER expressions for DL-NOMA over Nakagami-m fading channels
Venue: arXiv cs.IT 2018
Year: 2018

NOMA is as a strong candidate for the Future Radio Access Network (FRA) due to its potential to support massive connectivity and high spectral efficiency. However, the most important drawback of NOMA is the error during Successive Interference Canceller (SIC) is implemented because of the inter-user interferences. In this paper, we derive closed-form exact Bit-Error Rate expressions for Downlink(DL) NOMA over Nakagami-m fading channels in the presence of SIC errors. The derived expressions are validated by the computer simulations. It is shown that the m parameter still represents the diversity order like as OMA systems. Besides, the BER performances of users for NOMA have substantially depended on the power allocation coefficient.
Effect of the Error Propagation on the Error Performance of Cooperative Communications with the Best Relay Selection Schemes
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, error performance of the cooperative communication systems with the best relay selection scheme is investigated in the presence of error propagation from role to destination. The error propagation expression is derived firstly when the best relay is selected within M relays. The derived end-to-end BER expression is verified with the computer simulations. It is shown that the best relay selection does not ensure M+1 diversity order under the error propagation unlike perfect decoding. In addition, the threshold selection for the relays has dominant effect on the error performance of the system.
Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
Venue: arXiv cs.DS 2018
Year: 2018

Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.
A Survey Investigating Usage of Virtual Personal Assistants
Venue: arXiv cs.HC 2018
Year: 2018

Despite significant improvements in automatic speech recognition and spoken language understanding - human interaction with Virtual Personal Assistants (VPAs) through speech remains irregular and sporadic. According to recent studies, currently the usage of VPAs is constrained to basic tasks such as checking facts, playing music, and obtaining weather updates.In this paper, we present results of a survey (N = 118) that analyses usage of VPAs by frequent and infrequent users. We investigate how usage experience, performance expectations, and privacy concerns differ between these two groups. The results indicate that, compared with infrequent users, frequent users of VPAs are more satisfied with their assistants, more eager to use them in a variety of settings, yet equally concerned about their privacy.
Subset synchronization of DFAs and PFAs, and some other results
Venue: arXiv cs.FL 2018
Year: 2018

This paper contains results which arose from the research which led to arXiv:1801.10436, but which did not fit in arXiv:1801.10436. So arXiv:1801.10436 contains the highlight results, but there are more results which are interesting enough to be shared.
Learning to Segment Medical Images with Scribble-Supervision Alone
Venue: arXiv cs.CV 2018
Year: 2018

Semantic segmentation of medical images is a crucial step for the quantification of healthy anatomy and diseases alike. The majority of the current state-of-the-art segmentation algorithms are based on deep neural networks and rely on large datasets with full pixel-wise annotations. Producing such annotations can often only be done by medical professionals and requires large amounts of valuable time. Training a medical image segmentation network with weak annotations remains a relatively unexplored topic. In this work we investigate training strategies to learn the parameters of a pixel-wise segmentation network from scribble annotations alone. We evaluate the techniques on public cardiac (ACDC) and prostate (NCI-ISBI) segmentation datasets. We find that the networks trained on scribbles suffer from a remarkably small degradation in Dice of only 2.9% (cardiac) and 4.5% (prostate) with respect to a network trained on full annotations.
How to identify the roots of broad research topics and fields? The introduction of RPYS sampling using the example of climate change research
Venue: arXiv cs.DL 2018
Year: 2018

Since the introduction of the reference publication year spectroscopy (RPYS) method and the corresponding program CRExplorer, many studies have been published revealing the historical roots of topics, fields, and researchers. The application of the method was restricted up to now by the available memory of the computer used for running the CRExplorer. Thus, many users could not perform RPYS for broader research fields or topics. In this study, we present various sampling methods to solve this problem: random, systematic, and cluster sampling. We introduce the script language of the CRExplorer which can be used to draw many samples from the population dataset. Based on a large dataset of publications from climate change research, we compare RPYS results using population data with RPYS results using different sampling techniques. From our comparison with the full RPYS (population spectrogram), we conclude that the cluster sampling performs worst and the systematic sampling performs best. The random sampling also performs very well but not as well as the systematic sampling. The study therefore demonstrates the fruitfulness of the sampling approach for applying RPYS.
Know When to Fold 'Em: Self-Assembly of Shapes by Folding in Oritatami
Venue: arXiv cs.DS 2018
Year: 2018

An oritatami system (OS) is a theoretical model of self-assembly via co-transcriptional folding. It consists of a growing chain of beads which can form bonds with each other as they are transcribed. During the transcription process, the $δ$ most recently produced beads dynamically fold so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $δ$ is called the delay and is related to the transcription rate in nature. This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale n >= 3, by an OS with delay 1. We also show that any shape can be folded at the smaller scale 2 by an OS with unbounded delay. This leads us to investigate the influence of delay and to prove that, for all δ > 2, there are shapes that can be folded (at scale 1) with delay δ but not with delay δ'<δ. These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.
A network-based citation indicator of scientific performance
Venue: arXiv cs.DL 2018
Year: 2018

Scientists are embedded in social and information networks that influence and are influenced by the quality of their scientific work, its impact, and the recognition they receive. Here we quantify the systematic relationship between a scientist's position in the network of scientific collaborations and the citations they receive. As expected, we find that authors closer to others in this network are, on average, more highly cited than those further away from others. We construct a novel indicator, the s-index, that explicitly captures performance linked to network position along two complimentary dimensions: performance expected due to network position and performance relative to this position. The basis of our approach is to represent an author's network position through their distribution of distances to other authors. The s-index then ranks (1) the citation potential of an individual's network position relative to all other authors, and (2) the citations they accrue relative to authors that have a comparable network position. Characterizing scientists through these two complimentary dimensions can be used to make more informed evaluations in a networked environment. For example, it can identify individuals that play an important role in diffusing scientific ideas. It also sheds a new light on central debates in the Science of Science, namely the impact of author teams and comparisons of impact across scientific fields.
Orthogonal Matching Pursuit for Text Classification
Venue: arXiv cs.LG 2018
Year: 2018

In text classification, the problem of overfitting arises due to the high dimensionality, making regularization essential. Although classic regularizers provide sparsity, they fail to return highly accurate models. On the contrary, state-of-the-art group-lasso regularizers provide better results at the expense of low sparsity. In this paper, we apply a greedy variable selection algorithm, called Orthogonal Matching Pursuit, for the text classification task. We also extend standard group OMP by introducing overlapping Group OMP to handle overlapping groups of features. Empirical analysis verifies that both OMP and overlapping GOMP constitute powerful regularizers, able to produce effective and very sparse models. Code and data are available online: https://github.com/y3nk0/OMP-for-Text-Classification .
The Bottleneck Simulator: A Model-based Deep Reinforcement Learning Approach
Venue: arXiv cs.LG 2018
Year: 2018

Deep reinforcement learning has recently shown many impressive successes. However, one major obstacle towards applying such methods to real-world problems is their lack of data-efficiency. To this end, we propose the Bottleneck Simulator: a model-based reinforcement learning method which combines a learned, factorized transition model of the environment with rollout simulations to learn an effective policy from few examples. The learned transition model employs an abstract, discrete (bottleneck) state, which increases sample efficiency by reducing the number of model parameters and by exploiting structural properties of the environment. We provide a mathematical analysis of the Bottleneck Simulator in terms of fixed points of the learned policy, which reveals how performance is affected by four distinct sources of error: an error related to the abstract space structure, an error related to the transition model estimation variance, an error related to the transition model estimation bias, and an error related to the transition model class bias. Finally, we evaluate the Bottleneck Simulator on two natural language processing tasks: a text adventure game and a real-world, complex dialogue response selection task. On both tasks, the Bottleneck Simulator yields excellent performance beating competing approaches.