OpenRaiser/Intern-Atlas huggingface dataset:
Selfishness need not be bad: a general proof
Venue: arXiv cs.GT 2018
Year: 2018

This article studies the user behavior in non-atomic congestion games. We consider non-atomic congestion games with continuous and non-decreasing functions and investigate the limit of the price of anarchy when the total user volume approaches infinity. We deepen the knowledge on {\em asymptotically well designed games} \cite{Wu2017Selfishness}, {\em limit games} \cite{Wu2017Selfishness}, {\em scalability} \cite{Wu2017Selfishness} and {\em gaugeability} \cite{Colini2017b} that were recently used in the limit analyses of the price of anarchy for non-atomic congestion games. We develop a unified framework and derive new techniques that allow a general limit analysis of the price of anarchy. With these new techniques, we are able to prove a global convergence on the price of anarchy for non-atomic congestion games with arbitrary polynomial price functions and arbitrary user volume vector sequences. Moreover, we show that these new techniques are very flexible and robust and apply also to non-atomic congestion games with price functions of other types. In particular, we prove that non-atomic congestion games with regularly varying price functions are also asymptotically well designed, provided that the price functions are slightly restricted. Our results greatly generalize recent results. In particular, our results further support the view with a general proof that selfishness need not be bad for non-atomic congestion games.
Low-Cost Parameterizations of Deep Convolutional Neural Networks
Venue: arXiv cs.NA 2018
Year: 2018

Convolutional Neural Networks (CNNs) filter the input data using a series of spatial convolution operators with compactly supported stencils and point-wise nonlinearities. Commonly, the convolution operators couple features from all channels. For wide networks, this leads to immense computational cost in the training of and prediction with CNNs. In this paper, we present novel ways to parameterize the convolution more efficiently, aiming to decrease the number of parameters in CNNs and their computational complexity. We propose new architectures that use a sparser coupling between the channels and thereby reduce both the number of trainable weights and the computational cost of the CNN. Our architectures arise as new types of residual neural network (ResNet) that can be seen as discretizations of a Partial Differential Equations (PDEs) and thus have predictable theoretical properties. Our first architecture involves a convolution operator with a special sparsity structure, and is applicable to a large class of CNNs. Next, we present an architecture that can be seen as a discretization of a diffusion reaction PDE, and use it with three different convolution operators. We outline in our experiments that the proposed architectures, although considerably reducing the number of trainable weights, yield comparable accuracy to existing CNNs that are fully coupled in the channel dimension.
Learning to Teach in Cooperative Multiagent Reinforcement Learning
Venue: arXiv cs.MA 2018
Year: 2018

Collective human knowledge has clearly benefited from the fact that innovations by individuals are taught to others through communication. Similar to human social groups, agents in distributed learning systems would likely benefit from communication to share knowledge and teach skills. The problem of teaching to improve agent learning has been investigated by prior works, but these approaches make assumptions that prevent application of teaching to general multiagent problems, or require domain expertise for problems they can apply to. This learning to teach problem has inherent complexities related to measuring long-term impacts of teaching that compound the standard multiagent coordination challenges. In contrast to existing works, this paper presents the first general framework and algorithm for intelligent agents to learn to teach in a multiagent environment. Our algorithm, Learning to Coordinate and Teach Reinforcement (LeCTR), addresses peer-to-peer teaching in cooperative multiagent reinforcement learning. Each agent in our approach learns both when and what to advise, then uses the received advice to improve local learning. Importantly, these roles are not fixed; these agents learn to assume the role of student and/or teacher at the appropriate moments, requesting and providing advice in order to improve teamwide performance and learning. Empirical comparisons against state-of-the-art teaching methods show that our teaching agents not only learn significantly faster, but also learn to coordinate in tasks where existing methods fail.
A Text Analysis of Federal Reserve meeting minutes
Venue: arXiv cs.IR 2018
Year: 2018

Recent developments in monetary policy by the Federal Reserve has created a need for an objective method of communication analysis.Using methods developed for text analysis, we present a novel technique of analysis which creates a semantic space defined by various policymakers public comments and places the committee consensus in the appropriate location. Its then possible to determine which member of the committee is most closely aligned with the committee consensus over time and create a foundation for further actionable research.
Parallel Transport Convolution: A New Tool for Convolutional Neural Networks on Manifolds
Venue: arXiv cs.LG 2018
Year: 2018

Convolution has been playing a prominent role in various applications in science and engineering for many years. It is the most important operation in convolutional neural networks. There has been a recent growth of interests of research in generalizing convolutions on curved domains such as manifolds and graphs. However, existing approaches cannot preserve all the desirable properties of Euclidean convolutions, namely compactly supported filters, directionality, transferability across different manifolds. In this paper we develop a new generalization of the convolution operation, referred to as parallel transport convolution (PTC), on Riemannian manifolds and their discrete counterparts. PTC is designed based on the parallel transportation which is able to translate information along a manifold and to intrinsically preserve directionality. PTC allows for the construction of compactly supported filters and is also robust to manifold deformations. This enables us to preform wavelet-like operations and to define deep convolutional neural networks on curved domains.
Spherical Convolutional Neural Network for 3D Point Clouds
Venue: arXiv cs.CV 2018
Year: 2018

We propose a neural network for 3D point cloud processing that exploits `spherical' convolution kernels and octree partitioning of space. The proposed metric-based spherical kernels systematically quantize point neighborhoods to identify local geometric structures in data, while maintaining the properties of translation-invariance and asymmetry. The network architecture itself is guided by octree data structuring that takes full advantage of the sparse nature of irregular point clouds. We specify spherical kernels with the help of neurons in each layer that in turn are associated with spatial locations. We exploit this association to avert dynamic kernel generation during network training, that enables efficient learning with high resolution point clouds. We demonstrate the utility of the spherical convolutional neural network for 3D object classification on standard benchmark datasets.
Class Representative Autoencoder for Low Resolution Multi-Spectral Gender Classification
Venue: arXiv cs.CV 2018
Year: 2018

Gender is one of the most common attributes used to describe an individual. It is used in multiple domains such as human computer interaction, marketing, security, and demographic reports. Research has been performed to automate the task of gender recognition in constrained environment using face images, however, limited attention has been given to gender classification in unconstrained scenarios. This work attempts to address the challenging problem of gender classification in multi-spectral low resolution face images. We propose a robust Class Representative Autoencoder model, termed as AutoGen for the same. The proposed model aims to minimize the intra-class variations while maximizing the inter-class variations for the learned feature representations. Results on visible as well as near infrared spectrum data for different resolutions and multiple databases depict the efficacy of the proposed model. Comparative results with existing approaches and two commercial off-the-shelf systems further motivate the use of class representative features for classification.
IoT2Vec: Identification of Similar IoT Devices via Activity Footprints
Venue: arXiv cs.HC 2018
Year: 2018

We consider a smart home or smart office environment with a number of IoT devices connected and passing data between one another. The footprints of the data transferred can provide valuable information about the devices, which can be used to (a) identify the IoT devices and (b) in case of failure, to identify the correct replacements for these devices. In this paper, we generate the embeddings for IoT devices in a smart home using Word2Vec, and explore the possibility of having a similar concept for IoT devices, aka IoT2Vec. These embeddings can be used in a number of ways, such as to find similar devices in an IoT device store, or as a signature of each type of IoT device. We show results of a feasibility study on the CASAS dataset of IoT device activity logs, using our method to identify the patterns in embeddings of various types of IoT devices in a household.
Adaptive Neighborhood Resizing for Stochastic Reachability in Multi-Agent Systems
Venue: arXiv cs.SY 2018
Year: 2018

We present DAMPC, a distributed, adaptive-horizon and adaptive-neighborhood algorithm for solving the stochastic reachability problem in multi-agent systems, in particular flocking modeled as a Markov decision process. At each time step, every agent calls a centralized, adaptive-horizon model-predictive control (AMPC) algorithm to obtain an optimal solution for its local neighborhood. Second, the agents derive the flock-wide optimal solution through a sequence of consensus rounds. Third, the neighborhood is adaptively resized using a flock-wide, cost-based Lyapunov function V. This way DAMPC improves efficiency without compromising convergence. We evaluate DAMPC's performance using statistical model checking. Our results demonstrate that, compared to AMPC, DAMPC achieves considerable speed-up (two-fold in some cases) with only a slightly lower rate of convergence. The smaller average neighborhood size and lookahead horizon demonstrate the benefits of the DAMPC approach for stochastic reachability problems involving any controllable multi-agent system that possesses a cost function.
Silence
Venue: arXiv cs.DC 2018
Year: 2018

The cost of communication is a substantial factor affecting the scalability of many distributed applications. Every message sent can incur a cost in storage, computation, energy and bandwidth. Consequently, reducing the communication costs of distributed applications is highly desirable. The best way to reduce message costs is by communicating without sending any messages whatsoever. This paper initiates a rigorous investigation into the use of silence in synchronous settings, in which processes can fail. We formalize sufficient conditions for information transfer using silence, as well as necessary conditions for particular cases of interest. This allows us to identify message patterns that enable communication through silence. In particular, a pattern called a {\em silent choir} is identified, and shown to be central to information transfer via silence in failure-prone systems. The power of the new framework is demonstrated on the {\em atomic commitment} problem (AC). A complete characterization of the tradeoff between message complexity and round complexity in the synchronous model with crash failures is provided, in terms of lower bounds and matching protocols. In particular, a new message-optimal AC protocol is designed using silence, in which processes decide in~3 rounds in the common case. This significantly improves on the best previously known message-optimal AC protocol, in which decisions were performed in $Θ(n)$ rounds.
A Tensor-Based Sub-Mode Coordinate Algorithm for Stock Prediction
Venue: arXiv cs.LG 2018
Year: 2018

The investment on the stock market is prone to be affected by the Internet. For the purpose of improving the prediction accuracy, we propose a multi-task stock prediction model that not only considers the stock correlations but also supports multi-source data fusion. Our proposed model first utilizes tensor to integrate the multi-sourced data, including financial Web news, investors' sentiments extracted from the social network and some quantitative data on stocks. In this way, the intrinsic relationships among different information sources can be captured, and meanwhile, multi-sourced information can be complemented to solve the data sparsity problem. Secondly, we propose an improved sub-mode coordinate algorithm (SMC). SMC is based on the stock similarity, aiming to reduce the variance of their subspace in each dimension produced by the tensor decomposition. The algorithm is able to improve the quality of the input features, and thus improves the prediction accuracy. And the paper utilizes the Long Short-Term Memory (LSTM) neural network model to predict the stock fluctuation trends. Finally, the experiments on 78 A-share stocks in CSI 100 and thirteen popular HK stocks in the year 2015 and 2016 are conducted. The results demonstrate the improvement on the prediction accuracy and the effectiveness of the proposed model.
Adversarial Noise Layer: Regularize Neural Network By Adding Noise
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we introduce a novel regularization method called Adversarial Noise Layer (ANL) and its efficient version called Class Adversarial Noise Layer (CANL), which are able to significantly improve CNN's generalization ability by adding carefully crafted noise into the intermediate layer activations. ANL and CANL can be easily implemented and integrated with most of the mainstream CNN-based models. We compared the effects of the different types of noise and visually demonstrate that our proposed adversarial noise instruct CNN models to learn to extract cleaner feature maps, which further reduce the risk of over-fitting. We also conclude that models trained with ANL or CANL are more robust to the adversarial examples generated by FGSM than the traditional adversarial training approaches.
Performance Bound Analysis for Crowdsourced Mobile Video Streaming
Venue: arXiv cs.MM 2018
Year: 2018

Adaptive bitrate (ABR) streaming enables video users to adapt the playing bitrate to the real-time network conditions to achieve the desirable quality of experience (QoE). In this work, we propose a novel crowdsourced streaming framework for multi-user ABR video streaming over wireless networks. This framework enables the nearby mobile video users to crowdsource their radio links and resources for cooperative video streaming. We focus on analyzing the social welfare performance bound of the proposed crowdsourced streaming system. Directly solving this bound is challenging due to the asynchronous operations of users. To this end, we introduce a virtual time-slotted system with the synchronized operations, and formulate the associated social welfare optimization problem as a linear programming. We show that the optimal social welfare performance of the virtual system provides effective upper-bound and lower-bound for the optimal performance (bound) of the original asynchronous system, hence characterizes the feasible performance region of the proposed crowdsourced streaming system. The performance bounds derived in this work can serve as a benchmark for the future online algorithm design and incentive mechanism design.
Algorithms and Analysis for the SPARQL Constructs
Venue: arXiv cs.DB 2018
Year: 2018

As Resource Description Framework (RDF) is becoming a popular data modelling standard, the challenges of efficient processing of Basic Graph Pattern (BGP) SPARQL queries (a.k.a. SQL inner-joins) have been a focus of the research community over the past several years. In our recently published work we brought community's attention to another equally important component of SPARQL, i.e., OPTIONAL pattern queries (a.k.a. SQL left-outer-joins). We proposed novel optimization techniques -- first of a kind -- and showed experimentally that our techniques perform better for the low-selectivity queries, and give at par performance for the highly selective queries, compared to the state-of-the-art methods. BGPs and OPTIONALs (BGP-OPT) make the basic building blocks of the SPARQL query language. Thus, in this paper, treating our BGP-OPT query optimization techniques as the primitives, we extend them to handle other broader components of SPARQL such as such as UNION, FILTER, and DISTINCT. We mainly focus on the procedural (algorithmic) aspects of these extensions. We also make several important observations about the structural aspects of complex SPARQL queries with any intermix of these clauses, and relax some of the constraints regarding the cyclic properties of the queries proposed earlier. We do so without affecting the correctness of the results, thus providing more flexibility in using the BGP-OPT optimization techniques.
Identifying OSPF Anomalies Using Recurrence Quantification Analysis
Venue: arXiv cs.NI 2018
Year: 2018

Open Shortest Path First (OSPF) is one of the most widely used routing protocol to manage intra-domain routing. OSPF has been identified with many serious security issues. LSA falsification is one of the most critical vulnerability that can cause route loop and black hole. Network operators need to rapidly identity such anomalies. Network operators need also to identify hardware failure. In this paper, we investigate the capability of Recurrence Quantification Analysis (RQA), an advanced nonlinear statistical analysis technique, to identify OSPF anomalies. We evaluate the capability of RQA to identify OSPF anomalies using a controlled testbed where we introduced different types of LSA falsifications as well as hardware failures. Our evaluation shows that RQA can rapidly detect OSPF anomalies.
Constrained Sparse Subspace Clustering with Side-Information
Venue: arXiv cs.CV 2018
Year: 2018

Subspace clustering refers to the problem of segmenting high dimensional data drawn from a union of subspaces into the respective subspaces. In some applications, partial side-information to indicate "must-link" or "cannot-link" in clustering is available. This leads to the task of subspace clustering with side-information. However, in prior work the supervision value of the side-information for subspace clustering has not been fully exploited. To this end, in this paper, we present an enhanced approach for constrained subspace clustering with side-information, termed Constrained Sparse Subspace Clustering plus (CSSC+), in which the side-information is used not only in the stage of learning an affinity matrix but also in the stage of spectral clustering. Moreover, we propose to estimate clustering accuracy based on the partial side-information and theoretically justify the connection to the ground-truth clustering accuracy in terms of the Rand index. We conduct experiments on three cancer gene expression datasets to validate the effectiveness of our proposals.
Measurement-wise Occlusion in Multi-object Tracking
Venue: arXiv cs.CV 2018
Year: 2018

Handling object interaction is a fundamental challenge in practical multi-object tracking, even for simple interactive effects such as one object temporarily occluding another. We formalize the problem of occlusion in tracking with two different abstractions. In object-wise occlusion, objects that are occluded by other objects do not generate measurements. In measurement-wise occlusion, a previously unstudied approach, all objects may generate measurements but some measurements may be occluded by others. While the relative validity of each abstraction depends on the situation and sensor, measurement-wise occlusion fits into probabilistic multi-object tracking algorithms with much looser assumptions on object interaction. Its value is demonstrated by showing that it naturally derives a popular approximation for lidar tracking, and by an example of visual tracking in image space.
Joint Image Captioning and Question Answering
Venue: arXiv cs.CL 2018
Year: 2018

Answering visual questions need acquire daily common knowledge and model the semantic connection among different parts in images, which is too difficult for VQA systems to learn from images with the only supervision from answers. Meanwhile, image captioning systems with beam search strategy tend to generate similar captions and fail to diversely describe images. To address the aforementioned issues, we present a system to have these two tasks compensate with each other, which is capable of jointly producing image captions and answering visual questions. In particular, we utilize question and image features to generate question-related captions and use the generated captions as additional features to provide new knowledge to the VQA system. For image captioning, our system attains more informative results in term of the relative improvements on VQA tasks as well as competitive results using automated metrics. Applying our system to the VQA tasks, our results on VQA v2 dataset achieve 65.8% using generated captions and 69.1% using annotated captions in validation set and 68.4% in the test-standard set. Further, an ensemble of 10 models results in 69.7% in the test-standard split.
State-Denoised Recurrent Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Recurrent neural networks (RNNs) are difficult to train on sequence processing tasks, not only because input noise may be amplified through feedback, but also because any inaccuracy in the weights has similar consequences as input noise. We describe a method for denoising the hidden state during training to achieve more robust representations thereby improving generalization performance. Attractor dynamics are incorporated into the hidden state to `clean up' representations at each step of a sequence. The attractor dynamics are trained through an auxillary denoising loss to recover previously experienced hidden states from noisy versions of those states. This state-denoised recurrent neural network {SDRNN} performs multiple steps of internal processing for each external sequence step. On a range of tasks, we show that the SDRNN outperforms a generic RNN as well as a variant of the SDRNN with attractor dynamics on the hidden state but without the auxillary loss. We argue that attractor dynamics---and corresponding connectivity constraints---are an essential component of the deep learning arsenal and should be invoked not only for recurrent networks but also for improving deep feedforward nets and intertask transfer.