OpenRaiser/Intern-Atlas huggingface dataset:
Fast Cross-Polytope Locality-Sensitive Hashing
Venue: arXiv cs.DS 2016
Year: 2016

We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is provably optimal in asymptotic sensitivity and enjoys $\mathcal{O}(d \ln d )$ hash computation time. Building on a recent result (by Andoni, Indyk, Laarhoven, Razenshteyn, Schmidt, 2015), we show that optimal asymptotic sensitivity for cross-polytope LSH is retained even when the dense Gaussian matrix is replaced by a fast Johnson-Lindenstrauss transform followed by discrete pseudo-rotation, reducing the hash computation time from $\mathcal{O}(d^2)$ to $\mathcal{O}(d \ln d )$. Moreover, our scheme achieves the optimal rate of convergence for sensitivity. By incorporating a low-randomness Johnson-Lindenstrauss transform, our scheme can be modified to require only $\mathcal{O}(\ln^9(d))$ random bits
Augur: Mining Human Behaviors from Fiction to Power Interactive Systems
Venue: arXiv cs.HC 2016
Year: 2016

From smart homes that prepare coffee when we wake, to phones that know not to interrupt us during important conversations, our collective visions of HCI imagine a future in which computers understand a broad range of human behaviors. Today our systems fall short of these visions, however, because this range of behaviors is too large for designers or programmers to capture manually. In this paper, we instead demonstrate it is possible to mine a broad knowledge base of human behavior by analyzing more than one billion words of modern fiction. Our resulting knowledge base, Augur, trains vector models that can predict many thousands of user activities from surrounding objects in modern contexts: for example, whether a user may be eating food, meeting with a friend, or taking a selfie. Augur uses these predictions to identify actions that people commonly take on objects in the world and estimate a user's future activities given their current situation. We demonstrate Augur-powered, activity-based systems such as a phone that silences itself when the odds of you answering it are low, and a dynamic music player that adjusts to your present activity. A field deployment of an Augur-powered wearable camera resulted in 96% recall and 71% precision on its unsupervised predictions of common daily activities. A second evaluation where human judges rated the system's predictions over a broad set of input images found that 94% were rated sensible.
Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing
Venue: arXiv cs.CR 2016
Year: 2016

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.
Geo-Conquesting Based on Graph Analysis for Crowdsourced Metatrails from Mobile Sensing
Venue: arXiv cs.HC 2016
Year: 2016

This article investigates graph analysis for intelligent marketing in smart cities, where metatrails are crowdsourced by mobile sensing for marketing strategies. Unlike most works that focused on client sides, this study is intended for market planning, from the perspective of enterprises. Several novel crowdsourced features based on metatrails, including hotspot networks, crowd transitions, affinity subnetworks, and sequential visiting patterns, are discussed in the article. These smart footprints can reflect crowd preferences and the topology of a site of interest. Marketers can utilize such information for commercial resource planning and deployment. Simulations were conducted to demonstrate the performance. At the end, this study also discusses different scenarios for practical geo-conquesting applications.
Human-Machine Networks: Towards a Typology and Profiling Framework
Venue: arXiv cs.HC 2016
Year: 2016

In this paper we outline an initial typology and framework for the purpose of profiling human-machine networks, that is, collective structures where humans and machines interact to produce synergistic effects. Profiling a human-machine network along the dimensions of the typology is intended to facilitate access to relevant design knowledge and experience. In this way the profiling of an envisioned or existing human-machine network will both facilitate relevant design discussions and, more importantly, serve to identify the network type. We present experiences and results from two case trials: a crisis management system and a peer-to-peer reselling network. Based on the lessons learnt from the case trials we suggest potential benefits and challenges, and point out needed future work.
Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations
Venue: arXiv cs.CV 2016
Year: 2016

Despite progress in perceptual tasks such as image classification, computers still perform poorly on cognitive tasks such as image description and question answering. Cognition is core to tasks that involve not just recognizing, but reasoning about our visual world. However, models used to tackle the rich content in images for cognitive tasks are still being trained using the same datasets designed for perceptual tasks. To achieve success at cognitive tasks, models need to understand the interactions and relationships between objects in an image. When asked "What vehicle is the person riding?", computers will need to identify the objects in an image as well as the relationships riding(man, carriage) and pulling(horse, carriage) in order to answer correctly that "the person is riding a horse-drawn carriage". In this paper, we present the Visual Genome dataset to enable the modeling of such relationships. We collect dense annotations of objects, attributes, and relationships within each image to learn these models. Specifically, our dataset contains over 100K images where each image has an average of 21 objects, 18 attributes, and 18 pairwise relationships between objects. We canonicalize the objects, attributes, relationships, and noun phrases in region descriptions and questions answer pairs to WordNet synsets. Together, these annotations represent the densest and largest dataset of image descriptions, objects, attributes, relationships, and question answers.
Computing approximate PSD factorizations
Venue: arXiv cs.DS 2016
Year: 2016

We give an algorithm for computing approximate PSD factorizations of nonnegative matrices. The running time of the algorithm is polynomial in the dimensions of the input matrix, but exponential in the PSD rank and the approximation error. The main ingredient is an exact factorization algorithm when the rows and columns of the factors are constrained to lie in a general polyhedron. This strictly generalizes nonnegative matrix factorizations which can be captured by letting this polyhedron to be the nonnegative orthant.
SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size
Venue: arXiv cs.CV 2016
Year: 2016

Recent research on deep neural networks has focused primarily on improving accuracy. For a given accuracy level, it is typically possible to identify multiple DNN architectures that achieve that accuracy level. With equivalent accuracy, smaller DNN architectures offer at least three advantages: (1) Smaller DNNs require less communication across servers during distributed training. (2) Smaller DNNs require less bandwidth to export a new model from the cloud to an autonomous car. (3) Smaller DNNs are more feasible to deploy on FPGAs and other hardware with limited memory. To provide all of these advantages, we propose a small DNN architecture called SqueezeNet. SqueezeNet achieves AlexNet-level accuracy on ImageNet with 50x fewer parameters. Additionally, with model compression techniques we are able to compress SqueezeNet to less than 0.5MB (510x smaller than AlexNet). The SqueezeNet architecture is available for download here: https://github.com/DeepScale/SqueezeNet
Automatic Moth Detection from Trap Images for Pest Management
Venue: arXiv cs.CV 2016
Year: 2016

Monitoring the number of insect pests is a crucial component in pheromone-based pest management systems. In this paper, we propose an automatic detection pipeline based on deep learning for identifying and counting pests in images taken inside field traps. Applied to a commercial codling moth dataset, our method shows promising performance both qualitatively and quantitatively. Compared to previous attempts at pest detection, our approach uses no pest-specific engineering which enables it to adapt to other species and environments with minimal human effort. It is amenable to implementation on parallel hardware and therefore capable of deployment in settings where real-time performance is required.
Domain Specific Author Attribution Based on Feedforward Neural Network Language Models
Venue: arXiv cs.CL 2016
Year: 2016

Authorship attribution refers to the task of automatically determining the author based on a given sample of text. It is a problem with a long history and has a wide range of application. Building author profiles using language models is one of the most successful methods to automate this task. New language modeling methods based on neural networks alleviate the curse of dimensionality and usually outperform conventional N-gram methods. However, there have not been much research applying them to authorship attribution. In this paper, we present a novel setup of a Neural Network Language Model (NNLM) and apply it to a database of text samples from different authors. We investigate how the NNLM performs on a task with moderate author set size and relatively limited training and test data, and how the topics of the text samples affect the accuracy. NNLM achieves nearly 2.5% reduction in perplexity, a measurement of fitness of a trained language model to the test data. Given 5 random test sentences, it also increases the author classification accuracy by 3.43% on average, compared with the N-gram methods using SRILM tools. An open source implementation of our methodology is freely available at https://github.com/zge/authorship-attribution/.
Concentration of research funding leads to decreasing marginal returns
Venue: arXiv cs.DL 2016
Year: 2016

In most countries, basic research is supported by research councils that select, after peer review, the individuals or teams that are to receive funding. Unfortunately, the number of grants these research councils can allocate is not infinite and, in most cases, a minority of the researchers receive the majority of the funds. However, evidence as to whether this is an optimal way of distributing available funds is mixed. The purpose of this study is to measure the relation between the amount of funding provided to 12,720 researchers in Quebec over a fifteen year period (1998-2012) and their scientific output and impact from 2000 to 2013. Our results show that both in terms of the quantity of papers produced and of their scientific impact, the concentration of research funding in the hands of a so-called "elite" of researchers generally produces diminishing marginal returns. Also, we find that the most funded researchers do not stand out in terms of output and scientific impact.
The robust recoverable spanning tree problem with interval costs is polynomially solvable
Venue: arXiv cs.DS 2016
Year: 2016

In this paper the robust recoverable spanning tree problem with interval edge costs is considered. The complexity of this problem has remained open to date. It is shown that the problem is polynomially solvable, by using an iterative relaxation method. A generalization of this idea to the robust recoverable matroid basis problem is also presented. Polynomial algorithms for both robust recoverable problems are proposed.
TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
Venue: arXiv cs.DS 2016
Year: 2016

We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully-dynamic graph represented as an adversarial stream of edge insertions and deletions. Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches which use hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they will use. We show a full analysis of the variance of the estimations and novel concentration bounds for these quantities. Our experimental results on very large graphs show that TRIÈST outperforms state-of-the-art approaches in accuracy and exhibits a small update time.
A fine-grained approach to scene text script identification
Venue: arXiv cs.CV 2016
Year: 2016

This paper focuses on the problem of script identification in unconstrained scenarios. Script identification is an important prerequisite to recognition, and an indispensable condition for automatic text understanding systems designed for multi-language environments. Although widely studied for document images and handwritten documents, it remains an almost unexplored territory for scene text images. We detail a novel method for script identification in natural images that combines convolutional features and the Naive-Bayes Nearest Neighbor classifier. The proposed framework efficiently exploits the discriminative power of small stroke-parts, in a fine-grained classification framework. In addition, we propose a new public benchmark dataset for the evaluation of joint text detection and script identification in natural scenes. Experiments done in this new dataset demonstrate that the proposed method yields state of the art results, while it generalizes well to different datasets and variable number of scripts. The evidence provided shows that multi-lingual scene text recognition in the wild is a viable proposition. Source code of the proposed method is made available online.
5G 3GPP-like Channel Models for Outdoor Urban Microcellular and Macrocellular Environments
Venue: arXiv cs.IT 2016
Year: 2016

For the development of new 5G systems to operate in bands up to 100 GHz, there is a need for accurate radio propagation models at these bands that currently are not addressed by existing channel models developed for bands below 6 GHz. This document presents a preliminary overview of 5G channel models for bands up to 100 GHz. These have been derived based on extensive measurement and ray tracing results across a multitude of frequencies from 6 GHz to 100 GHz, and this document describes an initial 3D channel model which includes: 1) typical deployment scenarios for urban microcells (UMi) and urban macrocells (UMa), and 2) a baseline model for incorporating path loss, shadow fading, line of sight probability, penetration and blockage models for the typical scenarios. Various processing methodologies such as clustering and antenna decoupling algorithms are also presented.
Multilingual Twitter Sentiment Classification: The Role of Human Annotators
Venue: arXiv cs.CL 2016
Year: 2016

What are the limits of automated Twitter sentiment classification? We analyze a large set of manually labeled tweets in different languages, use them as training data, and construct automated classification models. It turns out that the quality of classification models depends much more on the quality and size of training data than on the type of the model trained. Experimental results indicate that there is no statistically significant difference between the performance of the top classification models. We quantify the quality of training data by applying various annotator agreement measures, and identify the weakest points of different datasets. We show that the model performance approaches the inter-annotator agreement when the size of the training set is sufficiently large. However, it is crucial to regularly monitor the self- and inter-annotator agreements since this improves the training datasets and consequently the model performance. Finally, we show that there is strong evidence that humans perceive the sentiment classes (negative, neutral, and positive) as ordered.
Advancing Trace Recovery Evaluation - Applied Information Retrieval in a Software Engineering Context
Venue: arXiv cs.SE 2016
Year: 2016

Successful development of software systems involves efficient navigation among software artifacts. One state-of-practice approach to structure information is to establish trace links between artifacts, a practice that is also enforced by several development standards. Unfortunately, manually maintaining trace links in an evolving system is a tedious task. To tackle this issue, several researchers have proposed treating the capture and recovery of trace links as an Information Retrieval (IR) problem. The work contains a Systematic Literature Review (SLR) of previous evaluations of IR-based trace recovery. We show that a majority of previous evaluations have been technology-oriented, conducted in "the cave of IR evaluation", using small datasets as experimental input. Also, software artifacts originating from student projects have frequently been used in evaluations. We conducted a survey among traceability researchers, and found that a majority consider student artifacts to be only partly representative to industrial counterparts. Our findings call for additional case studies to evaluate IR-based trace recovery within the full complexity of an industrial setting. Also, this thesis contributes to the body of empirical evidence of IR-based trace recovery in two experiments with industrial software artifacts. The technology-oriented experiment highlights the clear dependence between datasets and the accuracy of IR-based trace recovery, in line with findings from the SLR. The human-oriented experiment investigates how different quality levels of tool output affect the tracing accuracy of engineers. Finally, we present how tools and methods are evaluated in the general field of IR research, and propose a taxonomy of evaluation contexts tailored for IR-based trace recovery.
Regular Language Distance and Entropy
Venue: arXiv cs.FL 2016
Year: 2016

This paper addresses the problem of determining the distance between two regular languages. It will show how to expand Jaccard distance, which works on finite sets, to potentially-infinite regular languages. The entropy of a regular language plays a large role in the extension. Much of the paper is spent investigating the entropy of a regular language. This includes addressing issues that have required previous authors to rely on the upper limit of Shannon's traditional formulation of entropy, because its limit does not always exist. The paper also includes proposing a new limit based formulation for the entropy of a regular language and proves that formulation to both exist and be equivalent to Shannon's original formulation (when it exists). Additionally, the proposed formulation is shown to equal an analogous but formally quite different notion of topological entropy from Symbolic Dynamics -- consequently also showing Shannon's original formulation to be equivalent to topological entropy. Surprisingly, the natural Jaccard-like entropy distance is trivial in most cases. Instead, the {\it entropy sum} distance metric is suggested, and shown to be granular in certain situations.
Robust Air Data Sensor Fault Diagnosis With Enhanced Fault Sensitivity Using Moving Horizon Estimation
Venue: arXiv cs.SY 2016
Year: 2016

This paper investigates robust fault diagnosis of multiple air data sensor faults in the presence of winds. The trade-off between robustness to winds and sensitivity to faults is challenging due to simultaneous influence of winds and latent faults on monitored sensors. Different from conventional residual generators that do not consider any constraints, we propose a constrained residual generator using moving horizon estimation. The main contribution is improved fault sensitivity by exploiting known bounds on winds in residual generation. By analyzing the Karush-Kuhn-Tucker conditions of the formulated moving horizon estimation problem, it is shown that this improvement is attributed to active inequality constraints caused by faults. When the weighting matrices in the moving horizon estimation problem are tuned to increase robustness to winds, its fault sensitivity does not simply decrease as one would expect in conventional unconstrained residual generators. Instead, its fault sensitivity increases when the fault is large enough to activate some inequality constraints. This fault sensitivity improvement is not restricted to this particular application, but can be achieved by any general moving horizon estimation based residual generator. A high-fidelity Airbus simulator is used to illustrate the advantage of our proposed approach in terms of fault sensitivity.
A Markov chain model for the search time for max degree nodes in a graph using a biased random walk
Venue: arXiv cs.SI 2016
Year: 2016

We consider the problem of estimating the expected time to find a maximum degree node on a graph using a (parameterized) biased random walk. For assortative graphs the positive degree correlation serves as a local gradient for which a bias towards selecting higher degree neighbors will on average reduce the search time. Unfortunately, although the expected absorption time on the graph can be written down using the theory of absorbing Markov chains, computing this time is infeasible for large graphs. With this motivation, we construct an absorbing Markov chain with a state for each degree of the graph, and observe computing the expected absorption time is now computationally feasible. Our paper finds preliminary results along the following lines: i) there are graphs for which the proposed Markov model does and graphs for which the model does not capture the absorbtion time, ii) there are graphs where random sampling outperforms biased random walks, and graphs where biased random walks are superior, and iii) the optimal bias parameter for the random walk is graph dependent, and we study the dependence on the graph assortativity.
Automated Word Prediction in Bangla Language Using Stochastic Language Models
Venue: arXiv cs.CL 2016
Year: 2016

Word completion and word prediction are two important phenomena in typing that benefit users who type using keyboard or other similar devices. They can have profound impact on the typing of disable people. Our work is based on word prediction on Bangla sentence by using stochastic, i.e. N-gram language model such as unigram, bigram, trigram, deleted Interpolation and backoff models for auto completing a sentence by predicting a correct word in a sentence which saves time and keystrokes of typing and also reduces misspelling. We use large data corpus of Bangla language of different word types to predict correct word with the accuracy as much as possible. We have found promising results. We hope that our work will impact on the baseline for automated Bangla typing.