OpenRaiser/Intern-Atlas huggingface dataset:
Conditional Accelerated Lazy Stochastic Gradient Descent
Venue: arXiv cs.LG 2018
Year: 2018

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O\left(\frac{1}{\varepsilon^2}\right)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan and Kale [2012] with convergence rate $O\left(\frac{1}{\varepsilon^4}\right)$.
Complexity of Correspondence Homomorphisms
Venue: arXiv cs.DM 2018
Year: 2018

Correspondence homomorphisms are both a generalization of standard homomorphisms and a generalization of correspondence colourings. For a fixed target graph $H$, the problem is to decide whether an input graph $G$, with each edge labeled by a pair of permutations of $V(H)$, admits a homomorphism to $H$ `corresponding' to the labels, in a sense explained below. We classify the complexity of this problem as a function of the fixed graph $H$. It turns out that there is dichotomy -- each of the problems is polynomial-time solvable or NP-complete. While most graphs $H$ yield NP-complete problems, there are interesting cases of graphs $H$ for which the problem is solved by Gaussian elimination. We also classify the complexity of the analogous correspondence {\em list homomorphism} problems, and also the complexity of a {\em bipartite version} of both problems. We emphasize the proofs for the case when $H$ is reflexive, but, for the record, we include a rough sketch of the remaining proofs in an Appendix.
Construction of a Japanese Word Similarity Dataset
Venue: arXiv cs.CL 2018
Year: 2018

An evaluation of distributed word representation is generally conducted using a word similarity task and/or a word analogy task. There are many datasets readily available for these tasks in English. However, evaluating distributed representation in languages that do not have such resources (e.g., Japanese) is difficult. Therefore, as a first step toward evaluating distributed representations in Japanese, we constructed a Japanese word similarity dataset. To the best of our knowledge, our dataset is the first resource that can be used to evaluate distributed representations in Japanese. Moreover, our dataset contains various parts of speech and includes rare words in addition to common words.
Deep Sets
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of designing models for machine learning tasks defined on \emph{sets}. In contrast to traditional approach of operating on fixed dimensional vectors, we consider objective functions defined on sets that are invariant to permutations. Such problems are widespread, ranging from estimation of population statistics \cite{poczos13aistats}, to anomaly detection in piezometer data of embankment dams \cite{Jung15Exploration}, to cosmology \cite{Ntampaka16Dynamical,Ravanbakhsh16ICML1}. Our main theorem characterizes the permutation invariant functions and provides a family of functions to which any permutation invariant objective function must belong. This family of functions has a special structure which enables us to design a deep network architecture that can operate on sets and which can be deployed on a variety of scenarios including both unsupervised and supervised learning tasks. We also derive the necessary and sufficient conditions for permutation equivariance in deep models. We demonstrate the applicability of our method on population statistic estimation, point cloud classification, set expansion, and outlier detection.
On the Minimization of Convex Functionals of Probability Distributions Under Band Constraints
Venue: arXiv cs.IT 2018
Year: 2018

The problem of minimizing convex functionals of probability distributions is solved under the assumption that the density of every distribution is bounded from above and below. A system of sufficient and necessary first-order optimality conditions as well as a bound on the optimality gap of feasible candidate solutions are derived. Based on these results, two numerical algorithms are proposed that iteratively solve the system of optimality conditions on a grid of discrete points. Both algorithms use a block coordinate descent strategy and terminate once the optimality gap falls below the desired tolerance. While the first algorithm is conceptually simpler and more efficient, it is not guaranteed to converge for objective functions that are not strictly convex. This shortcoming is overcome in the second algorithm, which uses an additional outer proximal iteration, and, which is proven to converge under mild assumptions. Two examples are given to demonstrate the theoretical usefulness of the optimality conditions as well as the high efficiency and accuracy of the proposed numerical algorithms.
Towards a Quantum World Wide Web
Venue: arXiv cs.AI 2018
Year: 2018

We elaborate a quantum model for the meaning associated with corpora of written documents, like the pages forming the World Wide Web. To that end, we are guided by how physicists constructed quantum theory for microscopic entities, which unlike classical objects cannot be fully represented in our spatial theater. We suggest that a similar construction needs to be carried out by linguists and computational scientists, to capture the full meaning carried by collections of documental entities. More precisely, we show how to associate a quantum-like 'entity of meaning' to a 'language entity formed by printed documents', considering the latter as the collection of traces that are left by the former, in specific results of search actions that we describe as measurements. In other words, we offer a perspective where a collection of documents, like the Web, is described as the space of manifestation of a more complex entity - the QWeb - which is the object of our modeling, drawing its inspiration from previous studies on operational-realistic approaches to quantum physics and quantum modeling of human cognition and decision-making. We emphasize that a consistent QWeb model needs to account for the observed correlations between words appearing in printed documents, e.g., co-occurrences, as the latter would depend on the 'meaning connections' existing between the concepts that are associated with these words. In that respect, we show that both 'context and interference (quantum) effects' are required to explain the probabilities calculated by counting the relative number of documents containing certain words and co-ocurrrences of words.
Can you tell where in India I am from? Comparing humans and computers on fine-grained race face classification
Venue: arXiv cs.CV 2018
Year: 2018

Faces form the basis for a rich variety of judgments in humans, yet the underlying features remain poorly understood. Although fine-grained distinctions within a race might more strongly constrain possible facial features used by humans than in case of coarse categories such as race or gender, such fine grained distinctions are relatively less studied. Fine-grained race classification is also interesting because even humans may not be perfectly accurate on these tasks. This allows us to compare errors made by humans and machines, in contrast to standard object detection tasks where human performance is nearly perfect. We have developed a novel face database of close to 1650 diverse Indian faces labeled for fine-grained race (South vs North India) as well as for age, weight, height and gender. We then asked close to 130 human subjects who were instructed to categorize each face as belonging toa Northern or Southern state in India. We then compared human performance on this task with that of computational models trained on the ground-truth labels. Our main results are as follows: (1) Humans are highly consistent (average accuracy: 63.6%), with some faces being consistently classified with > 90% accuracy and others consistently misclassified with < 30% accuracy; (2) Models trained on ground-truth labels showed slightly worse performance (average accuracy: 62%) but showed higher accuracy (72.2%) on faces classified with > 80% accuracy by humans. This was true for models trained on simple spatial and intensity measurements extracted from faces as well as deep neural networks trained on race or gender classification; (3) Using overcomplete banks of features derived from each face part, we found that mouth shape was the single largest contributor towards fine-grained race classification, whereas distances between face parts was the strongest predictor of gender.
Constructing an LDPC Code Containing a Given Vector
Venue: arXiv cs.IT 2018
Year: 2018

The coding problem considered in this work is to construct a linear code $\mathcal{C}$ of given length $n$ and dimension $k<n$ such that a given binary vector $\mathbf{r} \in \mathbb{F}^{n}$ is contained in the code. We study a recent solution of this problem by Müelich and Bossert, which is based on LDPC codes. We address two open questions of this construction. First, we show that under certain assumptions, this code construction is possible with high probability if $\mathbf{r}$ is chosen uniformly at random. Second, we calculate the uncertainty of $\mathbf{r}$ given the constructed code $\mathcal{C}$. We present an application of this problem in the field of Physical Unclonable Functions (PUFs).
Competitive Equilibrium with Indivisible Goods and Generic Budgets
Venue: arXiv cs.GT 2018
Year: 2018

Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [Foley'67, Varian'74]. Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible, even in the simple two-agent, single-item market. Yet, it is easy to see that once the two budgets are slightly perturbed (made generic), a competitive equilibrium does exist. In this paper we aim to extend this approach beyond the single-item case, and study the existence of equilibria in markets with two agents and additive preferences over multiple items. We show that for agents with equal budgets, making the budgets generic -- by adding vanishingly small random perturbations -- ensures the existence of an equilibrium. We further consider agents with arbitrary non-equal budgets, representing non-equal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among non-equal agents, and that it exists in cases of interest (like when the agents have identical preferences) if budgets are perturbed. Our results open opportunities for future research on generic equilibrium existence and fair treatment of non-equals.
The Deep Poincaré Map: A Novel Approach for Left Ventricle Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Precise segmentation of the left ventricle (LV) within cardiac MRI images is a prerequisite for the quantitative measurement of heart function. However, this task is challenging due to the limited availability of labeled data and motion artifacts from cardiac imaging. In this work, we present an iterative segmentation algorithm for LV delineation. By coupling deep learning with a novel dynamic-based labeling scheme, we present a new methodology where a policy model is learned to guide an agent to travel over the the image, tracing out a boundary of the ROI -- using the magnitude difference of the Poincaré map as a stopping criterion. Our method is evaluated on two datasets, namely the Sunnybrook Cardiac Dataset (SCD) and data from the STACOM 2011 LV segmentation challenge. Our method outperforms the previous research over many metrics. In order to demonstrate the transferability of our method we present encouraging results over the STACOM 2011 data, when using a model trained on the SCD dataset.
Cheetah Experimental Platform Web 1.0: Cleaning Pupillary Data
Venue: arXiv cs.HC 2018
Year: 2018

Recently, researchers started using cognitive load in various settings, e.g., educational psychology, cognitive load theory, or human-computer interaction. Cognitive load characterizes a tasks' demand on the limited information processing capacity of the brain. The widespread adoption of eye-tracking devices led to increased attention for objectively measuring cognitive load via pupil dilation. However, this approach requires a standardized data processing routine to reliably measure cognitive load. This technical report presents CEP-Web, an open source platform to providing state of the art data processing routines for cleaning pupillary data combined with a graphical user interface, enabling the management of studies and subjects. Future developments will include the support for analyzing the cleaned data as well as support for Task-Evoked Pupillary Response (TEPR) studies.
How Reliable and Capable is Multi-Connectivity?
Venue: arXiv cs.IT 2018
Year: 2018

Multi-connectivity (MCo) is considered to be a key strategy for enabling reliable transmissions and enhanced data rates in fifth-generation mobile networks, as it provides multiple links from source to destination. In this work, we quantify the communication performance of MCo in terms of outage probability and throughput. For doing so, we establish a simple, yet accurate analytical framework at high signal-to-noise ratio (SNR), in which the number of links, the spectral efficiency, the path loss, and the SNR are incorporated, giving new insights into the potentials of MCo as compared with single-connectivity (SCo). These are our main contributions: (1) finding the exact coding gain of the outage probability for parallel block-fading channels; (2) quantifying the performance improvement of MCo over SCo in terms of SNR gain; and (3) comparing optimal and suboptimal combining algorithms for MCo at the receiver side, namely joint decoding, selection combining, and maximal-ratio combining, also in terms of SNR gain. Additionally, we apply our analytical framework to real field channel measurements and thereby illustrate the potential of MCo to achieve high reliability and high data rates in real cellular networks.
Efficient Parallel Translating Embedding For Knowledge Graphs
Venue: arXiv cs.AI 2018
Year: 2018

Knowledge graph embedding aims to embed entities and relations of knowledge graphs into low-dimensional vector spaces. Translating embedding methods regard relations as the translation from head entities to tail entities, which achieve the state-of-the-art results among knowledge graph embedding methods. However, a major limitation of these methods is the time consuming training process, which may take several days or even weeks for large knowledge graphs, and result in great difficulty in practical applications. In this paper, we propose an efficient parallel framework for translating embedding methods, called ParTrans-X, which enables the methods to be paralleled without locks by utilizing the distinguished structures of knowledge graphs. Experiments on two datasets with three typical translating embedding methods, i.e., TransE [3], TransH [17], and a more efficient variant TransE- AdaGrad [10] validate that ParTrans-X can speed up the training process by more than an order of magnitude.
Hidden Two-Stream Convolutional Networks for Action Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Analyzing videos of human actions involves understanding the temporal relationships among video frames. State-of-the-art action recognition approaches rely on traditional optical flow estimation methods to pre-compute motion information for CNNs. Such a two-stage approach is computationally expensive, storage demanding, and not end-to-end trainable. In this paper, we present a novel CNN architecture that implicitly captures motion information between adjacent frames. We name our approach hidden two-stream CNNs because it only takes raw video frames as input and directly predicts action classes without explicitly computing optical flow. Our end-to-end approach is 10x faster than its two-stage baseline. Experimental results on four challenging action recognition datasets: UCF101, HMDB51, THUMOS14 and ActivityNet v1.2 show that our approach significantly outperforms the previous best real-time approaches.
Detection and Resolution of Rumours in Social Media: A Survey
Venue: arXiv cs.CL 2018
Year: 2018

Despite the increasing use of social media platforms for information and news gathering, its unmoderated nature often leads to the emergence and spread of rumours, i.e. pieces of information that are unverified at the time of posting. At the same time, the openness of social media platforms provides opportunities to study how users share and discuss rumours, and to explore how natural language processing and data mining techniques may be used to find ways of determining their veracity. In this survey we introduce and discuss two types of rumours that circulate on social media; long-standing rumours that circulate for long periods of time, and newly-emerging rumours spawned during fast-paced events such as breaking news, where reports are released piecemeal and often with an unverified status in their early stages. We provide an overview of research into social media rumours with the ultimate goal of developing a rumour classification system that consists of four components: rumour detection, rumour tracking, rumour stance classification and rumour veracity classification. We delve into the approaches presented in the scientific literature for the development of each of these four components. We summarise the efforts and achievements so far towards the development of rumour classification systems and conclude with suggestions for avenues for future research in social media mining for detection and resolution of rumours.
The Cloudlet Bazaar Dynamic Markets for the Small Cloud
Venue: arXiv cs.DC 2018
Year: 2018

The recent emergence of the small cloud (SC), both in concept and in practice, has been driven mainly by issues related to service cost and complexity of commercial cloud providers (e.g., Amazon) employing massive data centers. However, the resource inelasticity problem faced by the SCs due to their relatively scarce resources (e.g., virtual machines) might lead to a potential degradation of customer QoS and loss of revenue. A proposed solution to this problem recommends the sharing of resources between competing SCs to alleviate the resource inelasticity issues that might arise [1]. Based on this idea, a recent effort ([2]) proposed SC-Share, a performance-driven static market model for competitive small cloud environments that results in an efficient market equilibrium jointly optimizing customer QoS satisfaction and SC revenue generation. However, an important non-obvious question still remains to be answered, without which SC sharing markets may not be guaranteed to sustain in the long-run - is it still possible to achieve a stable market efficient state when the supply of SC resources is dynamic in nature and there is a variation of customer demand over time? In this paper, we address the problem of efficient market design for SC resource sharing in dynamic environments. We answer our previous question in the affirmative through the use of Arrow and Hurwicz's disequilibrium process [3], [4] in economics, and the gradient play technique in game theory that allows us to iteratively converge upon efficient and stable market equilibria
Automatic Breast Ultrasound Image Segmentation: A Survey
Venue: arXiv cs.CV 2018
Year: 2018

Breast cancer is one of the leading causes of cancer death among women worldwide. In clinical routine, automatic breast ultrasound (BUS) image segmentation is very challenging and essential for cancer diagnosis and treatment planning. Many BUS segmentation approaches have been studied in the last two decades, and have been proved to be effective on private datasets. Currently, the advancement of BUS image segmentation seems to meet its bottleneck. The improvement of the performance is increasingly challenging, and only few new approaches were published in the last several years. It is the time to look at the field by reviewing previous approaches comprehensively and to investigate the future directions. In this paper, we study the basic ideas, theories, pros and cons of the approaches, group them into categories, and extensively review each category in depth by discussing the principles, application issues, and advantages/disadvantages.
Learning Combinatorial Optimization Algorithms over Graphs
Venue: arXiv cs.LG 2018
Year: 2018

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.
Optimal Las Vegas Locality Sensitive Data Structures
Venue: arXiv cs.DS 2018
Year: 2018

We show that approximate similarity (near neighbour) search can be solved in high dimensions with performance matching state of the art (data independent) Locality Sensitive Hashing, but with a guarantee of no false negatives. Specifically, we give two data structures for common problems. For $c$-approximate near neighbour in Hamming space we get query time $dn^{1/c+o(1)}$ and space $dn^{1+1/c+o(1)}$ matching that of \cite{indyk1998approximate} and answering a long standing open question from~\cite{indyk2000dimensionality} and~\cite{pagh2016locality} in the affirmative. By means of a new deterministic reduction from $\ell_1$ to Hamming we also solve $\ell_1$ and $\ell_2$ with query time $d^2n^{1/c+o(1)}$ and space $d^2 n^{1+1/c+o(1)}$. For $(s_1,s_2)$-approximate Jaccard similarity we get query time $dn^{ρ+o(1)}$ and space $dn^{1+ρ+o(1)}$, $ρ=\log\frac{1+s_1}{2s_1}\big/\log\frac{1+s_2}{2s_2}$, when sets have equal size, matching the performance of~\cite{tobias2016}. The algorithms are based on space partitions, as with classic LSH, but we construct these using a combination of brute force, tensoring, perfect hashing and splitter functions à la~\cite{naor1995splitters}. We also show a new dimensionality reduction lemma with 1-sided error.