OpenRaiser/Intern-Atlas huggingface dataset:
Boosting Named Entity Recognition with Neural Character Embeddings
Venue: arXiv cs.CL 2015
Year: 2015

Most state-of-the-art named entity recognition (NER) systems rely on handcrafted features and on the output of other NLP tasks such as part-of-speech (POS) tagging and text chunking. In this work we propose a language-independent NER system that uses automatically learned features only. Our approach is based on the CharWNN deep neural network, which uses word-level and character-level representations (embeddings) to perform sequential classification. We perform an extensive number of experiments using two annotated corpora in two different languages: HAREM I corpus, which contains texts in Portuguese; and the SPA CoNLL-2002 corpus, which contains texts in Spanish. Our experimental results shade light on the contribution of neural character embeddings for NER. Moreover, we demonstrate that the same neural network which has been successfully applied to POS tagging can also achieve state-of-the-art results for language-independet NER, using the same hyperparameters, and without any handcrafted features. For the HAREM I corpus, CharWNN outperforms the state-of-the-art system by 7.9 points in the F1-score for the total scenario (ten NE classes), and by 7.2 points in the F1 for the selective scenario (five NE classes).
Optimizing Dijkstra for real-world performance
Venue: arXiv cs.DC 2015
Year: 2015

Using Dijkstra's algorithm to compute the shortest paths in a graph from a single source node to all other nodes is common practice in industry and academia. Although the original description of the algorithm advises using a Fibonacci Heap as its internal queue, it has been noted that in practice, a binary (or $d$-ary) heap implementation is significantly faster. This paper introduces an even faster queue design for the algorithm. Our experimental results currently put our prototype implementation at about twice as fast as the Boost implementation of the algorithm on both real-world and generated large graphs. Furthermore, this preliminary implementation was written in only a few weeks, by a single programmer. The fact that such an early prototype compares favorably against Boost, a well-known open source library developed by expert programmers, gives us reason to believe our design for the queue is indeed better suited to the problem at hand, and the favorable time measurements are not a product of any specific implementation technique we employed.
Principles of Dataset Versioning: Exploring the Recreation/Storage Tradeoff
Venue: arXiv cs.DB 2015
Year: 2015

The relative ease of collaborative data science and analysis has led to a proliferation of many thousands or millions of $versions$ of the same datasets in many scientific and commercial domains, acquired or constructed at various stages of data analysis across many users, and often over long periods of time. Managing, storing, and recreating these dataset versions is a non-trivial task. The fundamental challenge here is the $storage-recreation\;trade-off$: the more storage we use, the faster it is to recreate or retrieve versions, while the less storage we use, the slower it is to recreate or retrieve versions. Despite the fundamental nature of this problem, there has been a surprisingly little amount of work on it. In this paper, we study this trade-off in a principled manner: we formulate six problems under various settings, trading off these quantities in various ways, demonstrate that most of the problems are intractable, and propose a suite of inexpensive heuristics drawing from techniques in delay-constrained scheduling, and spanning tree literature, to solve these problems. We have built a prototype version management system, that aims to serve as a foundation to our DATAHUB system for facilitating collaborative data science. We demonstrate, via extensive experiments, that our proposed heuristics provide efficient solutions in practical dataset versioning scenarios.
Live Video Synopsis for Multiple Cameras
Venue: arXiv cs.CV 2015
Year: 2015

Video surveillance cameras generate most of recorded video, and there is far more recorded video than operators can watch. Much progress has recently been made using summarization of recorded video, but such techniques do not have much impact on live video surveillance. We assume a camera hierarchy where a Master camera observes the decision-critical region, and one or more Slave cameras observe regions where past activity is important for making the current decision. We propose that when people appear in the live Master camera, the Slave cameras will display their past activities, and the operator could use past information for real-time decision making. The basic units of our method are action tubes, representing objects and their trajectories over time. Our object-based method has advantages over frame based methods, as it can handle multiple people, multiple activities for each person, and can address re-identification uncertainty.
A Survey Report on Operating Systems for Tiny Networked Sensors
Venue: arXiv cs.OS 2015
Year: 2015

Wireless sensor network (WSN) has attracted researchers worldwide to explore the research opportunities, with application mainly in health monitoring, industry automation, battlefields, home automation and environmental monitoring. A WSN is highly resource constrained in terms of energy, computation and memory. WSNs deployment ranges from the normal working environment up to hostile and hazardous environment such as in volcano monitoring and underground mines. These characteristics of WSNs hold additional set of challenges in front of the operating system designer. The objective of this survey is to highlight the features and weakness of the opearting system available for WSNs, with the focus on the current application demands. The paper also discusses the operating system design issues in terms of architecture, programming model, scheduling and memory management and support for real time applications.
A consensus based network intrusion detection system
Venue: arXiv cs.CR 2015
Year: 2015

Network intrusion detection is the process of identifying malicious behaviors that target a network and its resources. Current systems implementing intrusion detection processes observe traffic at several data collecting points in the network but analysis is often centralized or partly centralized. These systems are not scalable and suffer from the single point of failure, i.e. attackers only need to target the central node to compromise the whole system. This paper proposes an anomaly-based fully distributed network intrusion detection system where analysis is run at each data collecting point using a naive Bayes classifier. Probability values computed by each classifier are shared among nodes using an iterative average consensus protocol. The final analysis is performed redundantly and in parallel at the level of each data collecting point, thus avoiding the single point of failure issue. We run simulations focusing on DDoS attacks with several network configurations, comparing the accuracy of our fully distributed system with a hierarchical one. We also analyze communication costs and convergence speed during consensus phases.
Reactive Reasoning with the Event Calculus
Venue: arXiv cs.AI 2015
Year: 2015

Systems for symbolic event recognition accept as input a stream of time-stamped events from sensors and other computational devices, and seek to identify high-level composite events, collections of events that satisfy some pattern. RTEC is an Event Calculus dialect with novel implementation and 'windowing' techniques that allow for efficient event recognition, scalable to large data streams. RTEC can deal with applications where event data arrive with a (variable) delay from, and are revised by, the underlying sources. RTEC can update already recognised events and recognise new events when data arrive with a delay or following data revision. Our evaluation shows that RTEC can support real-time event recognition and is capable of meeting the performance requirements identified in a recent survey of event processing use cases.
Towards Ideal Semantics for Analyzing Stream Reasoning
Venue: arXiv cs.AI 2015
Year: 2015

The rise of smart applications has drawn interest to logical reasoning over data streams. Recently, different query languages and stream processing/reasoning engines were proposed in different communities. However, due to a lack of theoretical foundations, the expressivity and semantics of these diverse approaches are given only informally. Towards clear specifications and means for analytic study, a formal framework is needed to define their semantics in precise terms. To this end, we present a first step towards an ideal semantics that allows for exact descriptions and comparisons of stream reasoning systems.
Spatially Coupled Codes and Optical Fiber Communications: An Ideal Match?
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we highlight the class of spatially coupled codes and discuss their applicability to long-haul and submarine optical communication systems. We first demonstrate how to optimize irregular spatially coupled LDPC codes for their use in optical communications with limited decoding hardware complexity and then present simulation results with an FPGA-based decoder where we show that very low error rates can be achieved and that conventional block-based LDPC codes can be outperformed. In the second part of the paper, we focus on the combination of spatially coupled LDPC codes with different demodulators and detectors, important for future systems with adaptive modulation and for varying channel characteristics. We demonstrate that SC codes can be employed as universal, channel-agnostic coding schemes.
Millimeter Wave Beamforming Based on WiFi Fingerprinting in Indoor Environment
Venue: arXiv cs.NI 2015
Year: 2015

Millimeter Wave (mm-w), especially the 60 GHz band, has been receiving much attention as a key enabler for the 5G cellular networks. Beamforming (BF) is tremendously used with mm-w transmissions to enhance the link quality and overcome the channel impairments. The current mm-w BF mechanism, proposed by the IEEE 802.11ad standard, is mainly based on exhaustive searching the best transmit (TX) and receive (RX) antenna beams. This BF mechanism requires a very high setup time, which makes it difficult to coordinate a multiple number of mm-w Access Points (APs) in mobile channel conditions as a 5G requirement. In this paper, we propose a mm-w BF mechanism, which enables a mm-w AP to estimate the best beam to communicate with a User Equipment (UE) using statistical learning. In this scheme, the fingerprints of the UE WiFi signal and mm-w best beam identification (ID) are collected in an offline phase on a grid of arbitrary learning points (LPs) in target environments. Therefore, by just comparing the current UE WiFi signal with the pre-stored UE WiFi fingerprints, the mm-w AP can immediately estimate the best beam to communicate with the UE at its current position. The proposed mm-w BF can estimate the best beam, using a very small setup time, with a comparable performance to the exhaustive search BF.
Soft Decision Cooperative Spectrum Sensing Based Upon Noise Uncertainty Estimation
Venue: arXiv cs.IT 2015
Year: 2015

Spectrum Sensing (SS) constitutes the most critical task i n Cognitive Radio (CR) systems for Primary User (PU) detection. Cooperative Spectrum Sensing (CSS) is introduced to enhance the detection reliability of the PU in fading environments. In this paper, we propose a soft decision based CSS algorithm using energy detection by taking into account the noise uncertainty effect. In the proposed algorithm, two threshold levels are utilized based on predicting the current PU activity, which can be successfully expected using a simple successive averaging process with time. The two threshold levels are evaluated based on estimating the noise uncertainty factor. In addition, they are toggled in a dynamic manner to compensate the noise uncertainty effect and to increase the probability of detection and decrease the probability of false alarm. Theoretical analysis is performed on the proposed algorithm to evaluate its enhanced false alarm and detection probabilities over the conventional soft decision CSS using different combining schemes. In addition, simulation results show the high efficiency of the proposed scheme compared to the conventional soft decision CSS, with high computational complexity enhancements.
A generalization of Kung's theorem
Venue: arXiv cs.IT 2015
Year: 2015

We give a generalization of Kung's theorem on critical exponents of linear codes over a finite field, in terms of sums of extended weight polynomials of linear codes. For all i=k+1,...,n, we give an upper bound on the smallest integer m such that there exist m codewords whose union of supports has cardinality at least i.
Object Modelling with a Handheld RGB-D Camera
Venue: arXiv cs.CV 2015
Year: 2015

This work presents a flexible system to reconstruct 3D models of objects captured with an RGB-D sensor. A major advantage of the method is that our reconstruction pipeline allows the user to acquire a full 3D model of the object. This is achieved by acquiring several partial 3D models in different sessions that are automatically merged together to reconstruct a full model. In addition, the 3D models acquired by our system can be directly used by state-of-the-art object instance recognition and object tracking modules, providing object-perception capabilities for different applications, such as human-object interaction analysis or robot grasping. The system does not impose constraints in the appearance of objects (textured, untextured) nor in the modelling setup (moving camera with static object or a turn-table setup). The proposed reconstruction system has been used to model a large number of objects resulting in metrically accurate and visually appealing 3D models.
On the relation between accuracy and fairness in binary classification
Venue: arXiv cs.LG 2015
Year: 2015

Our study revisits the problem of accuracy-fairness tradeoff in binary classification. We argue that comparison of non-discriminatory classifiers needs to account for different rates of positive predictions, otherwise conclusions about performance may be misleading, because accuracy and discrimination of naive baselines on the same dataset vary with different rates of positive predictions. We provide methodological recommendations for sound comparison of non-discriminatory classifiers, and present a brief theoretical and empirical analysis of tradeoffs between accuracy and non-discrimination.
Graph edit distance : a new binary linear programming formulation
Venue: arXiv cs.DS 2015
Year: 2015

Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method.
A Pareto Front-Based Multiobjective Path Planning Algorithm
Venue: arXiv cs.AI 2015
Year: 2015

Path planning is one of the most vital elements of mobile robotics. With a priori knowledge of the environment, global path planning provides a collision-free route through the workspace. The global path plan can be calculated with a variety of informed search algorithms, most notably the A* search method, guaranteed to deliver a complete and optimal solution that minimizes the path cost. Path planning optimization typically looks to minimize the distance traversed from start to goal, yet many mobile robot applications call for additional path planning objectives, presenting a multiobjective optimization (MOO) problem. Past studies have applied genetic algorithms to MOO path planning problems, but these may have the disadvantages of computational complexity and suboptimal solutions. Alternatively, the algorithm in this paper approaches MOO path planning with the use of Pareto fronts, or finding non-dominated solutions. The algorithm presented incorporates Pareto optimality into every step of A* search, thus it is named A*-PO. Results of simulations show A*-PO outperformed several variations of the standard A* algorithm for MOO path planning. A planetary exploration rover case study was added to demonstrate the viability of A*-PO in a real-world application.
Approximate Closest Community Search in Networks
Venue: arXiv cs.SI 2015
Year: 2015

Recently, there has been significant interest in the study of the community search problem in social and information networks: given one or more query nodes, find densely connected communities containing the query nodes. However, most existing studies do not address the "free rider" issue, that is, nodes far away from query nodes and irrelevant to them are included in the detected community. Some state-of-the-art models have attempted to address this issue, but not only are their formulated problems NP-hard, they do not admit any approximations without restrictive assumptions, which may not always hold in practice. In this paper, given an undirected graph G and a set of query nodes Q, we study community search using the k-truss based community model. We formulate our problem of finding a closest truss community (CTC), as finding a connected k-truss subgraph with the largest k that contains Q, and has the minimum diameter among such subgraphs. We prove this problem is NP-hard. Furthermore, it is NP-hard to approximate the problem within a factor $(2-\varepsilon)$, for any $\varepsilon >0 $. However, we develop a greedy algorithmic framework, which first finds a CTC containing Q, and then iteratively removes the furthest nodes from Q, from the graph. The method achieves 2-approximation to the optimal solution. To further improve the efficiency, we make use of a compact truss index and develop efficient algorithms for k-truss identification and maintenance as nodes get eliminated. In addition, using bulk deletion optimization and local exploration strategies, we propose two more efficient algorithms. One of them trades some approximation quality for efficiency while the other is a very efficient heuristic. Extensive experiments on 6 real-world networks show the effectiveness and efficiency of our community model and search algorithms.
Nearest Neighbor based Clustering Algorithm for Large Data Sets
Venue: arXiv cs.DS 2015
Year: 2015

Clustering is an unsupervised learning technique in which data or objects are grouped into sets based on some similarity measure. Most of the clustering algorithms assume that the main memory is infinite and can accommodate the set of patterns. In reality many applications give rise to a large set of patterns which does not fit in the main memory. When the data set is too large, much of the data is stored in the secondary memory. Input/Outputs (I/O) from the disk are the major bottleneck in designing efficient clustering algorithms for large data sets. Different designing techniques have been used to design clustering algorithms for large data sets. External memory algorithms are one class of algorithms which can be used for large data sets. These algorithms exploit the hierarchical memory structure of the computers by incorporating locality of reference directly in the algorithm. This paper makes some contribution towards designing clustering algorithms in the external memory model (Proposed by Aggarwal and Vitter 1988) to make the algorithms scalable. In this paper, it is shown that the Shared near neighbors algorithm is not very I/O efficient since the computational complexity is same as the I/O complexity. The algorithm is designed in the external memory model and I/O complexity is reduced. The computational complexity remains same. We substantiate the theoretical analysis by showing the performance of the algorithms with their traditional counterpart by implementing in STXXL library.
Variable Neighborhood Search for solving Bandwidth Coloring Problem
Venue: arXiv cs.DS 2015
Year: 2015

This paper presents a variable neighborhood search (VNS) algorithm for solving bandwidth coloring problem (BCP) and bandwidth multicoloring problem (BMCP). BCP and BMCP are generalizations of the well known vertex coloring problem and they are of a great interest from both theoretical and practical points of view. Presented VNS combines a shaking procedure which perturbs the colors for an increasing number of vertices and a specific variable neighborhood descent (VND) procedure, based on the specially designed arrangement of the vertices which are the subject of re-coloring. By this approach, local search is split in a series of disjoint procedures, enabling better choice of the vertices which are addressed to re-color. The experiments show that proposed method is highly competitive with the state-of-the-art algorithms and improves 2 out of 33 previous best known solutions for BMCP.
Direct Variational Perspective Shape from Shading with Cartesian Depth Parametrisation
Venue: arXiv cs.CV 2015
Year: 2015

Most of today's state-of-the-art methods for perspective shape from shading are modelled in terms of partial differential equations (PDEs) of Hamilton-Jacobi type. To improve the robustness of such methods w.r.t. noise and missing data, first approaches have recently been proposed that seek to embed the underlying PDE into a variational framework with data and smoothness term. So far, however, such methods either make use of a radial depth parametrisation that makes the regularisation hard to interpret from a geometrical viewpoint or they consider indirect smoothness terms that require additional consistency constraints to provide valid solutions. Moreover the minimisation of such frameworks is an intricate task, since the underlying energy is typically non-convex. In our paper we address all three of the aforementioned issues. First, we propose a novel variational model that operates directly on the Cartesian depth. In this context, we also point out a common mistake in the derivation of the surface normal. Moreover, we employ a direct second-order regulariser with edge-preservation property. This direct regulariser yields by construction valid solutions without requiring additional consistency constraints. Finally, we also propose a novel coarse-to-fine minimisation framework based on an alternating explicit scheme. This framework allows us to avoid local minima during the minimisation and thus to improve the accuracy of the reconstruction. Experiments show the good quality of our model as well as the usefulness of the proposed numerical scheme.