OpenRaiser/Intern-Atlas huggingface dataset:
Recent progress on scaling algorithms and applications
Venue: arXiv cs.DS 2018
Year: 2018

Scaling problems have a rich and diverse history, and thereby have found numerous applications in several fields of science and engineering. For instance, the matrix scaling problem has had applications ranging from theoretical computer science to telephone forecasting, economics, statistics, optimization, among many other fields. Recently, a generalization of matrix scaling known as operator scaling has found applications in non-commutative algebra, invariant theory, combinatorics and algebraic complexity; and a further generalization (tensor scaling) has found more applications in quantum information theory, geometric complexity theory and invariant theory. In this survey, we will describe in detail the scaling problems mentioned above, showing how alternating minimization algorithms naturally arise in this setting, and we shall present a general framework to rigorously analyze such algorithms. These simple problems and algorithms are not just applicable to diverse mathematical and CS areas, but also serve to bring out deep connections between them. As this framework makes extensive use of concepts from invariant theory, we also provide a very gentle introduction to basic concepts of invariant theory and how they are used to analyze alternating minimization algorithms for the scaling problems. This survey is intended for a general computer science audience, and the only background required is basic knowledge of calculus and linear algebra, thereby making it accessible to graduate students and even to advanced undergraduates.
Characterizing the Influence of Features on Reading Difficulty Estimation for Non-native Readers
Venue: arXiv cs.CL 2018
Year: 2018

In recent years, the number of people studying English as a second language (ESL) has surpassed the number of native speakers. Recent work have demonstrated the success of providing personalized content based on reading difficulty, such as information retrieval and summarization. However, almost all prior studies of reading difficulty are designed for native speakers, rather than non-native readers. In this study, we investigate various features for ESL readers, by conducting a linear regression to estimate the reading level of English language sources. This estimation is based not only on the complexity of lexical and syntactic features, but also several novel concepts, including the age of word and grammar acquisition from several sources, word sense from WordNet, and the implicit relation between sentences. By employing Bayesian Information Criterion (BIC) to select the optimal model, we find that the combination of the number of words, the age of word acquisition and the height of the parsing tree generate better results than alternative competing models. Thus, our results show that proposed second language reading difficulty estimation outperforms other first language reading difficulty estimations.
MARL-FWC: Optimal Coordination of Freeway Traffic Control Measures
Venue: arXiv cs.SY 2018
Year: 2018

The objective of this article is to optimize the overall traffic flow on freeways using multiple ramp metering controls plus its complementary Dynamic Speed Limits (DSLs). An optimal freeway operation can be reached when minimizing the difference between the freeway density and the critical ratio for maximum traffic flow. In this article, a Multi-Agent Reinforcement Learning for Freeways Control (MARL-FWC) system for ramps metering and DSLs is proposed. MARL-FWC introduces a new microscopic framework at the network level based on collaborative Markov Decision Process modeling (Markov game) and an associated cooperative Q-learning algorithm. The technique incorporates payoff propagation (Max-Plus algorithm) under the coordination graphs framework, particularly suited for optimal control purposes. MARL-FWC provides three control designs: fully independent, fully distributed, and centralized; suited for different network architectures. MARL-FWC was extensively tested in order to assess the proposed model of the joint payoff, as well as the global payoff. Experiments are conducted with heavy traffic flow under the renowned VISSIM traffic simulator to evaluate MARL-FWC. The experimental results show a significant decrease in the total travel time and an increase in the average speed (when compared with the base case) while maintaining an optimal traffic flow.
Top-down Attention Recurrent VLAD Encoding for Action Recognition in Videos
Venue: arXiv cs.CV 2018
Year: 2018

Most recent approaches for action recognition from video leverage deep architectures to encode the video clip into a fixed length representation vector that is then used for classification. For this to be successful, the network must be capable of suppressing irrelevant scene background and extract the representation from the most discriminative part of the video. Our contribution builds on the observation that spatio-temporal patterns characterizing actions in videos are highly correlated with objects and their location in the video. We propose Top-down Attention Action VLAD (TA-VLAD), a deep recurrent architecture with built-in spatial attention that performs temporally aggregated VLAD encoding for action recognition from videos. We adopt a top-down approach of attention, by using class specific activation maps obtained from a deep CNN pre-trained for image classification, to weight appearance features before encoding them into a fixed-length video descriptor using Gated Recurrent Units. Our method achieves state of the art recognition accuracy on HMDB51 and UCF101 benchmarks.
Review Helpfulness Prediction with Embedding-Gated CNN
Venue: arXiv cs.CL 2018
Year: 2018

Product reviews, in the form of texts dominantly, significantly help consumers finalize their purchasing decisions. Thus, it is important for e-commerce companies to predict review helpfulness to present and recommend reviews in a more informative manner. In this work, we introduce a convolutional neural network model that is able to extract abstract features from multi-granularity representations. Inspired by the fact that different words contribute to the meaning of a sentence differently, we consider to learn word-level embedding-gates for all the representations. Furthermore, as it is common that some product domains/categories have rich user reviews, other domains not. To help domains with less sufficient data, we integrate our model into a cross-domain relationship learning framework for effectively transferring knowledge from other domains. Extensive experiments show that our model yields better performance than the existing methods.
MemComputing Integer Linear Programming
Venue: arXiv cs.ET 2018
Year: 2018

Integer linear programming (ILP) encompasses a very important class of optimization problems that are of great interest to both academia and industry. Several algorithms are available that attempt to explore the solution space of this class efficiently, while requiring a reasonable compute time. However, although these algorithms have reached various degrees of success over the years, they still face considerable challenges when confronted with particularly hard problem instances, such as those of the MIPLIB 2010 library. In this work we propose a radically different non-algorithmic approach to ILP based on a novel physics-inspired computing paradigm: Memcomputing. This paradigm is based on digital (hence scalable) machines represented by appropriate electrical circuits with memory. These machines can be either built in hardware or, as we do here, their equations of motion can be efficiently simulated on our traditional computers. We first describe a new circuit architecture of memcomputing machines specifically designed to solve for the linear inequalities representing a general ILP problem. We call these self-organizing algebraic circuits, since they self-organize dynamically to satisfy the correct (algebraic) linear inequalities. We then show simulations of these machines using MATLAB running on a single core of a Xeon processor for several ILP benchmark problems taken from the MIPLIB 2010 library, and compare our results against a renowned commercial solver. We show that our approach is very efficient when dealing with these hard problems. In particular, we find within minutes feasible solutions for one of these hard problems (f2000 from MIPLIB 2010) whose feasibility, to the best of our knowledge, has remained unknown for the past eight years.
Artifacts Detection and Error Block Analysis from Broadcasted Videos
Venue: arXiv cs.CV 2018
Year: 2018

With the advancement of IPTV and HDTV technology, previous subtle errors in videos are now becoming more prominent because of the structure oriented and compression based artifacts. In this paper, we focus towards the development of a real-time video quality check system. Light weighted edge gradient magnitude information is incorporated to acquire the statistical information and the distorted frames are then estimated based on the characteristics of their surrounding frames. Then we apply the prominent texture patterns to classify them in different block errors and analyze them not only in video error detection application but also in error concealment, restoration and retrieval. Finally, evaluating the performance through experiments on prominent datasets and broadcasted videos show that the proposed algorithm is very much efficient to detect errors for video broadcast and surveillance applications in terms of computation time and analysis of distorted frames.
Pronoun Translation in English-French Machine Translation: An Analysis of Error Types
Venue: arXiv cs.CL 2018
Year: 2018

Pronouns are a long-standing challenge in machine translation. We present a study of the performance of a range of rule-based, statistical and neural MT systems on pronoun translation based on an extensive manual evaluation using the PROTEST test suite, which enables a fine-grained analysis of different pronoun types and sheds light on the difficulties of the task. We find that the rule-based approaches in our corpus perform poorly as a result of oversimplification, whereas SMT and early NMT systems exhibit significant shortcomings due to a lack of awareness of the functional and referential properties of pronouns. A recent Transformer-based NMT system with cross-sentence context shows very promising results on non-anaphoric pronouns and intra-sentential anaphora, but there is still considerable room for improvement in examples with cross-sentence dependencies.
Competitive Data Trading in Wireless-Powered Internet of Things (IoT) Crowdsensing Systems with Blockchain
Venue: arXiv cs.NI 2018
Year: 2018

With the explosive growth of smart IoT devices at the edge of the Internet, embedding sensors on mobile devices for massive data collection and collective environment sensing has been envisioned as a cost-effective solution for IoT applications. However, existing IoT platforms and framework rely on dedicated middleware for (semi-) centralized task dispatching, data storage and incentive provision. Consequently, they are usually expensive to deploy, have limited adaptability to diverse requirements, and face a series of data security and privacy issues. In this paper, we employ permissionless blockchains to construct a purely decentralized platform for data storage and trading in a wireless-powered IoT crowdsensing system. In the system, IoT sensors use power wirelessly transferred from RF-energy beacons for data sensing and transmission to an access point. The data is then forwarded to the blockchain for distributed ledger services, i.e., data/transaction verification, recording, and maintenance. Due to coupled interference of wireless transmission and transaction fee incurred from blockchain's distributed ledger services, rational sensors have to decide on their transmission rates to maximize individual utility. Thus, we formulate a noncooperative game model to analyze this competitive situation among the sensors. We provide the analytical condition for the existence of the Nash equilibrium as well as a series of insightful numerical results about the equilibrium strategies in the game.
Comparative Studies of Detecting Abusive Language on Twitter
Venue: arXiv cs.CL 2018
Year: 2018

The context-dependent nature of online aggression makes annotating large collections of data extremely difficult. Previously studied datasets in abusive language detection have been insufficient in size to efficiently train deep learning models. Recently, Hate and Abusive Speech on Twitter, a dataset much greater in size and reliability, has been released. However, this dataset has not been comprehensively studied to its potential. In this paper, we conduct the first comparative study of various learning models on Hate and Abusive Speech on Twitter, and discuss the possibility of using additional features and context data for improvements. Experimental results show that bidirectional GRU networks trained on word-level features, with Latent Topic Clustering modules, is the most accurate model scoring 0.805 F1.
The Bounded Laplace Mechanism in Differential Privacy
Venue: arXiv cs.CR 2018
Year: 2018

The Laplace mechanism is the workhorse of differential privacy, applied to many instances where numerical data is processed. However, the Laplace mechanism can return semantically impossible values, such as negative counts, due to its infinite support. There are two popular solutions to this: (i) bounding/capping the output values and (ii) bounding the mechanism support. In this paper, we show that bounding the mechanism support, while using the parameters of the pure Laplace mechanism, does not typically preserve differential privacy. We also present a robust method to compute the optimal mechanism parameters to achieve differential privacy in such a setting.
Application of Self-Play Reinforcement Learning to a Four-Player Game of Imperfect Information
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a new virtual environment for simulating a card game known as "Big 2". This is a four-player game of imperfect information with a relatively complicated action space (being allowed to play 1,2,3,4 or 5 card combinations from an initial starting hand of 13 cards). As such it poses a challenge for many current reinforcement learning methods. We then use the recently proposed "Proximal Policy Optimization" algorithm to train a deep neural network to play the game, purely learning via self-play, and find that it is able to reach a level which outperforms amateur human players after only a relatively short amount of training time and without needing to search a tree of future game states.
On RAC Drawings of Graphs with one Bend per Edge
Venue: arXiv cs.DS 2018
Year: 2018

A k-bend right-angle-crossing drawing or (k-bend RAC drawing}, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing points of the edges are 90 degrees. Accordingly, a graph that admits a k-bend RAC drawing is referred to as k-bend right-angle-crossing graph (or k-bend RAC, for short). In this paper, we continue the study of the maximum edge-density of 1-bend RAC graphs. We show that an n-vertex 1-bend RAC graph cannot have more than $5.5n-O(1)$ edges. We also demonstrate that there exist infinitely many n-vertex 1-bend RAC graphs with exactly $5n-O(1)$ edges. Our results improve both the previously known best upper bound of $6.5n-O(1)$ edges and the corresponding lower bound of $4.5n-O(\sqrt{n})$ edges by Arikushi et al. (Comput. Geom. 45(4), 169--177 (2012)).
Ensemble Sequence Level Training for Multimodal MT: OSU-Baidu WMT18 Multimodal Machine Translation System Report
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes multimodal machine translation systems developed jointly by Oregon State University and Baidu Research for WMT 2018 Shared Task on multimodal translation. In this paper, we introduce a simple approach to incorporate image information by feeding image features to the decoder side. We also explore different sequence level training methods including scheduled sampling and reinforcement learning which lead to substantial improvements. Our systems ensemble several models using different architectures and training methods and achieve the best performance for three subtasks: En-De and En-Cs in task 1 and (En+De+Fr)-Cs task 1B.
Proximity Forest: An effective and scalable distance-based classifier for time series
Venue: arXiv cs.LG 2018
Year: 2018

Research into the classification of time series has made enormous progress in the last decade. The UCR time series archive has played a significant role in challenging and guiding the development of new learners for time series classification. The largest dataset in the UCR archive holds 10 thousand time series only; which may explain why the primary research focus has been in creating algorithms that have high accuracy on relatively small datasets. This paper introduces Proximity Forest, an algorithm that learns accurate models from datasets with millions of time series, and classifies a time series in milliseconds. The models are ensembles of highly randomized Proximity Trees. Whereas conventional decision trees branch on attribute values (and usually perform poorly on time series), Proximity Trees branch on the proximity of time series to one exemplar time series or another; allowing us to leverage the decades of work into developing relevant measures for time series. Proximity Forest gains both efficiency and accuracy by stochastic selection of both exemplars and similarity measures. Our work is motivated by recent time series applications that provide orders of magnitude more time series than the UCR benchmarks. Our experiments demonstrate that Proximity Forest is highly competitive on the UCR archive: it ranks among the most accurate classifiers while being significantly faster. We demonstrate on a 1M time series Earth observation dataset that Proximity Forest retains this accuracy on datasets that are many orders of magnitude greater than those in the UCR repository, while learning its models at least 100,000 times faster than current state of the art models Elastic Ensemble and COTE.
Single-Microphone Speech Enhancement and Separation Using Deep Learning
Venue: arXiv cs.SD 2018
Year: 2018

The cocktail party problem comprises the challenging task of understanding a speech signal in a complex acoustic environment, where multiple speakers and background noise signals simultaneously interfere with the speech signal of interest. A signal processing algorithm that can effectively increase the speech intelligibility and quality of speech signals in such complicated acoustic situations is highly desirable. Especially for applications involving mobile communication devices and hearing assistive devices. Due to the re-emergence of machine learning techniques, today, known as deep learning, the challenges involved with such algorithms might be overcome. In this PhD thesis, we study and develop deep learning-based techniques for two sub-disciplines of the cocktail party problem: single-microphone speech enhancement and single-microphone multi-talker speech separation. Specifically, we conduct in-depth empirical analysis of the generalizability capability of modern deep learning-based single-microphone speech enhancement algorithms. We show that performance of such algorithms is closely linked to the training data, and good generalizability can be achieved with carefully designed training data. Furthermore, we propose uPIT, a deep learning-based algorithm for single-microphone speech separation and we report state-of-the-art results on a speaker-independent multi-talker speech separation task. Additionally, we show that uPIT works well for joint speech separation and enhancement without explicit prior knowledge about the noise type or number of speakers. Finally, we show that deep learning-based speech enhancement algorithms designed to minimize the classical short-time spectral amplitude mean squared error leads to enhanced speech signals which are essentially optimal in terms of STOI, a state-of-the-art speech intelligibility estimator.
Learning in Memristive Neural Network Architectures using Analog Backpropagation Circuits
Venue: arXiv cs.ET 2018
Year: 2018

The on-chip implementation of learning algorithms would speed-up the training of neural networks in crossbar arrays. The circuit level design and implementation of backpropagation algorithm using gradient descent operation for neural network architectures is an open problem. In this paper, we proposed the analog backpropagation learning circuits for various memristive learning architectures, such as Deep Neural Network (DNN), Binary Neural Network (BNN), Multiple Neural Network (MNN), Hierarchical Temporal Memory (HTM) and Long-Short Term Memory (LSTM). The circuit design and verification is done using TSMC 180nm CMOS process models, and TiO2 based memristor models. The application level validations of the system are done using XOR problem, MNIST character and Yale face image databases
The use of Charts, Pivot Tables, and Array Formulas in two Popular Spreadsheet Corpora
Venue: arXiv cs.SE 2018
Year: 2018

The use of spreadsheets in industry is widespread. Companies base decisions on information coming from spreadsheets. Unfortunately, spreadsheets are error-prone and this increases the risk that companies base their decisions on inaccurate information, which can lead to incorrect decisions and loss of money. In general, spreadsheet research is aimed to reduce the error-proneness of spreadsheets. Most research is concentrated on the use of formulas. However, there are other constructions in spreadsheets, like charts, pivot tables, and array formulas, that are also used to present decision support information to the user. There is almost no research about how these constructions are used. To improve spreadsheet quality it is important to understand how spreadsheets are used and to obtain a complete understanding, the use of charts, pivot tables, and array formulas should be included in research. In this paper, we analyze two popular spreadsheet corpora: Enron and EUSES on the use of the aforementioned constructions.
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Venue: arXiv cs.DS 2018
Year: 2018

In a directed graph $G=(V,E)$ with a capacity on every edge, a \emph{bottleneck path} (or \emph{widest path}) between two vertices is a path maximizing the minimum capacity of edges in the path. For the single-source all-destination version of this problem in directed graphs, the previous best algorithm runs in $O(m+n\log n)$ ($m=|E|$ and $n=|V|$) time, by Dijkstra search with Fibonacci heap [Fredman and Tarjan 1987]. We improve this time bound to $O(m\sqrt{\log n})$, thus it is the first algorithm which breaks the time bound of classic Fibonacci heap when $m=o(n\sqrt{\log n})$. It is a Las-Vegas randomized approach. By contrast, the s-t bottleneck path has an algorithm with running time $O(mβ(m,n))$ [Chechik et al. 2016], where $β(m,n)=\min\{k\geq 1: \log^{(k)}n\leq\frac{m}{n}\}$.
Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of scheduling a set of jobs on a set of identical parallel machines, with the aim of minimizing the total weighted completion time. The problem has been solved in the literature with a number of mathematical formulations, some of which require the implementation of tailored branch-and-price methods. In our work, we solve the problem instead by means of new arc-flow formulations, by first representing it on a capacitated network and then invoking a mixed integer linear model with a pseudo-polynomial number of variables and constraints. According to our computational tests, existing formulations from the literature can solve to proven optimality benchmark instances with up to 100 jobs, whereas our most performing arc-flow formulation solves all instances with up to 400 jobs and provides very low gap for larger instances with up to 1000 jobs.