OpenRaiser/Intern-Atlas huggingface dataset:
Statistical Machine Translation for Indian Languages: Mission Hindi
Venue: arXiv cs.CL 2016
Year: 2016

This paper discusses Centre for Development of Advanced Computing Mumbai's (CDACM) submission to the NLP Tools Contest on Statistical Machine Translation in Indian Languages (ILSMT) 2014 (collocated with ICON 2014). The objective of the contest was to explore the effectiveness of Statistical Machine Translation (SMT) for Indian language to Indian language and English-Hindi machine translation. In this paper, we have proposed that suffix separation and word splitting for SMT from agglutinative languages to Hindi significantly improves over the baseline (BL). We have also shown that the factored model with reordering outperforms the phrase-based SMT for English-Hindi (\enhi). We report our work on all five pairs of languages, namely Bengali-Hindi (\bnhi), Marathi-Hindi (\mrhi), Tamil-Hindi (\tahi), Telugu-Hindi (\tehi), and \enhi for Health, Tourism, and General domains.
Optimistic Aborts for Geo-distributed Transactions
Venue: arXiv cs.DC 2016
Year: 2016

Network latency can have a significant impact on the performance of transactional storage systems, particularly in wide area or geo-distributed deployments. To reduce latency, systems typically rely on a cache to service read-requests closer to the client. However, caches are not effective for write-heavy workloads, which have to be processed by the storage system in order to maintain serializability. This paper presents a new technique, called optimistic abort, which reduces network latency for high-contention, write-heavy workloads by identifying transactions that will abort as early as possible, and aborting them before they reach the store. We have implemented optimistic abort in a system called Gotthard, which leverages recent advances in network data plane programmability to execute transaction processing logic directly in network devices. Gotthard examines network traffic to observe and log transaction requests. If Gotthard suspects that a transaction is likely to be aborted at the store, it aborts the transaction early by re-writing the packet header, and routing the packets back to the client. Gotthard significantly reduces the overall latency and improves the throughput for high-contention workloads.
Analyzing the structure of multidimensional compressed sensing problems through coherence
Venue: arXiv cs.IT 2016
Year: 2016

Recently it has been established that asymptotic incoherence can be used to facilitate subsampling, in order to optimize reconstruction quality, in a variety of continuous compressed sensing problems, and the coherence structure of certain one-dimensional Fourier sampling problems was determined. This paper extends the analysis of asymptotic incoherence to cover multidimensional reconstruction problems. It is shown that Fourier sampling and separable wavelet sparsity in any dimension can yield the same optimal asymptotic incoherence as in one dimensional case. Moreover in two dimensions the coherence structure is compatible with many standard two dimensional sampling schemes that are currently in use. However, in higher dimensional problems with poor wavelet smoothness we demonstrate that there are considerable restrictions on how one can subsample from the Fourier basis with optimal incoherence. This can be remedied by using a sufficiently smooth generating wavelet. It is also shown that using tensor bases will always provide suboptimal decay marred by problems associated with dimensionality. The impact of asymptotic incoherence on the ability to subsample is demonstrated with some simple two dimensional numerical experiments.
On the Network Reliability Problem of the Heterogeneous Key Predistribution Scheme
Venue: arXiv cs.IT 2016
Year: 2016

We consider the network reliability problem in wireless sensor networks secured by the heterogeneous random key predistribution scheme. This scheme generalizes Eschenauer-Gligor scheme by considering the cases when the network comprises sensor nodes with varying level of resources; e.g., regular nodes vs. cluster heads. The scheme induces the inhomogeneous random key graph, denoted $\mathbb{G}(n;\pmbμ,\pmb{K},P)$. We analyze the reliability of $\mathbb{G}(n;\pmbμ,\pmb{K},P)$ against random link failures. Namely, we consider $\mathbb{G}(n;\pmbμ,\pmb{K}, P,α)$ formed by deleting each edge of $\mathbb{G}(n;\pmbμ,\pmb{K},P)$ independently with probability $1-α$, and study the probability that the resulting graph i) has no isolated node; and ii) is connected. We present scaling conditions on $\pmb{K}$, $P$, and $α$ such that both events take place with probability zero or one, respectively, as the number of nodes gets large. We present numerical results to support these in the finite-node regime.
Predicting Counterfactuals from Large Historical Data and Small Randomized Trials
Venue: arXiv cs.LG 2016
Year: 2016

When a new treatment is considered for use, whether a pharmaceutical drug or a search engine ranking algorithm, a typical question that arises is, will its performance exceed that of the current treatment? The conventional way to answer this counterfactual question is to estimate the effect of the new treatment in comparison to that of the conventional treatment by running a controlled, randomized experiment. While this approach theoretically ensures an unbiased estimator, it suffers from several drawbacks, including the difficulty in finding representative experimental populations as well as the cost of running such trials. Moreover, such trials neglect the huge quantities of available control-condition data which are often completely ignored. In this paper we propose a discriminative framework for estimating the performance of a new treatment given a large dataset of the control condition and data from a small (and possibly unrepresentative) randomized trial comparing new and old treatments. Our objective, which requires minimal assumptions on the treatments, models the relation between the outcomes of the different conditions. This allows us to not only estimate mean effects but also to generate individual predictions for examples outside the randomized sample. We demonstrate the utility of our approach through experiments in three areas: Search engine operation, treatments to diabetes patients, and market value estimation for houses. Our results demonstrate that our approach can reduce the number and size of the currently performed randomized controlled experiments, thus saving significant time, money and effort on the part of practitioners.
Surprisal-Driven Zoneout
Venue: arXiv cs.LG 2016
Year: 2016

We propose a novel method of regularization for recurrent neural networks called suprisal-driven zoneout. In this method, states zoneout (maintain their previous value rather than updating), when the suprisal (discrepancy between the last state's prediction and target) is small. Thus regularization is adaptive and input-driven on a per-neuron basis. We demonstrate the effectiveness of this idea by achieving state-of-the-art bits per character of 1.31 on the Hutter Prize Wikipedia dataset, significantly reducing the gap to the best known highly-engineered compression methods.
EmojiNet: Building a Machine Readable Sense Inventory for Emoji
Venue: arXiv cs.CL 2016
Year: 2016

Emoji are a contemporary and extremely popular way to enhance electronic communication. Without rigid semantics attached to them, emoji symbols take on different meanings based on the context of a message. Thus, like the word sense disambiguation task in natural language processing, machines also need to disambiguate the meaning or sense of an emoji. In a first step toward achieving this goal, this paper presents EmojiNet, the first machine readable sense inventory for emoji. EmojiNet is a resource enabling systems to link emoji with their context-specific meaning. It is automatically constructed by integrating multiple emoji resources with BabelNet, which is the most comprehensive multilingual sense inventory available to date. The paper discusses its construction, evaluates the automatic resource creation process, and presents a use case where EmojiNet disambiguates emoji usage in tweets. EmojiNet is available online for use at http://emojinet.knoesis.org.
New results for traitor tracing schemes
Venue: arXiv cs.IT 2016
Year: 2016

In the last two decades, several classes of codes are introduced to protect the copyrighted digital data. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. In this paper we will discuss three important classes of such codes, namely, frameproof codes, parent-identifying codes and traceability codes. Firstly, suppose $N(t)$ is the minimal integer such that there exists a binary $t$-frameproof code of length $N$ with cardinality larger than $N$, we prove that $N(t)\ge\frac{15+\sqrt{33}}{24} (t-2)^2$, which is a great improvement of the previously known bound $N(t)\ge\binom{t+1}{2}$. Moreover, we find that the determination of $N(t)$ is closely related to a conjecture of Erdős, Frankl and Füredi posed in the 1980's, which implies the conjectured value $N(t)=t^2+o(t^2)$. Secondly, we derive a new upper bound for parent-identifying codes, which is superior than all previously known bounds. Thirdly, we present an upper bound for 3-traceability codes, which shows that a $q$-ary 3-traceability code of length $N$ can have at most $cq^{\lceil N/9\rceil}$ codewords, where $c$ is a constant only related to the code length $N$. It is the first meaningful upper bound for 3-traceability codes and our result supports a conjecture of Blackburn et al. posed in 2010.
Camera Fingerprint: A New Perspective for Identifying User's Identity
Venue: arXiv cs.CV 2016
Year: 2016

Identifying user's identity is a key problem in many data mining applications, such as product recommendation, customized content delivery and criminal identification. Given a set of accounts from the same or different social network platforms, user identification attempts to identify all accounts belonging to the same person. A commonly used solution is to build the relationship among different accounts by exploring their collective patterns, e.g., user profile, writing style, similar comments. However, this kind of method doesn't work well in many practical scenarios, since the information posted explicitly by users may be false due to various reasons. In this paper, we re-inspect the user identification problem from a novel perspective, i.e., identifying user's identity by matching his/her cameras. The underlying assumption is that multiple accounts belonging to the same person contain the same or similar camera fingerprint information. The proposed framework, called User Camera Identification (UCI), is based on camera fingerprints, which takes fully into account the problems of multiple cameras and reposting behaviors.
Construction of MDS self-dual codes from orthogonal matrices
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we give algorithms and methods of construction of self-dual codes over finite fields using orthogonal matrices. Randomization in the orthogonal group, and code extension are the main tools. Some optimal, almost MDS, and MDS self-dual codes over both small and large prime fields are constructed.
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
Venue: arXiv cs.DM 2016
Year: 2016

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access. For $k$-uniform matroids, we give a deterministic algorithm with competitive ratio at least $0.2959$, and the ratio approaches $\frac{1}{α_\infty} \approx 0.3178$ as $k$ approaches infinity, improving the previous best ratio of $0.25$ by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. Further, we prove that no deterministic monotone algorithm can be strictly better than $0.25$-competitive even for partition matroids, the most modest generalization of $k$-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio $\frac{1}{α_\infty} \approx 0.3178$.
mdBrief - A Fast Online Adaptable, Distorted Binary Descriptor for Real-Time Applications Using Calibrated Wide-Angle Or Fisheye Cameras
Venue: arXiv cs.CV 2016
Year: 2016

Fast binary descriptors build the core for many vision based applications with real-time demands like object detection, Visual Odometry or SLAM. Commonly it is assumed, that the acquired images and thus the patches extracted around keypoints originate from a perspective projection ignoring image distortion or completely different types of projections such as omnidirectional or fisheye. Usually the deviations from a perfect perspective projection are corrected by undistortion. Latter, however, introduces severe artifacts if the cameras field-of-view gets larger. In this paper, we propose a distorted and masked version of the BRIEF descriptor for calibrated cameras. Instead of correcting the distortion holistically, we distort the binary tests and thus adapt the descriptor to different image regions.
Anatomically Constrained Video-CT Registration via the V-IMLOP Algorithm
Venue: arXiv cs.CV 2016
Year: 2016

Functional endoscopic sinus surgery (FESS) is a surgical procedure used to treat acute cases of sinusitis and other sinus diseases. FESS is fast becoming the preferred choice of treatment due to its minimally invasive nature. However, due to the limited field of view of the endoscope, surgeons rely on navigation systems to guide them within the nasal cavity. State of the art navigation systems report registration accuracy of over 1mm, which is large compared to the size of the nasal airways. We present an anatomically constrained video-CT registration algorithm that incorporates multiple video features. Our algorithm is robust in the presence of outliers. We also test our algorithm on simulated and in-vivo data, and test its accuracy against degrading initializations.
PATH: Person Authentication using Trace Histories
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a solution to the problem of Active Authentication using trace histories is addressed. Specifically, the task is to perform user verification on mobile devices using historical location traces of the user as a function of time. Considering the movement of a human as a Markovian motion, a modified Hidden Markov Model (HMM)-based solution is proposed. The proposed method, namely the Marginally Smoothed HMM (MSHMM), utilizes the marginal probabilities of location and timing information of the observations to smooth-out the emission probabilities while training. Hence, it can efficiently handle unforeseen observations during the test phase. The verification performance of this method is compared to a sequence matching (SM) method , a Markov Chain-based method (MC) and an HMM with basic Laplace Smoothing (HMM-lap). Experimental results using the location information of the UMD Active Authentication Dataset-02 (UMDAA02) and the GeoLife dataset are presented. The proposed MSHMM method outperforms the compared methods in terms of equal error rate (EER). Additionally, the effects of different parameters on the proposed method are discussed.
Higher-Order Linearisability
Venue: arXiv cs.PL 2016
Year: 2016

Linearisability is a central notion for verifying concurrent libraries: a given library is proven safe if its operational history can be rearranged into a new sequential one which, in addition, satisfies a given specification. Linearisability has been examined for libraries in which method arguments and method results are of ground type, including libraries parameterised with such methods. In this paper we extend linearisability to the general higher-order setting: methods can be passed as arguments and returned as values. A library may also depend on abstract methods of any order. We use this generalised notion to show correctness of several higher-order example libraries.
Wasserstein Stability of the Entropy Power Inequality for Log-Concave Densities
Venue: arXiv cs.IT 2016
Year: 2016

We establish quantitative stability results for the entropy power inequality (EPI). Specifically, we show that if uniformly log-concave densities nearly saturate the EPI, then they must be close to Gaussian densities in the quadratic Wasserstein distance. Further, if one of the densities is log-concave and the other is Gaussian, then the deficit in the EPI can be controlled in terms of the $L^1$-Wasserstein distance. As a counterpoint, an example shows that the EPI can be unstable with respect to the quadratic Wasserstein distance when densities are uniformly log-concave on sets of measure arbitrarily close to one. Our stability results can be extended to non-log-concave densities, provided certain regularity conditions are met. The proofs are based on optimal transportation.
Dis-S2V: Discourse Informed Sen2Vec
Venue: arXiv cs.CL 2016
Year: 2016

Vector representation of sentences is important for many text processing tasks that involve clustering, classifying, or ranking sentences. Recently, distributed representation of sentences learned by neural models from unlabeled data has been shown to outperform the traditional bag-of-words representation. However, most of these learning methods consider only the content of a sentence and disregard the relations among sentences in a discourse by and large. In this paper, we propose a series of novel models for learning latent representations of sentences (Sen2Vec) that consider the content of a sentence as well as inter-sentence relations. We first represent the inter-sentence relations with a language network and then use the network to induce contextual information into the content-based Sen2Vec models. Two different approaches are introduced to exploit the information in the network. Our first approach retrofits (already trained) Sen2Vec vectors with respect to the network in two different ways: (1) using the adjacency relations of a node, and (2) using a stochastic sampling method which is more flexible in sampling neighbors of a node. The second approach uses a regularizer to encode the information in the network into the existing Sen2Vec model. Experimental results show that our proposed models outperform existing methods in three fundamental information system tasks demonstrating the effectiveness of our approach. The models leverage the computational power of multi-core CPUs to achieve fine-grained computational efficiency. We make our code publicly available upon acceptance.
Efficient Pattern Matching in Elastic-Degenerate Strings
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we extend the notion of gapped strings to elastic-degenerate strings. An elastic-degenerate string can been seen as an ordered collection of k > 1 seeds (substrings/subpatterns) interleaved by elastic-degenerate symbols such that each elastic-degenerate symbol corresponds to a set of two or more variable length strings. Here, we present an algorithm for solving the pattern matching problem with (solid) pattern and elastic-degenerate text, running in O(N+αγnm) time; where m is the length of the given pattern; n and N are the length and total size of the given elastic-degenerate text, respectively; α and γ are small constants, respectively representing the maximum number of strings in any elastic-degenerate symbol of the text and the largest number of elastic-degenerate symbols spanned by any occurrence of the pattern in the text. The space used by the algorithm is linear in the size of the input for a constant number of elastic-degenerate symbols in the text; α and γ are so small in real applications that the algorithm is expected to work very efficiently in practice.
A Physician Advisory System for Chronic Heart Failure Management Based on Knowledge Patterns
Venue: arXiv cs.AI 2016
Year: 2016

Management of chronic diseases such as heart failure, diabetes, and chronic obstructive pulmonary disease (COPD) is a major problem in health care. A standard approach that the medical community has devised to manage widely prevalent chronic diseases such as chronic heart failure (CHF) is to have a committee of experts develop guidelines that all physicians should follow. These guidelines typically consist of a series of complex rules that make recommendations based on a patient's information. Due to their complexity, often the guidelines are either ignored or not complied with at all, which can result in poor medical practices. It is not even clear whether it is humanly possible to follow these guidelines due to their length and complexity. In the case of CHF management, the guidelines run nearly 80 pages. In this paper we describe a physician-advisory system for CHF management that codes the entire set of clinical practice guidelines for CHF using answer set programming. Our approach is based on developing reasoning templates (that we call knowledge patterns) and using these patterns to systemically code the clinical guidelines for CHF as ASP rules. Use of the knowledge patterns greatly facilitates the development of our system. Given a patient's medical information, our system generates a recommendation for treatment just as a human physician would, using the guidelines. Our system will work even in the presence of incomplete information. Our work makes two contributions: (i) it shows that highly complex guidelines can be successfully coded as ASP rules, and (ii) it develops a series of knowledge patterns that facilitate the coding of knowledge expressed in a natural language and that can be used for other application domains. This paper is under consideration for acceptance in TPLP.
A Higher-order Calculus of Computational Fields
Venue: arXiv cs.LO 2016
Year: 2016

The complexity of large-scale distributed systems, particularly when deployed in physical space, calls for new mechanisms to address composability and reusability of collective adaptive behaviour. Computational fields have been proposed as an effective abstraction to fill the gap between the macro-level of such systems (specifying a system's collective behaviour) and the micro-level (individual devices' actions of computation and interaction to implement that collective specification), thereby providing a basis to better facilitate the engineering of collective APIs and complex systems at higher levels of abstraction. This paper proposes a full formal foundation for field computations, in terms of a core (higher-order) calculus of computational fields containing a few key syntactic constructs, and equipped with typing, denotational and operational semantics. Critically, this allows formal establishment of a link between the micro- and macro-levels of collective adaptive systems, by a result of full abstraction and adequacy for the (aggregate) denotational semantics with respect to the (per-device) operational semantics.