OpenRaiser/Intern-Atlas huggingface dataset:
An efficient algorithm for computing the edit distance of a regular language via input-altering transducers
Venue: arXiv cs.FL 2014
Year: 2014

We revisit the problem of computing the edit distance of a regular language given via an NFA. This problem relates to the inherent maximal error-detecting capability of the language in question. We present an efficient algorithm for solving this problem which executes in time $O(r^2n^2d)$, where $r$ is the cardinality of the alphabet involved, $n$ is the number of transitions in the given NFA, and $d$ is the computed edit distance. We have implemented the algorithm and present here performance tests. The correctness of the algorithm is based on the result (also presented here) that the particular error-detection property related to our problem can be defined via an input-altering transducer.
Lattice Codes for the Binary Deletion Channel
Venue: arXiv cs.IT 2014
Year: 2014

The construction of deletion codes for the Levenshtein metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of translates of lattices. These lattices, in turn, are obtained from Construction~A applied to binary codes and $\Z_4-$codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices.
Specifying and Placing Chains of Virtual Network Functions
Venue: arXiv cs.NI 2014
Year: 2014

Network appliances perform different functions on network flows and constitute an important part of an operator's network. Normally, a set of chained network functions process network flows. Following the trend of virtualization of networks, virtualization of the network functions has also become a topic of interest. We define a model for formalizing the chaining of network functions using a context-free language. We process deployment requests and construct virtual network function graphs that can be mapped to the network. We describe the mapping as a Mixed Integer Quadratically Constrained Program (MIQCP) for finding the placement of the network functions and chaining them together considering the limited network resources and requirements of the functions. We have performed a Pareto set analysis to investigate the possible trade-offs between different optimization objectives.
How inefficient can a sort algorithm be?
Venue: arXiv cs.DS 2014
Year: 2014

We find large lower bounds for a certain family of algorithms, and prove that such bounds are limited only by natural computability arguments.
Online Rotor Resistance Adaptation Of Induction Motor Drive
Venue: arXiv cs.SY 2014
Year: 2014

In this paper an adaptive control systems scheme is used to update the rotor resistance of an induction motor drive. Rotor resistance of the induction motor drive is dependent on the temperature where it is installed for one Induced Draft Fan (I.D Fan) in one of the 500 MW generating thermal power plant. The rotor resistance adaptation is of induction motor drive is achieved through Indirect Field Oriented. The desired value of the rotor flux along the q - axis should ideally be zero. This condition acts as a reference model for the proposed Adaptive Control scheme. Inductance does not change with the temperature. Therefore, the only parameter which changes with the temperature in the adjustable model is the rotor resistance. This resistance is adjusted such that the flux along the q - axis is driven to zero. The proposed method effectively adjusts the rotor resistance on-line and keeps the machine field oriented. The effectiveness of the proposed scheme is tested through simulation and is experimentally verified.
A self-organizing system for urban traffic control based on predictive interval microscopic model
Venue: arXiv cs.AI 2014
Year: 2014

This paper introduces a self-organizing traffic signal system for an urban road network. The key elements of this system are agents that control traffic signals at intersections. Each agent uses an interval microscopic traffic model to predict effects of its possible control actions in a short time horizon. The executed control action is selected on the basis of predicted delay intervals. Since the prediction results are represented by intervals, the agents can recognize and suspend those control actions, whose positive effect on the performance of traffic control is uncertain. Evaluation of the proposed traffic control system was performed in a simulation environment. The simulation experiments have shown that the proposed approach results in an improved performance, particularly for non-uniform traffic streams.
Local Decorrelation For Improved Detection
Venue: arXiv cs.CV 2014
Year: 2014

Even with the advent of more sophisticated, data-hungry methods, boosted decision trees remain extraordinarily successful for fast rigid object detection, achieving top accuracy on numerous datasets. While effective, most boosted detectors use decision trees with orthogonal (single feature) splits, and the topology of the resulting decision boundary may not be well matched to the natural topology of the data. Given highly correlated data, decision trees with oblique (multiple feature) splits can be effective. Use of oblique splits, however, comes at considerable computational expense. Inspired by recent work on discriminative decorrelation of HOG features, we instead propose an efficient feature transform that removes correlations in local neighborhoods. The result is an overcomplete but locally decorrelated representation ideally suited for use with orthogonal decision trees. In fact, orthogonal trees with our locally decorrelated features outperform oblique trees trained over the original features at a fraction of the computational cost. The overall improvement in accuracy is dramatic: on the Caltech Pedestrian Dataset, we reduce false positives nearly tenfold over the previous state-of-the-art.
Shared Representation Learning for Heterogeneous Face Recognition
Venue: arXiv cs.CV 2014
Year: 2014

After intensive research, heterogenous face recognition is still a challenging problem. The main difficulties are owing to the complex relationship between heterogenous face image spaces. The heterogeneity is always tightly coupled with other variations, which makes the relationship of heterogenous face images highly nonlinear. Many excellent methods have been proposed to model the nonlinear relationship, but they apt to overfit to the training set, due to limited samples. Inspired by the unsupervised algorithms in deep learning, this paper proposes an novel framework for heterogeneous face recognition. We first extract Gabor features at some localized facial points, and then use Restricted Boltzmann Machines (RBMs) to learn a shared representation locally to remove the heterogeneity around each facial point. Finally, the shared representations of local RBMs are connected together and processed by PCA. Two problems (Sketch-Photo and NIR-VIS) and three databases are selected to evaluate the proposed method. For Sketch-Photo problem, we obtain perfect results on the CUFS database. For NIR-VIS problem, we produce new state-of-the-art performance on the CASIA HFB and NIR-VIS 2.0 databases.
Finite Vector Spaces as Model of Simply-Typed Lambda-Calculi
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we use finite vector spaces (finite dimension, over finite fields) as a non-standard computational model of linear logic. We first define a simple, finite PCF-like lambda-calculus with booleans, and then we discuss two finite models, one based on finite sets and the other on finite vector spaces. The first model is shown to be fully complete with respect to the operational semantics of the language. The second model is not complete, but we develop an algebraic extension of the finite lambda calculus that recovers completeness. The relationship between the two semantics is described, and several examples based on Church numerals are presented.
An ACL2 Mechanization of an Axiomatic Framework for Weak Memory
Venue: arXiv cs.LO 2014
Year: 2014

Proving the correctness of programs written for multiple processors is a challenging problem, due in no small part to the weaker memory guarantees afforded by most modern architectures. In particular, the existence of store buffers means that the programmer can no longer assume that writes to different locations become visible to all processors in the same order. However, all practical architectures do provide a collection of weaker guarantees about memory consistency across processors, which enable the programmer to write provably correct programs in spite of a lack of full sequential consistency. In this work, we present a mechanization in the ACL2 theorem prover of an axiomatic weak memory model (introduced by Alglave et al.). In the process, we provide a new proof of an established theorem involving these axioms.
Ant Colony Optimization for Inferring Key Gene Interactions
Venue: arXiv cs.NE 2014
Year: 2014

Inferring gene interaction network from gene expression data is an important task in systems biology research. The gene interaction network, especially key interactions, plays an important role in identifying biomarkers for disease that further helps in drug design. Ant colony optimization is an optimization algorithm based on natural evolution and has been used in many optimization problems. In this paper, we applied ant colony optimization algorithm for inferring the key gene interactions from gene expression data. The algorithm has been tested on two different kinds of benchmark datasets and observed that it successfully identify some key gene interactions.
The dagger lambda calculus
Venue: arXiv cs.LO 2014
Year: 2014

We present a novel lambda calculus that casts the categorical approach to the study of quantum protocols into the rich and well established tradition of type theory. Our construction extends the linear typed lambda calculus with a linear negation of "trivialised" De Morgan duality. Reduction is realised through explicit substitution, based on a symmetric notion of binding of global scope, with rules acting on the entire typing judgement instead of on a specific subterm. Proofs of subject reduction, confluence, strong normalisation and consistency are provided, and the language is shown to be an internal language for dagger compact categories.
Linguistic Analysis of Requirements of a Space Project and their Conformity with the Recommendations Proposed by a Controlled Natural Language
Venue: arXiv cs.SE 2014
Year: 2014

The long term aim of the project carried out by the French National Space Agency (CNES) is to design a writing guide based on the real and regular writing of requirements. As a first step in the project, this paper proposes a lin-guistic analysis of requirements written in French by CNES engineers. The aim is to determine to what extent they conform to two rules laid down in INCOSE, a recent guide for writing requirements. Although CNES engineers are not obliged to follow any Controlled Natural Language in their writing of requirements, we believe that language regularities are likely to emerge from this task, mainly due to the writers' experience. The issue is approached using natural language processing tools to identify sentences that do not comply with INCOSE rules. We further review these sentences to understand why the recommendations cannot (or should not) always be applied when specifying large-scale projects.
Small Sample Learning of Superpixel Classifiers for EM Segmentation- Extended Version
Venue: arXiv cs.CV 2014
Year: 2014

Pixel and superpixel classifiers have become essential tools for EM segmentation algorithms. Training these classifiers remains a major bottleneck primarily due to the requirement of completely annotating the dataset which is tedious, error-prone and costly. In this paper, we propose an interactive learning scheme for the superpixel classifier for EM segmentation. Our algorithm is "active semi-supervised" because it requests the labels of a small number of examples from user and applies label propagation technique to generate these queries. Using only a small set ($<20\%$) of all datapoints, the proposed algorithm consistently generates a classifier almost as accurate as that estimated from a complete groundtruth. We provide segmentation results on multiple datasets to show the strength of these classifiers.
Analyzing noise in autoencoders and deep networks
Venue: arXiv cs.NE 2014
Year: 2014

Autoencoders have emerged as a useful framework for unsupervised learning of internal representations, and a wide variety of apparently conceptually disparate regularization techniques have been proposed to generate useful features. Here we extend existing denoising autoencoders to additionally inject noise before the nonlinearity, and at the hidden unit activations. We show that a wide variety of previous methods, including denoising, contractive, and sparse autoencoders, as well as dropout can be interpreted using this framework. This noise injection framework reaps practical benefits by providing a unified strategy to develop new internal representations by designing the nature of the injected noise. We show that noisy autoencoders outperform denoising autoencoders at the very task of denoising, and are competitive with other single-layer techniques on MNIST, and CIFAR-10. We also show that types of noise other than dropout improve performance in a deep network through sparsifying, decorrelating, and spreading information across representations.
Bullseye: Structured Passage Retrieval and Document Highlighting for Scholarly Search
Venue: arXiv cs.IR 2014
Year: 2014

We present the Bullseye system for scholarly search. Given a collection of research papers, Bullseye: 1) identifies relevant passages using any on-the-shelf algorithm; 2) automatically detects document structure and restricts retrieved passages to user-specifed sections; and 3) highlights those passages for each PDF document retrieved. We evaluate Bullseye with regard to three aspects: system effectiveness, user effectiveness, and user effort. In a system-blind evaluation, users were asked to compare passage retrieval using Bullseye vs. a baseline which ignores document structure, in regard to four types of graded assessments. Results show modest improvement in system effectiveness while both user effectiveness and user effort show substantial improvement. Users also report very strong demand for passage highlighting in scholarly search across both systems considered.
Fine-grained Activity Recognition with Holistic and Pose based Features
Venue: arXiv cs.CV 2014
Year: 2014

Holistic methods based on dense trajectories are currently the de facto standard for recognition of human activities in video. Whether holistic representations will sustain or will be superseded by higher level video encoding in terms of body pose and motion is the subject of an ongoing debate. In this paper we aim to clarify the underlying factors responsible for good performance of holistic and pose-based representations. To that end we build on our recent dataset leveraging the existing taxonomy of human activities. This dataset includes 24,920 video snippets covering 410 human activities in total. Our analysis reveals that holistic and pose-based methods are highly complementary, and their performance varies significantly depending on the activity. We find that holistic methods are mostly affected by the number and speed of trajectories, whereas pose-based methods are mostly influenced by viewpoint of the person. We observe striking performance differences across activities: for certain activities results with pose-based features are more than twice as accurate compared to holistic features, and vice versa. The best performing approach in our comparison is based on the combination of holistic and pose-based approaches, which again underlines their complementarity.
Refinement-Cut: User-Guided Segmentation Algorithm for Translational Science
Venue: arXiv cs.CV 2014
Year: 2014

In this contribution, a semi-automatic segmentation algorithm for (medical) image analysis is presented. More precise, the approach belongs to the category of interactive contouring algorithms, which provide real-time feedback of the segmentation result. However, even with interactive real-time contouring approaches there are always cases where the user cannot find a satisfying segmentation, e.g. due to homogeneous appearances between the object and the background, or noise inside the object. For these difficult cases the algorithm still needs additional user support. However, this additional user support should be intuitive and rapid integrated into the segmentation process, without breaking the interactive real-time segmentation feedback. I propose a solution where the user can support the algorithm by an easy and fast placement of one or more seed points to guide the algorithm to a satisfying segmentation result also in difficult cases. These additional seed(s) restrict(s) the calculation of the segmentation for the algorithm, but at the same time, still enable to continue with the interactive real-time feedback segmentation. For a practical and genuine application in translational science, the approach has been tested on medical data from the clinical routine in 2D and 3D.
Conversational Sensing
Venue: arXiv cs.HC 2014
Year: 2014

Recent developments in sensing technologies, mobile devices and context-aware user interfaces have made it possible to represent information fusion and situational awareness as a conversational process among actors - human and machine agents - at or near the tactical edges of a network. Motivated by use cases in the domain of security, policing and emergency response, this paper presents an approach to information collection, fusion and sense-making based on the use of natural language (NL) and controlled natural language (CNL) to support richer forms of human-machine interaction. The approach uses a conversational protocol to facilitate a flow of collaborative messages from NL to CNL and back again in support of interactions such as: turning eyewitness reports from human observers into actionable information (from both trained and untrained sources); fusing information from humans and physical sensors (with associated quality metadata); and assisting human analysts to make the best use of available sensing assets in an area of interest (governed by management and security policies). CNL is used as a common formal knowledge representation for both machine and human agents to support reasoning, semantic information fusion and generation of rationale for inferences, in ways that remain transparent to human users. Examples are provided of various alternative styles for user feedback, including NL, CNL and graphical feedback. A pilot experiment with human subjects shows that a prototype conversational agent is able to gather usable CNL information from untrained human subjects.
An exact and two heuristic strategies for truthful bidding in combinatorial transport auctions
Venue: arXiv cs.GT 2014
Year: 2014

To support a freight carrier in a combinatorial transport auction, we proposes an exact and two heuristic strategies for bidding on subsets of requests. The exact bidding strategy is based on the concept of elementary request combinations. We show that it is sufficient and necessary for a carrier to bid on each elementary request combination in order to guarantee the same result as bidding on each element of the powerset of the set of tendered requests. Both heuristic bidding strategies identify promising request combinations. For this, pairwise synergies based on saving values as well as the capacitated p-median problem are used. The bidding strategies are evaluated by a computational study that simulates an auction. It is based on 174 benchmark instances and therefore easily extendable by other researchers. On average, the two heuristic strategies achieve 91 percent and 81 percent of the available sales potential while generating 36 and only 4 percent of the bundle bids of the exact strategy. Therefore, the proposed bidding strategies help a carrier to increase her chance to win and at the same time reduce the computational burden to participate in a combinatorial transport auction.
A Semantic Enhanced Model for effective Spatial Information Retrieval
Venue: arXiv cs.IR 2014
Year: 2014

A lot of information on the web is geographically referenced. Discovering and retrieving this geographic information to satisfy various users needs across both open and distributed Spatial Data Infrastructures (SDI) poses eminent research challenges. However, this is mostly caused by semantic heterogeneity in users query and lack of semantic referencing of the Geographic Information (GI) metadata. To addressing these challenges, this paper discusses ontology based semantic enhanced model, which explicitly represents GI metadata, and provides linked RDF instances of each entity. The system focuses on semantic search, ontology, and efficient spatial information retrieval. In particular, an integrated model that uses specific domain information extraction to improve the searching and retrieval of ranked spatial search results.
Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks
Venue: arXiv cs.DS 2014
Year: 2014

We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time $T_{OPT}$ in the offline scenario in which the agents have complete knowledge about each others speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time $O(n T_{OPT})$ in a $n$-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to $Θ(T_{OPT})$ when the agents are allowed to exchange $Θ(n)$ bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time $Θ(T_{OPT})$.
Anticipating Activity in Social Media Spikes
Venue: arXiv cs.SI 2014
Year: 2014

We propose a novel mathematical model for the activity of microbloggers during an external, event-driven spike. The model leads to a testable prediction of who would become most active if a spike were to take place. This type of information is of great interest to commercial organisations, governments and charities, as it identifies key players who can be targeted with information in real time when the network is most receptive. The model takes account of the fact that dynamic interactions evolve over an underlying, static network that records who listens to whom. The model is based on the assumption that, in the case where the entire community has become aware of an external news event, a key driver of activity is the motivation to participate by responding to incoming messages. We test the model on a large scale Twitter conversation concerning the appointment of a UK Premier League football club manager. We also present further results for a Bundesliga football match, a marketing event and a television programme. In each case we find that exploiting the underlying connectivity structure improves the prediction of who will be active during a spike. We also show how the half-life of a spike in activity can be quantified in terms of the network size and the typical response rate.