OpenRaiser/Intern-Atlas huggingface dataset:
Agnostic Learning by Refuting
Venue: arXiv cs.LG 2017
Year: 2017

The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of \emph{efficient} agnostic learning. We introduce \emph{refutation complexity}, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of \emph{efficient} agnostic learning. Informally, refutation complexity of a class $\mathcal{C}$ is the minimum number of example-label pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of $\mathcal{C}$ (\emph{structure}) and the case where the labels are i.i.d. Rademacher random variables (\emph{noise}). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and co-authors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence. In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.
End-to-End United Video Dehazing and Detection
Venue: arXiv cs.CV 2017
Year: 2017

The recent development of CNN-based image dehazing has revealed the effectiveness of end-to-end modeling. However, extending the idea to end-to-end video dehazing has not been explored yet. In this paper, we propose an End-to-End Video Dehazing Network (EVD-Net), to exploit the temporal consistency between consecutive video frames. A thorough study has been conducted over a number of structure options, to identify the best temporal fusion strategy. Furthermore, we build an End-to-End United Video Dehazing and Detection Network(EVDD-Net), which concatenates and jointly trains EVD-Net with a video object detection model. The resulting augmented end-to-end pipeline has demonstrated much more stable and accurate detection results in hazy video.
Skyline Queries in O(1) time?
Venue: arXiv cs.DB 2017
Year: 2017

The skyline of a set $P$ of points ($SKY(P)$) consists of the "best" points with respect to minimization or maximization of the attribute values. A point $p$ dominates another point $q$ if $p$ is as good as $q$ in all dimensions and it is strictly better than $q$ in at least one dimension. In this work, we focus on the static $2$-d space and provide expected performance guarantees for $3$-sided Range Skyline Queries on the Grid, where $N$ is the cardinality of $P$, $B$ the size of a disk block, and $R$ the capacity of main memory. We present the MLR-tree, which offers optimal expected cost for finding planar skyline points in a $3$-sided query rectangle, $q=[a,b]\times(-\infty,d]$, in both RAM and I/O model on the grid $[1,M]\times [1,M]$, by single scanning only the points contained in $SKY(P)$. In particular, it supports skyline queries in a $3$-sided range in $O(t\cdot t_{PAM}(N))$ time ($O((t/B)\cdot t_{PAM}(N))$ I/Os), where $t$ is the answer size and $t_{PAM}(N)$ the time required for answering predecessor queries for $d$ in a PAM (Predecessor Access Method) structure, which is a special component of MLR-tree and stores efficiently root-to-leaf paths or sub-paths. By choosing PAM structures with $O(1)$ expected time for predecessor queries under discrete $μ$-random distributions of the $x$ and $y$ coordinates, MLR-tree supports skyline queries in optimal $O(t)$ expected time ($O(t/B)$ expected number of I/Os) with high probability. The space cost becomes superlinear and can be reduced to linear for many special practical cases. If we choose a PAM structure with $O(1)$ amortized time for batched predecessor queries (under no assumption on distributions of the $x$ and $y$ coordinates), MLR-tree supports batched skyline queries in optimal $O(t)$ amortized time, however the space becomes exponential. In dynamic case, the update time complexity is affected by a $O(log^{2}N)$ factor.
Joint Learning of Set Cardinality and State Distribution
Venue: arXiv cs.CV 2017
Year: 2017

We present a novel approach for learning to predict sets using deep learning. In recent years, deep neural networks have shown remarkable results in computer vision, natural language processing and other related problems. Despite their success, traditional architectures suffer from a serious limitation in that they are built to deal with structured input and output data, i.e. vectors or matrices. Many real-world problems, however, are naturally described as sets, rather than vectors. Existing techniques that allow for sequential data, such as recurrent neural networks, typically heavily depend on the input and output order and do not guarantee a valid solution. Here, we derive in a principled way, a mathematical formulation for set prediction where the output is permutation invariant. In particular, our approach jointly learns both the cardinality and the state distribution of the target set. We demonstrate the validity of our method on the task of multi-label image classification and achieve a new state of the art on the PASCAL VOC and MS COCO datasets.
Co-training for Demographic Classification Using Deep Learning from Label Proportions
Venue: arXiv cs.CV 2017
Year: 2017

Deep learning algorithms have recently produced state-of-the-art accuracy in many classification tasks, but this success is typically dependent on access to many annotated training examples. For domains without such data, an attractive alternative is to train models with light, or distant supervision. In this paper, we introduce a deep neural network for the Learning from Label Proportion (LLP) setting, in which the training data consist of bags of unlabeled instances with associated label distributions for each bag. We introduce a new regularization layer, Batch Averager, that can be appended to the last layer of any deep neural network to convert it from supervised learning to LLP. This layer can be implemented readily with existing deep learning packages. To further support domains in which the data consist of two conditionally independent feature views (e.g. image and text), we propose a co-training algorithm that iteratively generates pseudo bags and refits the deep LLP model to improve classification accuracy. We demonstrate our models on demographic attribute classification (gender and race/ethnicity), which has many applications in social media analysis, public health, and marketing. We conduct experiments to predict demographics of Twitter users based on their tweets and profile image, without requiring any user-level annotations for training. We find that the deep LLP approach outperforms baselines for both text and image features separately. Additionally, we find that co-training algorithm improves image and text classification by 4% and 8% absolute F1, respectively. Finally, an ensemble of text and image classifiers further improves the absolute F1 measure by 4% on average.
Empower Sequence Labeling with Task-Aware Neural Language Model
Venue: arXiv cs.CL 2017
Year: 2017

Linguistic sequence labeling is a general modeling approach that encompasses a variety of problems, such as part-of-speech tagging and named entity recognition. Recent advances in neural networks (NNs) make it possible to build reliable models without handcrafted features. However, in many cases, it is hard to obtain sufficient annotations to train these models. In this study, we develop a novel neural framework to extract abundant knowledge hidden in raw texts to empower the sequence labeling task. Besides word-level knowledge contained in pre-trained word embeddings, character-aware neural language models are incorporated to extract character-level knowledge. Transfer learning techniques are further adopted to mediate different components and guide the language model towards the key knowledge. Comparing to previous methods, these task-specific knowledge allows us to adopt a more concise model and conduct more efficient training. Different from most transfer learning methods, the proposed framework does not rely on any additional supervision. It extracts knowledge from self-contained order information of training sequences. Extensive experiments on benchmark datasets demonstrate the effectiveness of leveraging character-level knowledge and the efficiency of co-training. For example, on the CoNLL03 NER task, model training completes in about 6 hours on a single GPU, reaching F1 score of 91.71$\pm$0.10 without using any extra annotation.
Recursive Exponential Weighting for Online Non-convex Optimization
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we investigate the online non-convex optimization problem which generalizes the classic {online convex optimization problem by relaxing the convexity assumption on the cost function. For this type of problem, the classic exponential weighting online algorithm has recently been shown to attain a sub-linear regret of $O(\sqrt{T\log T})$. In this paper, we introduce a novel recursive structure to the online algorithm to define a recursive exponential weighting algorithm that attains a regret of $O(\sqrt{T})$, matching the well-known regret lower bound. To the best of our knowledge, this is the first online algorithm with provable $O(\sqrt{T})$ regret for the online non-convex optimization problem.
On the Accuracy of Formal Verification of Selective Defenses for TDoS Attacks
Venue: arXiv cs.NI 2017
Year: 2017

Telephony Denial of Service (TDoS) attacks target telephony services, such as Voice over IP (VoIP), not allowing legitimate users to make calls. There are few defenses that attempt to mitigate TDoS attacks, most of them using IP filtering, with limited applicability. In our previous work, we proposed to use selective strategies for mitigating HTTP Application-Layer DDoS Attacks demonstrating their effectiveness in mitigating different types of attacks. Developing such types of defenses is challenging as there are many design options, eg, which dropping functions and selection algorithms to use. Our first contribution is to demonstrate both experimentally and by using formal verification that selective strategies are suitable for mitigating TDoS attacks. We used our formal model to help decide which selective strategies to use with much less effort than carrying out experiments. Our second contribution is a detailed comparison of the results obtained from our formal models and the results obtained by carrying out experiments. We demonstrate that formal methods is a powerful tool for specifying defenses for mitigating Distributed Denial of Service attacks allowing to increase our confidence on the proposed defense before actual implementation.
Charge-based computing with analogue reconfigurable gates
Venue: arXiv cs.ET 2017
Year: 2017

As the world enters the age of ubiquitous computing, the need for reconfigurable hardware operating close to the fundamental limits of energy consumption becomes increasingly pressing. Simultaneously, scaling-driven performance improvements within the framework of traditional analogue and digital design become progressively more restricted by fundamental physical constraints. Thus, a true paradigm shift in electronics design is required for fuelling the next big burst in technology. Here we lay the foundations of a new design paradigm that fuses analogue and digital thinking by combining digital electronics with memristive devices for achieving charge-based computation; information processing where every dissipated charge counts. This is realised by introducing memristive devices into standard logic gates, thus rendering them reconfigurable and able to perform analogue computation at a power cost close to digital. The power of this concept is then showcased by experimentally demonstrating a hardware data clusterer and a fuzzy NAND gate using this principle.
Assessing State-of-the-Art Sentiment Models on State-of-the-Art Sentiment Datasets
Venue: arXiv cs.CL 2017
Year: 2017

There has been a good amount of progress in sentiment analysis over the past 10 years, including the proposal of new methods and the creation of benchmark datasets. In some papers, however, there is a tendency to compare models only on one or two datasets, either because of time restraints or because the model is tailored to a specific task. Accordingly, it is hard to understand how well a certain model generalizes across different tasks and datasets. In this paper, we contribute to this situation by comparing several models on six different benchmarks, which belong to different domains and additionally have different levels of granularity (binary, 3-class, 4-class and 5-class). We show that Bi-LSTMs perform well across datasets and that both LSTMs and Bi-LSTMs are particularly good at fine-grained sentiment tasks (i. e., with more than two classes). Incorporating sentiment information into word embeddings during training gives good results for datasets that are lexically similar to the training data. With our experiments, we contribute to a better understanding of the performance of different model architectures on different data sets. Consequently, we detect novel state-of-the-art results on the SenTube datasets.
Power-Efficient and Secure WPCNs with Hardware Impairments and Non-Linear EH Circuit
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we design a robust resource allocation algorithm for a wireless-powered communication network (WPCN) taking into account residual hardware impairments (HWIs) at the transceivers, the imperfectness of the channel state information, and the non-linearity of practical radio frequency energy harvesting circuits. In order to ensure power-efficient secure communication, physical layer security techniques are exploited to deliberately degrade the channel quality of a multiple-antenna eavesdropper. The resource allocation algorithm design is formulated as a non-convex optimization problem for minimization of the total consumed power in the network, while guaranteeing the quality of service of the information receivers in terms of secrecy rate. The globally optimal solution of the optimization problem is obtained via a two-dimensional search and semidefinite programming relaxation. To strike a balance between computational complexity and system performance, a low-complexity iterative suboptimal resource allocation algorithm is then proposed. Numerical results demonstrate that both the proposed optimal and suboptimal schemes can significantly reduce the total system power consumption required for guaranteeing secure communication, and unveil the impact of HWIs on the system performance: (1) residual HWIs create a system performance bottleneck in the high transmit/receive power regimes; (2) increasing the number of transmit antennas can effectively reduce the system power consumption and alleviate the performance degradation due to residual HWIs; (3) imperfect CSI increases the system power consumption and exacerbates the impact of residual HWIs.
Spectral Efficiency of Multi-User Adaptive Cognitive Radio Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this correspondence, the comprehensive problem of joint power, rate, and subcarrier allocation have been investigated for enhancing the spectral efficiency of multi-user orthogonal frequency-division multiple access (OFDMA) cognitive radio (CR) networks subject to satisfying total average transmission power and aggregate interference constraints. We propose novel optimal radio resource allocation (RRA) algorithms under different scenarios with deterministic and probabilistic interference violation limits based on a perfect and imperfect availability of cross-link channel state information (CSI). In particular, we propose a probabilistic approach to mitigate the total imposed interference on the primary service under imperfect cross-link CSI. A closed-form mathematical formulation of the cumulative density function (cdf) for the received signal-to-interference-plus-noise ratio (SINR) is formulated to evaluate the resultant average spectral efficiency (ASE). Dual decomposition is utilized to obtain sub-optimal solutions for the non-convex optimization problems. Through simulation results, we investigate the achievable performance and the impact of parameters uncertainty on the overall system performance. Furthermore, we present that the developed RRA algorithms can considerably improve the cognitive performance whilst abide the imposed power constraints. In particular, the performance under imperfect cross-link CSI knowledge for the proposed `probabilistic case' is compared to the conventional scenarios to show the potential gain in employing this scheme.
Accelerating Analytical Processing in MVCC using Fine-Granular High-Frequency Virtual Snapshotting
Venue: arXiv cs.DB 2017
Year: 2017

Efficient transactional management is a delicate task. As systems face transactions of inherently different types, ranging from point updates to long running analytical computations, it is hard to satisfy their individual requirements with a single processing component. Unfortunately, most systems nowadays rely on such a single component that implements its parallelism using multi-version concurrency control (MVCC). While MVCC parallelizes short-running OLTP transactions very well, it struggles in the presence of mixed workloads containing long-running scan-centric OLAP queries, as scans have to work their way through large amounts of versioned data. To overcome this problem, we propose a system, which reintroduces the concept of heterogeneous transaction processing: OLAP transactions are outsourced to run on separate (virtual) snapshots while OLTP transactions run on the most recent representation of the database. Inside both components, MVCC ensures a high degree of concurrency. The biggest challenge of such a heterogeneous approach is to generate the snapshots at a high frequency. Previous approaches heavily suffered from the tremendous cost of snapshot creation. In our system, we overcome the restrictions of the OS by introducing a custom system call vm_snapshot, that is hand-tailored to our precise needs: it allows fine-granular snapshot creation at very high frequencies, rendering the snapshot creation phase orders of magnitudes faster than state-of-the-art approaches. Our experimental evaluation on a heterogeneous workload based on TPC-H transactions and handcrafted OLTP transactions shows that our system enables significantly higher analytical transaction throughputs on mixed workloads than homogeneous approaches. In this sense, we introduce a system that accelerates Analytical processing by introducing custom Kernel functionalities: AnKerDB.
Approximate Integration of streaming data
Venue: arXiv cs.SI 2017
Year: 2017

We approximate analytic queries on streaming data with a weighted reservoir sampling. For a stream of tuples of a Datawarehouse we show how to approximate some OLAP queries. For a stream of graph edges from a Social Network, we approximate the communities as the large connected components of the edges in the reservoir. We show that for a model of random graphs which follow a power law degree distribution, the community detection algorithm is a good approximation. Given two streams of graph edges from two Sources, we define the {\em Community Correlation} as the fraction of the nodes in communities in both streams. Although we do not store the edges of the streams, we can approximate the Community Correlation and define the {\em Integration of two streams}. We illustrate this approach with Twitter streams, associated with TV programs.
Reading Scene Text with Attention Convolutional Sequence Modeling
Venue: arXiv cs.CV 2017
Year: 2017

Reading text in the wild is a challenging task in the field of computer vision. Existing approaches mainly adopted Connectionist Temporal Classification (CTC) or Attention models based on Recurrent Neural Network (RNN), which is computationally expensive and hard to train. In this paper, we present an end-to-end Attention Convolutional Network for scene text recognition. Firstly, instead of RNN, we adopt the stacked convolutional layers to effectively capture the contextual dependencies of the input sequence, which is characterized by lower computational complexity and easier parallel computation. Compared to the chain structure of recurrent networks, the Convolutional Neural Network (CNN) provides a natural way to capture long-term dependencies between elements, which is 9 times faster than Bidirectional Long Short-Term Memory (BLSTM). Furthermore, in order to enhance the representation of foreground text and suppress the background noise, we incorporate the residual attention modules into a small densely connected network to improve the discriminability of CNN features. We validate the performance of our approach on the standard benchmarks, including the Street View Text, IIIT5K and ICDAR datasets. As a result, state-of-the-art or highly-competitive performance and efficiency show the superiority of the proposed approach.
Power Optimizations in MTJ-based Neural Networks through Stochastic Computing
Venue: arXiv cs.NE 2017
Year: 2017

Artificial Neural Networks (ANNs) have found widespread applications in tasks such as pattern recognition and image classification. However, hardware implementations of ANNs using conventional binary arithmetic units are computationally expensive, energy-intensive and have large area overheads. Stochastic Computing (SC) is an emerging paradigm which replaces these conventional units with simple logic circuits and is particularly suitable for fault-tolerant applications. Spintronic devices, such as Magnetic Tunnel Junctions (MTJs), are capable of replacing CMOS in memory and logic circuits. In this work, we propose an energy-efficient use of MTJs, which exhibit probabilistic switching behavior, as Stochastic Number Generators (SNGs), which forms the basis of our NN implementation in the SC domain. Further, error resilient target applications of NNs allow us to introduce Approximate Computing, a framework wherein accuracy of computations is traded-off for substantial reductions in power consumption. We propose approximating the synaptic weights in our MTJ-based NN implementation, in ways brought about by properties of our MTJ-SNG, to achieve energy-efficiency. We design an algorithm that can perform such approximations within a given error tolerance in a single-layer NN in an optimal way owing to the convexity of the problem formulation. We then use this algorithm and develop a heuristic approach for approximating multi-layer NNs. To give a perspective of the effectiveness of our approach, a 43% reduction in power consumption was obtained with less than 1% accuracy loss on a standard classification problem, with 26% being brought about by the proposed algorithm.