OpenRaiser/Intern-Atlas huggingface dataset:
Distribution-Free One-Pass Learning
Venue: arXiv cs.LG 2017
Year: 2017

In many large-scale machine learning applications, data are accumulated with time, and thus, an appropriate model should be able to update in an online paradigm. Moreover, as the whole data volume is unknown when constructing the model, it is desired to scan each data item only once with a storage independent with the data volume. It is also noteworthy that the distribution underlying may change during the data accumulation procedure. To handle such tasks, in this paper we propose DFOP, a distribution-free one-pass learning approach. This approach works well when distribution change occurs during data accumulation, without requiring prior knowledge about the change. Every data item can be discarded once it has been scanned. Besides, theoretical guarantee shows that the estimate error, under a mild assumption, decreases until convergence with high probability. The performance of DFOP for both regression and classification are validated in experiments.
Climbing a shaky ladder: Better adaptive risk estimation
Venue: arXiv cs.LG 2017
Year: 2017

We revisit the \emph{leaderboard problem} introduced by Blum and Hardt (2015) in an effort to reduce overfitting in machine learning benchmarks. We show that a randomized version of their Ladder algorithm achieves leaderboard error O(1/n^{0.4}) compared with the previous best rate of O(1/n^{1/3}). Short of proving that our algorithm is optimal, we point out a major obstacle toward further progress. Specifically, any improvement to our upper bound would lead to asymptotic improvements in the general adaptive estimation setting as have remained elusive in recent years. This connection also directly leads to lower bounds for specific classes of algorithms. In particular, we exhibit a new attack on the leaderboard algorithm that both theoretically and empirically distinguishes between our algorithm and previous leaderboard algorithms.
Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
Venue: arXiv cs.AI 2017
Year: 2017

Multi-Agent Path Finding (MAPF) is an NP-hard problem well studied in artificial intelligence and robotics. It has many real-world applications for which existing MAPF solvers use various heuristics. However, these solvers are deterministic and perform poorly on "hard" instances typically characterized by many agents interfering with each other in a small region. In this paper, we enhance MAPF solvers with randomization and observe that they exhibit heavy-tailed distributions of runtimes on hard instances. This leads us to develop simple rapid randomized restart (RRR) strategies with the intuition that, given a hard instance, multiple short runs have a better chance of solving it compared to one long run. We validate this intuition through experiments and show that our RRR strategies indeed boost the performance of state-of-the-art MAPF solvers such as iECBS and M*.
Assigning personality/identity to a chatting machine for coherent conversation generation
Venue: arXiv cs.CL 2017
Year: 2017

Endowing a chatbot with personality or an identity is quite challenging but critical to deliver more realistic and natural conversations. In this paper, we address the issue of generating responses that are coherent to a pre-specified agent profile. We design a model consisting of three modules: a profile detector to decide whether a post should be responded using the profile and which key should be addressed, a bidirectional decoder to generate responses forward and backward starting from a selected profile value, and a position detector that predicts a word position from which decoding should start given a selected profile value. We show that general conversation data from social media can be used to generate profile-coherent responses. Manual and automatic evaluation shows that our model can deliver more coherent, natural, and diversified responses.
Overview of the NLPCC 2017 Shared Task: Chinese News Headline Categorization
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we give an overview for the shared task at the CCF Conference on Natural Language Processing \& Chinese Computing (NLPCC 2017): Chinese News Headline Categorization. The dataset of this shared task consists 18 classes, 12,000 short texts along with corresponded labels for each class. The dataset and example code can be accessed at https://github.com/FudanNLP/nlpcc2017_news_headline_categorization.
End-to-End Musical Key Estimation Using a Convolutional Neural Network
Venue: arXiv cs.LG 2017
Year: 2017

We present an end-to-end system for musical key estimation, based on a convolutional neural network. The proposed system not only out-performs existing key estimation methods proposed in the academic literature; it is also capable of learning a unified model for diverse musical genres that performs comparably to existing systems specialised for specific genres. Our experiments confirm that different genres do differ in their interpretation of tonality, and thus a system tuned e.g. for pop music performs subpar on pieces of electronic music. They also reveal that such cross-genre setups evoke specific types of error (predicting the relative or parallel minor). However, using the data-driven approach proposed in this paper, we can train models that deal with multiple musical styles adequately, and without major losses in accuracy.
Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
Venue: arXiv cs.DS 2017
Year: 2017

We present the first thorough practical study of the Lempel-Ziv-78 and the Lempel-Ziv-Welch computation based on trie data structures. With a careful selection of trie representations we can beat well-tuned popular trie data structures like Judy, m-Bonsai or Cedar.
Graph Reconstruction in the Congested Clique
Venue: arXiv cs.DC 2017
Year: 2017

The congested clique model is a message-passing model of distributed computation where the underlying communication network is the complete graph of $n$ nodes. In this paper we consider the situation where the joint input to the nodes is an $n$-node labeled graph $G$, i.e., the local input received by each node is the indicator function of its neighborhood in $G$. Nodes execute an algorithm, communicating with each other in synchronous rounds and their goal is to compute some function that depends on $G$. In every round, each of the $n$ nodes may send up to $n-1$ different $b$-bit messages through each of its $n-1$ communication links. We denote by $R$ the number of rounds of the algorithm. The product $Rb$, that is, the total number of bits received by a node through one link, is the cost of the algorithm. The most difficult problem we could attempt to solve is the reconstruction problem, where nodes are asked to recover all the edges of the input graph $G$. Formally, given a class of graphs $\mathcal G$, the problem is defined as follows: if $G \notin {\mathcal G}$, then every node must reject; on the other hand, if $G \in {\mathcal G}$, then every node must end up, after the $R$ rounds, knowing all the edges of $G$. It is not difficult to see that the cost $Rb$ of any algorithm that solves this problem (even with public coins) is at least $Ω(\log|\mathcal{G}_n|/n)$, where $\mathcal{G}_n$ is the subclass of all $n$-node labeled graphs in $\mathcal G$. In this paper we prove that previous bound is tight and that it is possible to achieve it with only $R=2$ rounds. More precisely, we exhibit (i) a one-round algorithm that achieves this bound for hereditary graph classes; and (ii) a two-round algorithm that achieves this bound for arbitrary graph classes.
Multi-View Surveillance Video Summarization via Joint Embedding and Sparse Optimization
Venue: arXiv cs.CV 2017
Year: 2017

Most traditional video summarization methods are designed to generate effective summaries for single-view videos, and thus they cannot fully exploit the complicated intra and inter-view correlations in summarizing multi-view videos in a camera network. In this paper, with the aim of summarizing multi-view videos, we introduce a novel unsupervised framework via joint embedding and sparse representative selection. The objective function is two-fold. The first is to capture the multi-view correlations via an embedding, which helps in extracting a diverse set of representatives. The second is to use a `2;1- norm to model the sparsity while selecting representative shots for the summary. We propose to jointly optimize both of the objectives, such that embedding can not only characterize the correlations, but also indicate the requirements of sparse representative selection. We present an efficient alternating algorithm based on half-quadratic minimization to solve the proposed non-smooth and non-convex objective with convergence analysis. A key advantage of the proposed approach with respect to the state-of-the-art is that it can summarize multi-view videos without assuming any prior correspondences/alignment between them, e.g., uncalibrated camera networks. Rigorous experiments on several multi-view datasets demonstrate that our approach clearly outperforms the state-of-the-art methods.
Deep Adaptive Feature Embedding with Local Sample Distributions for Person Re-identification
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification (re-id) aims to match pedestrians observed by disjoint camera views. It attracts increasing attention in computer vision due to its importance to surveillance system. To combat the major challenge of cross-view visual variations, deep embedding approaches are proposed by learning a compact feature space from images such that the Euclidean distances correspond to their cross-view similarity metric. However, the global Euclidean distance cannot faithfully characterize the ideal similarity in a complex visual feature space because features of pedestrian images exhibit unknown distributions due to large variations in poses, illumination and occlusion. Moreover, intra-personal training samples within a local range are robust to guide deep embedding against uncontrolled variations, which however, cannot be captured by a global Euclidean distance. In this paper, we study the problem of person re-id by proposing a novel sampling to mine suitable \textit{positives} (i.e. intra-class) within a local range to improve the deep embedding in the context of large intra-class variations. Our method is capable of learning a deep similarity metric adaptive to local sample structure by minimizing each sample's local distances while propagating through the relationship between samples to attain the whole intra-class minimization. To this end, a novel objective function is proposed to jointly optimize similarity metric learning, local positive mining and robust deep embedding. This yields local discriminations by selecting local-ranged positive samples, and the learned features are robust to dramatic intra-class variations. Experiments on benchmarks show state-of-the-art results achieved by our method.
LazyPIM: Efficient Support for Cache Coherence in Processing-in-Memory Architectures
Venue: arXiv cs.AR 2017
Year: 2017

Processing-in-memory (PIM) architectures have seen an increase in popularity recently, as the high internal bandwidth available within 3D-stacked memory provides greater incentive to move some computation into the logic layer of the memory. To maintain program correctness, the portions of a program that are executed in memory must remain coherent with the portions of the program that continue to execute within the processor. Unfortunately, PIM architectures cannot use traditional approaches to cache coherence due to the high off-chip traffic consumed by coherence messages, which, as we illustrate in this work, can undo the benefits of PIM execution for many data-intensive applications. We propose LazyPIM, a new hardware cache coherence mechanism designed specifically for PIM. Prior approaches for coherence in PIM are ill-suited to applications that share a large amount of data between the processor and the PIM logic. LazyPIM uses a combination of speculative cache coherence and compressed coherence signatures to greatly reduce the overhead of keeping PIM coherent with the processor, even when a large amount of sharing exists.We find that LazyPIM improves average performance across a range of data-intensive PIM applications by 19.6%, reduces off-chip traffic by 30.9%, and reduces energy consumption by 18.0%, over the best prior approaches to PIM coherence.
Attribute Based Administration of Role Based Access Control : A Detailed Description
Venue: arXiv cs.CR 2017
Year: 2017

Administrative Role Based Access Control (ARBAC) models deal with how to manage user-role assignments (URA), permission-role assignments (PRA), and role-role assignments (RRA). A wide variety of approaches has been proposed in the literature for URA, PRA, and RRA. In this paper, we propose attribute-based administrative models that unify many prior approaches for URA and PRA. The motivating factor is that attributes of various RBAC entities such as admin users, regular users and permissions can be used to administer URA and PRA in a highly flexible manner. We develop an attribute-based URA model called AURA and an attribute-based PRA model called ARPA. We demonstrate that AURA and ARPA can express and unify many prior URA and PRA models.
Critical Hyper-Parameters: No Random, No Cry
Venue: arXiv cs.LG 2017
Year: 2017

The selection of hyper-parameters is critical in Deep Learning. Because of the long training time of complex models and the availability of compute resources in the cloud, "one-shot" optimization schemes - where the sets of hyper-parameters are selected in advance (e.g. on a grid or in a random manner) and the training is executed in parallel - are commonly used. It is known that grid search is sub-optimal, especially when only a few critical parameters matter, and suggest to use random search instead. Yet, random search can be "unlucky" and produce sets of values that leave some part of the domain unexplored. Quasi-random methods, such as Low Discrepancy Sequences (LDS) avoid these issues. We show that such methods have theoretical properties that make them appealing for performing hyperparameter search, and demonstrate that, when applied to the selection of hyperparameters of complex Deep Learning models (such as state-of-the-art LSTM language models and image classification models), they yield suitable hyperparameters values with much fewer runs than random search. We propose a particularly simple LDS method which can be used as a drop-in replacement for grid or random search in any Deep Learning pipeline, both as a fully one-shot hyperparameter search or as an initializer in iterative batch optimization.
Analysis of Anomalies in the Internet Traffic Observed at the Campus Network Gateway
Venue: arXiv cs.CR 2017
Year: 2017

A considerable portion of the machine learning literature applied to intrusion detection uses outdated data sets based on a simulated network with a limited environment. Moreover, flaws usually appear in datasets and the way we handle them may impact on measurements. Finally, the detection capacity of intrusion detection is highly influenced by the system configuration. We focus on a topic rarely investigated: the characterization of anomalies in a large network environment. Intrusion Detection System (IDS) are used to detect exploits or other attacks that raise alarms. These anomalous events usually receive less attention than attack alarms, causing them to be frequently overlooked by security administrators. However, the observation of this activity contributes to understand the traffic network characteristics. On one hand, abnormal behaviors may be legitimate, e.g., misinterpreted protocols or malfunctioning network equipment, but on the other hand an attacker may intentionally craft packets to introduce anomalies to evade monitoring systems. Anomalies found in operational network environments may indicate cases of evasion attacks, application bugs, and a wide variety of factors that highly influence intrusion detection performance. This study explores the nature of anomalies found in U-Tokyo Network using cooperatively Bro and Snort IDS among other resources. We analyze 6.5 TB of compressed binary tcpdump data representing 12 hours of network traffic. Our major contributions can be summarized in: 1) reporting the anomalies observed in real, up-to-date traffic from a large academic network environment, and documenting problems in research that may lead to wrong results due to misinterpretations of data or misconfigurations in software; 2) assessing the quality of data by analyzing the potential and the real problems in the capture process.
Towards Statistical Reasoning in Description Logics over Finite Domains (Full Version)
Venue: arXiv cs.AI 2017
Year: 2017

We present a probabilistic extension of the description logic $\mathcal{ALC}$ for reasoning about statistical knowledge. We consider conditional statements over proportions of the domain and are interested in the probabilistic-logical consequences of these proportions. After introducing some general reasoning problems and analyzing their properties, we present first algorithms and complexity results for reasoning in some fragments of Statistical $\mathcal{ALC}$.
Maximum Correntropy Adaptive Filtering Approach for Robust Compressive Sensing Reconstruction
Venue: arXiv cs.IT 2017
Year: 2017

Robust compressive sensing(CS) reconstruction has become an attractive research topic in recent years. Robust CS aims to reconstruct the sparse signals under non-Gaussian(i.e. heavy tailed) noises where traditional CS reconstruction algorithms may perform very poorly due to utilizing $l_2$ norm of the residual vector in optimization. Most of existing robust CS reconstruction algorithms are based on greedy pursuit method or convex relaxation approach. Recently, the adaptive filtering framework has been introduced to deal with the CS reconstruction, which shows desirable performance in both efficiency and reconstruction performance under Gaussian noise. In this paper, we propose an adaptive filtering based robust CS reconstruction algorithm, called $l_0$ regularized maximum correntropy criterion($l_0$-MCC) algorithm, which combines the adaptive filtering framework and maximum correntropy criterion(MCC). MCC has recently been successfully used in adaptive filtering due to its robustness to impulsive non-Gaussian noises and low computational complexity. We analyze theoretically the stability of the proposed $l_0$-MCC algorithm. A mini-batch based $l_0$-MCC(MB-$l_0$-MCC) algorithm is further developed to speed up the convergence. Comparison with existing robust CS reconstruction algorithms is conducted via simulations, showing that the proposed $l_0$-MCC and MB-$l_0$-MCC can achieve significantly better performance than other algorithms.
Characterizing and Predicting Supply-side Engagement on Crowd-contributed Video Sharing Platforms
Venue: arXiv cs.HC 2017
Year: 2017

Video sharing and entertainment websites have rapidly grown in popularity and now constitute some of the most visited websites on the Internet. Despite the active user engagement on these online video-sharing platforms, most of recent research on online media platforms have restricted themselves to networking based social media sites, like Facebook or Twitter. We depart from previous studies in the online media space that have focused exclusively on demand-side user engagement, by modeling the supply-side of the crowd-contributed videos on this platform. The current study is among the first to perform a large-scale empirical study using longitudinal video upload data from a large online video platform. The modeling and subsequent prediction of video uploads is made complicated by the heterogeneity of video types (e.g. popular vs. niche video genres), and the inherent time trend effects associated with media uploads. We identify distinct genre-clusters from our dataset and employ a self-exciting Hawkes point-process model on each of these clusters to fully specify and estimate the video upload process. Additionally, we go beyond prediction to disentangle potential factors that govern user engagement and determine the video upload rates, which improves our analysis with additional explanatory power. Our findings show that using a relatively parsimonious point-process model, we are able to achieve higher model fit, and predict video uploads to the platform with a higher accuracy than competing models. The findings from this study can benefit platform owners in better understanding how their supply-side users engage with their site over time. We also offer a robust method for performing media upload prediction that is likely to be generalizable across media platforms which demonstrate similar temporal and genre-level heterogeneity.
Downlink Precoding for Massive MIMO Systems Exploiting Virtual Channel Model Sparsity
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, the problem of designing a forward link linear precoder for Massive Multiple-Input Multiple-Output (MIMO) systems in conjunction with Quadrature Amplitude Modulation (QAM) is addressed. First, we employ a novel and efficient methodology that allows for a sparse representation of multiple users and groups in a fashion similar to Joint Spatial Division and Multiplexing. Then, the method is generalized to include Orthogonal Frequency Division Multiplexing (OFDM) for frequency selective channels, resulting in Combined Frequency and Spatial Division and Multiplexing, a configuration that offers high flexibility in Massive MIMO systems. A challenge in such system design is to consider finite alphabet inputs, especially with larger constellation sizes such as $M\geq 16$. The proposed methodology is next applied jointly with the complexity-reducing Per-Group Processing (PGP) technique, on a per user group basis, in conjunction with QAM modulation and in simulations, for constellation size up to $M=64$. We show by numerical results that the precoders developed offer significantly better performance than the configuration with no precoder or the plain beamformer and with $M\geq 16$.
Style Transfer for Anime Sketches with Enhanced Residual U-net and Auxiliary Classifier GAN
Venue: arXiv cs.CV 2017
Year: 2017

Recently, with the revolutionary neural style transferring methods, creditable paintings can be synthesized automatically from content images and style images. However, when it comes to the task of applying a painting's style to an anime sketch, these methods will just randomly colorize sketch lines as outputs and fail in the main task: specific style tranfer. In this paper, we integrated residual U-net to apply the style to the gray-scale sketch with auxiliary classifier generative adversarial network (AC-GAN). The whole process is automatic and fast, and the results are creditable in the quality of art style as well as colorization.
Low Complexity Resource Allocation for Massive Carrier Aggregation
Venue: arXiv cs.IT 2017
Year: 2017

Optimal resource allocation (RA) in massive carrier aggregation scenarios is a challenging combinatorial optimization problem whose dimension is proportional to the number of users, component carriers (CCs), and OFDMA resource blocks per CC. Towards scalable, near-optimal RA in massive CA settings, an iterative RA algorithm is proposed for joint assignment of CCs and OFDMA resource blocks to users. The algorithm is based on the principle of successive geometric programming approximations and has a complexity that scales only linearly with the problem dimension. Although its derivation is based on a relaxed formulation of the RA problem, the algorithm is shown to converge to integer-valued RA variables with probability 1 under mild assumptions on the distribution of user utilities. Simulations demonstrate improved performance of the proposed algorithm compared to commonly considered heuristic RA procedures of comparable complexity.