OpenRaiser/Intern-Atlas huggingface dataset:
Learning Preferences for Manipulation Tasks from Online Coactive Feedback
Venue: arXiv cs.RO 2016
Year: 2016

We consider the problem of learning preferences over trajectories for mobile manipulators such as personal robots and assembly line robots. The preferences we learn are more intricate than simple geometric constraints on trajectories; they are rather governed by the surrounding context of various objects and human interactions in the environment. We propose a coactive online learning framework for teaching preferences in contextually rich environments. The key novelty of our approach lies in the type of feedback expected from the user: the human user does not need to demonstrate optimal trajectories as training data, but merely needs to iteratively provide trajectories that slightly improve over the trajectory currently proposed by the system. We argue that this coactive preference feedback can be more easily elicited than demonstrations of optimal trajectories. Nevertheless, theoretical regret bounds of our algorithm match the asymptotic rates of optimal trajectory algorithms. We implement our algorithm on two high degree-of-freedom robots, PR2 and Baxter, and present three intuitive mechanisms for providing such incremental feedback. In our experimental evaluation we consider two context rich settings -- household chores and grocery store checkout -- and show that users are able to train the robot with just a few feedbacks (taking only a few minutes).\footnote{Parts of this work has been published at NIPS and ISRR conferences~\citep{Jain13,Jain13b}. This journal submission presents a consistent full paper, and also includes the proof of regret bounds, more details of the robotic system, and a thorough related work.}
Robust Method of Vote Aggregation and Proposition Verification for Invariant Local Features
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a method for analysis of the vote space created from the local features extraction process in a multi-detection system. The method is opposed to the classic clustering approach and gives a high level of control over the clusters composition for further verification steps. Proposed method comprises of the graphical vote space presentation, the proposition generation, the two-pass iterative vote aggregation and the cascade filters for verification of the propositions. Cascade filters contain all of the minor algorithms needed for effective object detection verification. The new approach does not have the drawbacks of the classic clustering approaches and gives a substantial control over process of detection. Method exhibits an exceptionally high detection rate in conjunction with a low false detection chance in comparison to alternative methods.
Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
Venue: arXiv cs.DS 2016
Year: 2016

We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed epsilon > 0, we present a (1+epsilon)-approximate distance oracle with O(n(loglog n)^2) space and O((loglog n)^3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(n log n) to O(n(loglog n)^5).
Cross-layer distributed power control: A repeated games formulation to improve the sum energy-efficiency
Venue: arXiv cs.NI 2016
Year: 2016

The main objective of this work is to improve the energy-efficiency (EE) of a multiple access channel (MAC) system, through power control, in a distributed manner. In contrast with many existing works on energy-efficient power control, which ignore the possible presence of a queue at the transmitter, we consider a new generalized cross-layer EE metric. This approach is relevant when the transmitters have a non-zero energy cost even when the radiated power is zero and takes into account the presence of a finite packet buffer and packet arrival at the transmitter. As the Nash equilibrium (NE) is an energy-inefficient solution, the present work aims at overcoming this deficit by improving the global energy-efficiency. Indeed, as the considered system has multiple agencies each with their own interest, the performance metric reflecting the individual interest of each decision maker is the global energy-efficiency defined then as the sum over individual energy-efficiencies. Repeated games (RG) are investigated through the study of two dynamic games (finite RG and discounted RG), whose equilibrium is defined when introducing a new operating point (OP), Pareto-dominating the NE and relying only on individual channel state information (CSI). Accordingly, closed-form expressions of the minimum number of stages of the game for finite RG (FRG) and the maximum discount factor of the discounted RG (DRG) were established. The cross-layer model in the RG formulation leads to achieving a shorter minimum number of stages in the FRG even for higher number of users. In addition, the social welfare (sum of utilities) in the DRG decreases slightly with the cross-layer model when the number of users increases while it is reduced considerably with the Goodman model. Finally, we show that in real systems with random packet arrivals, the cross-layer power control algorithm outperforms the Goodman algorithm.
Joint learning of ontology and semantic parser from text
Venue: arXiv cs.AI 2016
Year: 2016

Semantic parsing methods are used for capturing and representing semantic meaning of text. Meaning representation capturing all the concepts in the text may not always be available or may not be sufficiently complete. Ontologies provide a structured and reasoning-capable way to model the content of a collection of texts. In this work, we present a novel approach to joint learning of ontology and semantic parser from text. The method is based on semi-automatic induction of a context-free grammar from semantically annotated text. The grammar parses the text into semantic trees. Both, the grammar and the semantic trees are used to learn the ontology on several levels -- classes, instances, taxonomic and non-taxonomic relations. The approach was evaluated on the first sentences of Wikipedia pages describing people.
Assessing Mission Impact of Cyberattacks: Report of the NATO IST-128 Workshop
Venue: arXiv cs.CR 2016
Year: 2016

This report presents the results of a workshop conducted by the North Atlantic Treaty Organization (NATO) Information Systems Technology (IST) Panel in Istanbul, Turkey, in June 2015 to explore science and technology for characterizing the impact of cyber-attacks on missions. Military mission success is highly dependent on the communications and information systems (CISs) that support the mission and their use in the cyber battlespace. The inexorably growing dependency on computational information processing for weapons, intelligence, communication, and logistics systems continues to increase the vulnerability of missions to various cyber threats. Attacks on CISs or other cyber incidents degrade or disrupt the usage of CISs, and the resulting mission capability, performance, and completion. These incidents are expected to increase in frequency and sophistication. The workshop participants concluded that the key to solving the mission impact assessment problem was in adopting and developing a new model-driven paradigm that creates and validates mechanisms of modeling the mission organization, the mission(s), and the cyber-vulnerable systems that support the mission(s). Such models then simulate or portray the impacts of the cyber-attacks. In addition, such model-based analysis could explore multiple alternative mitigation and work-around strategies - an essential part of coping with mission impact - and select the optimal course of mitigating actions. Only such a paradigm can be expected to provide meaningful, actionable information about mission impacts that have not been seen before or do not match prior experiences and patterns. The papers presented at this workshop are available in an accompanying volume, Proceedings of the NATO Workshop IST-128, Assessing Mission Impact of Cyber Attacks.
Complex Decomposition of the Negative Distance kernel
Venue: arXiv cs.LG 2016
Year: 2016

A Support Vector Machine (SVM) has become a very popular machine learning method for text classification. One reason for this relates to the range of existing kernels which allow for classifying data that is not linearly separable. The linear, polynomial and RBF (Gaussian Radial Basis Function) kernel are commonly used and serve as a basis of comparison in our study. We show how to derive the primal form of the quadratic Power Kernel (PK) -- also called the Negative Euclidean Distance Kernel (NDK) -- by means of complex numbers. We exemplify the NDK in the framework of text categorization using the Dewey Document Classification (DDC) as the target scheme. Our evaluation shows that the power kernel produces F-scores that are comparable to the reference kernels, but is -- except for the linear kernel -- faster to compute. Finally, we show how to extend the NDK-approach by including the Mahalanobis distance.
Notions of Connectivity in Overlay Networks
Venue: arXiv cs.DC 2016
Year: 2016

" How well connected is the network? " This is one of the most fundamental questions one would ask when facing the challenge of designing a communication network. Three major notions of connectivity have been considered in the literature, but in the context of traditional (single-layer) networks, they turn out to be equivalent. This paper introduces a model for studying the three notions of connectivity in multi-layer networks. Using this model, it is easy to demonstrate that in multi-layer networks the three notions may differ dramatically. Unfortunately, in contrast to the single-layer case, where the values of the three connectivity notions can be computed efficiently, it has been recently shown in the context of WDM networks (results that can be easily translated to our model) that the values of two of these notions of connectivity are hard to compute or even approximate in multi-layer networks. The current paper shed some positive light into the multi-layer connectivity topic: we show that the value of the third connectivity notion can be computed in polynomial time and develop an approximation for the construction of well connected overlay networks.
Tool support for reasoning in display calculi
Venue: arXiv cs.LO 2016
Year: 2016

We present a tool for reasoning in and about propositional sequent calculi. One aim is to support reasoning in calculi that contain a hundred rules or more, so that even relatively small pen and paper derivations become tedious and error prone. As an example, we implement the display calculus D.EAK of dynamic epistemic logic. Second, we provide embeddings of the calculus in the theorem prover Isabelle for formalising proofs about D.EAK. As a case study we show that the solution of the muddy children puzzle is derivable for any number of muddy children. Third, there is a set of meta-tools, that allows us to adapt the tool for a wide variety of user defined calculi.
On Measuring the Geographic Diversity of Internet Routes
Venue: arXiv cs.NI 2016
Year: 2016

Route diversity in networks is elemental for establishing reliable, high-capacity connections with appropriate security between endpoints. As for the Internet, route diversity has already been studied at both Autonomous System- and router-level topologies by means of graph theoretical disjoint paths. In this paper we complement these approaches by proposing a method for measuring the diversity of Internet paths in a geographical sense. By leveraging the recent developments in IP geolocation we show how to map the paths discovered by traceroute into geographically equivalent classes. This allows us to identify the geographical footprints of the major transmission paths between end-hosts, and building on our observations, we propose a quantitative measure for geographical diversity of Internet routes between any two hosts.
Streaming Gibbs Sampling for LDA Model
Venue: arXiv cs.LG 2016
Year: 2016

Streaming variational Bayes (SVB) is successful in learning LDA models in an online manner. However previous attempts toward developing online Monte-Carlo methods for LDA have little success, often by having much worse perplexity than their batch counterparts. We present a streaming Gibbs sampling (SGS) method, an online extension of the collapsed Gibbs sampling (CGS). Our empirical study shows that SGS can reach similar perplexity as CGS, much better than SVB. Our distributed version of SGS, DSGS, is much more scalable than SVB mainly because the updates' communication complexity is small.
Introducing CitedReferencesExplorer (CRExplorer): A program for Reference Publication Year Spectroscopy with Cited References Standardization
Venue: arXiv cs.DL 2016
Year: 2016

We introduce a new tool - the CitedReferencesExplorer (CRExplorer, www.crexplorer.net) - which can be used to disambiguate and analyze the cited references (CRs) of a publication set downloaded from the Web of Science (WoS). The tool is especially suitable to identify those publications which have been frequently cited by the researchers in a field and thereby to study for example the historical roots of a research field or topic. CRExplorer simplifies the identification of key publications by enabling the user to work with both a graph for identifying most frequently cited reference publication years (RPYs) and the list of references for the RPYs which have been most frequently cited. A further focus of the program is on the standardization of CRs. It is a serious problem in bibliometrics that there are several variants of the same CR in the WoS. In this study, CRExplorer is used to study the CRs of all papers published in the Journal of Informetrics. The analyses focus on the most important papers published between 1980 and 1990.
Adaptive and Efficient Nonlinear Channel Equalization for Underwater Acoustic Communication
Venue: arXiv cs.LG 2016
Year: 2016

We investigate underwater acoustic (UWA) channel equalization and introduce hierarchical and adaptive nonlinear channel equalization algorithms that are highly efficient and provide significantly improved bit error rate (BER) performance. Due to the high complexity of nonlinear equalizers and poor performance of linear ones, to equalize highly difficult underwater acoustic channels, we employ piecewise linear equalizers. However, in order to achieve the performance of the best piecewise linear model, we use a tree structure to hierarchically partition the space of the received signal. Furthermore, the equalization algorithm should be completely adaptive, since due to the highly non-stationary nature of the underwater medium, the optimal MSE equalizer as well as the best piecewise linear equalizer changes in time. To this end, we introduce an adaptive piecewise linear equalization algorithm that not only adapts the linear equalizer at each region but also learns the complete hierarchical structure with a computational complexity only polynomial in the number of nodes of the tree. Furthermore, our algorithm is constructed to directly minimize the final squared error without introducing any ad-hoc parameters. We demonstrate the performance of our algorithms through highly realistic experiments performed on accurately simulated underwater acoustic channels.
A Proof-of-Concept Device-to-Device Communication Testbed
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents the design and development of proof-of-concept Device-to-Device (D2D) Communication testbed. This testbed also seeks to address the design issues involved in the implementation of a D2D network in a realistic scenario. The performance of this testbed has been validated by emulating a Cellular network consisting of a Base Staion (BTS) and many D2D devices in its proximity. The devices and the BTS coordinate and communicate with each other to select the optimum communication range, mode of communication and transmit parameters. Through the experimental results it has been shown that the proposed testbed has a communication radius of 120m and a D2D communication range of 62m with over 90% efficiency.
BitAV: Fast Anti-Malware by Distributed Blockchain Consensus and Feedforward Scanning
Venue: arXiv cs.CR 2016
Year: 2016

I present the design and implementation of a novel anti-malware environment called BitAV. BitAV allows for the decentralization of the update and maintenance mechanisms of the software, traditionally performed by a central host, and uses a staggered scanning mechanism in order to improve performance. The peer-to-peer network maintenance mechanism lowered the average update propagation speed by 500% and is far less susceptible to targeted denial-of-service attacks. The feedforward scanning mechanism significantly improved end-to-end performance of the malware matching system, to a degree of an average 14x increase, by decomposing the file matching process into efficient queries that operate in verifiably constant time.
Sparse signals for the control of human movements using the infinity norm
Venue: arXiv cs.SY 2016
Year: 2016

Optimal control models have been successful in describing many aspects of human movement. The interpretation of such models regarding neuronal implementation of the human motor system is not clear. An important aspects of optimal control policies is the notion of cost. Optimal control seeks to minimize a notion of cost, while meeting certain goals. We offer a method to transform current methods in the literature from their traditional form by changing the norm by which cost is assessed. We show how sparsity can be introduced into current optimal approaches that use continuous control signals. We assess cost using the infinity norm. This results in optimal signals which can be represented by a small amount of Dirac delta functions. Sparsity has played an important role in theoretical neuroscience for information processing (such as vision). In this work, to obtain sparse control signals, the infinity norm is used as a penalty on the control signal, which is then encoded with Dirac delta functions. We show, for a basic physical system, a point mass can be moved between two points in a way that resembles human fast reaching movements. Despite the sparse nature of the control signal, the movements that result are continuous and smooth. These control signals are simpler than their non-sparse counterparts, yet yield comparable results when applied towards modeling reaching movements. In addition, such sparse control signals resemble a sequence of spikes, giving this approach a biological interpretation. Actual neuronal implementations are more complex. However, this work shows, in principle, that sparsely encoded control signals are a plausible implementation for the control of reaching movements. Leading techniques for modeling human movements can easily be adjusted in order to introduce sparsity, with a biological interpretation and the simplified information content of the control signal.
Repeated-root constacyclic codes of length $3lp^{s}$ and their dual codes
Venue: arXiv cs.IT 2016
Year: 2016

Let $p\neq3$ be any prime and $l\neq3$ be any odd prime with $gcd(p,l)=1$. $F_{q}^{*}=\langleξ\rangle$ is decomposed into mutually disjoint union of $gcd(q-1,3lp^{s})$ coset over the subgroup $\langleξ^{3lp^{s}}\rangle$, where $ξ$ is a primitive $(q-1)$th root of unity. We classify all repeated-root constacyclic codes of length $3lp^{s}$ over the finite field $F_{q}$ into some equivalence classes by the decomposition, where $q=p^{m}$, $s$ and $m$ are positive integers. According to the equivalence classes, we explicitly determine the generator polynomials of all repeated-root constacyclic codes of length $3lp^{s}$ over $F_{q}$ and their dual codes. Self-dual cyclic(negacyclic) codes of length $3lp^{s}$ over $F_{q}$ exist only when $p=2$. And we give all self-dual cyclic(negacyclic) codes of length $3l2^{s}$over $F_{2^{m}}$ and its enumeration.
A Routing Mechanism Based on Social Networks and Betweenness Centrality in Delay-Tolerant Networks
Venue: arXiv cs.NI 2016
Year: 2016

With the growing popularity of mobile smart devices, the existing networks are unable to meet the requirement of many complex scenarios; current network architectures and protocols do not work well with the network with high latency and frequent disconnections. To improve the performance of these networks some scholars opened up a new research field, delay-tolerant networks, in which one of the important research subjects is the forwarding and routing mechanism of data packets. This paper presents a routing scheme based on social networks owing to the fact that nodes in computer networks and social networks have high behavioural similarity. To further improve efficiency this paper also suggests a mechanism, which is the improved version of an existing betweenness centrality based routing algorithm. The experiments showed that the proposed scheme has better performance than the existing friendship routing algorithms.
Maximum Leaf Spanning Trees of Growing Sierpinski Networks Models
Venue: arXiv cs.DS 2016
Year: 2016

The dynamical phenomena of complex networks are very difficult to predict from local information due to the rich microstructures and corresponding complex dynamics. On the other hands, it is a horrible job to compute some stochastic parameters of a large network having thousand and thousand nodes. We design several recursive algorithms for finding spanning trees having maximal leaves (MLS-trees) in investigation of topological structures of Sierpinski growing network models, and use MLS-trees to determine the kernels, dominating and balanced sets of the models. We propose a new stochastic method for the models, called the edge-cumulative distribution, and show that it obeys a power law distribution.
Elaborate lexicon extended language with a lot of conceptual information
Venue: arXiv cs.SE 2016
Year: 2016

The use of model such as LEL (Lexicon Extended Language) in natural language is very interesting in Requirements Engineering. But LEL, even if it is derived from the Universe of Discourse (UofD) does not provide further details on the concepts it describes. However, we believe that the elements inherent in the conceptual level of a system are already defined in the Universe of Discourse. Therefore, in this work we propose a more elaborate natural language model called eLEL. It is a model that describes the concepts in a domain in more detail than the conventional LEL. We also propose a modeling process of a domain using an eLEL model.
Guarded Dependent Type Theory with Coinductive Types
Venue: arXiv cs.LO 2016
Year: 2016

We present guarded dependent type theory, gDTT, an extensional dependent type theory with a `later' modality and clock quantifiers for programming and proving with guarded recursive and coinductive types. The later modality is used to ensure the productivity of recursive definitions in a modular, type based, way. Clock quantifiers are used for controlled elimination of the later modality and for encoding coinductive types using guarded recursive types. Key to the development of gDTT are novel type and term formers involving what we call `delayed substitutions'. These generalise the applicative functor rules for the later modality considered in earlier work, and are crucial for programming and proving with dependent types. We show soundness of the type theory with respect to a denotational model.