OpenRaiser/Intern-Atlas huggingface dataset:
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Venue: arXiv cs.DM 2019
Year: 2019

An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a graph $H$ and a graph $G$ of an infinite set of independent vertices. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some finite round there is a monochromatic copy of the graph $H$, otherwise Painter wins. The online Ramsey number $\widetilde{r}(H)$ is the minimum number of rounds such that Builder can force a monochromatic copy of $H$ in $G$. This is an analogy to the size-Ramsey number $\overline{r}(H)$ defined as the minimum number such that there exists graph $G$ with $\overline{r}(H)$ edges where for any edge two-coloring $G$ contains a monochromatic copy of $H$. In this paper, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number $\widetilde{r}_{ind}(H)$ is the minimum number of rounds Builder can force an induced monochromatic copy of $H$ in $G$. We prove asymptotically tight bounds on the induced online Ramsey numbers of paths, cycles and two families of trees. Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009], showing that there is an infinite family of trees $T_1,T_2,\dots$, $|T_i|<|T_{i+1}|$ for $i\ge1$, such that \[ \lim_{i\to\infty} \frac{\widetilde{r}(T_i)}{\overline{r}(T_i)} = 0. \]
Low-Power Neuromorphic Hardware for Signal Processing Applications
Venue: arXiv cs.ET 2019
Year: 2019

Machine learning has emerged as the dominant tool for implementing complex cognitive tasks that require supervised, unsupervised, and reinforcement learning. While the resulting machines have demonstrated in some cases even super-human performance, their energy consumption has often proved to be prohibitive in the absence of costly super-computers. Most state-of-the-art machine learning solutions are based on memory-less models of neurons. This is unlike the neurons in the human brain, which encode and process information using temporal information in spike events. The different computing principles underlying biological neurons and how they combine together to efficiently process information is believed to be a key factor behind their superior efficiency compared to current machine learning systems. Inspired by the time-encoding mechanism used by the brain, third generation spiking neural networks (SNNs) are being studied for building a new class of information processing engines. Modern computing systems based on the von Neumann architecture, however, are ill-suited for efficiently implementing SNNs, since their performance is limited by the need to constantly shuttle data between physically separated logic and memory units. Hence, novel computational architectures that address the von Neumann bottleneck are necessary in order to build systems that can implement SNNs with low energy budgets. In this paper, we review some of the architectural and system level design aspects involved in developing a new class of brain-inspired information processing engines that mimic the time-based information encoding and processing aspects of the brain.
Automated Rationale Generation: A Technique for Explainable AI and its Effects on Human Perceptions
Venue: arXiv cs.AI 2019
Year: 2019

Automated rationale generation is an approach for real-time explanation generation whereby a computational model learns to translate an autonomous agent's internal state and action data representations into natural language. Training on human explanation data can enable agents to learn to generate human-like explanations for their behavior. In this paper, using the context of an agent that plays Frogger, we describe (a) how to collect a corpus of explanations, (b) how to train a neural rationale generator to produce different styles of rationales, and (c) how people perceive these rationales. We conducted two user studies. The first study establishes the plausibility of each type of generated rationale and situates their user perceptions along the dimensions of confidence, humanlike-ness, adequate justification, and understandability. The second study further explores user preferences between the generated rationales with regard to confidence in the autonomous agent, communicating failure and unexpected behavior. Overall, we find alignment between the intended differences in features of the generated rationales and the perceived differences by users. Moreover, context permitting, participants preferred detailed rationales to form a stable mental model of the agent's behavior.
EQUATE: A Benchmark Evaluation Framework for Quantitative Reasoning in Natural Language Inference
Venue: arXiv cs.CL 2019
Year: 2019

Quantitative reasoning is a higher-order reasoning skill that any intelligent natural language understanding system can reasonably be expected to handle. We present EQUATE (Evaluating Quantitative Understanding Aptitude in Textual Entailment), a new framework for quantitative reasoning in textual entailment. We benchmark the performance of 9 published NLI models on EQUATE, and find that on average, state-of-the-art methods do not achieve an absolute improvement over a majority-class baseline, suggesting that they do not implicitly learn to reason with quantities. We establish a new baseline Q-REAS that manipulates quantities symbolically. In comparison to the best performing NLI model, it achieves success on numerical reasoning tests (+24.2%), but has limited verbal reasoning capabilities (-8.1%). We hope our evaluation framework will support the development of models of quantitative reasoning in language understanding.
Input Prioritization for Testing Neural Networks
Venue: arXiv cs.SE 2019
Year: 2019

Deep neural networks (DNNs) are increasingly being adopted for sensing and control functions in a variety of safety and mission-critical systems such as self-driving cars, autonomous air vehicles, medical diagnostics, and industrial robotics. Failures of such systems can lead to loss of life or property, which necessitates stringent verification and validation for providing high assurance. Though formal verification approaches are being investigated, testing remains the primary technique for assessing the dependability of such systems. Due to the nature of the tasks handled by DNNs, the cost of obtaining test oracle data---the expected output, a.k.a. label, for a given input---is high, which significantly impacts the amount and quality of testing that can be performed. Thus, prioritizing input data for testing DNNs in meaningful ways to reduce the cost of labeling can go a long way in increasing testing efficacy. This paper proposes using gauges of the DNN's sentiment derived from the computation performed by the model, as a means to identify inputs that are likely to reveal weaknesses. We empirically assessed the efficacy of three such sentiment measures for prioritization---confidence, uncertainty, and surprise---and compare their effectiveness in terms of their fault-revealing capability and retraining effectiveness. The results indicate that sentiment measures can effectively flag inputs that expose unacceptable DNN behavior. For MNIST models, the average percentage of inputs correctly flagged ranged from 88% to 94.8%.
ALiPy: Active Learning in Python
Venue: arXiv cs.LG 2019
Year: 2019

Supervised machine learning methods usually require a large set of labeled examples for model training. However, in many real applications, there are plentiful unlabeled data but limited labeled data; and the acquisition of labels is costly. Active learning (AL) reduces the labeling cost by iteratively selecting the most valuable data to query their labels from the annotator. This article introduces a Python toobox ALiPy for active learning. ALiPy provides a module based implementation of active learning framework, which allows users to conveniently evaluate, compare and analyze the performance of active learning methods. In the toolbox, multiple options are available for each component of the learning framework, including data process, active selection, label query, results visualization, etc. In addition to the implementations of more than 20 state-of-the-art active learning algorithms, ALiPy also supports users to easily configure and implement their own approaches under different active learning settings, such as AL for multi-label data, AL with noisy annotators, AL with different costs and so on. The toolbox is well-documented and open-source on Github, and can be easily installed through PyPI.
Summarization and Visualization of Large Volumes of Broadcast Video Data
Venue: arXiv cs.CV 2019
Year: 2019

Over the past few years, there has been an astounding growth in the number of news channels as well as the amount of broadcast news video data. As a result, it is imperative that automated methods need to be developed in order to effectively summarize and store this voluminous data. Format detection of news videos plays an important role in news video analysis. Our problem involves building a robust and versatile news format detector, which identifies the different band elements in a news frame. Probabilistic progressive Hough transform has been used for the detection of band edges. The detected bands are classified as natural images, computer generated graphics (non-text) and text bands. A contrast based text detector has been used to identify the text regions from news frames. Two classifers have been trained and evaluated for the labeling of the detected bands as natural or artificial - Support Vector Machine (SVM) Classifer with RBF kernel, and Extreme Learning Machine (ELM) classifier. The classifiers have been trained on a dataset of 6000 images (3000 images of each class). The ELM classifier reports a balanced accuracy of 77.38%, while the SVM classifier outperforms it with a balanced accuracy of 96.5% using 10-fold cross-validation. The detected bands which have been fragmented due to the presence of gradients in the image have been merged using a three-tier hierarchical reasoning model. The bands were detected with a Jaccard Index of 0.8138, when compared to manually marked ground truth data. We have also presented an extensive literature review of previous work done towards news videos format detection, element band classification, and associative reasoning.
Learning Accurate Extended-Horizon Predictions of High Dimensional Trajectories
Venue: arXiv cs.LG 2019
Year: 2019

We present a novel predictive model architecture based on the principles of predictive coding that enables open loop prediction of future observations over extended horizons. There are two key innovations. First, whereas current methods typically learn to make long-horizon open-loop predictions using a multi-step cost function, we instead run the model open loop in the forward pass during training. Second, current predictive coding models initialize the representation layer's hidden state to a constant value at the start of an episode, and consequently typically require multiple steps of interaction with the environment before the model begins to produce accurate predictions. Instead, we learn a mapping from the first observation in an episode to the hidden state, allowing the trained model to immediately produce accurate predictions. We compare the performance of our architecture to a standard predictive coding model and demonstrate the ability of the model to make accurate long horizon open-loop predictions of simulated Doppler radar altimeter readings during a six degree of freedom Mars landing. Finally, we demonstrate a 2X reduction in sample complexity by using the model to implement a Dyna style algorithm to accelerate policy learning with proximal policy optimization.
The Superior Knowledge Proximity Measure for Patent Mapping
Venue: arXiv cs.DL 2019
Year: 2019

Network maps of patent classes have been widely used to analyze the coherence and diversification of technology or knowledge positions of inventors, firms, industries, regions, and so on. To create such networks, a measure is required to associate different classes of patents in the patent database and often indicates knowledge proximity (or distance). Prior studies have used a variety of knowledge proximity measures based on different perspectives and association rules. It is unclear how to consistently assess and compare them, and which ones are superior for constructing a generally useful total patent class network. Such uncertainty has limited the generality and applications of the previously reported maps. Herein, we use a statistical method to identify the superior proximity measure from a comprehensive set of typical measures, by evaluating and comparing their explanatory powers on the historical expansions of the patent portfolios of individual inventors and organizations across different patent classes. Based on the complete United States granted patent database from 1976 to 2017, our analysis identifies a reference-based Jaccard index as the statistically superior measure, for explaining the historical diversifications and predicting future movement directions of both individual inventors and organizations across technology domains.
A Machine-Synesthetic Approach To DDoS Network Attack Detection
Venue: arXiv cs.CV 2019
Year: 2019

In the authors' opinion, anomaly detection systems, or ADS, seem to be the most perspective direction in the subject of attack detection, because these systems can detect, among others, the unknown (zero-day) attacks. To detect anomalies, the authors propose to use machine synesthesia. In this case, machine synesthesia is understood as an interface that allows using image classification algorithms in the problem of detecting network anomalies, making it possible to use non-specialized image detection methods that have recently been widely and actively developed. The proposed approach is that the network traffic data is "projected" into the image. It can be seen from the experimental results that the proposed method for detecting anomalies shows high results in the detection of attacks. On a large sample, the value of the complex efficiency indicator reaches 97%.
Modeling neural dynamics during speech production using a state space variational autoencoder
Venue: arXiv cs.NE 2019
Year: 2019

Characterizing the neural encoding of behavior remains a challenging task in many research areas due in part to complex and noisy spatiotemporal dynamics of evoked brain activity. An important aspect of modeling these neural encodings involves separation of robust, behaviorally relevant signals from background activity, which often contains signals from irrelevant brain processes and decaying information from previous behavioral events. To achieve this separation, we develop a two-branch State Space Variational AutoEncoder (SSVAE) model to individually describe the instantaneous evoked foreground signals and the context-dependent background signals. We modeled the spontaneous speech-evoked brain dynamics using smoothed Gaussian mixture models. By applying the proposed SSVAE model to track ECoG dynamics in one participant over multiple hours, we find that the model can predict speech-related dynamics more accurately than other latent factor inference algorithms. Our results demonstrate that separately modeling the instantaneous speech-evoked and slow context-dependent brain dynamics can enhance tracking performance, which has important implications for the development of advanced neural encoding and decoding models in various neuroscience sub-disciplines.
Gradient Regularized Budgeted Boosting
Venue: arXiv cs.LG 2019
Year: 2019

As machine learning transitions increasingly towards real world applications controlling the test-time cost of algorithms becomes more and more crucial. Recent work, such as the Greedy Miser and Speedboost, incorporate test-time budget constraints into the training procedure and learn classifiers that provably stay within budget (in expectation). However, so far, these algorithms are limited to the supervised learning scenario where sufficient amounts of labeled data are available. In this paper we investigate the common scenario where labeled data is scarce but unlabeled data is available in abundance. We propose an algorithm that leverages the unlabeled data (through Laplace smoothing) and learns classifiers with budget constraints. Our model, based on gradient boosted regression trees (GBRT), is, to our knowledge, the first algorithm for semi-supervised budgeted learning.
Image Based Review Text Generation with Emotional Guidance
Venue: arXiv cs.CL 2019
Year: 2019

In the current field of computer vision, automatically generating texts from given images has been a fully worked technique. Up till now, most works of this area focus on image content describing, namely image-captioning. However, rare researches focus on generating product review texts, which is ubiquitous in the online shopping malls and is crucial for online shopping selection and evaluation. Different from content describing, review texts include more subjective information of customers, which may bring difference to the results. Therefore, we aimed at a new field concerning generating review text from customers based on images together with the ratings of online shopping products, which appear as non-image attributes. We made several adjustments to the existing image-captioning model to fit our task, in which we should also take non-image features into consideration. We also did experiments based on our model and get effective primary results.
Distributed Monitoring of Topological Events via Homology
Venue: arXiv cs.DC 2019
Year: 2019

Topological event detection allows for the distributed computation of homology by focusing on local changes occurring in a network over time. In this paper, a model for the monitoring of topological events in dynamically changing regions will be developed. Regions are approximated as the connected components of the communication graph of a sensor network, reducing homology computation to graph homology. Betti number differences together with cyclic neighbor-rings are used to categorize topological event types. The focus lies on the correct detection of non-incremental (i.e., multiple concurrently occurring) events and the necessary region update process. Network number differences between a network's state before and after events are spread from event nodes into network regions, allowing for the conflict-free updating of regions independent of the update messages' order of arrival.
Learning Shared Semantic Space with Correlation Alignment for Cross-modal Event Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

In this paper, we propose to learn shared semantic space with correlation alignment (${S}^{3}CA$) for multimodal data representations, which aligns nonlinear correlations of multimodal data distributions in deep neural networks designed for heterogeneous data. In the context of cross-modal (event) retrieval, we design a neural network with convolutional layers and fully-connected layers to extract features for images, including images on Flickr-like social media. Simultaneously, we exploit a fully-connected neural network to extract semantic features for texts, including news articles from news media. In particular, nonlinear correlations of layer activations in the two neural networks are aligned with correlation alignment during the joint training of the networks. Furthermore, we project the multimodal data into a shared semantic space for cross-modal (event) retrieval, where the distances between heterogeneous data samples can be measured directly. In addition, we contribute a Wiki-Flickr Event dataset, where the multimodal data samples are not describing each other in pairs like the existing paired datasets, but all of them are describing semantic events. Extensive experiments conducted on both paired and unpaired datasets manifest the effectiveness of ${S}^{3}CA$, outperforming the state-of-the-art methods.
Ordinal Monte Carlo Tree Search
Venue: arXiv cs.AI 2019
Year: 2019

In many problem settings, most notably in game playing, an agent receives a possibly delayed reward for its actions. Often, those rewards are handcrafted and not naturally given. Even simple terminal-only rewards, like winning equals 1 and losing equals -1, can not be seen as an unbiased statement, since these values are chosen arbitrarily, and the behavior of the learner may change with different encodings, such as setting the value of a loss to -0:5, which is often done in practice to encourage learning. It is hard to argue about good rewards and the performance of an agent often depends on the design of the reward signal. In particular, in domains where states by nature only have an ordinal ranking and where meaningful distance information between game state values are not available, a numerical reward signal is necessarily biased. In this paper, we take a look at Monte Carlo Tree Search (MCTS), a popular algorithm to solve MDPs, highlight a reoccurring problem concerning its use of rewards, and show that an ordinal treatment of the rewards overcomes this problem. Using the General Video Game Playing framework we show a dominance of our newly proposed ordinal MCTS algorithm over preference-based MCTS, vanilla MCTS and various other MCTS variants.
Exploring Transfer Learning for Low Resource Emotional TTS
Venue: arXiv cs.SD 2019
Year: 2019

During the last few years, spoken language technologies have known a big improvement thanks to Deep Learning. However Deep Learning-based algorithms require amounts of data that are often difficult and costly to gather. Particularly, modeling the variability in speech of different speakers, different styles or different emotions with few data remains challenging. In this paper, we investigate how to leverage fine-tuning on a pre-trained Deep Learning-based TTS model to synthesize speech with a small dataset of another speaker. Then we investigate the possibility to adapt this model to have emotional TTS by fine-tuning the neutral TTS model with a small emotional dataset.
Trajectory Design for Cellular-Connected UAV Under Outage Duration Constraint
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study the trajectory design for a cellular-connected unmanned aerial vehicle (UAV) with given initial and final locations, while communicating with the ground base stations (GBSs) along its flight. We consider delay-limited communications between the UAV and its associated GBSs, where a given signal-to-noise ratio (SNR) target needs to be satisfied at the receiver. However, in practice, due to various factors such as quality-of-service (QoS) requirement, GBSs' availability and UAV mobility constraints, the SNR target may not be met at certain time periods during the flight, each termed as an outage duration. In this paper, we aim to optimize the UAV trajectory to minimize its mission completion time, subject to a constraint on the maximum tolerable outage duration in its flight. To tackle this non-convex problem, we first transform it into a more tractable form and thereby reveal some useful properties of the optimal trajectory solution. Based on these properties, we then further simplify the problem and propose efficient algorithms to check the feasibility of the problem as well as to obtain its optimal and high-quality suboptimal solutions, by leveraging graph theory and convex optimization techniques. Numerical results show that our proposed trajectory designs outperform the conventional method based on dynamic programming, in terms of both performance and complexity.
A lower bound on the tree-width of graphs with irrelevant vertices
Venue: arXiv cs.DM 2019
Year: 2019

For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there is a function $f$ such that if the tree-width of a graph $G$ with $k$ pairs of terminals is at least $f(k)$, then $G$ contains a solution-irrelevant vertex (Graph Minors. XXII., JCTB 2012). We give a single-exponential lower bound on $f$. This bound even holds for planar graphs.