OpenRaiser/Intern-Atlas huggingface dataset:
Popular Matching with Lower Quotas
Venue: arXiv cs.DS 2017
Year: 2017

We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph $G = (\mathcal{R} \cup \mathcal{H}, E)$ where $\mathcal{R}$ and $\mathcal{H}$ denote sets of residents and hospitals respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital $h$ has an associated upper-quota $q^+(h)$ and lower-quota $q^-(h)$. A matching $M$ in $G$ is an assignment of residents to hospitals, and $M$ is said to be feasible if every resident is assigned to at most one hospital and a hospital $h$ is assigned at least $q^-(h)$ and at most $q^+(h)$ residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching $M$ is popular if no other matching $M'$ gets more votes than $M$ when vertices vote between $M$ and $M'$. When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance.
A Methodology of Guiding Web Content Mining and Knowledge Discovery in Evidence-based Software Engineering
Venue: arXiv cs.SE 2017
Year: 2017

Systematic Literature Review (SLR) is a rigorous methodology applied for Evidence-Based Software Engineering (EBSE) that identify, assess and synthesize the relevant evidence for answering specific research questions. Benefiting from the booming online materials in the era of Web 2.0, the technical Web content starts acting as alternative sources for EBSE. Web knowledge has been investigated and derived from Web content mining and knowledge discovery techniques, however they are still significantly different from reviewing academic literature. Thus the direct adoption of Web knowledge in EBSE lacks of systematic guidelines. In this paper, we propose to make an SLR adaptation to bridge the aforementioned gap along two stages. Firstly, we follow the general logic and procedure of SLR to regulate Web mining activities. Secondly, we substitute and enhance particular SLR processes with Web-mining-friendly methods and approaches. At the second stage, we mainly focus on adapting Conducting Review by integrating a set of automated components ranging from programmatic searching to various text mining techniques.
Beyond WYSIWYG: Sharing Contextual Sensing Data Through mmWave V2V Communications
Venue: arXiv cs.IT 2017
Year: 2017

In vehicular scenarios context awareness is a key enabler for road safety. However, the amount of contextual information that can be collected by a vehicle is stringently limited by the sensor technology itself (e.g., line-of-sight, coverage, weather robustness) and by the low bandwidths offered by current wireless vehicular technologies such as DSRC/802.11p. Motivated by the upsurge of research around millimeter-wave vehicle-to-anything (V2X) communications, in this work we propose a distributed vehicle-to-vehicle (V2V) association scheme that considers a quantitative measure of the potential value of the shared contextual information in the pairing process. First, we properly define the utility function of every vehicle balancing classical channel state and queuing state information (CSI/QSI) with context information i.e., sensing content resolution, timeliness and enhanced range of the sensing. Next we solve the problem via a distributed many-to-one matching game in a junction scenario with realistic vehicular mobility traces. It is shown that when receivers are able to leverage information from different sources, the average volume of collected extended sensed information under our proposed scheme is up to 71% more than that of distance and minimum delay-based matching baselines.
Arabidopsis roots segmentation based on morphological operations and CRFs
Venue: arXiv cs.CV 2017
Year: 2017

Arabidopsis thaliana is a plant species widely utilized by scientists to estimate the impact of genetic differences in root morphological features. For this purpose, images of this plant after genetic modifications are taken to study differences in the root architecture. This task requires manual segmentations of radicular structures, although this is a particularly tedious and time-consuming labor. In this work, we present an unsupervised method for Arabidopsis thaliana root segmentation based on morphological operations and fully-connected Conditional Random Fields. Although other approaches have been proposed to this purpose, all of them are based on more complex and expensive imaging modalities. Our results prove that our method can be easily applied over images taken using conventional scanners, with a minor user intervention. A first data set, our results and a fully open source implementation are available online.
Z3str3: A String Solver with Theory-aware Branching
Venue: arXiv cs.LO 2017
Year: 2017

We present a new string SMT solver, Z3str3, that is faster than its competitors Z3str2, Norn, CVC4, S3, and S3P over a majority of three industrial-strength benchmarks, namely Kaluza, PISA, and IBM AppScan. Z3str3 supports string equations, linear arithmetic over length function, and regular language membership predicate. The key algorithmic innovation behind the efficiency of Z3str3 is a technique we call theory-aware branching, wherein we modify Z3's branching heuristic to take into account the structure of theory literals to compute branching activities. In the traditional DPLL(T) architecture, the structure of theory literals is hidden from the DPLL(T) SAT solver because of the Boolean abstraction constructed over the input theory formula. By contrast, the theory-aware technique presented in this paper exposes the structure of theory literals to the DPLL(T) SAT solver's branching heuristic, thus enabling it to make much smarter decisions during its search than otherwise. As a consequence, Z3str3 has better performance than its competitors.
Exact Algorithms via Multivariate Subroutines
Venue: arXiv cs.DS 2017
Year: 2017

We consider the family of $Φ$-Subset problems, where the input consists of an instance $I$ of size $N$ over a universe $U_I$ of size $n$ and the task is to check whether the universe contains a subset with property $Φ$ (e.g., $Φ$ could be the property of being a feedback vertex set for the input graph of size at most $k$). Our main tool is a simple randomized algorithm which solves $Φ$-Subset in time $(1+b-\frac{1}{c})^n N^{O(1)}$, provided that there is an algorithm for the $Φ$-Extension problem with running time $b^{n-|X|} c^k N^{O(1)}$. Here, the input for $Φ$-Extension is an instance $I$ of size $N$ over a universe $U_I$ of size $n$, a subset $X\subseteq U_I$, and an integer $k$, and the task is to check whether there is a set $Y$ with $X\subseteq Y \subseteq U_I$ and $|Y\setminus X|\le k$ with property $Φ$. We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in $n$, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property $Φ$. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where $b=1$. As case studies, we use these results to design faster deterministic algorithms for: - checking whether a graph has a feedback vertex set of size at most $k$ - enumerating all minimal feedback vertex sets - enumerating all minimal vertex covers of size at most $k$, and - enumerating all minimal 3-hitting sets. We obtain these results by deriving new $b^{n-|X|} c^k N^{O(1)}$-time algorithms for the corresponding $Φ$-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, $1+b-\frac{1}{c}$, is unconventional and requires non-convex optimization.
Measurement Matrix Design for Phase Retrieval Based on Mutual Information
Venue: arXiv cs.IT 2017
Year: 2017

In phase retrieval problems, a signal of interest (SOI) is reconstructed based on the magnitude of a linear transformation of the SOI observed with additive noise. The linear transform is typically referred to as a measurement matrix. Many works on phase retrieval assume that the measurement matrix is a random Gaussian matrix, which, in the noiseless scenario with sufficiently many measurements, guarantees invertability of the transformation between the SOI and the observations, up to an inherent phase ambiguity. However, in many practical applications, the measurement matrix corresponds to an underlying physical setup, and is therefore deterministic, possibly with structural constraints. In this work we study the design of deterministic measurement matrices, based on maximizing the mutual information between the SOI and the observations. We characterize necessary conditions for the optimality of a measurement matrix, and analytically obtain the optimal matrix in the low signal-to-noise ratio regime. Practical methods for designing general measurement matrices and masked Fourier measurements are proposed. Simulation tests demonstrate the performance gain achieved by the proposed techniques compared to random Gaussian measurements for various phase recovery algorithms.
Automatic Viseme Vocabulary Construction to Enhance Continuous Lip-reading
Venue: arXiv cs.CV 2017
Year: 2017

Speech is the most common communication method between humans and involves the perception of both auditory and visual channels. Automatic speech recognition focuses on interpreting the audio signals, but it has been demonstrated that video can provide information that is complementary to the audio. Thus, the study of automatic lip-reading is important and is still an open problem. One of the key challenges is the definition of the visual elementary units (the visemes) and their vocabulary. Many researchers have analyzed the importance of the phoneme to viseme mapping and have proposed viseme vocabularies with lengths between 11 and 15 visemes. These viseme vocabularies have usually been manually defined by their linguistic properties and in some cases using decision trees or clustering techniques. In this work, we focus on the automatic construction of an optimal viseme vocabulary based on the association of phonemes with similar appearance. To this end, we construct an automatic system that uses local appearance descriptors to extract the main characteristics of the mouth region and HMMs to model the statistic relations of both viseme and phoneme sequences. To compare the performance of the system different descriptors (PCA, DCT and SIFT) are analyzed. We test our system in a Spanish corpus of continuous speech. Our results indicate that we are able to recognize approximately 58% of the visemes, 47% of the phonemes and 23% of the words in a continuous speech scenario and that the optimal viseme vocabulary for Spanish is composed by 20 visemes.
On Maximizing Sensor Network Lifetime by Energy Balancing
Venue: arXiv cs.SY 2017
Year: 2017

Many physical systems, such as water/electricity distribution networks, are monitored by battery-powered Wireless Sensor Networks (WSNs). Since battery replacement of sensor nodes is generally difficult, long-term monitoring can be only achieved if the operation of the WSN nodes contributes to a long WSN lifetime. Two prominent techniques to long WSN lifetime are i) optimal sensor activation and ii) efficient data gathering and forwarding based on compressive sensing. These techniques are feasible only if the activated sensor nodes establish a connected communication network (connectivity constraint), and satisfy a compressive sensing decoding constraint (cardinality constraint). These two constraints make the problem of maximizing network lifetime via sensor node activation and compressive sensing NP-hard. To overcome this difficulty, an alternative approach that iteratively solves energy balancing problems is proposed. However, understanding whether maximizing network lifetime and energy balancing problems are aligned objectives is a fundamental open issue. The analysis reveals that the two optimization problems give different solutions, but the difference between the lifetime achieved by the energy balancing approach and the maximum lifetime is small when the initial energy at sensor nodes is significantly larger than the energy consumed for a single transmission. The lifetime achieved by the energy balancing is asymptotically optimal, and that the achievable network lifetime is at least $50$\% of the optimum. Analysis and numerical simulations quantify the efficiency of the proposed energy balancing approach.
Event Stream-Based Process Discovery using Abstract Representations
Venue: arXiv cs.DB 2017
Year: 2017

The aim of process discovery, originating from the area of process mining, is to discover a process model based on business process execution data. A majority of process discovery techniques relies on an event log as an input. An event log is a static source of historical data capturing the execution of a business process. In this paper we focus on process discovery relying on online streams of business process execution events. Learning process models from event streams poses both challenges and opportunities, i.e. we need to handle unlimited amounts of data using finite memory and, preferably, constant time. We propose a generic architecture that allows for adopting several classes of existing process discovery techniques in context of event streams. Moreover, we provide several instantiations of the architecture, accompanied by implementations in the process mining tool-kit ProM (http://promtools.org). Using these instantiations, we evaluate several dimensions of stream-based process discovery. The evaluation shows that the proposed architecture allows us to lift process discovery to the streaming domain.
Connected Vehicular Transportation: Data Analytics and Traffic-dependent Networking
Venue: arXiv cs.NI 2017
Year: 2017

With onboard operating systems becoming increasingly common in vehicles, the real-time broadband infotainment and Intelligent Transportation System (ITS) service applications in fast-motion vehicles become ever demanding, which are highly expected to significantly improve the efficiency and safety of our daily on-road lives. The emerging ITS and vehicular applications, e.g., trip planning, however, require substantial efforts on the real-time pervasive information collection and big data processing so as to provide quick decision making and feedbacks to the fast moving vehicles, which thus impose the significant challenges on the development of an efficient vehicular communication platform. In this article, we present TrasoNET, an integrated network framework to provide realtime intelligent transportation services to connected vehicles by exploring the data analytics and networking techniques. TrasoNET is built upon two key components. The first one guides vehicles to the appropriate access networks by exploring the information of realtime traffic status, specific user preferences, service applications and network conditions. The second component mainly involves a distributed automatic access engine, which enables individual vehicles to make distributed access decisions based on access recommender, local observation and historic information. We showcase the application of TrasoNET in a case study on real-time traffic sensing based on real traces of taxis.
New region force for variational models in image segmentation and high dimensional data clustering
Venue: arXiv cs.CV 2017
Year: 2017

We propose an effective framework for multi-phase image segmentation and semi-supervised data clustering by introducing a novel region force term into the Potts model. Assume the probability that a pixel or a data point belongs to each class is known a priori. We show that the corresponding indicator function obeys the Bernoulli distribution and the new region force function can be computed as the negative log-likelihood function under the Bernoulli distribution. We solve the Potts model by the primal-dual hybrid gradient method and the augmented Lagrangian method, which are based on two different dual problems of the same primal problem. Empirical evaluations of the Potts model with the new region force function on benchmark problems show that it is competitive with existing variational methods in both image segmentation and semi-supervised data clustering.
C-VQA: A Compositional Split of the Visual Question Answering (VQA) v1.0 Dataset
Venue: arXiv cs.CV 2017
Year: 2017

Visual Question Answering (VQA) has received a lot of attention over the past couple of years. A number of deep learning models have been proposed for this task. However, it has been shown that these models are heavily driven by superficial correlations in the training data and lack compositionality -- the ability to answer questions about unseen compositions of seen concepts. This compositionality is desirable and central to intelligence. In this paper, we propose a new setting for Visual Question Answering where the test question-answer pairs are compositionally novel compared to training question-answer pairs. To facilitate developing models under this setting, we present a new compositional split of the VQA v1.0 dataset, which we call Compositional VQA (C-VQA). We analyze the distribution of questions and answers in the C-VQA splits. Finally, we evaluate several existing VQA models under this new setting and show that the performances of these models degrade by a significant amount compared to the original VQA setting.
Face Identification and Clustering
Venue: arXiv cs.CV 2017
Year: 2017

In this thesis, we study two problems based on clustering algorithms. In the first problem, we study the role of visual attributes using an agglomerative clustering algorithm to whittle down the search area where the number of classes is high to improve the performance of clustering. We observe that as we add more attributes, the clustering performance increases overall. In the second problem, we study the role of clustering in aggregating templates in a 1:N open set protocol using multi-shot video as a probe. We observe that by increasing the number of clusters, the performance increases with respect to the baseline and reaches a peak, after which increasing the number of clusters causes the performance to degrade. Experiments are conducted using recently introduced unconstrained IARPA Janus IJB-A, CS2, and CS3 face recognition datasets.
Joint Semantic and Motion Segmentation for dynamic scenes using Deep Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Dynamic scene understanding is a challenging problem and motion segmentation plays a crucial role in solving it. Incorporating semantics and motion enhances the overall perception of the dynamic scene. For applications of outdoor robotic navigation, joint learning methods have not been extensively used for extracting spatio-temporal features or adding different priors into the formulation. The task becomes even more challenging without stereo information being incorporated. This paper proposes an approach to fuse semantic features and motion clues using CNNs, to address the problem of monocular semantic motion segmentation. We deduce semantic and motion labels by integrating optical flow as a constraint with semantic features into dilated convolution network. The pipeline consists of three main stages i.e Feature extraction, Feature amplification and Multi Scale Context Aggregation to fuse the semantics and flow features. Our joint formulation shows significant improvements in monocular motion segmentation over the state of the art methods on challenging KITTI tracking dataset.
DeepCCI: End-to-end Deep Learning for Chemical-Chemical Interaction Prediction
Venue: arXiv cs.LG 2017
Year: 2017

Chemical-chemical interaction (CCI) plays a key role in predicting candidate drugs, toxicity, therapeutic effects, and biological functions. In various types of chemical analyses, computational approaches are often required due to the amount of data that needs to be handled. The recent remarkable growth and outstanding performance of deep learning have attracted considerable research attention. However,even in state-of-the-art drug analysis methods, deep learning continues to be used only as a classifier, although deep learning is capable of not only simple classification but also automated feature extraction. In this paper, we propose the first end-to-end learning method for CCI, named DeepCCI. Hidden features are derived from a simplified molecular input line entry system (SMILES), which is a string notation representing the chemical structure, instead of learning from crafted features. To discover hidden representations for the SMILES strings, we use convolutional neural networks (CNNs). To guarantee the commutative property for homogeneous interaction, we apply model sharing and hidden representation merging techniques. The performance of DeepCCI was compared with a plain deep classifier and conventional machine learning methods. The proposed DeepCCI showed the best performance in all seven evaluation metrics used. In addition, the commutative property was experimentally validated. The automatically extracted features through end-to-end SMILES learning alleviates the significant efforts required for manual feature engineering. It is expected to improve prediction performance, in drug analyses.
Consensus measure of rankings
Venue: arXiv cs.AI 2017
Year: 2017

A ranking is an ordered sequence of items, in which an item with higher ranking score is more preferred than the items with lower ranking scores. In many information systems, rankings are widely used to represent the preferences over a set of items or candidates. The consensus measure of rankings is the problem of how to evaluate the degree to which the rankings agree. The consensus measure can be used to evaluate rankings in many information systems, as quite often there is not ground truth available for evaluation. This paper introduces a novel approach for consensus measure of rankings by using graph representation, in which the vertices or nodes are the items and the edges are the relationship of items in the rankings. Such representation leads to various algorithms for consensus measure in terms of different aspects of rankings, including the number of common patterns, the number of common patterns with fixed length and the length of the longest common patterns. The proposed measure can be adopted for various types of rankings, such as full rankings, partial rankings and rankings with ties. This paper demonstrates how the proposed approaches can be used to evaluate the quality of rank aggregation and the quality of top-$k$ rankings from Google and Bing search engines.