OpenRaiser/Intern-Atlas huggingface dataset:
Compact CAR: Low-Overhead Cache Replacement Policy for an ICN Router
Venue: arXiv cs.NI 2016
Year: 2016

Information-centric networking (ICN) has gained attention from network research communities due to its capability of efficient content dissemination. In-network caching function in ICN plays an important role to achieve the design motivation. However, many researchers on in-network caching have focused on where to cache rather than how to cache: the former is known as contents deployment in the network and the latter is known as cache replacement in an ICN element. Although, the cache replacement has been intensively researched in the context of web-caching and content delivery network previously, the conventional approaches cannot be directly applied to ICN due to the fine granularity of cacheable items in ICN, which eventually changes the access patterns. In this paper, we argue that ICN requires a novel cache replacement algorithm to fulfill the requirements in the design of high performance ICN element. Then, we propose a novel cache replacement algorithm to satisfy the requirements named Compact CLOCK with Adaptive Replacement (Compact CAR), which can reduce the consumption of cache memory to one-tenth compared to conventional approaches.
Decision Theory in an Algebraic Setting
Venue: arXiv cs.AI 2016
Year: 2016

In decision theory an act is a function from a set of conditions to the set of real numbers. The set of conditions is a partition in some algebra of events. The expected value of an act can be calculated when a probability measure is given. We adopt an algebraic point of view by substituting the algebra of events with a finite distributive lattice and the probability measure with a lattice valuation. We introduce a partial order on acts that generalizes the dominance relation and show that the set of acts is a lattice with respect to this order. Finally we analyze some different kinds of comparison between acts, without supposing a common set of conditions for the acts to be compared.
A constructive algorithm for the LLL on permutations
Venue: arXiv cs.DS 2016
Year: 2016

While there has been significant progress on algorithmic aspects of the Lovász Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations. The breakthrough algorithm of Moser & Tardos only works in the setting of independent variables, and does not apply in this context. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin transversals: the best-known general result here (Bissacot et al., improving on Erdős and Spencer), states that any $n \times n$ matrix in which each entry appears at most $(27/256)n$ times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. We also develop RNC algorithms for Latin transversals, rainbow Hamiltonian cycles, strong chromatic number, and hypergraph packing. In addition to efficiently finding a configuration which avoids bad-events, the algorithm of Moser & Tardos has many powerful extensions and properties. These include a well-characterized distribution on the output distribution, parallel algorithms, and a partial resampling variant. We show that our algorithm has nearly all of the same useful properties as the Moser-Tardos algorithm, and present a comparison of this aspect with recent works on the LLL in general probability spaces.
Controlling Robot Morphology from Incomplete Measurements
Venue: arXiv cs.RO 2016
Year: 2016

Mobile robots with complex morphology are essential for traversing rough terrains in Urban Search & Rescue missions (USAR). Since teleoperation of the complex morphology causes high cognitive load of the operator, the morphology is controlled autonomously. The autonomous control measures the robot state and surrounding terrain which is usually only partially observable, and thus the data are often incomplete. We marginalize the control over the missing measurements and evaluate an explicit safety condition. If the safety condition is violated, tactile terrain exploration by the body-mounted robotic arm gathers the missing data.
Hierarchy through Composition with Linearly Solvable Markov Decision Processes
Venue: arXiv cs.AI 2016
Year: 2016

Hierarchical architectures are critical to the scalability of reinforcement learning methods. Current hierarchical frameworks execute actions serially, with macro-actions comprising sequences of primitive actions. We propose a novel alternative to these control hierarchies based on concurrent execution of many actions in parallel. Our scheme uses the concurrent compositionality provided by the linearly solvable Markov decision process (LMDP) framework, which naturally enables a learning agent to draw on several macro-actions simultaneously to solve new tasks. We introduce the Multitask LMDP module, which maintains a parallel distributed representation of tasks and may be stacked to form deep hierarchies abstracted in space and time.
Feedback Neural Network for Weakly Supervised Geo-Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Learning from weakly-supervised data is one of the main challenges in machine learning and computer vision, especially for tasks such as image semantic segmentation where labeling is extremely expensive and subjective. In this paper, we propose a novel neural network architecture to perform weakly-supervised learning by suppressing irrelevant neuron activations. It localizes objects of interest by learning from image-level categorical labels in an end-to-end manner. We apply this algorithm to a practical challenge of transforming satellite images into a map of settlements and individual buildings. Experimental results show that the proposed algorithm achieves superior performance and efficiency when compared with various baseline models.
Task-Guided and Path-Augmented Heterogeneous Network Embedding for Author Identification
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we study the problem of author identification under double-blind review setting, which is to identify potential authors given information of an anonymized paper. Different from existing approaches that rely heavily on feature engineering, we propose to use network embedding approach to address the problem, which can automatically represent nodes into lower dimensional feature vectors. However, there are two major limitations in recent studies on network embedding: (1) they are usually general-purpose embedding methods, which are independent of the specific tasks; and (2) most of these approaches can only deal with homogeneous networks, where the heterogeneity of the network is ignored. Hence, challenges faced here are two folds: (1) how to embed the network under the guidance of the author identification task, and (2) how to select the best type of information due to the heterogeneity of the network. To address the challenges, we propose a task-guided and path-augmented heterogeneous network embedding model. In our model, nodes are first embedded as vectors in latent feature space. Embeddings are then shared and jointly trained according to task-specific and network-general objectives. We extend the existing unsupervised network embedding to incorporate meta paths in heterogeneous networks, and select paths according to the specific task. The guidance from author identification task for network embedding is provided both explicitly in joint training and implicitly during meta path selection. Our experiments demonstrate that by using path-augmented network embedding with task guidance, our model can obtain significantly better accuracy at identifying the true authors comparing to existing methods.
Facial Expression Recognition using Convolutional Neural Networks: State of the Art
Venue: arXiv cs.CV 2016
Year: 2016

The ability to recognize facial expressions automatically enables novel applications in human-computer interaction and other areas. Consequently, there has been active research in this field, with several recent works utilizing Convolutional Neural Networks (CNNs) for feature extraction and inference. These works differ significantly in terms of CNN architectures and other factors. Based on the reported results alone, the performance impact of these factors is unclear. In this paper, we review the state of the art in image-based facial expression recognition using CNNs and highlight algorithmic differences and their performance impact. On this basis, we identify existing bottlenecks and consequently directions for advancing this research field. Furthermore, we demonstrate that overcoming one of these bottlenecks - the comparatively basic architectures of the CNNs utilized in this field - leads to a substantial performance increase. By forming an ensemble of modern deep CNNs, we obtain a FER2013 test accuracy of 75.2%, outperforming previous works without requiring auxiliary training data or face registration.
Data mining when each data point is a network
Venue: arXiv cs.SI 2016
Year: 2016

We discuss the problem of extending data mining approaches to cases in which data points arise in the form of individual graphs. Being able to find the intrinsic low-dimensionality in ensembles of graphs can be useful in a variety of modeling contexts, especially when coarse-graining the detailed graph information is of interest. One of the main challenges in mining graph data is the definition of a suitable pairwise similarity metric in the space of graphs. We explore two practical solutions to solving this problem: one based on finding subgraph densities, and one using spectral information. The approach is illustrated on three test data sets (ensembles of graphs); two of these are obtained from standard graph generating algorithms, while the graphs in the third example are sampled as dynamic snapshots from an evolving network simulation. We further incorporate these approaches with equation free techniques, demonstrating how such data mining approaches can enhance scientific computation of network evolution dynamics.
Hard Capacitated Set Cover and Uncapacitated Geometric Set Cover
Venue: arXiv cs.DS 2016
Year: 2016

The first part of this report describes the following result that, logarithmic approximation factor for hard capacitated set cover can be achieved from Wolsey's work [9], using a simpler and more intuitive analysis. We further show in our work, that O(log n) approximation factor can be achieved for the same problem by applying analysis of general set cover to analyze Wolsey's algorithm [5]. This work is based on the key observation that we make in Lemma 3 of this report. The second part of the report describes the geometric hitting set problem, where X is a ground set of points in a plane and S is a set of axis parallel rectangles. It is shown that epsilon-nets of size O(1/epsilon log log 1/epsilon) can be computed in polynomial time. Applying Bronnimann and Goodrich result [3] gives the hitting set of size O(log log OPT) for this problem.
A Systematic and Semi-Automatic Safety-Based Test Case Generation Approach Based on Systems-Theoretic Process Analysis
Venue: arXiv cs.SE 2016
Year: 2016

Software safety is a crucial aspect during the development of modern safety-critical systems. Software is becoming responsible for most of the critical functions of systems. Therefore, the software components in the systems need to be tested extensively against their safety requirements to ensure a high level of system safety. However, performing testing exhaustively to test all software behaviours is impossible. Numerous testing approaches exist. However, they do not directly concern the information derived during the safety analysis. STPA (Systems-Theoretic Process Analysis) is a unique safety analysis approach based on system and control theory, and was developed to identify unsafe scenarios of a complex system including software. In this paper, we present a systematic and semi-automatic testing approach based on STPA to generate test cases from the STPA safety analysis results to help software and safety engineers to recognize and reduce the associated software risks. We also provide an open-source safety-based testing tool called STPA TCGenerator to support the proposed approach. We illustrate the proposed approach with a prototype of a software of the Adaptive Cruise Control System (ACC) with a stop-and-go function with a Lego-Mindstorms EV3 robot.
A comprehensive safety engineering approach for software-intensive systems based on STPA
Venue: arXiv cs.SE 2016
Year: 2016

Formal verification and testing are complementary approaches which are used in the development process to verify the functional correctness of software. However, the correctness of software cannot ensure the safe operation of safety-critical software systems. The software must be verified against its safety requirements which are identified by safety analysis, to ensure that potential hazardous causes cannot occur. The complexity of software makes defining appropriate software safety requirements with traditional safety analysis techniques difficult. STPA (Systems-Theoretic Processes Analysis) is a unique safety analysis approach that has been developed to identify system hazards, including the software-related hazards. This paper presents a comprehensive safety engineering approach based on STPA, including software testing and model checking approaches for the purpose of developing safe software. The proposed approach can be embedded within a defined software engineering process or applied to existing software systems, allow software and safety engineers integrate the analysis of software risks with their verification. The application of the proposed approach is illustrated with an automotive software controller.
Delay-Optimal Scheduling and Power Control for Instantaneous-Interference-Limited CRs
Venue: arXiv cs.IT 2016
Year: 2016

We study an uplink multi secondary user (SU) cognitive radio system suffering statistical heterogeneity among SUs' channels. This heterogeneity may result in differentiated delay performances to these SUs and result in harmful interference to the PU. We first derive an explicit closed-form expression for the average delay in terms of an arbitrary power-control policy. Then, we propose a delay-optimal closed-form scheduling and power-control policy that can provide the required average delay guarantees to all SUs besides protecting the PU from harmful interference. We support our findings by extensive system simulations and show that it outperforms existing policies substantially.
A natural language interface to a graph-based bibliographic information retrieval system
Venue: arXiv cs.IR 2016
Year: 2016

With the ever-increasing scientific literature, there is a need on a natural language interface to bibliographic information retrieval systems to retrieve related information effectively. In this paper, we propose a natural language interface, NLI-GIBIR, to a graph-based bibliographic information retrieval system. In designing NLI-GIBIR, we developed a novel framework that can be applicable to graph-based bibliographic information retrieval systems. Our framework integrates algorithms/heuristics for interpreting and analyzing natural language bibliographic queries. NLI-GIBIR allows users to search for a variety of bibliographic data through natural language. A series of text- and linguistic-based techniques are used to analyze and answer natural language queries, including tokenization, named entity recognition, and syntactic analysis. We find that our framework can effectively represents and addresses complex bibliographic information needs. Thus, the contributions of this paper are as follows: First, to our knowledge, it is the first attempt to propose a natural language interface to graph-based bibliographic information retrieval. Second, we propose a novel customized natural language processing framework that integrates a few original algorithms/heuristics for interpreting and analyzing natural language bibliographic queries. Third, we show that the proposed framework and natural language interface provide a practical solution in building real-world natural language interface-based bibliographic information retrieval systems. Our experimental results show that the presented system can correctly answer 39 out of 40 example natural language queries with varying lengths and complexities.
The Team Surviving Orienteers Problem: Routing Robots in Uncertain Environments with Survival Constraints
Venue: arXiv cs.RO 2016
Year: 2016

In this paper we study the following multi-robot coordination problem: given a graph, where each edge is weighted by the probability of surviving while traversing it, find a set of paths for $K$ robots that maximizes the expected number of nodes collectively visited, subject to constraints on the probability that each robot survives to its destination. We call this problem the Team Surviving Orienteers (TSO) problem. The TSO problem is motivated by scenarios where a team of robots must traverse a dangerous, uncertain environment, such as aid delivery in disaster or war zones. We present the TSO problem formally along with several variants, which represent "survivability-aware" counterparts for a wide range of multi-robot coordination problems such as vehicle routing, patrolling, and informative path planning. We propose an approximate greedy approach for selecting paths, and prove that the value of its output is bounded within a factor $1-e^{-p_s/λ}$ of the optimum where $p_s$ is the per-robot survival probability threshold, and $1/λ\le 1$ is the approximation factor of an oracle routine for the well-known orienteering problem. Our approach has linear time complexity in the team size and polynomial complexity in the graph size. Using numerical simulations, we verify that our approach is close to the optimum in practice and that it scales to problems with hundreds of nodes and tens of robots.
Data Curation APIs
Venue: arXiv cs.IR 2016
Year: 2016

Understanding and analyzing big data is firmly recognized as a powerful and strategic priority. For deeper interpretation of and better intelligence with big data, it is important to transform raw data (unstructured, semi-structured and structured data sources, e.g., text, video, image data sets) into curated data: contextualized data and knowledge that is maintained and made available for use by end-users and applications. In particular, data curation acts as the glue between raw data and analytics, providing an abstraction layer that relieves users from time consuming, tedious and error prone curation tasks. In this context, the data curation process becomes a vital analytics asset for increasing added value and insights. In this paper, we identify and implement a set of curation APIs and make them available (on GitHub) to researchers and developers to assist them transforming their raw data into curated data. The curation APIs enable developers to easily add features - such as extracting keyword, part of speech, and named entities such as Persons, Locations, Organizations, Companies, Products, Diseases, Drugs, etc.; providing synonyms and stems for extracted information items leveraging lexical knowledge bases for the English language such as WordNet; linking extracted entities to external knowledge bases such as Google Knowledge Graph and Wikidata; discovering similarity among the extracted information items, such as calculating similarity between string, number, date and time data; classifying, sorting and categorizing data into various types, forms or any other distinct class; and indexing structured and unstructured data - into their applications.
Label Visualization and Exploration in IR
Venue: arXiv cs.IR 2016
Year: 2016

There is a renaissance in visual analytics systems for data analysis and sharing, in particular, in the current wave of big data applications. We introduce RAVE, a prototype that automates the generation of an interface that uses facets and visualization techniques for exploring and analyzing relevance assessments data sets collected via crowdsourcing. We present a technical description of the main components and demonstrate its use.
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
Venue: arXiv cs.DS 2016
Year: 2016

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^n f_j(C_j)$. Bansal \& Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the LP is less than 4. Finally, we show how the technique can be adapted to yield, for any $ε>0$, a $(4+ε)$-approximation algorithm for this problem.
An Energy-Efficient VCO-Based Matrix Multiplier Block to Support On-Chip Image Analysis
Venue: arXiv cs.ET 2016
Year: 2016

Images typically are represented as uniformly sampled data in the form of matrix of pixels/voxels. Therefore, matrix multiply-and-accumulate (MAC) forms the core of most state-of-the-art image analysis algorithms. While digital implementation of MAC has generally been the preferred approach, high power consumption is an impediment to adopting it for medical image analysis. In this work, we present a time-domain signal processing architecture which performs MAC operations with 7bit accuracy while consuming 400X lower energy than digital implementation. The proposed architecture performs analog computation using mostly digital circuits and is suitable for scaled CMOS technologies. The proposed time-domain MAC architecture is expected to play a central role in empowering the advancement of various on-chip image analysis operations.
On Choosing Training and Testing Data for Supervised Algorithms in Ground Penetrating Radar Data for Buried Threat Detection
Venue: arXiv cs.CV 2016
Year: 2016

Ground penetrating radar (GPR) is one of the most popular and successful sensing modalities that has been investigated for landmine and subsurface threat detection. Many of the detection algorithms applied to this task are supervised and therefore require labeled examples of target and non-target data for training. Training data most often consists of 2-dimensional images (or patches) of GPR data, from which features are extracted, and provided to the classifier during training and testing. Identifying desirable training and testing locations to extract patches, which we term "keypoints", is well established in the literature. In contrast however, a large variety of strategies have been proposed regarding keypoint utilization (e.g., how many of the identified keypoints should be used at targets, or non-target, locations). Given the variety keypoint utilization strategies that are available, it is very unclear (i) which strategies are best, or (ii) whether the choice of strategy has a large impact on classifier performance. We address these questions by presenting a taxonomy of existing utilization strategies, and then evaluating their effectiveness on a large dataset using many different classifiers and features. We analyze the results and propose a new strategy, called PatchSelect, which outperforms other strategies across all experiments.