OpenRaiser/Intern-Atlas huggingface dataset:
Structured Differential Learning for Automatic Threshold Setting
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a technique that can automatically tune the parameters of a rule-based computer vision system comprised of thresholds, combinational logic, and time constants. This lets us retain the flexibility and perspicacity of a conventionally structured system while allowing us to perform approximate gradient descent using labeled data. While this is only a heuristic procedure, as far as we are aware there is no other efficient technique for tuning such systems. We describe the components of the system and the associated supervised learning mechanism. We also demonstrate the utility of the algorithm by comparing its performance versus hand tuning for an automotive headlight controller. Despite having over 100 parameters, the method is able to profitably adjust the system values given just the desired output for a number of videos.
How Does Tweet Difficulty Affect Labeling Performance of Annotators?
Venue: arXiv cs.HC 2018
Year: 2018

Crowdsourcing is a popular means to obtain labeled data at moderate costs, for example for tweets, which can then be used in text mining tasks. To alleviate the problem of low-quality labels in this context, multiple human factors have been analyzed to identify and deal with workers who provide such labels. However, one aspect that has been rarely considered is the inherent difficulty of tweets to be labeled and how this affects the reliability of the labels that annotators assign to such tweets. Therefore, we investigate in this preliminary study this connection using a hierarchical sentiment labeling task on Twitter. We find that there is indeed a relationship between both factors, assuming that annotators have labeled some tweets before: labels assigned to easy tweets are more reliable than those assigned to difficult tweets. Therefore, training predictors on easy tweets enhances the performance by up to 6% in our experiment. This implies potential improvements for active learning techniques and crowdsourcing.
Efficient Progressive Neural Architecture Search
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the difficult problem of finding an optimal neural architecture design for a given image classification task. We propose a method that aggregates two main results of the previous state-of-the-art in neural architecture search. These are, appealing to the strong sampling efficiency of a search scheme based on sequential model-based optimization (SMBO), and increasing training efficiency by sharing weights among sampled architectures. Sequential search has previously demonstrated its capabilities to find state-of-the-art neural architectures for image classification. However, its computational cost remains high, even unreachable under modest computational settings. Affording SMBO with weight-sharing alleviates this problem. On the other hand, progressive search with SMBO is inherently greedy, as it leverages a learned surrogate function to predict the validation error of neural architectures. This prediction is directly used to rank the sampled neural architectures. We propose to attenuate the greediness of the original SMBO method by relaxing the role of the surrogate function so it predicts architecture sampling probability instead. We demonstrate with experiments on the CIFAR-10 dataset that our method, denominated Efficient progressive neural architecture search (EPNAS), leads to increased search efficiency, while retaining competitiveness of found architectures.
Almost Envy Freeness and Welfare Efficiency in Fair Division with Goods or Bads
Venue: arXiv cs.GT 2018
Year: 2018

We consider two models of fair division with indivisible items: one for goods and one for bads. For goods, we study two generalized envy freeness proxies (EF1 and EFX for goods) and three common welfare (utilitarian, egalitarian and Nash) efficiency notions. For bads, we study two generalized envy freeness proxies (1EF and XEF for goods) and two less common diswelfare (egalitarian and Nash) efficiency notions. Some existing algorithms for goods do not work for bads. We thus propose several new algorithms for the model with bads. Our new algorithms exhibit many nice properties. For example, with additive identical valuations, an allocation that maximizes the egalitarian diswelfare or Nash diswelfare is XEF and PE. Finally, we also give simple and tractable cases when these envy freeness proxies and welfare efficiency are attainable in combination (e.g. binary valuations, house allocations).
Leveraging Knowledge Graph Embedding Techniques for Industry 4.0 Use Cases
Venue: arXiv cs.AI 2018
Year: 2018

Industry is evolving towards Industry 4.0, which holds the promise of increased flexibility in manufacturing, better quality and improved productivity. A core actor of this growth is using sensors, which must capture data that can used in unforeseen ways to achieve a performance not achievable without them. However, the complexity of this improved setting is much greater than what is currently used in practice. Hence, it is imperative that the management cannot only be performed by human labor force, but part of that will be done by automated algorithms instead. A natural way to represent the data generated by this large amount of sensors, which are not acting measuring independent variables, and the interaction of the different devices is by using a graph data model. Then, machine learning could be used to aid the Industry 4.0 system to, for example, perform predictive maintenance. However, machine learning directly on graphs, needs feature engineering and has scalability issues. In this paper we discuss methods to convert (embed) the graph in a vector space, such that it becomes feasible to use traditional machine learning methods for Industry 4.0 settings.
Code-Switching Detection with Data-Augmented Acoustic and Language Models
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we investigate the code-switching detection performance of a code-switching (CS) automatic speech recognition (ASR) system with data-augmented acoustic and language models. We focus on the recognition of Frisian-Dutch radio broadcasts where one of the mixed languages, namely Frisian, is under-resourced. Recently, we have explored how the acoustic modeling (AM) can benefit from monolingual speech data belonging to the high-resourced mixed language. For this purpose, we have trained state-of-the-art AMs on a significantly increased amount of CS speech by applying automatic transcription and monolingual Dutch speech. Moreover, we have improved the language model (LM) by creating CS text in various ways including text generation using recurrent LMs trained on existing CS text. Motivated by the significantly improved CS ASR performance, we delve into the CS detection performance of the same ASR system in this work by reporting CS detection accuracies together with a detailed detection error analysis.
Parameter estimation for optimal path planning in internal transportation
Venue: arXiv cs.SY 2018
Year: 2018

The costs incurred in a mobile robot (MR) change due to change in physical and environmental factors. Usually, there are two approaches to consider these costs, either explicitly modelling these different factors to calculate the cost or consider heuristics costs. First approach is lengthy and cumbersome and requires a new model for every new factor. Heuristics cost cannot account for the change in cost due to change in state. This work proposes a new method to compute these costs, without the need of explicitly modelling the factors. The identified cost is modelled in a bi-linear state-space form where the change of costs is formed due to the change of these states. This eliminates the need to model all factors to derive the cost for every robot. In context of transportation, the travel time is identified as the key parameter to understand costs of traversing paths to carry material. The necessity to identify and estimate these travel times is proved by using them in route planning. The paths are computed constantly and average of total path costs of these paths are compared with that of paths obtained by heuristics costs. The results show that average total path costs of paths obtained through on-line estimated travel times are 15\% less that of paths obtained by heuristics costs.
The impact of imbalanced training data on machine learning for author name disambiguation
Venue: arXiv cs.IR 2018
Year: 2018

In supervised machine learning for author name disambiguation, negative training data are often dominantly larger than positive training data. This paper examines how the ratios of negative to positive training data can affect the performance of machine learning algorithms to disambiguate author names in bibliographic records. On multiple labeled datasets, three classifiers - Logistic Regression, Naïve Bayes, and Random Forest - are trained through representative features such as coauthor names, and title words extracted from the same training data but with various positive-negative training data ratios. Results show that increasing negative training data can improve disambiguation performance but with a few percent of performance gains and sometimes degrade it. Logistic Regression and Naïve Bayes learn optimal disambiguation models even with a base ratio (1:1) of positive and negative training data. Also, the performance improvement by Random Forest tends to quickly saturate roughly after 1:10 ~ 1:15. These findings imply that contrary to the common practice using all training data, name disambiguation algorithms can be trained using part of negative training data without degrading much disambiguation performance while increasing computational efficiency. This study calls for more attention from author name disambiguation scholars to methods for machine learning from imbalanced data.
Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching
Venue: arXiv cs.CG 2018
Year: 2018

Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points have angular orientations in addition to their positions.
Improving IR-Based Bug Localization with Context-Aware Query Reformulation
Venue: arXiv cs.SE 2018
Year: 2018

Recent findings suggest that Information Retrieval (IR)-based bug localization techniques do not perform well if the bug report lacks rich structured information (eg relevant program entity names). Conversely, excessive structured information (eg stack traces) in the bug report might not always help the automated localization either. In this paper, we propose a novel technique--BLIZZARD-- that automatically localizes buggy entities from project source using appropriate query reformulation and effective information retrieval. In particular, our technique determines whether there are excessive program entities or not in a bug report (query), and then applies appropriate reformulations to the query for bug localization. Experiments using 5,139 bug reports show that our technique can localize the buggy source documents with 7%--56% higher Hit@10, 6%--62% higher MAP@10 and 6%--62% higher MRR@10 than the baseline technique. Comparison with the state-of-the-art techniques and their variants report that our technique can improve 19% in MAP@10 and 20% in MRR@10 over the state-of-the-art, and can improve 59% of the noisy queries and 39% of the poor queries.
Deep Learning for Radio Resource Allocation in Multi-Cell Networks
Venue: arXiv cs.NI 2018
Year: 2018

Increased complexity and heterogeneity of emerging 5G and beyond 5G (B5G) wireless networks will require a paradigm shift from traditional resource allocation mechanisms. Deep learning (DL) is a powerful tool where a multi-layer neural network can be trained to model a resource management algorithm using network data.Therefore, resource allocation decisions can be obtained without intensive online computations which would be required otherwise for the solution of resource allocation problems. In this context, this article focuses on the application of DL to obtain solutions for the radio resource allocation problems in multi-cell networks. Starting with a brief overview of a deep neural network (DNN) as a DL model, relevant DNN architectures and the data training procedure, we provide an overview of existing state-of-the-art applying DL in the context of radio resource allocation. A qualitative comparison is provided in terms of their objectives, inputs/outputs, learning and data training methods. Then, we present a supervised DL model to solve the sub-band and power allocation problem in a multi-cell network. Using the data generated by a genetic algorithm, we first train the model and then test the accuracy of the proposed model in predicting the resource allocation solutions. Simulation results show that the trained DL model is able to provide the desired optimal solution 86.3% of time.
Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

The problem called "String reconstruction from substrings" is a mathematical model of sequencing by hybridization that plays an important role in DNA sequencing. In this problem, we are given a blackbox oracle holding an unknown string ${\mathcal X}$ and are required to obtain (reconstruct) ${\mathcal X}$ through "substring queries" $Q(S)$. $Q(S)$ is given to the oracle with a string $S$ and the answer of the oracle is Yes if ${\mathcal X}$ includes $S$ as a substring and No otherwise. Our goal is to minimize the number of queries for the reconstruction. In this paper, we deal with only binary strings for ${\mathcal X}$ whose length $n$ is given in advance by using a sequence of good $S$'s. In 1995, Skiena and Sundaram first studied this problem and obtained an algorithm whose query complexity is $n+O(\log n)$. Its information theoretic lower bound is $n$, and they posed an obvious open question; if we can remove the $O(\log n)$ additive term. No progress has been made until now. This paper gives two partially positive answers to this open question. One is a randomized algorithm whose query complexity is $n+O(1)$ with high probability and the other is an average-case algorithm also having a query complexity of $n+O(1)$ on average. The $n$ lower bound is still true for both cases, and hence they are optimal up to an additive constant.
Weakly Supervised Localisation for Fetal Ultrasound Images
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the task of detecting and localising fetal anatomical regions in 2D ultrasound images, where only image-level labels are present at training, i.e. without any localisation or segmentation information. We examine the use of convolutional neural network architectures coupled with soft proposal layers. The resulting network simultaneously performs anatomical region detection (classification) and localisation tasks. We generate a proposal map describing the attention of the network for a particular class. The network is trained on 85,500 2D fetal Ultrasound images and their associated labels. Labels correspond to six anatomical regions: head, spine, thorax, abdomen, limbs, and placenta. Detection achieves an average accuracy of 90\% on individual regions, and show that the proposal maps correlate well with relevant anatomical structures. This work presents itself as a powerful and essential step towards subsequent tasks such as fetal position and pose estimation, organ-specific segmentation, or image-guided navigation. Code and additional material is available at https://ntoussaint.github.io/fetalnav
Energy-Efficient Multi-Cell Multigroup Multicasting with Joint Beamforming and Antenna Selection
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies the energy efficiency and sum rate trade-off for coordinated beamforming in multi-cell multi-user multigroup multicast multiple-input single-output systems. We first consider a conventional network energy efficiency maximization (EEmax) problem by jointly optimizing the transmit beamformers and antennas selected to be used in transmission. We also account for per-antenna maximum power constraints to avoid non-linear distortion in power amplifiers and user-specific minimum rate constraints to guarantee certain service levels and fairness. To be energy-efficient, transmit antenna selection is employed. It eventually leads to a mixed-Boolean fractional program. We then propose two different approaches to solve this difficult problem. The first solution is based on a novel modeling technique that produces a tight continuous relaxation. The second approach is based on sparsity-inducing method, which does not require the introduction of any Boolean variable. We also investigate the trade-off between the energy efficiency and sum rate by proposing two different formulations. In the first formulation, we propose a new metric that is the ratio of the sum rate and the so-called weighted power. Specifically, this metric reduces to EEmax when the weight is 1, and to sum rate maximization when the weight is 0. In the other method, we treat the trade-off problem as a multi-objective optimization for which a scalarization approach is adopted. Numerical results illustrate significant achievable energy efficiency gains over the method where the antenna selection is not employed. The effect of antenna selection on the energy efficiency and sum rate trade-off is also demonstrated.
Supervised classification for object identification in urban areas using satellite imagery
Venue: arXiv cs.LG 2018
Year: 2018

This paper presents a useful method to achieve classification in satellite imagery. The approach is based on pixel level study employing various features such as correlation, homogeneity, energy and contrast. In this study gray-scale images are used for training the classification model. For supervised classification, two classification techniques are employed namely the Support Vector Machine (SVM) and the Naive Bayes. With textural features used for gray-scale images, Naive Bayes performs better with an overall accuracy of 76% compared to 68% achieved by SVM. The computational time is evaluated while performing the experiment with two different window sizes i.e., 50x50 and 70x70. The required computational time on a single image is found to be 27 seconds for a window size of 70x70 and 45 seconds for a window size of 50x50.
Parallelization of the FFT on SO(3)
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, a work-optimal parallelization of Kostelec and Rockmore's well-known fast Fourier transform and its inverse on the three-dimensional rotation group SO(3) is designed, implemented, and tested. To this end, the sequential algorithms are reviewed briefly first. In the subsequent design and implementation of the parallel algorithms, we use the well-known Forster (PCAM) method and the OpenMP standard. The parallelization itself is based on symmetries of the underlying basis functions and a geometric approach in which the resulting index range is transformed in such a way that distinct work packages can be distributed efficiently to the computation nodes. The benefit of the parallel algorithms in practice is demonstrated in a speedup- and efficiency-assessing benchmark test on a system with 64 cores. Here, for the first time, we present positive results for the full transforms for the both accuracy- and memory-critical bandwidth 512. Using all 64 available cores, the speedup for the largest considered bandwidths 128, 256, and 512 amounted to 29.57, 36.86, and 34.36 in the forward, and 24.57, 26.69, and 24.25 in the inverse transform, respectively.
The Lyapunov Neural Network: Adaptive Stability Certification for Safe Learning of Dynamical Systems
Venue: arXiv cs.SY 2018
Year: 2018

Learning algorithms have shown considerable prowess in simulation by allowing robots to adapt to uncertain environments and improve their performance. However, such algorithms are rarely used in practice on safety-critical systems, since the learned policy typically does not yield any safety guarantees. That is, the required exploration may cause physical harm to the robot or its environment. In this paper, we present a method to learn accurate safety certificates for nonlinear, closed-loop dynamical systems. Specifically, we construct a neural network Lyapunov function and a training algorithm that adapts it to the shape of the largest safe region in the state space. The algorithm relies only on knowledge of inputs and outputs of the dynamics, rather than on any specific model structure. We demonstrate our method by learning the safe region of attraction for a simulated inverted pendulum. Furthermore, we discuss how our method can be used in safe learning algorithms together with statistical models of dynamical systems.
Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools
Venue: arXiv cs.DS 2018
Year: 2018

This dissertation focuses on two fundamental sorting problems: string sorting and suffix sorting. The first part considers parallel string sorting on shared-memory multi-core machines, the second part external memory suffix sorting using the induced sorting principle, and the third part distributed external memory suffix sorting with a new distributed algorithmic big data framework named Thrill.
Systematic Testing of Genetic Algorithms: A Metamorphic Testing based Approach
Venue: arXiv cs.SE 2018
Year: 2018

Genetic Algorithms are a popular set of optimization algorithms often used to aid software testing. However, no work has been done to apply systematic software testing techniques to genetic algorithms because of the stochasticity and the lack of known outputs for genetic algorithms. Statistical metamorphic testing is a useful technique for testing programs when the output is unknown or when the program has random elements. In this paper, we identify 17 metamorphic relations for testing a genetic algorithm and show, through mutation testing, that these relations are more effective at finding defects than traditional unit tests based on known outputs. We examined the failure rates of the system-level relations when initialized with various fitness functions. We found three relations failed excessively and we then modified these relations so that they failed less often. We also identified some metamorphic relations for genetic algorithms that are generalizable across different types of evolutionary algorithms and showed that our relations had similar mutation scores between two implementations. This is the first time statistical metamorphic testing has been applied for testing genetic algorithms.
On profitability of stubborn mining
Venue: arXiv cs.CR 2018
Year: 2018

We compute and compare profitabilities of stubborn mining strategies that are variations of selfish mining. These are deviant mining strategies violating Bitcoin's network protocol rules. We apply the foundational set-up from our previous companion article on the profitability of selfish mining, and the new martingale techniques to get a closed-form computation for the revenue ratio, which is the correct benchmark for profitability. Catalan numbers and Catalan distributions appear in the closed-form computations. This marks the first appearance of Catalan numbers in the Mathematics of the Bitcoin protocol.
The Complexity of Sequential Routing Games
Venue: arXiv cs.GT 2018
Year: 2018

We study routing games where every agent sequentially decides her next edge when she obtains the green light at each vertex. Because every edge only has capacity to let out one agent per round, an edge acts as a FIFO waiting queue that causes congestion on agents who enter. Given $n$ agents over $|V|$ vertices, we show that for one agent, approximating a winning strategy within $n^{1-\varepsilon}$ of the optimum for any $\varepsilon>0$, or within any polynomial of $|V|$, are PSPACE-hard. Under perfect information, computing a subgame perfect equilibrium (SPE) is PSPACE-hard and in FPSPACE. Under imperfect information, deciding SPE existence is PSPACE-complete.