OpenRaiser/Intern-Atlas huggingface dataset:
Communication complexity of approximate maximum matching in the message-passing model
Venue: arXiv cs.DS 2017
Year: 2017

We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is one of the most fundamental graph combinatorial problems, with a variety of applications. The input to the problem is a graph $G$ that has $n$ vertices and the set of edges partitioned over $k$ sites, and an approximation ratio parameter $α$. The output is required to be a matching in $G$ that has to be reported by one of the sites, whose size is at least factor $α$ of the size of a maximum matching in $G$. We show that the communication complexity of this problem is $Ω(α^2 k n)$ information bits. This bound is shown to be tight up to a $\log n$ factor, by constructing an algorithm, establishing its correctness, and an upper bound on the communication cost. The lower bound also applies to other graph combinatorial problems in the message-passing communication model, including max-flow and graph sparsification.
A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry
Venue: arXiv cs.DM 2017
Year: 2017

The paper develops a new technique to extract a characteristic subset from a random source that repeatedly samples from a set of elements. Here a characteristic subset is a set that when containing an element contains all elements that have the same probability. With this technique at hand the paper looks at the special case of the tournament isomorphism problem that stands in the way towards a polynomial-time algorithm for the graph isomorphism problem. Noting that there is a reduction from the automorphism (asymmetry) problem to the isomorphism problem, a reduction in the other direction is nevertheless not known and remains a thorny open problem. Applying the new technique, we develop a randomized polynomial-time Turing-reduction from the tournament isomorphism problem to the tournament automorphism problem. This is the first such reduction for any kind of combinatorial object not known to have a polynomial-time solvable isomorphism problem.
EEG-Based User Reaction Time Estimation Using Riemannian Geometry Features
Venue: arXiv cs.HC 2017
Year: 2017

Riemannian geometry has been successfully used in many brain-computer interface (BCI) classification problems and demonstrated superior performance. In this paper, for the first time, it is applied to BCI regression problems, an important category of BCI applications. More specifically, we propose a new feature extraction approach for Electroencephalogram (EEG) based BCI regression problems: a spatial filter is first used to increase the signal quality of the EEG trials and also to reduce the dimensionality of the covariance matrices, and then Riemannian tangent space features are extracted. We validate the performance of the proposed approach in reaction time estimation from EEG signals measured in a large-scale sustained-attention psychomotor vigilance task, and show that compared with the traditional powerband features, the tangent space features can reduce the root mean square estimation error by 4.30-8.30%, and increase the estimation correlation coefficient by 6.59-11.13%.
Modeling Events as Machines
Venue: arXiv cs.AI 2017
Year: 2017

The notion of events has occupied a central role in modeling and has an influence in computer science and philosophy. Recent developments in diagrammatic modeling have made it possible to examine conceptual representation of events. This paper explores some aspects of the notion of events that are produced by applying a new diagrammatic methodology with a focus on the interaction of events with such concepts as time and space, objects. The proposed description applies to abstract machines where events form the dynamic phases of a system. The results of this nontechnical research can be utilized in many fields where the notion of an event is typically used in interdisciplinary application.
Dissecting Robotics - historical overview and future perspectives
Venue: arXiv cs.RO 2017
Year: 2017

Robotics is called to be the next technological revolution and estimations indicate that it will trigger the fourth industrial revolution. This article presents a review of some of the most relevant milestones that occurred in robotics over the last few decades and future perspectives. Despite the fact that, nowadays, robotics is an emerging field, the challenges in many technological aspects and more importantly bringing innovative solutions to the market still remain open. The need of reducing the integration time, costs and a common hardware infrastructure are discussed and further analysed in this work. We conclude with a discussion of the future perspectives of robotics as an engineering discipline and with suggestions for future research directions.
End-to-End Multimodal Emotion Recognition using Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Automatic affect recognition is a challenging task due to the various modalities emotions can be expressed with. Applications can be found in many domains including multimedia retrieval and human computer interaction. In recent years, deep neural networks have been used with great success in determining emotional states. Inspired by this success, we propose an emotion recognition system using auditory and visual modalities. To capture the emotional content for various styles of speaking, robust features need to be extracted. To this purpose, we utilize a Convolutional Neural Network (CNN) to extract features from the speech, while for the visual modality a deep residual network (ResNet) of 50 layers. In addition to the importance of feature extraction, a machine learning algorithm needs also to be insensitive to outliers while being able to model the context. To tackle this problem, Long Short-Term Memory (LSTM) networks are utilized. The system is then trained in an end-to-end fashion where - by also taking advantage of the correlations of the each of the streams - we manage to significantly outperform the traditional approaches based on auditory and visual handcrafted features for the prediction of spontaneous and natural emotions on the RECOLA database of the AVEC 2016 research challenge on emotion recognition.
Age-Minimal Transmission in Energy Harvesting Two-hop Networks
Venue: arXiv cs.IT 2017
Year: 2017

We consider an energy harvesting two-hop network where a source is communicating to a destination through a relay. During a given communication session time, the source collects measurement updates from a physical phenomenon and sends them to the relay, which then forwards them to the destination. The objective is to send these updates to the destination as timely as possible; namely, such that the total age of information is minimized by the end of the communication session, subject to energy causality constraints at the source and the relay, and data causality constraints at the relay. Both the source and the relay use fixed, yet possibly different, transmission rates. Hence, each update packet incurs fixed non-zero transmission delays. We first solve the single-hop version of this problem, and then show that the two-hop problem is solved by treating the source and relay nodes as one combined node, with some parameter transformations, and solving a single-hop problem between that combined node and the destination.
AWEsome: An open-source test platform for airborne wind energy systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we present AWEsome (Airborne Wind Energy Standardized Open-source Model Environment), a test platform for airborne wind energy systems that consists of low-cost hardware and is entirely based on open-source software. It can hence be used without the need of large financial investments, in particular by research groups and startups to acquire first experiences in their flight operations, to test novel control strategies or technical designs, or for usage in public relations. Our system consists of a modified off-the-shelf model aircraft that is controlled by the pixhawk autopilot hardware and the ardupilot software for fixed wing aircraft. The aircraft is attached to the ground by a tether. We have implemented new flight modes for the autonomous tethered flight of the aircraft along periodic patterns. We present the principal functionality of our algorithms. We report on first successful tests of these modes in real flights.
A universal tree balancing theorem
Venue: arXiv cs.CC 2017
Year: 2017

We present a general framework for balancing expressions (terms) in form of so called tree straight-line programs. The latter can be seen as circuits over the free term algebra extended by contexts (terms with a hole) and the operations which insert terms/contexts into contexts. It is shown that for every term one can compute in DLOGTIME-uniform TC$^0$ a tree straight-line program of logarithmic depth and size $O(n/\log n)$. This allows reducing the term evaluation problem over an arbitrary algebra $\mathcal{A}$ to the term evaluation problem over a derived two-sorted algebra $\mathcal{F}(\mathcal{A})$. Several applications are presented: (i) an alternative proof for a recent result by Krebs, Limaye and Ludwig on the expression evaluation problem is given, (ii) it is shown that expressions for an arbitrary (possibly non-commutative) semiring can be transformed in DLOGTIME-uniform TC$^0$ into equivalent circuits of logarithmic depth and size $O(n/\log n)$, and (iii) a corresponding result for regular expressions is shown.
Genealogical Distance as a Diversity Estimate in Evolutionary Algorithms
Venue: arXiv cs.NE 2017
Year: 2017

The evolutionary edit distance between two individuals in a population, i.e., the amount of applications of any genetic operator it would take the evolutionary process to generate one individual starting from the other, seems like a promising estimate for the diversity between said individuals. We introduce genealogical diversity, i.e., estimating two individuals' degree of relatedness by analyzing large, unused parts of their genome, as a computationally efficient method to approximate that measure for diversity.
Risk Stratification of Lung Nodules Using 3D CNN-Based Multi-task Learning
Venue: arXiv cs.CV 2017
Year: 2017

Risk stratification of lung nodules is a task of primary importance in lung cancer diagnosis. Any improvement in robust and accurate nodule characterization can assist in identifying cancer stage, prognosis, and improving treatment planning. In this study, we propose a 3D Convolutional Neural Network (CNN) based nodule characterization strategy. With a completely 3D approach, we utilize the volumetric information from a CT scan which would be otherwise lost in the conventional 2D CNN based approaches. In order to address the need for a large amount for training data for CNN, we resort to transfer learning to obtain highly discriminative features. Moreover, we also acquire the task dependent feature representation for six high-level nodule attributes and fuse this complementary information via a Multi-task learning (MTL) framework. Finally, we propose to incorporate potential disagreement among radiologists while scoring different nodule attributes in a graph regularized sparse multi-task learning. We evaluated our proposed approach on one of the largest publicly available lung nodule datasets comprising 1018 scans and obtained state-of-the-art results in regressing the malignancy scores.
Neural Ranking Models with Weak Supervision
Venue: arXiv cs.IR 2017
Year: 2017

Despite the impressive improvements achieved by unsupervised deep neural networks in computer vision and NLP tasks, such improvements have not yet been observed in ranking for information retrieval. The reason may be the complexity of the ranking problem, as it is not obvious how to learn from queries and documents when no supervised signal is available. Hence, in this paper, we propose to train a neural ranking model using weak supervision, where labels are obtained automatically without human annotators or any external resources (e.g., click data). To this aim, we use the output of an unsupervised ranking model, such as BM25, as a weak supervision signal. We further train a set of simple yet effective ranking models based on feed-forward neural networks. We study their effectiveness under various learning scenarios (point-wise and pair-wise models) and using different input representations (i.e., from encoding query-document pairs into dense/sparse vectors to using word embedding representation). We train our networks using tens of millions of training instances and evaluate it on two standard collections: a homogeneous news collection(Robust) and a heterogeneous large-scale web collection (ClueWeb). Our experiments indicate that employing proper objective functions and letting the networks to learn the input representation based on weakly supervised data leads to impressive performance, with over 13% and 35% MAP improvements over the BM25 model on the Robust and the ClueWeb collections. Our findings also suggest that supervised neural ranking models can greatly benefit from pre-training on large amounts of weakly labeled data that can be easily obtained from unsupervised IR models.
Automatic Real-time Background Cut for Portrait Videos
Venue: arXiv cs.CV 2017
Year: 2017

We in this paper solve the problem of high-quality automatic real-time background cut for 720p portrait videos. We first handle the background ambiguity issue in semantic segmentation by proposing a global background attenuation model. A spatial-temporal refinement network is developed to further refine the segmentation errors in each frame and ensure temporal coherence in the segmentation map. We form an end-to-end network for training and testing. Each module is designed considering efficiency and accuracy. We build a portrait dataset, which includes 8,000 images with high-quality labeled map for training and testing. To further improve the performance, we build a portrait video dataset with 50 sequences to fine-tune video segmentation. Our framework benefits many video processing applications.
A Tribe Competition-Based Genetic Algorithm for Feature Selection in Pattern Classification
Venue: arXiv cs.LG 2017
Year: 2017

Feature selection has always been a critical step in pattern recognition, in which evolutionary algorithms, such as the genetic algorithm (GA), are most commonly used. However, the individual encoding scheme used in various GAs would either pose a bias on the solution or require a pre-specified number of features, and hence may lead to less accurate results. In this paper, a tribe competition-based genetic algorithm (TCbGA) is proposed for feature selection in pattern classification. The population of individuals is divided into multiple tribes, and the initialization and evolutionary operations are modified to ensure that the number of selected features in each tribe follows a Gaussian distribution. Thus each tribe focuses on exploring a specific part of the solution space. Meanwhile, tribe competition is introduced to the evolution process, which allows the winning tribes, which produce better individuals, to enlarge their sizes, i.e. having more individuals to search their parts of the solution space. This algorithm, therefore, avoids the bias on solutions and requirement of a pre-specified number of features. We have evaluated our algorithm against several state-of-the-art feature selection approaches on 20 benchmark datasets. Our results suggest that the proposed TCbGA algorithm can identify the optimal feature subset more effectively and produce more accurate pattern classification.
Object Discovery via Cohesion Measurement
Venue: arXiv cs.CV 2017
Year: 2017

Color and intensity are two important components in an image. Usually, groups of image pixels, which are similar in color or intensity, are an informative representation for an object. They are therefore particularly suitable for computer vision tasks, such as saliency detection and object proposal generation. However, image pixels, which share a similar real-world color, may be quite different since colors are often distorted by intensity. In this paper, we reinvestigate the affinity matrices originally used in image segmentation methods based on spectral clustering. A new affinity matrix, which is robust to color distortions, is formulated for object discovery. Moreover, a Cohesion Measurement (CM) for object regions is also derived based on the formulated affinity matrix. Based on the new Cohesion Measurement, a novel object discovery method is proposed to discover objects latent in an image by utilizing the eigenvectors of the affinity matrix. Then we apply the proposed method to both saliency detection and object proposal generation. Experimental results on several evaluation benchmarks demonstrate that the proposed CM based method has achieved promising performance for these two tasks.
Expressing Facial Structure and Appearance Information in Frequency Domain for Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Beneath the uncertain primitive visual features of face images are the primitive intrinsic structural patterns (PISP) essential for characterizing a sample face discriminative attributes. It is on this basis that this paper presents a simple yet effective facial descriptor formed from derivatives of Gaussian and Gabor Wavelets. The new descriptor is coined local edge gradient Gabor magnitude (LEGGM) pattern. LEGGM first uncovers the PISP locked in every pixel through determining the pixel gradient in relation to its neighbors using the Derivatives of Gaussians. Then, the resulting output is embedded into the global appearance of the face which are further processed using Gabor wavelets in order to express its frequency characteristics. Additionally, we adopted various subspace models for dimensionality reduction in order to ascertain the best fit model for reporting a more effective representation of the LEGGM patterns. The proposed descriptor-based face recognition method is evaluated on three databases: Plastic surgery, LFW, and GT face databases. Through experiments, using a base classifier, the efficacy of the proposed method is demonstrated, especially in the case of plastic surgery database. The heterogeneous database, which we created to typify real-world scenario, show that the proposed method is to an extent insensitive to image formation factors with impressive recognition performances.
Design of robust two-dimensional polynomial beamformers as a convex optimization problem with application to robot audition
Venue: arXiv cs.SD 2017
Year: 2017

We propose a robust two-dimensional polynomial beamformer design method, formulated as a convex optimization problem, which allows for flexible steering of a previously proposed data-independent robust beamformer in both azimuth and elevation direction.~As an exemplary application, the proposed two-dimensional polynomial beamformer design is applied to a twelve-element microphone array, integrated into the head of a humanoid robot. To account for the effects of the robot's head on the sound field, measured head-related transfer functions are integrated into the optimization problem as steering vectors. The two-dimensional polynomial beamformer design is evaluated using signal-independent and signal-dependent measures. The results confirm that the proposed polynomial beamformer design approximates the original fixed beamformer design very accurately, which makes it an attractive approach for robust real-time data-independent beamforming.
EviPlant: An efficient digital forensic challenge creation, manipulation and distribution solution
Venue: arXiv cs.CR 2017
Year: 2017

Education and training in digital forensics requires a variety of suitable challenge corpora containing realistic features including regular wear-and-tear, background noise, and the actual digital traces to be discovered during investigation. Typically, the creation of these challenges requires overly arduous effort on the part of the educator to ensure their viability. Once created, the challenge image needs to be stored and distributed to a class for practical training. This storage and distribution step requires significant time and resources and may not even be possible in an online/distance learning scenario due to the data sizes involved. As part of this paper, we introduce a more capable methodology and system as an alternative to current approaches. EviPlant is a system designed for the efficient creation, manipulation, storage and distribution of challenges for digital forensics education and training. The system relies on the initial distribution of base disk images, i.e., images containing solely base operating systems. In order to create challenges for students, educators can boot the base system, emulate the desired activity and perform a "diffing" of resultant image and the base image. This diffing process extracts the modified artefacts and associated metadata and stores them in an "evidence package". Evidence packages can be created for different personae, different wear-and-tear, different emulated crimes, etc., and multiple evidence packages can be distributed to students and integrated into the base images. A number of additional applications in digital forensic challenge creation for tool testing and validation, proficiency testing, and malware analysis are also discussed as a result of using EviPlant.
Efficient Type Checking for Path Polymorphism
Venue: arXiv cs.LO 2017
Year: 2017

A type system combining type application, constants as types, union types (associative, commutative and idempotent) and recursive types has recently been proposed for statically typing path polymorphism, the ability to define functions that can operate uniformly over recursively specified applicative data structures. A typical pattern such functions resort to is $x\,y$ which decomposes a compound, in other words any applicative tree structure, into its parts. We study type-checking for this type system in two stages. First we propose algorithms for checking type equivalence and subtyping based on coinductive characterizations of those relations. We then formulate a syntax-directed presentation and prove its equivalence with the original one. This yields a type-checking algorithm which unfortunately has exponential time complexity in the worst case. A second algorithm is then proposed, based on automata techniques, which yields a polynomial-time type-checking algorithm.
Compressive Sensing Approaches for Autonomous Object Detection in Video Sequences
Venue: arXiv cs.CV 2017
Year: 2017

Video analytics requires operating with large amounts of data. Compressive sensing allows to reduce the number of measurements required to represent the video using the prior knowledge of sparsity of the original signal, but it imposes certain conditions on the design matrix. The Bayesian compressive sensing approach relaxes the limitations of the conventional approach using the probabilistic reasoning and allows to include different prior knowledge about the signal structure. This paper presents two Bayesian compressive sensing methods for autonomous object detection in a video sequence from a static camera. Their performance is compared on the real datasets with the non-Bayesian greedy algorithm. It is shown that the Bayesian methods can provide the same accuracy as the greedy algorithm but much faster; or if the computational time is not critical they can provide more accurate results.
Kiwi - A Minimalist CP Solver
Venue: arXiv cs.AI 2017
Year: 2017

Kiwi is a minimalist and extendable Constraint Programming (CP) solver specifically designed for education. The particularities of Kiwi stand in its generic trailing state restoration mechanism and its modulable use of variables. By developing Kiwi, the author does not aim to provide an alternative to full featured constraint solvers but rather to provide readers with a basic architecture that will (hopefully) help them to understand the core mechanisms hidden under the hood of constraint solvers, to develop their own extended constraint solver, or to test innovative ideas.