OpenRaiser/Intern-Atlas huggingface dataset:
The Matching Augmentation Problem: A $\frac74$-Approximation Algorithm
Venue: arXiv cs.DS 2018
Year: 2018

We present a $\frac74$ approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a $\frac74$ approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (`Factor 4/3 approximations for minimum 2-connected subgraphs,' APPROX 2000, LNCS 1913, pp.262-273).
Automatic Brain Tumor Segmentation using Convolutional Neural Networks with Test-Time Augmentation
Venue: arXiv cs.CV 2018
Year: 2018

Automatic brain tumor segmentation plays an important role for diagnosis, surgical planning and treatment assessment of brain tumors. Deep convolutional neural networks (CNNs) have been widely used for this task. Due to the relatively small data set for training, data augmentation at training time has been commonly used for better performance of CNNs. Recent works also demonstrated the usefulness of using augmentation at test time, in addition to training time, for achieving more robust predictions. We investigate how test-time augmentation can improve CNNs' performance for brain tumor segmentation. We used different underpinning network structures and augmented the image by 3D rotation, flipping, scaling and adding random noise at both training and test time. Experiments with BraTS 2018 training and validation set show that test-time augmentation helps to improve the brain tumor segmentation accuracy and obtain uncertainty estimation of the segmentation results.
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Venue: arXiv cs.DS 2018
Year: 2018

Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al.~(STOC 1990) is strictly better than $0.5$-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be $(1-1/e)$-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is $2-\sqrt{2} \approx 0.585$-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art $\frac{1}{1+\ln 2} \approx 0.5906$ upper bound. For integral algorithms, we show a tight competitive ratio of $\approx 0.567$ for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018).
S-Net: A Scalable Convolutional Neural Network for JPEG Compression Artifact Reduction
Venue: arXiv cs.CV 2018
Year: 2018

Recent studies have used deep residual convolutional neural networks (CNNs) for JPEG compression artifact reduction. This study proposes a scalable CNN called S-Net. Our approach effectively adjusts the network scale dynamically in a multitask system for real-time operation with little performance loss. It offers a simple and direct technique to evaluate the performance gains obtained with increasing network depth, and it is helpful for removing redundant network layers to maximize the network efficiency. We implement our architecture using the Keras framework with the TensorFlow backend on an NVIDIA K80 GPU server. We train our models on the DIV2K dataset and evaluate their performance on public benchmark datasets. To validate the generality and universality of the proposed method, we created and utilized a new dataset, called WIN143, for over-processed images evaluation. Experimental results indicate that our proposed approach outperforms other CNN-based methods and achieves state-of-the-art performance.
Learning Postural Synergies for Categorical Grasping through Shape Space Registration
Venue: arXiv cs.RO 2018
Year: 2018

Every time a person encounters an object with a given degree of familiarity, he/she immediately knows how to grasp it. Adaptation of the movement of the hand according to the object geometry happens effortlessly because of the accumulated knowledge of previous experiences grasping similar objects. In this paper, we present a novel method for inferring grasp configurations based on the object shape. Grasping knowledge is gathered in a synergy space of the robotic hand built by following a human grasping taxonomy. The synergy space is constructed through human demonstrations employing a exoskeleton that provides force feedback, which provides the advantage of evaluating the quality of the grasp. The shape descriptor is obtained by means of a categorical non-rigid registration that encodes typical intra-class variations. This approach is especially suitable for on-line scenarios where only a portion of the object's surface is observable. This method is demonstrated through simulation and real robot experiments by grasping objects never seen before by the robot.
k-RNN: Extending NN-heuristics for the TSP
Venue: arXiv cs.AI 2018
Year: 2018

In this paper we present an extension of existing Nearest-Neighbor heuristics to an algorithm called k-Repetitive-Nearest-Neighbor. The idea is to start with a tour of k nodes and then perform a Nearest-Neighbor search from there on. After doing this for all permutations of k nodes the result gets selected as the shortest tour found. Experimental results show that for 2-RNN the solutions quality remains relatively stable between about 10% to 40% above the optimum.
The Institutional Approach
Venue: arXiv cs.LO 2018
Year: 2018

This chapter discusses the institutional approach for organizing and maintaining ontologies. The theory of institutions was named and initially developed by Joseph Goguen and Rod Burstall. This theory, a metatheory based on category theory, regards ontologies as logical theories or local logics. The theory of institutions uses the category-theoretic ideas of fibrations and indexed categories to develop logical theories. Institutions unite the lattice approach of Formal Concept Analysis of Ganter and Wille with the distributed logic of Information Flow of Barwise and Seligman. The institutional approach incorporates locally the lattice of theories idea of Sowa from the theory of knowledge representation. The Information Flow Framework, which was initiated within the IEEE Standard Upper Ontology project, uses the institutional approach in its applied aspect for the comparison, semantic integration and maintenance of ontologies. This chapter explains the central ideas of the institutional approach to ontologies in a careful and detailed manner.
Best-of-two-worlds analysis of online search
Venue: arXiv cs.DS 2018
Year: 2018

In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line nature, in that the input is unknown to the searcher, and the performance of a search strategy is usually analyzed by means of the standard framework of the competitive ratio, which compares the cost incurred by the searcher to an optimal strategy that knows the location of the target. However, one can argue that even for simple search problems, competitive analysis fails to distinguish between strategies which, intuitively, should have different performance in practice. Motivated by the above, in this work we introduce and study measures supplementary to competitive analysis in the context of search problems. In particular, we focus on the well-known problem of linear search, informally known as the cow-path problem, for which there is an infinite number of strategies that achieve an optimal competitive ratio equal to 9. We propose a measure that reflects the rate at which the line is being explored by the searcher, and which can be seen as an extension of the bijective ratio over an uncountable set of requests. Using this measure we show that a natural strategy that explores the line aggressively is optimal among all 9-competitive strategies. This provides, in particular, a strict separation from the competitively optimal doubling strategy, which is much more conservative in terms of exploration. We also provide evidence that this aggressiveness is requisite for optimality, by showing that any optimal strategy must mimic the aggressive strategy in its first few explorations.
Adversarial TableQA: Attention Supervision for Question Answering on Tables
Venue: arXiv cs.CL 2018
Year: 2018

The task of answering a question given a text passage has shown great developments on model performance thanks to community efforts in building useful datasets. Recently, there have been doubts whether such rapid progress has been based on truly understanding language. The same question has not been asked in the table question answering (TableQA) task, where we are tasked to answer a query given a table. We show that existing efforts, of using "answers" for both evaluation and supervision for TableQA, show deteriorating performances in adversarial settings of perturbations that do not affect the answer. This insight naturally motivates to develop new models that understand question and table more precisely. For this goal, we propose Neural Operator (NeOp), a multi-layer sequential network with attention supervision to answer the query given a table. NeOp uses multiple Selective Recurrent Units (SelRUs) to further help the interpretability of the answers of the model. Experiments show that the use of operand information to train the model significantly improves the performance and interpretability of TableQA models. NeOp outperforms all the previous models by a big margin.
Merge: An Architecture for Interconnected Testbed Ecosystems
Venue: arXiv cs.DC 2018
Year: 2018

In the cybersecurity research community, there is no one-size-fits-all solution for merging large numbers of heterogeneous resources and experimentation capabilities from disparate specialized testbeds into integrated experiments. The current landscape for cyber-experimentation is diverse, encompassing many fields including critical infrastructure, enterprise IT, cyber-physical systems, cellular networks, automotive platforms, IoT and industrial control systems. Existing federated testbeds are constricted in design to predefined domains of applicability, lacking the systematic ability to integrate the burgeoning number of heterogeneous devices or tools that enable their effective use for experimentation. We have developed the Merge architecture to dynamically integrate disparate testbeds in a logically centralized way that allows researchers to effectively discover, and use the resources and capabilities provided the by evolving ecosystem of distributed testbeds for the development of rigorous and high-fidelity cybersecurity experiments.
A Comparative Analysis of Registration Tools: Traditional vs Deep Learning Approach on High Resolution Tissue Cleared Data
Venue: arXiv cs.CV 2018
Year: 2018

Image registration plays an important role in comparing images. It is particularly important in analyzing medical images like CT, MRI, PET, etc. to quantify different biological samples, to monitor disease progression and to fuse different modalities to support better diagnosis. The recent emergence of tissue clearing protocols enable us to take images at cellular level resolution. Image registration tools developed for other modalities are currently unable to manage images of such extreme high resolution. The recent popularity of deep learning based methods in the computer vision community justifies a rigorous investigation of deep-learning based methods on tissue cleared images along with their traditional counterparts. In this paper, we investigate and compare the performance of a deep learning based registration method with traditional optimization based methods on samples from tissue-clearing methods. From the comparative results it is found that a deep-learning based method outperforms all traditional registration tools in terms of registration time and has achieved promising registration accuracy.
Multi-Domain Pose Network for Multi-Person Pose Estimation and Tracking
Venue: arXiv cs.CV 2018
Year: 2018

Multi-person human pose estimation and tracking in the wild is important and challenging. For training a powerful model, large-scale training data are crucial. While there are several datasets for human pose estimation, the best practice for training on multi-dataset has not been investigated. In this paper, we present a simple network called Multi-Domain Pose Network (MDPN) to address this problem. By treating the task as multi-domain learning, our methods can learn a better representation for pose prediction. Together with prediction heads fine-tuning and multi-branch combination, it shows significant improvement over baselines and achieves the best performance on PoseTrack ECCV 2018 Challenge without additional datasets other than MPII and COCO.
Flow Network Models for Online Scheduling Real-time Tasks on Multiprocessors
Venue: arXiv cs.DC 2018
Year: 2018

We consider the flow network model to solve the multiprocessor real-time task scheduling problems. Using the flow network model or its generic form, linear programming (LP) formulation, for the problems is not new. However, the previous works have limitations, for example, that they are classified as offline scheduling techniques since they establish a flow network model or an LP problem considering a very long time interval. In this study, we propose how to construct the flow network model for online scheduling periodic real-time tasks on multiprocessors. Our key idea is to construct the flow network only for the active instances of tasks at the current scheduling time, while guaranteeing the existence of an optimal schedule for the future instances of the tasks. The optimal scheduling is here defined to ensure that all real-time tasks meet their deadlines when the total utilization demand of the given tasks does not exceed the total processing capacity. We then propose the flow network model-based polynomial-time scheduling algorithms. Advantageously, the flow network model allows the task workload to be collected unfairly within a certain time interval without losing the optimality. It thus leads us to designing three unfair-but-optimal scheduling algorithms on both continuous and discrete-time models. Especially, our unfair-but-optimal scheduling algorithm on a discrete-time model is, to the best of our knowledge, the first in the problem domain. We experimentally demonstrate that it significantly alleviates the scheduling overheads, i.e., the reduced number of preemptions with the comparable number of task migrations across processors.
Impact of Corpora Quality on Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

Large parallel corpora that are automatically obtained from the web, documents or elsewhere often exhibit many corrupted parts that are bound to negatively affect the quality of the systems and models that learn from these corpora. This paper describes frequent problems found in data and such data affects neural machine translation systems, as well as how to identify and deal with them. The solutions are summarised in a set of scripts that remove problematic sentences from input corpora.
IoT-KEEPER: Securing IoT Communications in Edge Networks
Venue: arXiv cs.CR 2018
Year: 2018

The increased popularity of IoT devices have made them lucrative targets for attackers. Due to insecure product development practices, these devices are often vulnerable even to very trivial attacks and can be easily compromised. Due to the sheer number and heterogeneity of IoT devices, it is not possible to secure the IoT ecosystem using traditional endpoint and network security solutions. To address the challenges and requirements of securing IoT devices in edge networks, we present IoT-Keeper, which is a novel system capable of securing the network against any malicious activity, in real time. The proposed system uses a lightweight anomaly detection technique, to secure both device-to-device and device-to-infrastructure communications, while using limited resources available on the gateway. It uses unlabeled network data to distinguish between benign and malicious traffic patterns observed in the network. A detailed evaluation, done with real world testbed, shows that IoT-Keeper detects any device generating malicious traffic with high accuracy (0.982) and low false positive rate (0.01). The results demonstrate that IoT-Keeper is lightweight, responsive and can effectively handle complex D2D interactions without requiring explicit attack signatures or sophisticated hardware.
Efficient Dependency-Guided Named Entity Recognition
Venue: arXiv cs.CL 2018
Year: 2018

Named entity recognition (NER), which focuses on the extraction of semantically meaningful named entities and their semantic classes from text, serves as an indispensable component for several down-stream natural language processing (NLP) tasks such as relation extraction and event extraction. Dependency trees, on the other hand, also convey crucial semantic-level information. It has been shown previously that such information can be used to improve the performance of NER (Sasano and Kurohashi 2008, Ling and Weld 2012). In this work, we investigate on how to better utilize the structured information conveyed by dependency trees to improve the performance of NER. Specifically, unlike existing approaches which only exploit dependency information for designing local features, we show that certain global structured information of the dependency trees can be exploited when building NER models where such information can provide guided learning and inference. Through extensive experiments, we show that our proposed novel dependency-guided NER model performs competitively with models based on conventional semi-Markov conditional random fields, while requiring significantly less running time.
Coordinated exploration for labyrinthine environments with application to the Pursuit-Evasion problem
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces a multirobot cooperation approach to solve the "pursuit evasion" problem for mobile robots that have omnidirectional vision sensors. The main characteristic of this approach is to implement a real cooperation between robots based on knowledge sharing and makes them work as a team. A complete algorithm for computing a motion strategy of robots is also presented. This algorithm is based on searching critical points in the environment. Finally, the deliberation protocol which distributes the exploration task among the team and takes the best possible outcome from the robots resources is presented.
Transfer Learning versus Multi-agent Learning regarding Distributed Decision-Making in Highway Traffic
Venue: arXiv cs.LG 2018
Year: 2018

Transportation and traffic are currently undergoing a rapid increase in terms of both scale and complexity. At the same time, an increasing share of traffic participants are being transformed into agents driven or supported by artificial intelligence resulting in mixed-intelligence traffic. This work explores the implications of distributed decision-making in mixed-intelligence traffic. The investigations are carried out on the basis of an online-simulated highway scenario, namely the MIT \emph{DeepTraffic} simulation. In the first step traffic agents are trained by means of a deep reinforcement learning approach, being deployed inside an elitist evolutionary algorithm for hyperparameter search. The resulting architectures and training parameters are then utilized in order to either train a single autonomous traffic agent and transfer the learned weights onto a multi-agent scenario or else to conduct multi-agent learning directly. Both learning strategies are evaluated on different ratios of mixed-intelligence traffic. The strategies are assessed according to the average speed of all agents driven by artificial intelligence. Traffic patterns that provoke a reduction in traffic flow are analyzed with respect to the different strategies.
Fairness for Whom? Critically reframing fairness with Nash Welfare Product
Venue: arXiv cs.CY 2018
Year: 2018

Recent studies on disparate impact in machine learning applications have sparked a debate around the concept of fairness along with attempts to formalize its different criteria. Many of these approaches focus on reducing prediction errors while maximizing sole utility of the institution. This work seeks to reconceptualize and critically frame the existing discourse on fairness by underlining the implicit biases embedded in common understandings of fairness in the literature and how they contrast with its corresponding economic and legal definitions. This paper expands the concept of utility and fairness by bringing in concepts from established literature in welfare economics and game theory. We then translate these concepts for the algorithmic prediction domain by defining a formalization of Nash Welfare Product that seeks to expand utility by collapsing that of the institution using the prediction tool and the individual subject to the prediction into one function. We then apply a modulating function that makes the fairness and welfare trade-offs explicit based on designated policy goals and then apply it to a temporal model to take into account the effects of decisions beyond the scope of one-shot predictions. We apply this on a binary classification problem and present results of a multi-epoch simulation based on the UCI Adult Income dataset and a test case analysis of the ProPublica recidivism dataset that show that expanding the concept of utility results in a fairer distribution correcting for the embedded biases in the dataset without sacrificing the classifier accuracy.
Weak Semi-Markov CRFs for NP Chunking in Informal Text
Venue: arXiv cs.CL 2018
Year: 2018

This paper introduces a new annotated corpus based on an existing informal text corpus: the NUS SMS Corpus (Chen and Kan, 2013). The new corpus includes 76,490 noun phrases from 26,500 SMS messages, annotated by university students. We then explored several graphical models, including a novel variant of the semi-Markov conditional random fields (semi-CRF) for the task of noun phrase chunking. We demonstrated through empirical evaluations on the new dataset that the new variant yielded similar accuracy but ran in significantly lower running time compared to the conventional semi-CRF.
An Exploration of Dropout with RNNs for Natural Language Inference
Venue: arXiv cs.CL 2018
Year: 2018

Dropout is a crucial regularization technique for the Recurrent Neural Network (RNN) models of Natural Language Inference (NLI). However, dropout has not been evaluated for the effectiveness at different layers and dropout rates in NLI models. In this paper, we propose a novel RNN model for NLI and empirically evaluate the effect of applying dropout at different layers in the model. We also investigate the impact of varying dropout rates at these layers. Our empirical evaluation on a large (Stanford Natural Language Inference (SNLI)) and a small (SciTail) dataset suggest that dropout at each feed-forward connection severely affects the model accuracy at increasing dropout rates. We also show that regularizing the embedding layer is efficient for SNLI whereas regularizing the recurrent layer improves the accuracy for SciTail. Our model achieved an accuracy 86.14% on the SNLI dataset and 77.05% on SciTail.