OpenRaiser/Intern-Atlas huggingface dataset:
Novelty-organizing team of classifiers in noisy and dynamic environments
Venue: arXiv cs.AI 2018
Year: 2018

In the real world, the environment is constantly changing with the input variables under the effect of noise. However, few algorithms were shown to be able to work under those circumstances. Here, Novelty-Organizing Team of Classifiers (NOTC) is applied to the continuous action mountain car as well as two variations of it: a noisy mountain car and an unstable weather mountain car. These problems take respectively noise and change of problem dynamics into account. Moreover, NOTC is compared with NeuroEvolution of Augmenting Topologies (NEAT) in these problems, revealing a trade-off between the approaches. While NOTC achieves the best performance in all of the problems, NEAT needs less trials to converge. It is demonstrated that NOTC achieves better performance because of its division of the input space (creating easier problems). Unfortunately, this division of input space also requires a bit of time to bootstrap.
Improved Bounds for the Traveling Salesman Problem with Neighborhoods on Uniform Disks
Venue: arXiv cs.CG 2018
Year: 2018

Given a set of $n$ disks of radius $R$ in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all of the disks. The problem is a generalization of the classical Traveling Salesman Problem(TSP) on points and has been widely studied in the literature. For the case of disjoint uniform disks of radius $R$, Dumitrescu and Mitchell[2001] show that the optimal TSP tour on the centers of the disks is a $3.547$-approximation to the TSPN version. The core of their analysis is based on bounding the detour that the optimal TSPN tour has to make in order to visit the centers of each disk and shows that it is at most $2Rn$ in the worst case. Häme, Hyytiä and Hakula[2011] asked whether this bound is tight when $R$ is small and conjectured that it is at most $\sqrt{3}Rn$. We further investigate this question and derive structural properties of the optimal TSPN tour to describe the cases in which the bound is smaller than $2Rn$. Specifically, we show that if the optimal TSPN tour is not a straight line, at least one of the following is guaranteed to be true: the bound is smaller than $1.999Rn$ or the $TSP$ on the centers is a $2$-approximation. The latter bound of $2$ is the best that we can get in general. Our framework is based on using the optimality of the TSPN tour to identify local structures for which the detour is large and then using their geometry to derive better lower bounds on the length of the TSPN tour. This leads to an improved approximation factor of $3.53$ for disjoint uniform disks and $6.728$ for the general case. We further show that the Häme, Hyytiä and Hakula conjecture is true for the case of three disks and discuss the method used to obtain it. Along the way, we will uncover one way in which the TSPN problem is structurally different from the classical TSP.
Parameter Synthesis Problems for one parametric clock Timed Automata
Venue: arXiv cs.FL 2018
Year: 2018

In this paper, we study the parameter synthesis problem for a class of parametric timed automata. The problem asks to construct the set of valuations of the parameters in the parametric timed automa- ton, referred to as the feasible region, under which the resulting timed automaton satisfies certain properties. We show that the parameter syn- thesis problem of parametric timed automata with only one parametric clock (unlimited concretely constrained clock) and arbitrarily many pa- rameters is solvable when all the expressions are linear expressions. And it is moreover the synthesis problem is solvable when the form of con- straints are parameter polynomial inequality not just simple constraint and parameter domain is nonnegative real number.
String Transduction with Target Language Models and Insertion Handling
Venue: arXiv cs.CL 2018
Year: 2018

Many character-level tasks can be framed as sequence-to-sequence transduction, where the target is a word from a natural language. We show that leveraging target language models derived from unannotated target corpora, combined with a precise alignment of the training data, yields state-of-the art results on cognate projection, inflection generation, and phoneme-to-grapheme conversion.
A Physical Perspective on Control Points and Polar Forms: Bézier Curves, Angular Momentum and Harmonic Oscillators
Venue: arXiv cs.CG 2018
Year: 2018

Bernstein polynomials and Bézier curves play an important role in computer-aided geometric design and numerical analysis, and their study relates to mathematical fields such as abstract algebra, algebraic geometry and probability theory. We describe a theoretical framework that incorporates the different aspects of the Bernstein-Bézier theory, based on concepts from theoretical physics. We relate Bézier curves to the theory of angular momentum in both classical and quantum mechanics, and describe physical analogues of various properties of Bézier curves -- such as their connection with polar forms -- in the context of quantum spin systems. This previously unexplored relationship between geometric design and theoretical physics is established using the mathematical theory of Hamiltonian mechanics and geometric quantization. An alternative description of spin systems in terms of harmonic oscillators serves as a physical analogue of Pólya's urn models for Bézier curves. We relate harmonic oscillators to Poisson curves and the analytical blossom as well. We present an overview of the relevant mathematical and physical concepts, and discuss opportunities for further research.
Revisit of the Eigenfilter Method for the Design of FIR Filters and Wideband Beamformers
Venue: arXiv cs.IT 2018
Year: 2018

The least squares based eigenfilter method has been applied to the design of both finite impulse response (FIR) filters and wideband beamformers successfully. It involves calculating the resultant filter coefficients as the eigenvector of an appropriate Hermitian matrix, and offers lower complexity and less computation time with better numerical stability as compared to the standard least squares method. In this paper, we revisit the method and critically analyze the eigenfilter method by revealing a serious performance issue in the passband of the designed FIR filter and the mainlobe of the wideband beamformer, which occurs due to a formulation problem. A solution is then proposed to mitigate this issue by imposing an additional constraint to control the response at the passband/mainlode, and design examples for both FIR filters and wideband beamformers are provided to demonstrate the effectiveness of the proposed method.
Analyzing Social Book Reading Behavior on Goodreads and how it predicts Amazon Best Sellers
Venue: arXiv cs.SI 2018
Year: 2018

A book's success/popularity depends on various parameters - extrinsic and intrinsic. In this paper, we study how the book reading characteristics might influence the popularity of a book. Towards this objective, we perform a cross-platform study of Goodreads entities and attempt to establish the connection between various Goodreads entities and the popular books ("Amazon best sellers"). We analyze the collective reading behavior on Goodreads platform and quantify various characteristic features of the Goodreads entities to identify differences between these Amazon best sellers (ABS) and the other non-best selling books. We then develop a prediction model using the characteristic features to predict if a book shall become a best seller after one month (15 days) since its publication. On a balanced set, we are able to achieve a very high average accuracy of 88.72% (85.66%) for the prediction where the other competitive class contains books which are randomly selected from the Goodreads dataset. Our method primarily based on features derived from user posts and genre related characteristic properties achieves an improvement of 16.4% over the traditional popularity factors (ratings, reviews) based baseline methods. We also evaluate our model with two more competitive set of books a) that are both highly rated and have received a large number of reviews (but are not best sellers) (HRHR) and b) Goodreads Choice Awards Nominated books which are non-best sellers (GCAN). We are able to achieve quite good results with very high average accuracy of 87.1% and as well a high ROC for ABS vs GCAN. For ABS vs HRHR, our model yields a high average accuracy of 86.22%.
Improved Bounds on Information Dissemination by Manhattan Random Waypoint Model
Venue: arXiv cs.MA 2018
Year: 2018

With the popularity of portable wireless devices it is important to model and predict how information or contagions spread by natural human mobility -- for understanding the spreading of deadly infectious diseases and for improving delay tolerant communication schemes. Formally, we model this problem by considering $M$ moving agents, where each agent initially carries a \emph{distinct} bit of information. When two agents are at the same location or in close proximity to one another, they share all their information with each other. We would like to know the time it takes until all bits of information reach all agents, called the \textit{flood time}, and how it depends on the way agents move, the size and shape of the network and the number of agents moving in the network. We provide rigorous analysis for the \MRWP model (which takes paths with minimum number of turns), a convenient model used previously to analyze mobile agents, and find that with high probability the flood time is bounded by $O\big(N\log M\lceil(N/M) \log(NM)\rceil\big)$, where $M$ agents move on an $N\times N$ grid. In addition to extensive simulations, we use a data set of taxi trajectories to show that our method can successfully predict flood times in both experimental settings and the real world.
Distances for WiFi Based Topological Indoor Mapping
Venue: arXiv cs.LG 2018
Year: 2018

For localization and mapping of indoor environments through WiFi signals, locations are often represented as likelihoods of the received signal strength indicator. In this work we compare various measures of distance between such likelihoods in combination with different methods for estimation and representation. In particular, we show that among the considered distance measures the Earth Mover's Distance seems the most beneficial for the localization task. Combined with kernel density estimation we were able to retain the topological structure of rooms in a real-world office scenario.
Exploiting Tournament Selection for Efficient Parallel Genetic Programming
Venue: arXiv cs.NE 2018
Year: 2018

Genetic Programming (GP) is a computationally intensive technique which is naturally parallel in nature. Consequently, many attempts have been made to improve its run-time from exploiting highly parallel hardware such as GPUs. However, a second methodology of improving the speed of GP is through efficiency techniques such as subtree caching. However achieving parallel performance and efficiency is a difficult task. This paper will demonstrate an efficiency saving for GP compatible with the harnessing of parallel CPU hardware by exploiting tournament selection. Significant efficiency savings are demonstrated whilst retaining the capability of a high performance parallel implementation of GP. Indeed, a 74% improvement in the speed of GP is achieved with a peak rate of 96 billion GPop/s for classification type problems.
Deep Part Induction from Articulated Object Pairs
Venue: arXiv cs.CV 2018
Year: 2018

Object functionality is often expressed through part articulation -- as when the two rigid parts of a scissor pivot against each other to perform the cutting function. Such articulations are often similar across objects within the same functional category. In this paper, we explore how the observation of different articulation states provides evidence for part structure and motion of 3D objects. Our method takes as input a pair of unsegmented shapes representing two different articulation states of two functionally related objects, and induces their common parts along with their underlying rigid motion. This is a challenging setting, as we assume no prior shape structure, no prior shape category information, no consistent shape orientation, the articulation states may belong to objects of different geometry, plus we allow inputs to be noisy and partial scans, or point clouds lifted from RGB images. Our method learns a neural network architecture with three modules that respectively propose correspondences, estimate 3D deformation flows, and perform segmentation. To achieve optimal performance, our architecture alternates between correspondence, deformation flow, and segmentation prediction iteratively in an ICP-like fashion. Our results demonstrate that our method significantly outperforms state-of-the-art techniques in the task of discovering articulated parts of objects. In addition, our part induction is object-class agnostic and successfully generalizes to new and unseen objects.
Towards Accountable AI: Hybrid Human-Machine Analyses for Characterizing System Failure
Venue: arXiv cs.LG 2018
Year: 2018

As machine learning systems move from computer-science laboratories into the open world, their accountability becomes a high priority problem. Accountability requires deep understanding of system behavior and its failures. Current evaluation methods such as single-score error metrics and confusion matrices provide aggregate views of system performance that hide important shortcomings. Understanding details about failures is important for identifying pathways for refinement, communicating the reliability of systems in different settings, and for specifying appropriate human oversight and engagement. Characterization of failures and shortcomings is particularly complex for systems composed of multiple machine learned components. For such systems, existing evaluation methods have limited expressiveness in describing and explaining the relationship among input content, the internal states of system components, and final output quality. We present Pandora, a set of hybrid human-machine methods and tools for describing and explaining system failures. Pandora leverages both human and system-generated observations to summarize conditions of system malfunction with respect to the input content and system architecture. We share results of a case study with a machine learning pipeline for image captioning that show how detailed performance views can be beneficial for analysis and debugging.
Deep Generative Classifiers for Thoracic Disease Diagnosis with Chest X-ray Images
Venue: arXiv cs.CV 2018
Year: 2018

Thoracic diseases are very serious health problems that plague a large number of people. Chest X-ray is currently one of the most popular methods to diagnose thoracic diseases, playing an important role in the healthcare workflow. However, reading the chest X-ray images and giving an accurate diagnosis remain challenging tasks for expert radiologists. With the success of deep learning in computer vision, a growing number of deep neural network architectures were applied to chest X-ray image classification. However, most of the previous deep neural network classifiers were based on deterministic architectures which are usually very noise-sensitive and are likely to aggravate the overfitting issue. In this paper, to make a deep architecture more robust to noise and to reduce overfitting, we propose using deep generative classifiers to automatically diagnose thorax diseases from the chest X-ray images. Unlike the traditional deterministic classifier, a deep generative classifier has a distribution middle layer in the deep neural network. A sampling layer then draws a random sample from the distribution layer and input it to the following layer for classification. The classifier is generative because the class label is generated from samples of a related distribution. Through training the model with a certain amount of randomness, the deep generative classifiers are expected to be robust to noise and can reduce overfitting and then achieve good performances. We implemented our deep generative classifiers based on a number of well-known deterministic neural network architectures, and tested our models on the chest X-ray14 dataset. The results demonstrated the superiority of deep generative classifiers compared with the corresponding deep deterministic classifiers.
Towards Discrete Solution: A Sparse Preserving Method for Correspondence Problem
Venue: arXiv cs.CV 2018
Year: 2018

Many problems of interest in computer vision can be formulated as a problem of finding consistent correspondences between two feature sets. Feature correspondence (matching) problem with one-to-one mapping constraint is usually formulated as an Integral Quadratic Programming (IQP) problem with permutation (or orthogonal) constraint. Since it is NP-hard, relaxation models are required. One main challenge for optimizing IQP matching problem is how to incorporate the discrete one-to-one mapping (permutation) constraint in its quadratic objective optimization. In this paper, we present a new relaxation model, called Sparse Constraint Preserving Matching (SPM), for IQP matching problem. SPM is motivated by our observation that the discrete permutation constraint can be well encoded via a sparse constraint. Comparing with traditional relaxation models, SPM can incorporate the discrete one-to-one mapping constraint straightly via a sparse constraint and thus provides a tighter relaxation for original IQP matching problem. A simple yet effective update algorithm has been derived to solve the proposed SPM model. Experimental results on several feature matching tasks demonstrate the effectiveness and efficiency of SPM method.
Layered BPSK for High Data Rates
Venue: arXiv cs.IT 2018
Year: 2018

This paper proposes a novel transmission strategy, referred to as layered BPSK, which allows two independent symbol streams to be layered at the transmitter on a non-orthogonal basis and isolated from each other at the receiver without inter-stream interference, aiming to achieve high data rates. To evaluate the performance of the proposed scheme, its data rate is formulated over additive white Gaussian noise (AWGN) channels. Based on the theoretical analysis, numerical results are provided for the performance comparisons between the proposed scheme and conventional transmission schemes, which substantiate the validity of the proposed scheme.
Towards practical key exchange from ordinary isogeny graphs
Venue: arXiv cs.CR 2018
Year: 2018

We revisit the ordinary isogeny-graph based cryptosystems of Couveignes and Rostovtsev-Stolbunov, long dismissed as impractical. We give algorithmic improvements that accelerate key exchange in this framework, and explore the problem of generating suitable system parameters for contemporary pre-and post-quantum security that take advantage of these new algorithms. We also prove the session-key security of this key exchange in the Canetti-Krawczyk model, and the IND-CPA security of the related public-key encryption scheme, under reasonable assumptions on the hardness of computing isogeny walks. Our systems admit efficient key-validation techniques that yield CCA-secure encryp-tion, thus providing an important step towards efficient post-quantum non-interactive key exchange (NIKE).
Assessing the quality of home detection from mobile phone data for official statistics
Venue: arXiv cs.CY 2018
Year: 2018

Mobile phone data are an interesting new data source for official statistics. However, multiple problems and uncertainties need to be solved before these data can inform, support or even become an integral part of statistical production processes. In this paper, we focus on arguably the most important problem hindering the application of mobile phone data in official statistics: detecting home locations. We argue that current efforts to detect home locations suffer from a blind deployment of criteria to define a place of residence and from limited validation possibilities. We support our argument by analysing the performance of five home detection algorithms (HDAs) that have been applied to a large, French, Call Detailed Record (CDR) dataset (~18 million users, 5 months). Our results show that criteria choice in HDAs influences the detection of home locations for up to about 40% of users, that HDAs perform poorly when compared with a validation dataset (the 35°-gap), and that their performance is sensitive to the time period and the duration of observation. Based on our findings and experiences, we offer several recommendations for official statistics. If adopted, our recommendations would help in ensuring a more reliable use of mobile phone data vis-à-vis official statistics.
Interactive Camera Network Design using a Virtual Reality Interface
Venue: arXiv cs.HC 2018
Year: 2018

Traditional literature on camera network design focuses on constructing automated algorithms. These require problem specific input from experts in order to produce their output. The nature of the required input is highly unintuitive leading to an unpractical workflow for human operators. In this work we focus on developing a virtual reality user interface allowing human operators to manually design camera networks in an intuitive manner. From real world practical examples we conclude that the camera networks designed using this interface are highly competitive with, or superior to those generated by automated algorithms, but the associated workflow is much more intuitive and simple. The competitiveness of the human-generated camera networks is remarkable because the structure of the optimization problem is a well known combinatorial NP-hard problem. These results indicate that human operators can be used in challenging geometrical combinatorial optimization problems given an intuitive visualization of the problem.
On constructing orthogonal generalized doubly stochastic matrices
Venue: arXiv cs.NA 2018
Year: 2018

A real quadratic matrix is generalized doubly stochastic (g.d.s.) if all of its row sums and column sums equal one. We propose numerically stable methods for generating such matrices having possibly orthogonality property or/and satisfying Yang-Baxter equation (YBE). Additionally, an inverse eigenvalue problem for finding orthogonal generalized doubly stochastic matrices with prescribed eigenvalues is solved here. The tests performed in \textsl{MATLAB} illustrate our proposed algorithms and demonstrate their useful numerical properties.
Deep HMResNet Model for Human Activity-Aware Robotic Systems
Venue: arXiv cs.RO 2018
Year: 2018

Endowing the robotic systems with cognitive capabilities for recognizing daily activities of humans is an important challenge, which requires sophisticated and novel approaches. Most of the proposed approaches explore pattern recognition techniques which are generally based on hand-crafted features or learned features. In this paper, a novel Hierarchal Multichannel Deep Residual Network (HMResNet) model is proposed for robotic systems to recognize daily human activities in the ambient environments. The introduced model is comprised of multilevel fusion layers. The proposed Multichannel 1D Deep Residual Network model is, at the features level, combined with a Bottleneck MLP neural network to automatically extract robust features regardless of the hardware configuration and, at the decision level, is fully connected with an MLP neural network to recognize daily human activities. Empirical experiments on real-world datasets and an online demonstration are used for validating the proposed model. Results demonstrated that the proposed model outperforms the baseline models in daily human activity recognition.