OpenRaiser/Intern-Atlas huggingface dataset:
Predicting Effective Control Parameters for Differential Evolution using Cluster Analysis of Objective Function Features
Venue: arXiv cs.NE 2019
Year: 2019

A methodology is introduced which uses three simple objective function features to predict effective control parameters for differential evolution. This is achieved using cluster analysis techniques to classify objective functions using these features. Information on prior performance of various control parameters for each classification is then used to determine which control parameters to use in future optimisations. Our approach is compared to state-of-the-art adaptive and non-adaptive techniques. Two accepted bench mark suites are used to compare performance and in all cases we show that the improvement resulting from our approach is statistically significant. The majority of the computational effort of this methodology is performed off-line, however even when taking into account the additional on-line cost our approach outperforms other adaptive techniques. We also investigate the key tuning parameters of our methodology, such as number of clusters, which further support the finding that the simple features selected are predictors of effective control parameters. The findings presented in this paper are significant because they show that simple to calculate features of objective functions can help to select control parameters for optimisation algorithms. This can have an immediate positive impact on the application of these optimisation algorithms on real world problems, where it is often difficult to select effective control parameters.
Maximum Weight Independent Sets for ($S_{1,2,4}$,Triangle)-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2019
Year: 2019

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for $P_k$-free graphs, $k \ge 7$, is an open problem. In \cite{BraMos2018}, it is shown that MWIS can be solved in polynomial time for ($P_7$,triangle)-free graphs. This result is extended by Maffray and Pastor \cite{MafPas2016} showing that MWIS can be solved in polynomial time for ($P_7$,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for ($S_{1,2,3}$,bull)-free graphs. In this paper, using a similar approach as in \cite{BraMos2018}, we show that MWIS can be solved in polynomial time for ($S_{1,2,4}$,triangle)-free graphs which generalizes the result for ($P_7$,triangle)-free graphs.
Multi-agent Inverse Reinforcement Learning for Certain General-sum Stochastic Games
Venue: arXiv cs.LG 2019
Year: 2019

This paper addresses the problem of multi-agent inverse reinforcement learning (MIRL) in a two-player general-sum stochastic game framework. Five variants of MIRL are considered: uCS-MIRL, advE-MIRL, cooE-MIRL, uCE-MIRL, and uNE-MIRL, each distinguished by its solution concept. Problem uCS-MIRL is a cooperative game in which the agents employ cooperative strategies that aim to maximize the total game value. In problem uCE-MIRL, agents are assumed to follow strategies that constitute a correlated equilibrium while maximizing total game value. Problem uNE-MIRL is similar to uCE-MIRL in total game value maximization, but it is assumed that the agents are playing a Nash equilibrium. Problems advE-MIRL and cooE-MIRL assume agents are playing an adversarial equilibrium and a coordination equilibrium, respectively. We propose novel approaches to address these five problems under the assumption that the game observer either knows or is able to accurate estimate the policies and solution concepts for players. For uCS-MIRL, we first develop a characteristic set of solutions ensuring that the observed bi-policy is a uCS and then apply a Bayesian inverse learning method. For uCE-MIRL, we develop a linear programming problem subject to constraints that define necessary and sufficient conditions for the observed policies to be correlated equilibria. The objective is to choose a solution that not only minimizes the total game value difference between the observed bi-policy and a local uCS, but also maximizes the scale of the solution. We apply a similar treatment to the problem of uNE-MIRL. The remaining two problems can be solved efficiently by taking advantage of solution uniqueness and setting up a convex optimization problem. Results are validated on various benchmark grid-world games.
Autonomous Wireless Systems with Artificial Intelligence
Venue: arXiv cs.NI 2019
Year: 2019

This paper discusses technology and opportunities to embrace artificial intelligence (AI) in the design of autonomous wireless systems. We aim to provide readers with motivation and general AI methodology of autonomous agents in the context of self-organization in real time by unifying knowledge management with sensing, reasoning and active learning. We highlight differences between training-based methods for matching problems and training-free methods for environment-specific problems. Finally, we conceptually introduce the functions of an autonomous agent with knowledge management.
Efficient Deployment and Mission Timing of Autonomous Underwater Vehicles in Large-Scale Operations
Venue: arXiv cs.RO 2019
Year: 2019

This study introduces a connective model of routing -- local path planning for Autonomous Underwater Vehicle (AUV) time efficient maneuver in long-range operations. Assuming the vehicle operating in a turbulent underwater environment, the local path planner produces the water-current resilient shortest paths along the existent nodes in the global route. A re-routing procedure is defined to re-organize the order of nodes in a route and compensate any lost time during the mission. The Firefly Optimization Algorithm (FOA) is conducted by both of the planners to validate the model's performance in mission timing and its robustness against water current variations. Considering the limitation over the battery life time, the model offers an accurate mission timing and real-time performance. The routing system and the local path planner operate cooperatively, and this is another reason for model's real-time performance. The simulation results confirms the model's capability in fulfillment of the expected criterion and proves its significant robustness against underwater uncertainties and variations of the mission conditions.
Definable Inapproximability: New Challenges for Duplicator
Venue: arXiv cs.LO 2019
Year: 2019

We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances.
Counting to Explore and Generalize in Text-based Games
Venue: arXiv cs.CL 2019
Year: 2019

We propose a recurrent RL agent with an episodic exploration mechanism that helps discovering good policies in text-based game environments. We show promising results on a set of generated text-based games of varying difficulty where the goal is to collect a coin located at the end of a chain of rooms. In contrast to previous text-based RL approaches, we observe that our agent learns policies that generalize to unseen games of greater difficulty.
Modeling Mistrust in End-of-Life Care
Venue: arXiv cs.AI 2019
Year: 2019

In this work, we characterize the doctor-patient relationship using a machine learning-derived trust score. We show that this score has statistically significant racial associations, and that by modeling trust directly we find stronger disparities in care than by stratifying on race. We further demonstrate that mistrust is indicative of worse outcomes, but is only weakly associated with physiologically-created severity scores. Finally, we describe sentiment analysis experiments indicating patients with higher levels of mistrust have worse experiences and interactions with their caregivers. This work is a step towards measuring fairer machine learning in the healthcare domain.
Dynamic Prediction Length for Time Series with Sequence to Sequence Networks
Venue: arXiv cs.LG 2019
Year: 2019

Recurrent neural networks and sequence to sequence models require a predetermined length for prediction output length. Our model addresses this by allowing the network to predict a variable length output in inference. A new loss function with a tailored gradient computation is developed that trades off prediction accuracy and output length. The model utilizes a function to determine whether a particular output at a time should be evaluated or not given a predetermined threshold. We evaluate the model on the problem of predicting the prices of securities. We find that the model makes longer predictions for more stable securities and it naturally balances prediction accuracy and length.
Verifying Security Protocols using Dynamic Strategies
Venue: arXiv cs.CR 2019
Year: 2019

Current formal approaches have been successfully used to find design flaws in many security protocols. However, it is still challenging to automatically analyze protocols due to their large or infinite state spaces. In this paper, we propose a novel framework that can automatically verifying security protocols without any human intervention. Experimental results show that SmartVerif automatically verifies security protocols that cannot be automatically verified by existing approaches. The case study also validates the effectiveness of our dynamic strategy.
An approach based on the geometric mean of basic quantitative and qualitative bibliometric indicators to evaluate and analyse the research performance of countries and institutions
Venue: arXiv cs.DL 2019
Year: 2019

We present a straightforward procedure to evaluate the scientific contribution of territories and institutions that combines the size-dependent geometric mean, Q, of the number of research documents (N) and citations (C), and a scale-free measure of quality, q=C/N. We introduce a Global Research Output (GRO-index) as the geometric mean of Q and q. We show that the GRO-index correlates with the h-index, but appears to be more strongly correlated with other well known, widely used bibliometric indicators. We also compute relative GRO-indexes (GROr) associated with the scientific production within research fields. We note that although total sums of GROr values are larger than the GRO-index, due to the non-linearity in the computation of the geometric means, both counts are nevertheless highly correlated. That enables us to make useful comparative analyses among territories and institutions. Furthermore, to identify strengths and weaknesses of a given country or institution, we compute a Relative Research Output count (RROr-index) to tackle variations of the C/N ratio across research fields. Moreover, by using a wealth-index also based on quantitative and qualitative variables, we show that the GRO and RRO indexes are highly correlated with the wealth of the countries and the states of the USA. Given the simplicity of the procedures introduced in this paper and the fact that their results are easily understandable by non-specialists, we believe they could become as useful for the assessment of the research output of countries and institutions as the impact factor is for journals or the h-index for individuals.
A Semantics for Hybrid Iteration
Venue: arXiv cs.PL 2019
Year: 2019

The recently introduced notions of guarded traced (monoidal) category and guarded (pre-)iterative monad aim at unifying different instances of partial iteration whilst keeping in touch with the established theory of total iteration and preserving its merits. In this paper we use these notions and the corresponding stock of results to examine different types of iteration for hybrid computations. As a starting point we use an available notion of hybrid monad restricted to the category of sets, and modify it in order to obtain a suitable notion of guarded iteration with guardedness interpreted as progressiveness in time - we motivate this modification by our intention to capture Zeno behaviour in an arguably general and feasible way. We illustrate our results with a simple programming language for hybrid computations and interpret it over the developed semantic foundations.
One-Class Kernel Spectral Regression
Venue: arXiv cs.LG 2019
Year: 2019

The paper introduces a new efficient nonlinear one-class classifier formulated as the Rayleigh quotient criterion optimisation. The method, operating in a reproducing kernel Hilbert space, minimises the scatter of target distribution along an optimal projection direction while at the same time keeping projections of positive observations distant from the mean of the negative class. We provide a graph embedding view of the problem which can then be solved efficiently using the spectral regression approach. In this sense, unlike previous similar methods which often require costly eigen-computations of dense matrices, the proposed approach casts the problem under consideration into a regression framework which is computationally more efficient. In particular, it is shown that the dominant complexity of the proposed method is the complexity of computing the kernel matrix. Additional appealing characteristics of the proposed one-class classifier are: 1-the ability to be trained in an incremental fashion (allowing for application in streaming data scenarios while also reducing the computational complexity in a non-streaming operation mode); 2-being unsupervised, but providing the option for refining the solution using negative training examples, when available; And last but not the least, 3-the use of the kernel trick which facilitates a nonlinear mapping of the data into a high-dimensional feature space to seek better solutions.
The USA is an indisputable world leader in medical and biotechnological research
Venue: arXiv cs.DL 2019
Year: 2019

A country's research success can be assessed from the power law function that links country and world rank numbers when publications are ordered by their number of citations; a similar function describes the distribution of country papers in world percentiles. These functions allow calculating the ep index and the probability of publishing highly cited papers, which measure the efficiency of the research system and the ability of achieving important discoveries or scientific breakthroughs, respectively. The aim of this paper was to use these metrics and other parameters derived from the percentile-based power law function to investigate research success in the USA, the EU, and other countries in hot medical, biochemical, and biotechnological topics. The results show that, in the investigated fields, the USA is scientifically ahead of all countries and that its research is likely to produce approximately 80% of the important global breakthroughs in the research topics investigated in this study. EU research has maintained a constant weak position with reference to USA research over the last 30 years.
Training behavior of deep neural network in frequency domain
Venue: arXiv cs.LG 2019
Year: 2019

Why deep neural networks (DNNs) capable of overfitting often generalize well in practice is a mystery [#zhang2016understanding]. To find a potential mechanism, we focus on the study of implicit biases underlying the training process of DNNs. In this work, for both real and synthetic datasets, we empirically find that a DNN with common settings first quickly captures the dominant low-frequency components, and then relatively slowly captures the high-frequency ones. We call this phenomenon Frequency Principle (F-Principle). The F-Principle can be observed over DNNs of various structures, activation functions, and training algorithms in our experiments. We also illustrate how the F-Principle help understand the effect of early-stopping as well as the generalization of DNNs. This F-Principle potentially provides insights into a general principle underlying DNN optimization and generalization.
On the Computational Power of Online Gradient Descent
Venue: arXiv cs.LG 2019
Year: 2019

We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradient descent.
Quantum Random Self-Modifiable Computation
Venue: arXiv cs.CC 2019
Year: 2019

Among the fundamental questions in computer science, at least two have a deep impact on mathematics. What can computation compute? How many steps does a computation require to solve an instance of the 3-SAT problem? Our work addresses the first question, by introducing a new model called the ex-machine. The ex-machine executes Turing machine instructions and two special types of instructions. Quantum random instructions are physically realizable with a quantum random number generator. Meta instructions can add new states and add new instructions to the ex-machine. A countable set of ex-machines is constructed, each with a finite number of states and instructions; each ex-machine can compute a Turing incomputable language, whenever the quantum randomness measurements behave like unbiased Bernoulli trials. In 1936, Alan Turing posed the halting problem for Turing machines and proved that this problem is unsolvable for Turing machines. Consider an enumeration E_a(i) = (M_i, T_i) of all Turing machines M_i and initial tapes T_i. Does there exist an ex-machine X that has at least one evolutionary path X --> X_1 --> X_2 --> . . . --> X_m, so at the mth stage ex-machine X_m can correctly determine for 0 <= i <= m whether M_i's execution on tape T_i eventually halts? We demonstrate an ex-machine Q(x) that has one such evolutionary path. The existence of this evolutionary path suggests that David Hilbert was not misguided to propose in 1900 that mathematicians search for finite processes to help construct mathematical proofs. Our refinement is that we cannot use a fixed computer program that behaves according to a fixed set of mechanical rules. We must pursue methods that exploit randomness and self-modification so that the complexity of the program can increase as it computes.
Face-Cap: Image Captioning using Facial Expression Analysis
Venue: arXiv cs.CV 2019
Year: 2019

Image captioning is the process of generating a natural language description of an image. Most current image captioning models, however, do not take into account the emotional aspect of an image, which is very relevant to activities and interpersonal relationships represented therein. Towards developing a model that can produce human-like captions incorporating these, we use facial expression features extracted from images including human faces, with the aim of improving the descriptive ability of the model. In this work, we present two variants of our Face-Cap model, which embed facial expression features in different ways, to generate image captions. Using all standard evaluation metrics, our Face-Cap models outperform a state-of-the-art baseline model for generating image captions when applied to an image caption dataset extracted from the standard Flickr 30K dataset, consisting of around 11K images containing faces. An analysis of the captions finds that, perhaps surprisingly, the improvement in caption quality appears to come not from the addition of adjectives linked to emotional aspects of the images, but from more variety in the actions described in the captions.
EnTrans:Leveraging Kinetic Energy Harvesting Signal for Transportation Mode Detection
Venue: arXiv cs.HC 2019
Year: 2019

Monitoring the daily transportation modes of an individual provides useful information in many application domains, such as urban design, real-time journey recommendation, as well as providing location-based services. In existing systems, accelerometer and GPS are the dominantly used signal sources for transportation context monitoring which drain out the limited battery life of the wearable devices very quickly. To resolve the high energy consumption issue, in this paper, we present EnTrans, which enables transportation mode detection by using only the kinetic energy harvester as an energy-efficient signal source. The proposed idea is based on the intuition that the vibrations experienced by the passenger during traveling with different transportation modes are distinctive. Thus, voltage signal generated by the energy harvesting devices should contain sufficient features to distinguish different transportation modes. We evaluate our system using over 28 hours of data, which is collected by eight individuals using a practical energy harvesting prototype. The evaluation results demonstrate that EnTrans is able to achieve an overall accuracy over 92% in classifying five different modes while saving more than 34% of the system power compared to conventional accelerometer-based approaches.
Maximizing Welfare in Social Networks under a Utility Driven Influence Diffusion Model
Venue: arXiv cs.SI 2019
Year: 2019

Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for economic considerations of a user in buying/adopting items. (2) Most studies on multiple items focus on competition, with complementary items receiving limited attention. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature. In this paper, we address all three limitations and propose a novel model called UIC that combines utility-driven item adoption with influence propagation over networks. Focusing on the mutually complementary setting, we formulate the problem of social welfare maximization in this novel setting. We show that while the objective function is neither submodular nor supermodular, surprisingly a simple greedy allocation algorithm achieves a factor of $(1-1/e-ε)$ of the optimum expected social welfare. We develop \textsf{bundleGRD}, a scalable version of this approximation algorithm, and demonstrate, with comprehensive experiments on real and synthetic datasets, that it significantly outperforms all baselines.