OpenRaiser/Intern-Atlas huggingface dataset:
Deleting vertices to graphs of bounded genus
Venue: arXiv cs.DS 2017
Year: 2017

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time $2^{C_g \cdot k^2 \log k} n^{O(1)}$, where $k$ is the size of the deletion set, $C_g$ is a constant depending on the Euler genus $g$ of the target surface, and $n$ is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time $2^{O((t+g) \log (t+g))} n$, given a tree decomposition of the input graph of width $t$. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter [Algorithmica 2012], Kawarabayashi [FOCS 2009], and Jansen, Lokshtanov, and Saurabh [SODA 2014].
Compressing networks with super nodes
Venue: arXiv cs.SI 2017
Year: 2017

Community detection is a commonly used technique for identifying groups in a network based on similarities in connectivity patterns. To facilitate community detection in large networks, we recast the network to be partitioned into a smaller network of 'super nodes', each super node comprising one or more nodes in the original network. To define the seeds of our super nodes, we apply the 'CoreHD' ranking from dismantling and decycling. We test our approach through the analysis of two common methods for community detection: modularity maximization with the Louvain algorithm and maximum likelihood optimization for fitting a stochastic block model. Our results highlight that applying community detection to the compressed network of super nodes is significantly faster while successfully producing partitions that are more aligned with the local network connectivity, more stable across multiple (stochastic) runs within and between community detection algorithms, and overlap well with the results obtained using the full network.
Joint Max Margin and Semantic Features for Continuous Event Detection in Complex Scenes
Venue: arXiv cs.CV 2017
Year: 2017

In this paper the problem of complex event detection in the continuous domain (i.e. events with unknown starting and ending locations) is addressed. Existing event detection methods are limited to features that are extracted from the local spatial or spatio-temporal patches from the videos. However, this makes the model vulnerable to the events with similar concepts e.g. "Open drawer" and "Open cupboard". In this work, in order to address the aforementioned limitations we present a novel model based on the combination of semantic and temporal features extracted from video frames. We train a max-margin classifier on top of the extracted features in an adaptive framework that is able to detect the events with unknown starting and ending locations. Our model is based on the Bidirectional Region Neural Network and large margin Structural Output SVM. The generality of our model allows it to be simply applied to different labeled and unlabeled datasets. We finally test our algorithm on three challenging datasets, "UCF 101-Action Recognition", "MPII Cooking Activities" and "Hollywood", and we report state-of-the-art performance.
Preprint Déjà Vu: an FAQ
Venue: arXiv cs.DL 2017
Year: 2017

I give a brief overview of arXiv history, and describe the current state of arXiv practice, both technical and sociological. This commentary originally appeared in the EMBO Journal, 19 Oct 2016. It was intended as an update on comments from the late 1990s regarding use of preprints by biologists (or lack thereof), but may be of interest to practitioners of other disciplines. It is based largely on a keynote presentation I gave to the ASAPbio inaugural meeting in Feb 2016, and responds as well to some follow-up questions.
Autonomous Reactive Mission Scheduling and Task-Path Planning Architecture for Autonomous Underwater Vehicle
Venue: arXiv cs.RO 2017
Year: 2017

An Autonomous Underwater Vehicle (AUV) should carry out complex tasks in a limited time interval. Since existing AUVs have limited battery capacity and restricted endurance, they should autonomously manage mission time and the resources to perform effective persistent deployment in longer missions. Task assignment requires making decisions subject to resource constraints, while tasks are assigned with costs and/or values that are budgeted in advance. Tasks are distributed in a particular operation zone and mapped by a waypoint covered network. Thus, design an efficient routing-task priority assign framework considering vehicle's availabilities and properties is essential for increasing mission productivity and on-time mission completion. This depends strongly on the order and priority of the tasks that are located between node-like waypoints in an operation network. On the other hand, autonomous operation of AUVs in an unfamiliar dynamic underwater and performing quick response to sudden environmental changes is a complicated process. Water current instabilities can deflect the vehicle to an undesired direction and perturb AUVs safety. The vehicle's robustness to strong environmental variations is extremely crucial for its safe and optimum operations in an uncertain and dynamic environment. To this end, the AUV needs to have a general overview of the environment in top level to perform an autonomous action selection (task selection) and a lower level local motion planner to operate successfully in dealing with continuously changing situations. This research deals with developing a novel reactive control architecture to provide a higher level of decision autonomy for the AUV operation that enables a single vehicle to accomplish multiple tasks in a single mission in the face of periodic disturbances in a turbulent and highly uncertain environment.
Opinion formation in a locally interacting community with recommender
Venue: arXiv cs.SI 2017
Year: 2017

We present a user of model interaction based on the physics of kinetic exchange, and extend it to individuals placed in a grid with local interaction. We show with numerical analysis and partial analytical results that the critical symmetry breaking transitions and percolation effects typical of the full interaction model do not take place if the range of interaction is limited, allowing for the co-existence of majorty and minority opinions in the same community. We then introduce a peer recommender system in the model, showing that, even with very local iteraction and a small probability of appeal to the recommender, its presence is sufficient to make both symmetry breaking and percolation reappear. This seems to indicate that one effect of a recommendation system is to uniform the opinions of a community, reducing minority opinions or making them disappear. Although the recommender system does uniform the community opinion, it doesn't constrain it, in the sense that all opinions have the same probability of becoming the dominating one. We do a partial study, however, that suggests that a "mischievous" recommender might be able to bias a community so that one opinion will emerge over the opposite with overwhelming probability.
Online Convolutional Dictionary Learning for Multimodal Imaging
Venue: arXiv cs.CV 2017
Year: 2017

Computational imaging methods that can exploit multiple modalities have the potential to enhance the capabilities of traditional sensing systems. In this paper, we propose a new method that reconstructs multimodal images from their linear measurements by exploiting redundancies across different modalities. Our method combines a convolutional group-sparse representation of images with total variation (TV) regularization for high-quality multimodal imaging. We develop an online algorithm that enables the unsupervised learning of convolutional dictionaries on large-scale datasets that are typical in such applications. We illustrate the benefit of our approach in the context of joint intensity-depth imaging.
Saliency detection by aggregating complementary background template with optimization framework
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes an unsupervised bottom-up saliency detection approach by aggregating complementary background template with refinement. Feature vectors are extracted from each superpixel to cover regional color, contrast and texture information. By using these features, a coarse detection for salient region is realized based on background template achieved by different combinations of boundary regions instead of only treating four boundaries as background. Then, by ranking the relevance of the image nodes with foreground cues extracted from the former saliency map, we obtain an improved result. Finally, smoothing operation is utilized to refine the foreground-based saliency map to improve the contrast between salient and non-salient regions until a close to binary saliency map is reached. Experimental results show that the proposed algorithm generates more accurate saliency maps and performs favorably against the state-off-the-art saliency detection methods on four publicly available datasets.
Transfer Learning for Neural Semantic Parsing
Venue: arXiv cs.CL 2017
Year: 2017

The goal of semantic parsing is to map natural language to a machine interpretable meaning representation language (MRL). One of the constraints that limits full exploration of deep learning technologies for semantic parsing is the lack of sufficient annotation training data. In this paper, we propose using sequence-to-sequence in a multi-task setup for semantic parsing with a focus on transfer learning. We explore three multi-task architectures for sequence-to-sequence modeling and compare their performance with an independently trained model. Our experiments show that the multi-task setup aids transfer learning from an auxiliary task with large labeled data to a target task with smaller labeled data. We see absolute accuracy gains ranging from 1.0% to 4.4% in our in- house data set, and we also see good gains ranging from 2.5% to 7.0% on the ATIS semantic parsing tasks with syntactic and semantic auxiliary tasks.
Towards Adaptive Resilience in High Performance Computing
Venue: arXiv cs.DC 2017
Year: 2017

Failure rates in high performance computers rapidly increase due to the growth in system size and complexity. Hence, failures became the norm rather than the exception. Different approaches on high performance computing (HPC) systems have been introduced, to prevent failures (e. g., redundancy) or at least minimize their impacts (e. g., checkpoint and restart). In most cases, when these approaches are employed to increase the resilience of certain parts of a system, energy consumption rapidly increases, or performance significantly degrades. To address this challenge, we propose on-demand resilience as an approach to achieve adaptive resilience in HPC systems. In this work, the HPC system is considered in its entirety and resilience mechanisms such as checkpointing, isolation, and migration, are activated on-demand. Using the proposed approach, the unavoidable increase in total energy consumption and system performance degradation is decreased compared to the typical checkpoint/restart and redundant resilience mechanisms. Our work aims to mitigate a large number of failures occurring at various layers in the system, to prevent their propagation, and to minimize their impact, all of this in an energy-saving manner. In the case of failures that are estimated to occur but cannot be mitigated using the proposed on-demand resilience approach, the system administrators will be notified in view of performing further investigations into the causes of these failures and their impacts.
Simultaneous merging multiple grid maps using the robust motion averaging
Venue: arXiv cs.AI 2017
Year: 2017

Mapping in the GPS-denied environment is an important and challenging task in the field of robotics. In the large environment, mapping can be significantly accelerated by multiple robots exploring different parts of the environment. Accordingly, a key problem is how to integrate these local maps built by different robots into a single global map. In this paper, we propose an approach for simultaneous merging of multiple grid maps by the robust motion averaging. The main idea of this approach is to recover all global motions for map merging from a set of relative motions. Therefore, it firstly adopts the pair-wise map merging method to estimate relative motions for grid map pairs. To obtain as many reliable relative motions as possible, a graph-based sampling scheme is utilized to efficiently remove unreliable relative motions obtained from the pair-wise map merging. Subsequently, the accurate global motions can be recovered from the set of reliable relative motions by the motion averaging. Experimental results carried on real robot data sets demonstrate that proposed approach can achieve simultaneous merging of multiple grid maps with good performances.
Failure-Directed Program Trimming (Extended Version)
Venue: arXiv cs.SE 2017
Year: 2017

This paper describes a new program simplification technique called program trimming that aims to improve the scalability and precision of safety checking tools. Given a program ${\mathcal P}$, program trimming generates a new program ${\mathcal P}'$ such that ${\mathcal P}$ and ${\mathcal P}'$ are equi-safe (i.e., ${\mathcal P}'$ has a bug if and only if ${\mathcal P}$ has a bug), but ${\mathcal P}'$ has fewer execution paths than ${\mathcal P}$. Since many program analyzers are sensitive to the number of execution paths, program trimming has the potential to improve the effectiveness of safety checking tools. In addition to introducing the concept of program trimming, this paper also presents a lightweight static analysis that can be used as a pre-processing step to remove program paths while retaining equi-safety. We have implemented the proposed technique in a tool called Trimmer and evaluate it in the context of two program analysis techniques, namely abstract interpretation and dynamic symbolic execution. Our experiments show that program trimming significantly improves the effectiveness of both techniques.
Idea density for predicting Alzheimer's disease from transcribed speech
Venue: arXiv cs.CL 2017
Year: 2017

Idea Density (ID) measures the rate at which ideas or elementary predications are expressed in an utterance or in a text. Lower ID is found to be associated with an increased risk of developing Alzheimer's disease (AD) (Snowdon et al., 1996; Engelman et al., 2010). ID has been used in two different versions: propositional idea density (PID) counts the expressed ideas and can be applied to any text while semantic idea density (SID) counts pre-defined information content units and is naturally more applicable to normative domains, such as picture description tasks. In this paper, we develop DEPID, a novel dependency-based method for computing PID, and its version DEPID-R that enables to exclude repeating ideas---a feature characteristic to AD speech. We conduct the first comparison of automatically extracted PID and SID in the diagnostic classification task on two different AD datasets covering both closed-topic and free-recall domains. While SID performs better on the normative dataset, adding PID leads to a small but significant improvement (+1.7 F-score). On the free-topic dataset, PID performs better than SID as expected (77.6 vs 72.3 in F-score) but adding the features derived from the word embedding clustering underlying the automatic SID increases the results considerably, leading to an F-score of 84.8.
On the Hamming Auto- and Cross-correlation Functions of a Class of Frequency Hopping Sequences of Length $ p^{n} $
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, a new class of frequency hopping sequences (FHSs) of length $ p^{n} $ is constructed by using Ding-Helleseth generalized cyclotomic classes of order 2, of which the Hamming auto- and cross-correlation functions are investigated (for the Hamming cross-correlation, only the case $ p\equiv 3\pmod 4 $ is considered). It is shown that the set of the constructed FHSs is optimal with respect to the average Hamming correlation functions.
Learning without Prejudice: Avoiding Bias in Webly-Supervised Action Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Webly-supervised learning has recently emerged as an alternative paradigm to traditional supervised learning based on large-scale datasets with manual annotations. The key idea is that models such as CNNs can be learned from the noisy visual data available on the web. In this work we aim to exploit web data for video understanding tasks such as action recognition and detection. One of the main problems in webly-supervised learning is cleaning the noisy labeled data from the web. The state-of-the-art paradigm relies on training a first classifier on noisy data that is then used to clean the remaining dataset. Our key insight is that this procedure biases the second classifier towards samples that the first one understands. Here we train two independent CNNs, a RGB network on web images and video frames and a second network using temporal information from optical flow. We show that training the networks independently is vastly superior to selecting the frames for the flow classifier by using our RGB network. Moreover, we show benefits in enriching the training set with different data sources from heterogeneous public web databases. We demonstrate that our framework outperforms all other webly-supervised methods on two public benchmarks, UCF-101 and Thumos'14.
Planning with Verbal Communication for Human-Robot Collaboration
Venue: arXiv cs.RO 2017
Year: 2017

Human collaborators coordinate effectively their actions through both verbal and non-verbal communication. We believe that the the same should hold for human-robot teams. We propose a formalism that enables a robot to decide optimally between doing a task and issuing an utterance. We focus on two types of utterances: verbal commands, where the robot expresses how it wants its human teammate to behave, and state-conveying actions, where the robot explains why it is behaving this way. Human subject experiments show that enabling the robot to issue verbal commands is the most effective form of communicating objectives, while retaining user trust in the robot. Communicating why information should be done judiciously, since many participants questioned the truthfulness of the robot statements.
Suggestive Annotation: A Deep Active Learning Framework for Biomedical Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Image segmentation is a fundamental problem in biomedical image analysis. Recent advances in deep learning have achieved promising results on many biomedical image segmentation benchmarks. However, due to large variations in biomedical images (different modalities, image settings, objects, noise, etc), to utilize deep learning on a new application, it usually needs a new set of training data. This can incur a great deal of annotation effort and cost, because only biomedical experts can annotate effectively, and often there are too many instances in images (e.g., cells) to annotate. In this paper, we aim to address the following question: With limited effort (e.g., time) for annotation, what instances should be annotated in order to attain the best performance? We present a deep active learning framework that combines fully convolutional network (FCN) and active learning to significantly reduce annotation effort by making judicious suggestions on the most effective annotation areas. We utilize uncertainty and similarity information provided by FCN and formulate a generalized version of the maximum set cover problem to determine the most representative and uncertain areas for annotation. Extensive experiments using the 2015 MICCAI Gland Challenge dataset and a lymph node ultrasound image segmentation dataset show that, using annotation suggestions by our method, state-of-the-art segmentation performance can be achieved by using only 50% of training data.
Software Model Checking: A Promising Approach to Verify Mobile App Security
Venue: arXiv cs.SE 2017
Year: 2017

In this position paper we advocate software model checking as a technique suitable for security analysis of mobile apps. Our recommendation is based on promising results that we achieved on analysing app collusion in the context of the Android operating system. Broadly speaking, app collusion appears when, in performing a threat, several apps are working together, i.e., they exchange information which they could not obtain on their own. In this context, we developed the Kandroid tool, which provides an encoding of the Android/Smali code semantics within the K framework. Kandroid allows for software model checking of Android APK files. Though our experience so far is limited to collusion, we believe the approach to be applicable to further security properties as well as other mobile operating systems.
DSRIM: A Deep Neural Information Retrieval Model Enhanced by a Knowledge Resource Driven Representation of Documents
Venue: arXiv cs.IR 2017
Year: 2017

The state-of-the-art solutions to the vocabulary mismatch in information retrieval (IR) mainly aim at leveraging either the relational semantics provided by external resources or the distributional semantics, recently investigated by deep neural approaches. Guided by the intuition that the relational semantics might improve the effectiveness of deep neural approaches, we propose the Deep Semantic Resource Inference Model (DSRIM) that relies on: 1) a representation of raw-data that models the relational semantics of text by jointly considering objects and relations expressed in a knowledge resource, and 2) an end-to-end neural architecture that learns the query-document relevance by leveraging the distributional and relational semantics of documents and queries. The experimental evaluation carried out on two TREC datasets from TREC Terabyte and TREC CDS tracks relying respectively on WordNet and MeSH resources, indicates that our model outperforms state-of-the-art semantic and deep neural IR models.
Measuring Personalization of Web Search
Venue: arXiv cs.CY 2017
Year: 2017

Web search is an integral part of our daily lives. Recently, there has been a trend of personalization in Web search, where different users receive different results for the same search query. The increasing level of personalization is leading to concerns about Filter Bubble effects, where certain users are simply unable to access information that the search engines' algorithm decides is irrelevant. Despite these concerns, there has been little quantification of the extent of personalization in Web search today, or the user attributes that cause it. In light of this situation, we make three contributions. First, we develop a methodology for measuring personalization in Web search results. While conceptually simple, there are numerous details that our methodology must handle in order to accurately attribute differences in search results to personalization. Second, we apply our methodology to 200 users on Google Web Search and 100 users on Bing. We find that, on average, 11.7% of results show differences due to personalization on Google, while 15.8% of results are personalized on Bing, but that this varies widely by search query and by result ranking. Third, we investigate the user features used to personalize on Google Web Search and Bing. Surprisingly, we only find measurable personalization as a result of searching with a logged in account and the IP address of the searching user. Our results are a first step towards understanding the extent and effects of personalization on Web search engines today.