OpenRaiser/Intern-Atlas huggingface dataset:
Particle Competition and Cooperation for Semi-Supervised Learning with Label Noise
Venue: arXiv cs.LG 2020
Year: 2020

Semi-supervised learning methods are usually employed in the classification of data sets where only a small subset of the data items is labeled. In these scenarios, label noise is a crucial issue, since the noise may easily spread to a large portion or even the entire data set, leading to major degradation in classification accuracy. Therefore, the development of new techniques to reduce the nasty effects of label noise in semi-supervised learning is a vital issue. Recently, a graph-based semi-supervised learning approach based on Particle competition and cooperation was developed. In this model, particles walk in the graphs constructed from the data sets. Competition takes place among particles representing different class labels, while the cooperation occurs among particles with the same label. This paper presents a new particle competition and cooperation algorithm, specifically designed to increase the robustness to the presence of label noise, improving its label noise tolerance. Different from other methods, the proposed one does not require a separate technique to deal with label noise. It performs classification of unlabeled nodes and reclassification of the nodes affected by label noise in a unique process. Computer simulations show the classification accuracy of the proposed method when applied to some artificial and real-world data sets, in which we introduce increasing amounts of label noise. The classification accuracy is compared to those achieved by previous particle competition and cooperation algorithms and other representative graph-based semi-supervised learning methods using the same scenarios. Results show the effectiveness of the proposed method.
Scheduling Observers Over a Shared Channel with Hard Delivery Deadlines
Venue: arXiv cs.IT 2020
Year: 2020

We abstract the core logical functions from applications that require ultra-low-latency wireless communications to provide a novel definition for reliability. Real-time applications -- such as intelligent transportation, remote surgery, and industrial automation -- involve a significant element of control and decision making. Such systems involve three logical components: observers (e.g. sensors) measuring the state of an environment or dynamical system, a centralized executive (e.g. controller) deciding on the state, and agents (e.g. actuators) that implement the executive's decisions. The executive harvests the observers' measurements and decides on the short-term trajectory of the system by instructing its agents to take appropriate actions. All observation packets (typically uplink) and action packets (typically downlink) must be delivered by hard deadlines to ensure the proper functioning of the controlled system. In-full on-time delivery cannot be guaranteed in wireless systems due to inherent uncertainties in the channel such as fading and unpredictable interference; accordingly, the executive will have to drop some packets. We develop a novel framework to formulate the observer selection problem (OSP) through which the executive schedules a sequence of observations that maximize its knowledge about the current state of the system. To solve this problem efficiently yet optimally, we devise a branch-and-bound algorithm that systematically prunes the search space. Our work is different from existing work on real-time communications in that communication reliability is not conveyed by packet loss or error rate, but rather by the extent of the executive's knowledge about the state of the system it controls.
Understanding the Impact of Customer Reviews on Hotel Rating: An Empirical Research
Venue: arXiv cs.CY 2020
Year: 2020

The ascent of the Internet has caused numerous adjustments in our lives. The Internet has radically changed the manner in which we carry on with our lives, the manner in which we spend our occasions, how we speak with one another day by day, and how we buy items. The development of the Internet among users has created content on the Internet by sources, for example, web-based life, reviews site, online journals, item fan page and some more. This has a lead on to another method for arranging an occasion or searching for a reasonable hotel to remain. Thus, hotel review sites have turned into a famous stage for visitors to share their experiences, reviews, and suggestions on hotels, which they have visited. In Europe, the hotel business has been a standout amongst the most vital monetary developments of the nation. The essential objective of a hotel is to satisfy the customers, to have the capacity to give a high caliber of administration and give them a vital affair while remaining at the hotel. The motivation behind this examination is to comprehend and recognize the scope of elements, which may add as per the general inclination of customers and in addition through their reviews to decide the measures of customers' desires. Information was gathered from online review sites, for example, Booking.com. Text analytics is utilized to analyze the contents gathered.
Keyphrase Extraction with Span-based Feature Representations
Venue: arXiv cs.CL 2020
Year: 2020

Keyphrases are capable of providing semantic metadata characterizing documents and producing an overview of the content of a document. Since keyphrase extraction is able to facilitate the management, categorization, and retrieval of information, it has received much attention in recent years. There are three approaches to address keyphrase extraction: (i) traditional two-step ranking method, (ii) sequence labeling and (iii) generation using neural networks. Two-step ranking approach is based on feature engineering, which is labor intensive and domain dependent. Sequence labeling is not able to tackle overlapping phrases. Generation methods (i.e., Sequence-to-sequence neural network models) overcome those shortcomings, so they have been widely studied and gain state-of-the-art performance. However, generation methods can not utilize context information effectively. In this paper, we propose a novelty Span Keyphrase Extraction model that extracts span-based feature representation of keyphrase directly from all the content tokens. In this way, our model obtains representation for each keyphrase and further learns to capture the interaction between keyphrases in one document to get better ranking results. In addition, with the help of tokens, our model is able to extract overlapped keyphrases. Experimental results on the benchmark datasets show that our proposed model outperforms the existing methods by a large margin.
Internet of Smart-Cameras for Traffic Lights Optimization in Smart Cities
Venue: arXiv cs.MA 2020
Year: 2020

Smart and decentralized control systems have recently been proposed to handle the growing traffic congestion in urban cities. Proposed smart traffic light solutions based on Wireless Sensor Network and Vehicular Ad-hoc NETwork are either unreliable and inflexible or complex and costly. Furthermore, the handling of special vehicles such as emergency is still not viable, especially during busy hours. Inspired by the emergence of distributed smart cameras, we present a novel approach to traffic control at intersections. Our approach uses smart cameras at intersections along with image understanding for real-time traffic monitoring and assessment. Besides understanding the traffic flow, the cameras can detect and track special vehicles and help prioritize emergency cases. Traffic violations can be identified as well and traffic statistics collected. In this paper, we introduce a flexible, adaptive and distributed control algorithm that uses the information provided by distributed smart cameras to efficiently control traffic signals. Experimental results show that our collision-free approach outperforms the state-of-the-art of the average user's waiting time in the queue and improves the routing of emergency vehicles in a cross congestion area.
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
Venue: arXiv cs.CG 2020
Year: 2020

We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature $-1$. Let $α$ denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an $n^{O(\log^2 n)\max(1,1/α)}$ algorithm for Hyperbolic TSP. This is quasi-polynomial time if $α$ is at least some absolute constant, and it grows to $n^{O(\sqrt{n})}$ as $α$ decreases to $\log^2 n/\sqrt{n}$. (For even smaller values of $α$, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of $n^{O(\sqrt{n})}$.)
Comparison of Turkish Word Representations Trained on Different Morphological Forms
Venue: arXiv cs.CL 2020
Year: 2020

Increased popularity of different text representations has also brought many improvements in Natural Language Processing (NLP) tasks. Without need of supervised data, embeddings trained on large corpora provide us meaningful relations to be used on different NLP tasks. Even though training these vectors is relatively easy with recent methods, information gained from the data heavily depends on the structure of the corpus language. Since the popularly researched languages have a similar morphological structure, problems occurring for morphologically rich languages are mainly disregarded in studies. For morphologically rich languages, context-free word vectors ignore morphological structure of languages. In this study, we prepared texts in morphologically different forms in a morphologically rich language, Turkish, and compared the results on different intrinsic and extrinsic tasks. To see the effect of morphological structure, we trained word2vec model on texts which lemma and suffixes are treated differently. We also trained subword model fastText and compared the embeddings on word analogy, text classification, sentimental analysis, and language model tasks.
Genetic Algorithms for Redundancy in Interaction Testing
Venue: arXiv cs.NE 2020
Year: 2020

It is imperative for testing to determine if the components within large-scale software systems operate functionally. Interaction testing involves designing a suite of tests, which guarantees to detect a fault if one exists among a small number of components interacting together. The cost of this testing is typically modeled by the number of tests, and thus much effort has been taken in reducing this number. Here, we incorporate redundancy into the model, which allows for testing in non-deterministic environments. Existing algorithms for constructing these test suites usually involve one "fast" algorithm for generating most of the tests, and another "slower" algorithm to "complete" the test suite. We employ a genetic algorithm that generalizes these approaches that also incorporates redundancy by increasing the number of algorithms chosen, which we call "stages." By increasing the number of stages, we show that not only can the number of tests be reduced compared to existing techniques, but the computational time in generating them is also greatly reduced.
The PHOTON Wizard -- Towards Educational Machine Learning Code Generators
Venue: arXiv cs.SE 2020
Year: 2020

Despite the tremendous efforts to democratize machine learning, especially in applied-science, the application is still often hampered by the lack of coding skills. As we consider programmatic understanding key to building effective and efficient machine learning solutions, we argue for a novel educational approach that builds upon the accessibility and acceptance of graphical user interfaces to convey programming skills to an applied-science target group. We outline a proof-of-concept, open-source web application, the PHOTON Wizard, which dynamically translates GUI interactions into valid source code for the Python machine learning framework PHOTON. Thereby, users possessing theoretical machine learning knowledge gain key insights into the model development workflow as well as an intuitive understanding of custom implementations. Specifically, the PHOTON Wizard integrates the concept of Educational Machine Learning Code Generators to teach users how to write code for designing, training, optimizing and evaluating custom machine learning pipelines.
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Venue: arXiv cs.DS 2020
Year: 2020

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires $Ω\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $Ω\left(\frac{n}{K}\right)$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms when we only have a weak oracle with which we can only evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$, respectively, whose space complexity is exponential in $K$ but is independent of $n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of $n$.
Improving Generalization of Reinforcement Learning with Minimax Distributional Soft Actor-Critic
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning (RL) has achieved remarkable performance in numerous sequential decision making and control tasks. However, a common problem is that learned nearly optimal policy always overfits to the training environment and may not be extended to situations never encountered during training. For practical applications, the randomness of environment usually leads to some devastating events, which should be the focus of safety-critical systems such as autonomous driving. In this paper, we introduce the minimax formulation and distributional framework to improve the generalization ability of RL algorithms and develop the Minimax Distributional Soft Actor-Critic (Minimax DSAC) algorithm. Minimax formulation aims to seek optimal policy considering the most severe variations from environment, in which the protagonist policy maximizes action-value function while the adversary policy tries to minimize it. Distributional framework aims to learn a state-action return distribution, from which we can model the risk of different returns explicitly, thereby formulating a risk-averse protagonist policy and a risk-seeking adversarial policy. We implement our method on the decision-making tasks of autonomous vehicles at intersections and test the trained policy in distinct environments. Results demonstrate that our method can greatly improve the generalization ability of the protagonist agent to different environmental variations.
Algorithmic Complexity of Isolate Secure Domination in Graphs
Venue: arXiv cs.DM 2020
Year: 2020

A dominating set $S$ is an Isolate Dominating Set (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set $S\subseteq V$ is an isolate secure dominating set (ISDS), if for each vertex $u \in V \setminus S$, there exists a neighboring vertex $v$ of $u$ in $S$ such that $(S \setminus \{v\}) \cup \{u\}$ is an IDS of $G$. The minimum cardinality of an ISDS of $G$ is called as an isolate secure domination number, and is denoted by $γ_{0s}(G)$. Given a graph $ G=(V,E)$ and a positive integer $ k,$ the ISDM problem is to check whether $ G $ has an isolate secure dominating set of size at most $ k.$ We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.
Learning Halfspaces with Massart Noise Under Structured Distributions
Venue: arXiv cs.LG 2020
Year: 2020

We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for this problem with respect to a broad family of distributions, including log-concave distributions. This resolves an open question posed in a number of prior works. Our approach is extremely simple: We identify a smooth {\em non-convex} surrogate loss with the property that any approximate stationary point of this loss defines a halfspace that is close to the target halfspace. Given this structural result, we can use SGD to solve the underlying learning problem.
AGATHA: Automatic Graph-mining And Transformer based Hypothesis generation Approach
Venue: arXiv cs.LG 2020
Year: 2020

Medical research is risky and expensive. Drug discovery, as an example, requires that researchers efficiently winnow thousands of potential targets to a small candidate set for more thorough evaluation. However, research groups spend significant time and money to perform the experiments necessary to determine this candidate set long before seeing intermediate results. Hypothesis generation systems address this challenge by mining the wealth of publicly available scientific information to predict plausible research directions. We present AGATHA, a deep-learning hypothesis generation system that can introduce data-driven insights earlier in the discovery process. Through a learned ranking criteria, this system quickly prioritizes plausible term-pairs among entity sets, allowing us to recommend new research directions. We massively validate our system with a temporal holdout wherein we predict connections first introduced after 2015 using data published beforehand. We additionally explore biomedical sub-domains, and demonstrate AGATHA's predictive capacity across the twenty most popular relationship types. This system achieves best-in-class performance on an established benchmark, and demonstrates high recommendation scores across subdomains. Reproducibility: All code, experimental data, and pre-trained models are available online: sybrandt.com/2020/agatha
GANILLA: Generative Adversarial Networks for Image to Illustration Translation
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we explore illustrations in children's books as a new domain in unpaired image-to-image translation. We show that although the current state-of-the-art image-to-image translation models successfully transfer either the style or the content, they fail to transfer both at the same time. We propose a new generator network to address this issue and show that the resulting network strikes a better balance between style and content. There are no well-defined or agreed-upon evaluation metrics for unpaired image-to-image translation. So far, the success of image translation models has been based on subjective, qualitative visual comparison on a limited number of images. To address this problem, we propose a new framework for the quantitative evaluation of image-to-illustration models, where both content and style are taken into account using separate classifiers. In this new evaluation framework, our proposed model performs better than the current state-of-the-art models on the illustrations dataset. Our code and pretrained models can be found at https://github.com/giddyyupp/ganilla.
Ethics of Food Recommender Applications
Venue: arXiv cs.CY 2020
Year: 2020

The recent unprecedented popularity of food recommender applications has raised several issues related to the ethical, societal and legal implications of relying on these applications. In this paper, in order to assess the relevant ethical issues, we rely on the emerging principles across the AI\&Ethics community and define them tailored context specifically. Considering the popular Food Recommender Systems (henceforth F-RS) in the European market cannot be regarded as personalised F-RS, we show how merely this lack of feature shifts the relevance of the focal ethical concerns. We identify the major challenges and propose a scheme for how explicit ethical agendas should be explained. We also argue how a multi-stakeholder approach is indispensable to ensure producing long-term benefits for all stakeholders. After proposing eight ethical desiderata points for F-RS, we present a case-study and assess it based on our proposed desiderata points.
Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
Venue: arXiv cs.DS 2020
Year: 2020

Algorithms for dynamically maintaining minimum spanning trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optimal algorithms for dense graphs, all existing parallel batch-dynamic algorithms perform polynomial work per update in the worst case for sparse graphs. In this paper, we present the first work-efficient parallel batch-dynamic algorithm for incremental MST, which can insert $\ell$ edges in $O(\ell \log(1+n/\ell))$ work in expectation and $O(\text{polylog}(n))$ span w.h.p. The key ingredient of our algorithm is an algorithm for constructing a compressed path tree of an edge-weighted tree, which is a smaller tree that contains all pairwise heaviest edges between a given set of marked vertices. Using our batch-incremental MST algorithm, we demonstrate a range of applications that become efficiently solvable in parallel in the sliding-window model, such as graph connectivity, approximate MSTs, testing bipartiteness, $k$-certificates, cycle-freeness, and maintaining sparsifiers.