OpenRaiser/Intern-Atlas huggingface dataset:
Learning Python Code Suggestion with a Sparse Pointer Network
Venue: arXiv cs.NE 2016
Year: 2016

To enhance developer productivity, all modern integrated development environments (IDEs) include code suggestion functionality that proposes likely next tokens at the cursor. While current IDEs work well for statically-typed languages, their reliance on type annotations means that they do not provide the same level of support for dynamic programming languages as for statically-typed languages. Moreover, suggestion engines in modern IDEs do not propose expressions or multi-statement idiomatic code. Recent work has shown that language models can improve code suggestion systems by learning from software repositories. This paper introduces a neural language model with a sparse pointer network aimed at capturing very long-range dependencies. We release a large-scale code suggestion corpus of 41M lines of Python code crawled from GitHub. On this corpus, we found standard neural language models to perform well at suggesting local phenomena, but struggle to refer to identifiers that are introduced many tokens in the past. By augmenting a neural language model with a pointer network specialized in referring to predefined classes of identifiers, we obtain a much lower perplexity and a 5 percentage points increase in accuracy for code suggestion compared to an LSTM baseline. In fact, this increase in code suggestion accuracy is due to a 13 times more accurate prediction of identifiers. Furthermore, a qualitative analysis shows this model indeed captures interesting long-range dependencies, like referring to a class member defined over 60 tokens in the past.
Incremental analysis of nonlinear systems with efficient methods for piecewise-affine systems
Venue: arXiv cs.SY 2016
Year: 2016

This paper is concerned with incremental stability properties of nonlinear systems. We propose conditions to compute an upper bound on the incremental L2-gain and to assess incremental asymptotic stability of piecewise-affine (PWA) systems. The conditions are derived from dissipativity analysis, and are based on the construction of piecewise-quadratic functions via linear matrix inequalities (LMI) that can be efficiently solved numerically. The developments are shown to be less conservative than previous results, and are illustrated with numerical examples. In the last part of this paper, we study the connection between incremental L2-gain stability and incremental asymptotic stability. It is shown that, with appropriate observability and reachability assumptions on the input-output operator, incremental L2-gain implies incremental asymptotic stability. Finally, it is shown that the converse implication follows provided some regularity conditions on the state space representation are met.
Kannada Spell Checker with Sandhi Splitter
Venue: arXiv cs.CL 2016
Year: 2016

Spelling errors are introduced in text either during typing, or when the user does not know the correct phoneme or grapheme. If a language contains complex words like sandhi where two or more morphemes join based on some rules, spell checking becomes very tedious. In such situations, having a spell checker with sandhi splitter which alerts the user by flagging the errors and providing suggestions is very useful. A novel algorithm of sandhi splitting is proposed in this paper. The sandhi splitter can split about 7000 most common sandhi words in Kannada language used as test samples. The sandhi splitter was integrated with a Kannada spell checker and a mechanism for generating suggestions was added. A comprehensive, platform independent, standalone spell checker with sandhi splitter application software was thus developed and tested extensively for its efficiency and correctness. A comparative analysis of this spell checker with sandhi splitter was made and results concluded that the Kannada spell checker with sandhi splitter has an improved performance. It is twice as fast, 200 times more space efficient, and it is 90% accurate in case of complex nouns and 50% accurate for complex verbs. Such a spell checker with sandhi splitter will be of foremost significance in machine translation systems, voice processing, etc. This is the first sandhi splitter in Kannada and the advantage of the novel algorithm is that, it can be extended to all Indian languages.
Deep Video Deblurring
Venue: arXiv cs.CV 2016
Year: 2016

Motion blur from camera shake is a major problem in videos captured by hand-held devices. Unlike single-image deblurring, video-based approaches can take advantage of the abundant information that exists across neighboring frames. As a result the best performing methods rely on aligning nearby frames. However, aligning images is a computationally expensive and fragile procedure, and methods that aggregate information must therefore be able to identify which regions have been accurately aligned and which have not, a task which requires high level scene understanding. In this work, we introduce a deep learning solution to video deblurring, where a CNN is trained end-to-end to learn how to accumulate information across frames. To train this network, we collected a dataset of real videos recorded with a high framerate camera, which we use to generate synthetic motion blur for supervision. We show that the features learned from this dataset extend to deblurring motion blur that arises due to camera shake in a wide range of videos, and compare the quality of results to a number of other baselines.
Color Constancy with Derivative Colors
Venue: arXiv cs.CV 2016
Year: 2016

Information about the illuminant color is well contained in both achromatic regions and the specular components of highlight regions. In this paper, we propose a novel way to achieve color constancy by exploiting such clues. The key to our approach lies in the use of suitably extracted derivative colors, which are able to compute the illuminant color robustly with kernel density estimation. While extracting derivative colors from achromatic regions to approximate the illuminant color well is basically straightforward, the success of our extraction in highlight regions is attributed to the different rates of variation of the diffuse and specular magnitudes in the dichromatic reflection model. The proposed approach requires no training phase and is simple to implement. More significantly, it performs quite satisfactorily under inter-database parameter settings. Our experiments on three standard databases demonstrate its effectiveness and fine performance in comparison to state-of-the-art methods.
Multimodal Latent Variable Analysis
Venue: arXiv cs.CV 2016
Year: 2016

Consider a set of multiple, multimodal sensors capturing a complex system or a physical phenomenon of interest. Our primary goal is to distinguish the underlying sources of variability manifested in the measured data. The first step in our analysis is to find the common source of variability present in all sensor measurements. We base our work on a recent paper, which tackles this problem with alternating diffusion (AD). In this work, we suggest to further the analysis by extracting the sensor-specific variables in addition to the common source. We propose an algorithm, which we analyze theoretically, and then demonstrate on three different applications: a synthetic example, a toy problem, and the task of fetal ECG extraction.
The G-ACM Tool: using the Drools Rule Engine for Access Control Management
Venue: arXiv cs.CR 2016
Year: 2016

In this paper we explore the usage of rule engines in a graphical framework for visualising dynamic access control policies. We use the Drools rule engine to dynamically compute permissions, following the Category-Based Access Control metamodel.
The sum of it all: revealing collaboration patterns by combining authorship and acknowledgements
Venue: arXiv cs.DL 2016
Year: 2016

Acknowledgments are one of many conventions by which researchers publicly bestow recognition towards individuals, organizations and institutions that contributed in some way to the work that led to publication. Combining data on both co-authors and acknowledged individuals, the present study analyses disciplinary differences in researchers credit attribution practices in collaborative context. Our results show that the important differences traditionally observed between disciplines in terms of team size are greatly reduced when acknowledgees are taken into account. Broadening the measurement of collaboration beyond co-authorship by including individuals credited in the acknowledgements allows for an assessment of collaboration practices and team work that might be closer to the reality of contemporary research, especially in the social sciences and humanities.
New Trends in Neutrosophic Theory and Applications
Venue: arXiv cs.AI 2016
Year: 2016

Neutrosophic theory and applications have been expanding in all directions at an astonishing rate especially after the introduction the journal entitled Neutrosophic Sets and Systems. New theories, techniques, algorithms have been rapidly developed. One of the most striking trends in the neutrosophic theory is the hybridization of neutrosophic set with other potential sets such as rough set, bipolar set, soft set, hesitant fuzzy set, etc. The different hybrid structure such as rough neutrosophic set, single valued neutrosophic rough set, bipolar neutrosophic set, single valued neutrosophic hesitant fuzzy set, etc. are proposed in the literature in a short period of time. Neutrosophic set has been a very important tool in all various areas of data mining, decision making, e-learning, engineering, medicine, social science, and some more. The book New Trends in Neutrosophic Theories and Applications focuses on theories, methods, algorithms for decision making and also applications involving neutrosophic information. Some topics deal with data mining, decision making, e-learning, graph theory, medical diagnosis, probability theory, topology, and some more.
Knowledge Graph Representation with Jointly Structural and Textual Encoding
Venue: arXiv cs.CL 2016
Year: 2016

The objective of knowledge graph embedding is to encode both entities and relations of knowledge graphs into continuous low-dimensional vector spaces. Previously, most works focused on symbolic representation of knowledge graph with structure information, which can not handle new entities or entities with few facts well. In this paper, we propose a novel deep architecture to utilize both structural and textual information of entities. Specifically, we introduce three neural models to encode the valuable information from text description of entity, among which an attentive model can select related information as needed. Then, a gating mechanism is applied to integrate representations of structure and text into a unified architecture. Experiments show that our models outperform baseline by margin on link prediction and triplet classification tasks. Source codes of this paper will be available on Github.
Low-latency Ultra Reliable 5G Communications: Finite-Blocklength Bounds and Coding Schemes
Venue: arXiv cs.IT 2016
Year: 2016

Future autonomous systems require wireless connectivity able to support extremely stringent requirements on both latency and reliability. In this paper, we leverage recent developments in the field of finite-blocklength information theory to illustrate how to optimally design wireless systems in the presence of such stringent constraints. Focusing on a multi-antenna Rayleigh block-fading channel, we obtain bounds on the maximum number of bits that can be transmitted within given bandwidth, latency, and reliability constraints, using an orthogonal frequency-division multiplexing system similar to LTE. These bounds unveil the fundamental interplay between latency, bandwidth, rate, and reliability. Furthermore, they suggest how to optimally use the available spatial and frequency diversity. Finally, we use our bounds to benchmark the performance of an actual coding scheme involving the transmission of short packets.
Machine-to-Machine (M2M) Communications in Software-defined and Virtualized Cellular Networks
Venue: arXiv cs.NI 2016
Year: 2016

Machine-to-machine (M2M) communications have attracted great attention from both academia and industry. In this paper, with recent advances in wireless network virtualization and software-defined networking (SDN), we propose a novel framework for M2M communications in software-defined cellular networks with wireless network virtualization. In the proposed framework, according to different functions and quality of service (QoS) requirements of machine-type communication devices (MTCDs), a hypervisor enables the virtualization of the physical M2M network, which is abstracted and sliced into multiple virtual M2M networks. In addition, we develop a decision-theoretic approach to optimize the random access process of M2M communications. Furthermore, we develop a feedback and control loop to dynamically adjust the number of resource blocks (RBs) that are used in the random access phase in a virtual M2M network by the SDN controller. Extensive simulation results with different system parameters are presented to show the performance of the proposed scheme.
Number Balancing is as hard as Minkowski's Theorem and Shortest Vector
Venue: arXiv cs.DM 2016
Year: 2016

The number balancing (NBP) problem is the following: given real numbers $a_1,\ldots,a_n \in [0,1]$, find two disjoint subsets $I_1,I_2 \subseteq [n]$ so that the difference $|\sum_{i \in I_1}a_i - \sum_{i \in I_2}a_i|$ of their sums is minimized. An application of the pigeonhole principle shows that there is always a solution where the difference is at most $O(\frac{\sqrt{n}}{2^n})$. Finding the minimum, however, is NP-hard. In polynomial time,the differencing algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most $n^{-Θ(\log n)}$, but no further improvement has been made since then. In this paper, we show a relationship between NBP and Minkowski's Theorem. First we show that an approximate oracle for Minkowski's Theorem gives an approximate NBP oracle. Perhaps more surprisingly, we show that an approximate NBP oracle gives an approximate Minkowski oracle. In particular, we prove that any polynomial time algorithm that guarantees a solution of difference at most $2^{\sqrt{n}} / 2^{n}$ would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem.
Fill it up: Exploiting partial dependency annotations in a minimum spanning tree parser
Venue: arXiv cs.CL 2016
Year: 2016

Unsupervised models of dependency parsing typically require large amounts of clean, unlabeled data plus gold-standard part-of-speech tags. Adding indirect supervision (e.g. language universals and rules) can help, but we show that obtaining small amounts of direct supervision - here, partial dependency annotations - provides a strong balance between zero and full supervision. We adapt the unsupervised ConvexMST dependency parser to learn from partial dependencies expressed in the Graph Fragment Language. With less than 24 hours of total annotation, we obtain 7% and 17% absolute improvement in unlabeled dependency scores for English and Spanish, respectively, compared to the same parser using only universal grammar constraints.
Kernel classification of connectomes based on earth mover's distance between graph spectra
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we tackle a problem of predicting phenotypes from structural connectomes. We propose that normalized Laplacian spectra can capture structural properties of brain networks, and hence graph spectral distributions are useful for a task of connectome-based classification. We introduce a kernel that is based on earth mover's distance (EMD) between spectral distributions of brain networks. We access performance of an SVM classifier with the proposed kernel for a task of classification of autism spectrum disorder versus typical development based on a publicly available dataset. Classification quality (area under the ROC-curve) obtained with the EMD-based kernel on spectral distributions is 0.71, which is higher than that based on simpler graph embedding methods.
A neuro-mathematical model for geometrical optical illusions
Venue: arXiv cs.CV 2016
Year: 2016

Geometrical optical illusions have been object of many studies due to the possibility they offer to understand the behaviour of low-level visual processing. They consist in situations in which the perceived geometrical properties of an object differ from those of the object in the visual stimulus. Starting from the geometrical model introduced by Citti and Sarti in [3], we provide a mathematical model and a computational algorithm which allows to interpret these phenomena and to qualitatively reproduce the perceived misperception.
Propositions in Linear Multirole Logic as Multiparty Session Types
Venue: arXiv cs.PL 2016
Year: 2016

We identify multirole logic as a new form of logic and formalize linear multirole logic (LMRL) as a natural generalization of classical linear logic (CLL). Among various meta-properties established for LMRL, we obtain one named multi-cut elimination stating that every cut between three (or more) sequents (as a generalization of a cut between two sequents) can be eliminated, thus extending the celebrated result of cut-elimination by Gentzen. We also present a variant of $π$-calculus for multiparty sessions that demonstrates a tight correspondence between process communication in this variant and multi-cut elimination in LMRL, thus extending some recent results by Caires and Pfenning (2010) and Wadler (2012), among others, along a similar line of work.
Teams in Online Scheduling Polls: Game-Theoretic Aspects
Venue: arXiv cs.GT 2016
Year: 2016

Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team would like to maximize its relative attendance in the meeting (i.e., the proportional number of its participating team members). We introduce a corresponding game, where each team can declare (in the scheduling poll) a lower total availability, in order to improve its relative attendance---the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.
"Model and Run" Constraint Networks with a MILP Engine
Venue: arXiv cs.AI 2016
Year: 2016

Constraint Programming (CP) users need significant expertise in order to model their problems appropriately, notably to select propagators and search strategies. This puts the brakes on a broader uptake of CP. In this paper, we introduce MICE, a complete Java CP modeler that can use any Mixed Integer Linear Programming (MILP) solver as a solution technique. Our aim is to provide an alternative tool for democratizing the "CP-style" modeling thanks to its simplicity of use, with reasonable solving capabilities. Our contributions include new decompositions of (reified) constraints and constraints on numerical variables.
Asynchronous Broadcasting with Bivalent Beeps
Venue: arXiv cs.DC 2016
Year: 2016

In broadcasting, one node of a network has a message that must be learned by all other nodes. We study deterministic algorithms for this fundamental communication task in a very weak model of wireless communication. The only signals sent by nodes are beeps. Moreover, they are delivered to neighbors of the beeping node in an asynchronous way: the time between sending and reception is finite but unpredictable. We first observe that under this scenario, no communication is possible, if beeps are all of the same strength. Hence we study broadcasting in the bivalent beeping model, where every beep can be either soft or loud. At the receiving end, if exactly one soft beep is received by a node in a round, it is heard as soft. Any other combination of beeps received in a round is heard as a loud beep. The cost of a broadcasting algorithm is the total number of beeps sent by all nodes. We consider four levels of knowledge that nodes may have about the network: anonymity (no knowledge whatsoever), ad-hoc (all nodes have distinct labels and every node knows only its own label), neighborhood awareness (every node knows its label and labels of all neighbors), and full knowledge (every node knows the entire labeled map of the network and the identity of the source). We first show that in the anonymous case, broadcasting is impossible even for very simple networks. For each of the other three knowledge levels we provide upper and lower bounds on the minimum cost of a broadcasting algorithm. Our results show separations between all these scenarios. Perhaps surprisingly, the jump in broadcasting cost between the ad-hoc and neighborhood awareness levels is much larger than between the neighborhood awareness and full knowledge levels, although in the two former levels knowledge of nodes is local, and in the latter it is global.
Distributed Estimation for Adaptive Networks Based on Serial-Inspired Diffusion
Venue: arXiv cs.MA 2016
Year: 2016

Distributed estimation and processing in networks modeled by graphs have received a great deal of interest recently, due to the benefits of decentralised processing in terms of performance and robustness to communications link failure between nodes of the network. Diffusion-based algorithms have been demonstrated to be among the most effective for distributed signal processing problems, through the combination of local node estimate updates and sharing of information with neighbour nodes through diffusion. In this work, we develop a serial-inspired approach based on message-passing strategies that provides a significant improvement in performance over prior art. The concept of serial processing in the graph has been successfully applied in sum-product based algorithms and here provides inspiration for an algorithm which makes use of the most up-to-date information in the graph in combination with the diffusion approach to offer improved performance.