OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Agent Game Abstraction via Graph Attention Neural Network
Venue: arXiv cs.AI 2019
Year: 2019

In large-scale multi-agent systems, the large number of agents and complex game relationship cause great difficulty for policy learning. Therefore, simplifying the learning process is an important research issue. In many multi-agent systems, the interactions between agents often happen locally, which means that agents neither need to coordinate with all other agents nor need to coordinate with others all the time. Traditional methods attempt to use pre-defined rules to capture the interaction relationship between agents. However, the methods cannot be directly used in a large-scale environment due to the difficulty of transforming the complex interactions between agents into rules. In this paper, we model the relationship between agents by a complete graph and propose a novel game abstraction mechanism based on two-stage attention network (G2ANet), which can indicate whether there is an interaction between two agents and the importance of the interaction. We integrate this detection mechanism into graph neural network-based multi-agent reinforcement learning for conducting game abstraction and propose two novel learning algorithms GA-Comm and GA-AC. We conduct experiments in Traffic Junction and Predator-Prey. The results indicate that the proposed methods can simplify the learning process and meanwhile get better asymptotic performance compared with state-of-the-art algorithms.
Faster Privacy-Preserving Computation of Edit Distance with Moves
Venue: arXiv cs.CR 2019
Year: 2019

We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings $x$ and $y$, respectively, want to jointly compute an approximate value for $\mathrm{EDM}(x,y)$, the minimum number of edit operations including substring moves needed to transform $x$ into $y$, without revealing any private information. Recently, the first secure two-party protocol for this was proposed, based on homomorphic encryption, but this approach is not suitable for long strings due to its high communication and round complexities. In this paper, we propose an improved algorithm that significantly reduces the round complexity without sacrificing its cryptographic strength. We examine the performance of our algorithm for DNA sequences compared to previous one.
A Causal Inference Method for Reducing Gender Bias in Word Embedding Relations
Venue: arXiv cs.CL 2019
Year: 2019

Word embedding has become essential for natural language processing as it boosts empirical performances of various tasks. However, recent research discovers that gender bias is incorporated in neural word embeddings, and downstream tasks that rely on these biased word vectors also produce gender-biased results. While some word-embedding gender-debiasing methods have been developed, these methods mainly focus on reducing gender bias associated with gender direction and fail to reduce the gender bias presented in word embedding relations. In this paper, we design a causal and simple approach for mitigating gender bias in word vector relation by utilizing the statistical dependency between gender-definition word embeddings and gender-biased word embeddings. Our method attains state-of-the-art results on gender-debiasing tasks, lexical- and sentence-level evaluation tasks, and downstream coreference resolution tasks.
Detecting Unknown Behaviors by Pre-defined Behaviours: An Bayesian Non-parametric Approach
Venue: arXiv cs.CY 2019
Year: 2019

An automatic mouse behavior recognition system can considerably reduce the workload of experimenters and facilitate the analysis process. Typically, supervised approaches, unsupervised approaches and semi-supervised approaches are applied for behavior recognition purpose under a setting which has all of predefined behaviors. In the real situation, however, as mouses can show various types of behaviors, besides the predefined behaviors that we want to analyze, there are many undefined behaviors existing. Both supervised approaches and conventional semi-supervised approaches cannot identify these undefined behaviors. Though unsupervised approaches can detect these undefined behaviors, a post-hoc labeling is needed. In this paper, we propose a semi-supervised infinite Gaussian mixture model (SsIGMM), to incorporate both labeled and unlabelled information in learning process while considering undefined behaviors. It also generates the distribution of the predefined and undefined behaviors by mixture Gaussians, which can be used for further analysis. In our experiments, we confirmed the superiority of SsIGMM for segmenting and labelling mouse-behavior videos.
Coloring outerplanar graphs and planar 3-trees with small monochromatic components
Venue: arXiv cs.DS 2019
Year: 2019

In this work, we continue the study of vertex colorings of graphs, in which adjacent vertices are allowed to be of the same color as long as each monochromatic connected component is of relatively small cardinality. We focus on colorings with two and three available colors and present improved bounds on the size of the monochromatic connected components for two meaningful subclasses of planar graphs, namely maximal outerplanar graphs and complete planar 3-trees.
State Alignment-based Imitation Learning
Venue: arXiv cs.LG 2019
Year: 2019

Consider an imitation learning problem that the imitator and the expert have different dynamics models. Most of the current imitation learning methods fail because they focus on imitating actions. We propose a novel state alignment-based imitation learning method to train the imitator to follow the state sequences in expert demonstrations as much as possible. The state alignment comes from both local and global perspectives and we combine them into a reinforcement learning framework by a regularized policy update objective. We show the superiority of our method on standard imitation learning settings and imitation learning settings where the expert and imitator have different dynamics models.
FLATM: A Fuzzy Logic Approach Topic Model for Medical Documents
Venue: arXiv cs.IR 2019
Year: 2019

One of the challenges for text analysis in medical domains is analyzing large-scale medical documents. As a consequence, finding relevant documents has become more difficult. One of the popular methods to retrieve information based on discovering the themes in the documents is topic modeling. The themes in the documents help to retrieve documents on the same topic with and without a query. In this paper, we present a novel approach to topic modeling using fuzzy clustering. To evaluate our model, we experiment with two text datasets of medical documents. The evaluation metrics carried out through document classification and document modeling show that our model produces better performance than LDA, indicating that fuzzy set theory can improve the performance of topic models in medical domains.
Greedy Algorithms for Fair Division of Mixed Manna
Venue: arXiv cs.AI 2019
Year: 2019

We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for bundles of items. For this model, we give several general impossibility results and special possibility results for three common fairness concepts (i.e. EF1, EFX, EFX3) and one popular efficiency concept (i.e. PO). We also study how these interact with common welfare objectives such as the Nash, disutility Nash and egalitarian welfares. For example, we show that maximizing the Nash welfare with mixed manna (or minimizing the disutility Nash welfare) does not ensure an EF1 allocation whereas with goods and the Nash welfare it does. We also prove that an EFX3 allocation may not exist even with identical utilities. By comparison, with tertiary utilities, EFX and PO allocations, or EFX3 and PO allocations always exist. Also, with identical utilities, EFX and PO allocations always exist. For these cases, we give polynomial-time algorithms, returning such allocations and approximating further the Nash, disutility Nash and egalitarian welfares in special cases.
Korean-to-Chinese Machine Translation using Chinese Character as Pivot Clue
Venue: arXiv cs.CL 2019
Year: 2019

Korean-Chinese is a low resource language pair, but Korean and Chinese have a lot in common in terms of vocabulary. Sino-Korean words, which can be converted into corresponding Chinese characters, account for more than fifty of the entire Korean vocabulary. Motivated by this, we propose a simple linguistically motivated solution to improve the performance of the Korean-to-Chinese neural machine translation model by using their common vocabulary. We adopt Chinese characters as a translation pivot by converting Sino-Korean words in Korean sentences to Chinese characters and then train the machine translation model with the converted Korean sentences as source sentences. The experimental results on Korean-to-Chinese translation demonstrate that the models with the proposed method improve translation quality up to 1.5 BLEU points in comparison to the baseline models.
An End-to-End Framework for Cold Question Routing in Community Question Answering Services
Venue: arXiv cs.IR 2019
Year: 2019

Routing newly posted questions (a.k.a cold questions) to potential answerers with the suitable expertise in Community Question Answering sites (CQAs) is an important and challenging task. The existing methods either focus only on embedding the graph structural information and are less effective for newly posted questions, or adopt manually engineered feature vectors that are not as representative as the graph embedding methods. Therefore, we propose to address the challenge of leveraging heterogeneous graph and textual information for cold question routing by designing an end-to-end framework that jointly learns CQA node embeddings and finds best answerers for cold questions. We conducted extensive experiments to confirm the usefulness of incorporating the textual information from question tags and demonstrate that an end-2-end framework can achieve promising performances on routing newly posted questions asked by both existing users and newly registered users.
A Coefficient of Determination for Probabilistic Topic Models
Venue: arXiv cs.IR 2019
Year: 2019

This research proposes a new (old) metric for evaluating goodness of fit in topic models, the coefficient of determination, or $R^2$. Within the context of topic modeling, $R^2$ has the same interpretation that it does when used in a broader class of statistical models. Reporting $R^2$ with topic models addresses two current problems in topic modeling: a lack of standard cross-contextual evaluation metrics for topic modeling and ease of communication with lay audiences. The author proposes that $R^2$ should be reported as a standard metric when constructing topic models.
Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
Venue: arXiv cs.LG 2019
Year: 2019

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.
Radius Adaptive Convolutional Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural network (CNN) is widely used in computer vision applications. In the networks that deal with images, CNNs are the most time-consuming layer of the networks. Usually, the solution to address the computation cost is to decrease the number of trainable parameters. This solution usually comes with the cost of dropping the accuracy. Another problem with this technique is that usually the cost of memory access is not taken into account which results in insignificant speedup gain. The number of operations and memory access in a standard convolution layer is independent of the input content, which makes it limited for certain accelerations. We propose a simple modification to a standard convolution to bridge this gap. We propose an adaptive convolution that adopts different kernel sizes (or radii) based on the content. The network can learn and select the proper radius based on the input content in a soft decision manner. Our proposed radius-adaptive convolutional neural network (RACNN) has a similar number of weights to a standard one, yet, results show it can reach higher speeds. The code has been made available at: https://github.com/meisamrf/racnn.
Stit Semantics for Epistemic Notions Based on Information Disclosure in Interactive Settings
Venue: arXiv cs.LO 2019
Year: 2019

We characterize four types of agentive knowledge using a stit semantics over branching discrete-time structures. These are \emph{ex ante} knowledge, \emph{ex interim} knowledge, \emph{ex post} knowledge, and know-how. The first three are notions that arose from game-theoretical analyses on the stages of information disclosure across the decision making process, and the fourth has gained prominence both in logics of action and in deontic logic as a means to formalize ability. In recent years, logicians in AI have argued that any comprehensive study of responsibility attribution and blameworthiness should include proper treatment of these kinds of knowledge. This paper intends to clarify previous attempts to formalize them in stit logic and to propose alternative interpretations that in our opinion are more akin to the study of responsibility in the stit tradition. The logic we present uses an extension with knowledge operators of the Xstit language, and formulas are evaluated with respect to branching discrete-time models. We also present an axiomatic system for this logic, and address its soundness and completeness.
Polyhedral study of the Convex Recoloring problem
Venue: arXiv cs.DM 2019
Year: 2019

A coloring of the vertices of a connected graph is convex if each color class induces a connected subgraph. We address the convex recoloring (CR) problem defined as follows. Given a graph $G$ and a coloring of its vertices, recolor a minimum number of vertices of $G$ so that the resulting coloring is convex. This problem, known to be NP-hard even on paths, was firstly motivated by applications on perfect phylogenies. In this work, we study CR on general graphs from a polyhedral point of view. First, we introduce a full-dimensional polytope based on the idea of connected subgraphs, and present a class of valid inequalities with righthand side one that comprises all facet-defining inequalities with binary coefficients when the input graph is a tree. Moreover, we define a general class of inequalities with righthand side in $\{1, \ldots, k\}$, where $k$ is the amount of colors used in the initial coloring, and show sufficient conditions for validity and facetness of such inequalities. Finally, we report on computational experiments for an application on mobile networks that can be modeled by the polytope of CR on paths. We evaluate the potential of the proposed inequalities to reduce the integrality gaps.
Efficient Global String Kernel with Random Features: Beyond Counting Substructures
Venue: arXiv cs.LG 2019
Year: 2019

Analysis of large-scale sequential data has been one of the most crucial tasks in areas such as bioinformatics, text, and audio mining. Existing string kernels, however, either (i) rely on local features of short substructures in the string, which hardly capture long discriminative patterns, (ii) sum over too many substructures, such as all possible subsequences, which leads to diagonal dominance of the kernel matrix, or (iii) rely on non-positive-definite similarity measures derived from the edit distance. Furthermore, while there have been works addressing the computational challenge with respect to the length of string, most of them still experience quadratic complexity in terms of the number of training samples when used in a kernel-based classifier. In this paper, we present a new class of global string kernels that aims to (i) discover global properties hidden in the strings through global alignments, (ii) maintain positive-definiteness of the kernel, without introducing a diagonal dominant kernel matrix, and (iii) have a training cost linear with respect to not only the length of the string but also the number of training string samples. To this end, the proposed kernels are explicitly defined through a series of different random feature maps, each corresponding to a distribution of random strings. We show that kernels defined this way are always positive-definite, and exhibit computational benefits as they always produce \emph{Random String Embeddings (RSE)} that can be directly used in any linear classification models. Our extensive experiments on nine benchmark datasets corroborate that RSE achieves better or comparable accuracy in comparison to state-of-the-art baselines, especially with the strings of longer lengths. In addition, we empirically show that RSE scales linearly with the increase of the number and the length of string.
Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays
Venue: arXiv cs.LG 2019
Year: 2019

We investigate the adversarial bandit problem with multiple plays under semi-bandit feedback. We introduce a highly efficient algorithm that asymptotically achieves the performance of the best switching $m$-arm strategy with minimax optimal regret bounds. To construct our algorithm, we introduce a new expert advice algorithm for the multiple-play setting. By using our expert advice algorithm, we additionally improve the best-known high-probability bound for the multi-play setting by $O(\sqrt{m})$. Our results are guaranteed to hold in an individual sequence manner since we have no statistical assumption on the bandit arm gains. Through an extensive set of experiments involving synthetic and real data, we demonstrate significant performance gains achieved by the proposed algorithm with respect to the state-of-the-art algorithms.
Self-Enhanced Convolutional Network for Facial Video Hallucination
Venue: arXiv cs.CV 2019
Year: 2019

As a domain-specific super-resolution problem, facial image hallucination has enjoyed a series of breakthroughs thanks to the advances of deep convolutional neural networks. However, the direct migration of existing methods to video is still difficult to achieve good performance due to its lack of alignment and consistency modelling in temporal domain. Taking advantage of high inter-frame dependency in videos, we propose a self-enhanced convolutional network for facial video hallucination. It is implemented by making full usage of preceding super-resolved frames and a temporal window of adjacent low-resolution frames. Specifically, the algorithm first obtains the initial high-resolution inference of each frame by taking into consideration a sequence of consecutive low-resolution inputs through temporal consistency modelling. It further recurrently exploits the reconstructed results and intermediate features of a sequence of preceding frames to improve the initial super-resolution of the current frame by modelling the coherence of structural facial features across frames. Quantitative and qualitative evaluations demonstrate the superiority of the proposed algorithm against state-of-the-art methods. Moreover, our algorithm also achieves excellent performance in the task of general video super-resolution in a single-shot setting.
Emotional Neural Language Generation Grounded in Situational Contexts
Venue: arXiv cs.CL 2019
Year: 2019

Emotional language generation is one of the keys to human-like artificial intelligence. Humans use different type of emotions depending on the situation of the conversation. Emotions also play an important role in mediating the engagement level with conversational partners. However, current conversational agents do not effectively account for emotional content in the language generation process. To address this problem, we develop a language modeling approach that generates affective content when the dialogue is situated in a given context. We use the recently released Empathetic-Dialogues corpus to build our models. Through detailed experiments, we find that our approach outperforms the state-of-the-art method on the perplexity metric by about 5 points and achieves a higher BLEU metric score.
My Approach = Your Apparatus? Entropy-Based Topic Modeling on Multiple Domain-Specific Text Collections
Venue: arXiv cs.IR 2019
Year: 2019

Comparative text mining extends from genre analysis and political bias detection to the revelation of cultural and geographic differences, through to the search for prior art across patents and scientific papers. These applications use cross-collection topic modeling for the exploration, clustering, and comparison of large sets of documents, such as digital libraries. However, topic modeling on documents from different collections is challenging because of domain-specific vocabulary. We present a cross-collection topic model combined with automatic domain term extraction and phrase segmentation. This model distinguishes collection-specific and collection-independent words based on information entropy and reveals commonalities and differences of multiple text collections. We evaluate our model on patents, scientific papers, newspaper articles, forum posts, and Wikipedia articles. In comparison to state-of-the-art cross-collection topic modeling, our model achieves up to 13% higher topic coherence, up to 4% lower perplexity, and up to 31% higher document classification accuracy. More importantly, our approach is the first topic model that ensures disjunct general and specific word distributions, resulting in clear-cut topic representations.