OpenRaiser/Intern-Atlas huggingface dataset:
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
Venue: arXiv cs.CC 2017
Year: 2017

We study the class $\textrm{AC}^0$ of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean class $\textrm{AC}^0$, we remedy this situation and develop such a characterization of $\textrm{AC}^0$. Our characterization can be interpreted as follows: Functions in $\textrm{AC}^0$ are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of $\textrm{TC}^0$, the class of languages accepted by constant-depth polynomial-size majority circuits.
Detecting One-variable Patterns
Venue: arXiv cs.DS 2017
Year: 2017

Given a pattern $p = s_1x_1s_2x_2\cdots s_{r-1}x_{r-1}s_r$ such that $x_1,x_2,\ldots,x_{r-1}\in\{x,\overset{{}_{\leftarrow}}{x}\}$, where $x$ is a variable and $\overset{{}_{\leftarrow}}{x}$ its reversal, and $s_1,s_2,\ldots,s_r$ are strings that contain no variables, we describe an algorithm that constructs in $O(rn)$ time a compact representation of all $P$ instances of $p$ in an input string of length $n$ over a polynomially bounded integer alphabet, so that one can report those instances in $O(P)$ time.
Allocation Schemes of Ressources with Downgrading
Venue: arXiv cs.NI 2017
Year: 2017

We consider a server with large capacity delivering video files encoded in various resolutions. We assume that the system is under saturation in the sense that the total demand exceeds the server capacity $C$. In such a case, requests may be rejected. For the policies considered in this paper, instead of rejecting a video request, it is downgraded. When the occupancy of the server is above some value $C_0{<}C$, the server delivers the video at a minimal bit rate. The quantity $C_0$ is the bit rate adaptation threshold. For these policies, request blocking is thus replaced by bit rate adaptation. Under the assumptions of Poisson request arrivals and exponential service times, we show that, by rescaling the system, a process associated to the occupancy of the server converges to some limiting process whose invariant distribution is computed by a Wiener-Hopf technique. This allows us to derive an asymptotic expression of the key performance measure of such a policy, the equilibrium probability that a request is transmitted without downgrading. Numerical applications of these results are presented.
Integrating Local Material Recognition with Large-Scale Perceptual Attribute Discovery
Venue: arXiv cs.CV 2017
Year: 2017

Material attributes have been shown to provide a discriminative intermediate representation for recognizing materials, especially for the challenging task of recognition from local material appearance (i.e., regardless of object and scene context). In the past, however, material attributes have been recognized separately preceding category recognition. In contrast, neuroscience studies on material perception and computer vision research on object and place recognition have shown that attributes are produced as a by-product during the category recognition process. Does the same hold true for material attribute and category recognition? In this paper, we introduce a novel material category recognition network architecture to show that perceptual attributes can, in fact, be automatically discovered inside a local material recognition framework. The novel material-attribute-category convolutional neural network (MAC-CNN) produces perceptual material attributes from the intermediate pooling layers of an end-to-end trained category recognition network using an auxiliary loss function that encodes human material perception. To train this model, we introduce a novel large-scale database of local material appearance organized under a canonical material category taxonomy and careful image patch extraction that avoids unwanted object and scene context. We show that the discovered attributes correspond well with semantically-meaningful visual material traits via Boolean algebra, and enable recognition of previously unseen material categories given only a few examples. These results have strong implications in how perceptually meaningful attributes can be learned in other recognition tasks.
Isolate First, Then Share: a New OS Architecture for Datacenter Computing
Venue: arXiv cs.OS 2017
Year: 2017

This paper presents the "isolate first, then share" OS model in which the processor cores, memory, and devices are divided up between disparate OS instances and a new abstraction, subOS, is proposed to encapsulate an OS instance that can be created, destroyed, and resized on-the-fly. The intuition is that this avoids shared kernel states between applications, which in turn reduces performance loss caused by contention. We decompose the OS into the supervisor and several subOSes running at the same privilege level: a subOS directly manages physical resources, while the supervisor can create, destroy, resize a subOS on-the-fly. The supervisor and subOSes have few state sharing, but fast inter-subOS communication mechanisms are provided on demand. We present the first implementation, RainForest, which supports unmodified Linux binaries. Our comprehensive evaluation shows RainForest outperforms Linux with four different kernels, LXC, and Xen in terms of worst-case and average performance most of time when running a large number of benchmarks. The source code is available soon.
Free-Space Detection with Self-Supervised and Online Trained Fully Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Recently, vision-based Advanced Driver Assist Systems have gained broad interest. In this work, we investigate free-space detection, for which we propose to employ a Fully Convolutional Network (FCN). We show that this FCN can be trained in a self-supervised manner and achieve similar results compared to training on manually annotated data, thereby reducing the need for large manually annotated training sets. To this end, our self-supervised training relies on a stereo-vision disparity system, to automatically generate (weak) training labels for the color-based FCN. Additionally, our self-supervised training facilitates online training of the FCN instead of offline. Consequently, given that the applied FCN is relatively small, the free-space analysis becomes highly adaptive to any traffic scene that the vehicle encounters. We have validated our algorithm using publicly available data and on a new challenging benchmark dataset that is released with this paper. Experiments show that the online training boosts performance with 5% when compared to offline training, both for Fmax and AP.
T-CNN: Tubelets with Convolutional Neural Networks for Object Detection from Videos
Venue: arXiv cs.CV 2017
Year: 2017

The state-of-the-art performance for object detection has been significantly improved over the past two years. Besides the introduction of powerful deep neural networks such as GoogleNet and VGG, novel object detection frameworks such as R-CNN and its successors, Fast R-CNN and Faster R-CNN, play an essential role in improving the state-of-the-art. Despite their effectiveness on still images, those frameworks are not specifically designed for object detection from videos. Temporal and contextual information of videos are not fully investigated and utilized. In this work, we propose a deep learning framework that incorporates temporal and contextual information from tubelets obtained in videos, which dramatically improves the baseline performance of existing still-image detection frameworks when they are applied to videos. It is called T-CNN, i.e. tubelets with convolutional neueral networks. The proposed framework won the recently introduced object-detection-from-video (VID) task with provided data in the ImageNet Large-Scale Visual Recognition Challenge 2015 (ILSVRC2015).
TextProposals: a Text-specific Selective Search Algorithm for Word Spotting in the Wild
Venue: arXiv cs.CV 2017
Year: 2017

Motivated by the success of powerful while expensive techniques to recognize words in a holistic way, object proposals techniques emerge as an alternative to the traditional text detectors. In this paper we introduce a novel object proposals method that is specifically designed for text. We rely on a similarity based region grouping algorithm that generates a hierarchy of word hypotheses. Over the nodes of this hierarchy it is possible to apply a holistic word recognition method in an efficient way. Our experiments demonstrate that the presented method is superior in its ability of producing good quality word proposals when compared with class-independent algorithms. We show impressive recall rates with a few thousand proposals in different standard benchmarks, including focused or incidental text datasets, and multi-language scenarios. Moreover, the combination of our object proposals with existing whole-word recognizers shows competitive performance in end-to-end word spotting, and, in some benchmarks, outperforms previously published results. Concretely, in the challenging ICDAR2015 Incidental Text dataset, we overcome in more than 10 percent f-score the best-performing method in the last ICDAR Robust Reading Competition. Source code of the complete end-to-end system is available at https://github.com/lluisgomez/TextProposals
Synthesizing Training Images for Boosting Human 3D Pose Estimation
Venue: arXiv cs.CV 2017
Year: 2017

Human 3D pose estimation from a single image is a challenging task with numerous applications. Convolutional Neural Networks (CNNs) have recently achieved superior performance on the task of 2D pose estimation from a single image, by training on images with 2D annotations collected by crowd sourcing. This suggests that similar success could be achieved for direct estimation of 3D poses. However, 3D poses are much harder to annotate, and the lack of suitable annotated training images hinders attempts towards end-to-end solutions. To address this issue, we opt to automatically synthesize training images with ground truth pose annotations. Our work is a systematic study along this road. We find that pose space coverage and texture diversity are the key ingredients for the effectiveness of synthetic training data. We present a fully automatic, scalable approach that samples the human pose space for guiding the synthesis procedure and extracts clothing textures from real images. Furthermore, we explore domain adaptation for bridging the gap between our synthetic training images and real testing photos. We demonstrate that CNNs trained with our synthetic images out-perform those trained with real photos on 3D pose estimation tasks.
Fast Failure Recovery for Main-Memory DBMSs on Multicores
Venue: arXiv cs.DB 2017
Year: 2017

Main-memory database management systems (DBMS) can achieve excellent performance when processing massive volume of on-line transactions on modern multi-core machines. But existing durability schemes, namely, tuple-level and transaction-level logging-and-recovery mechanisms, either degrade the performance of transaction processing or slow down the process of failure recovery. In this paper, we show that, by exploiting application semantics, it is possible to achieve speedy failure recovery without introducing any costly logging overhead to the execution of concurrent transactions. We propose PACMAN, a parallel database recovery mechanism that is specifically designed for lightweight, coarse-grained transaction-level logging. PACMAN leverages a combination of static and dynamic analyses to parallelize the log recovery: at compile time, PACMAN decomposes stored procedures by carefully analyzing dependencies within and across programs; at recovery time, PACMAN exploits the availability of the runtime parameter values to attain an execution schedule with a high degree of parallelism. As such, recovery performance is remarkably increased. We evaluated PACMAN in a fully-fledged main-memory DBMS running on a 40-core machine. Compared to several state-of-the-art database recovery mechanisms, PACMAN can significantly reduce recovery time without compromising the efficiency of transaction processing.
From Pixels to Sentiment: Fine-tuning CNNs for Visual Sentiment Prediction
Venue: arXiv cs.CV 2017
Year: 2017

Visual multimedia have become an inseparable part of our digital social lives, and they often capture moments tied with deep affections. Automated visual sentiment analysis tools can provide a means of extracting the rich feelings and latent dispositions embedded in these media. In this work, we explore how Convolutional Neural Networks (CNNs), a now de facto computational machine learning tool particularly in the area of Computer Vision, can be specifically applied to the task of visual sentiment prediction. We accomplish this through fine-tuning experiments using a state-of-the-art CNN and via rigorous architecture analysis, we present several modifications that lead to accuracy improvements over prior art on a dataset of images from a popular social media platform. We additionally present visualizations of local patterns that the network learned to associate with image sentiment for insight into how visual positivity (or negativity) is perceived by the model.
Moving Beyond the Turing Test with the Allen AI Science Challenge
Venue: arXiv cs.AI 2017
Year: 2017

Given recent successes in AI (e.g., AlphaGo's victory against Lee Sedol in the game of GO), it's become increasingly important to assess: how close are AI systems to human-level intelligence? This paper describes the Allen AI Science Challenge---an approach towards that goal which led to a unique Kaggle Competition, its results, the lessons learned, and our next steps.
On the Performance of Channel Statistics-Based Codebook for Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

The channel feedback overhead for massive MIMO systems with a large number of base station (BS) antennas is very high, since the number of feedback bits of traditional codebooks scales linearly with the number of BS antennas. To reduce the feedback overhead, an effective codebook based on channel statistics has been designed, where the required number of feedback bits only scales linearly with the rank of the channel correlation matrix. However, this attractive conclusion was only intuitively explained and then verified through simulation results in the literature, while no rigorous theoretical proof has been provided. To fill in the gap between the theoretical conclusion and simulation results, in this paper, we quantitatively analyze the performance of the channel statistics-based codebook. Specifically, we firstly introduce the rate gap between the ideal case of perfect channel state information at the transmitter and the practical case of limited channel feedback, where we find that the rate gap is dependent on the quantization error of the codebook. Then, we derive an upper bound of the quantization error, based on which we prove that the required feedback bits to ensure a constant rate gap only scales linearly with the rank of the channel correlation matrix. Finally, numerical results are provided to verify this conclusion. To the best of our knowledge, our work is the first one to provide a rigorous proof of this conclusion.
Locating a Small Cluster Privately
Venue: arXiv cs.DS 2017
Year: 2017

We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal of outliers. Furthermore, we use it to significantly relax the requirements of the sample and aggregate technique [Nissim, Raskhodnikova, and Smith, 2007], which allows compiling of "off the shelf" (non-private) analyses into analyses that preserve differential privacy.
Estimating 3D Trajectories from 2D Projections via Disjunctive Factored Four-Way Conditional Restricted Boltzmann Machines
Venue: arXiv cs.CV 2017
Year: 2017

Estimation, recognition, and near-future prediction of 3D trajectories based on their two dimensional projections available from one camera source is an exceptionally difficult problem due to uncertainty in the trajectories and environment, high dimensionality of the specific trajectory states, lack of enough labeled data and so on. In this article, we propose a solution to solve this problem based on a novel deep learning model dubbed Disjunctive Factored Four-Way Conditional Restricted Boltzmann Machine (DFFW-CRBM). Our method improves state-of-the-art deep learning techniques for high dimensional time-series modeling by introducing a novel tensor factorization capable of driving forth order Boltzmann machines to considerably lower energy levels, at no computational costs. DFFW-CRBMs are capable of accurately estimating, recognizing, and performing near-future prediction of three-dimensional trajectories from their 2D projections while requiring limited amount of labeled data. We evaluate our method on both simulated and real-world data, showing its effectiveness in predicting and classifying complex ball trajectories and human activities.
Enhancing Multiuser MIMO Through Opportunistic D2D Cooperation
Venue: arXiv cs.IT 2017
Year: 2017

We propose a cellular architecture that combines multiuser MIMO (MU-MIMO) downlink with opportunistic use of unlicensed ISM bands to establish device-to-device (D2D) cooperation. The architecture consists of a physical-layer cooperation scheme based on forming downlink virtual MIMO channels through D2D relaying, and a novel resource allocation strategy for such D2D-enabled networks. We prove the approximate optimality of the physical-layer scheme, and demonstrate that such cooperation boosts the effective SNR of the weakest user in the system, especially in the many-user regime, due to multiuser diversity. To harness this physical-layer scheme, we formulate the cooperative user scheduling and relay selection problem using the network utility maximization framework. For such a cooperative network, we propose a novel utility metric that jointly captures fairness in throughput and the cost of relaying in the system. We propose a joint user scheduling and relay selection algorithm, which we prove to be asymptotically optimal. We study the architecture through system-level simulations over a wide range of scenarios. The highlight of these simulations is an approximately $6$x improvement in data rate for cell-edge (bottom fifth-percentile) users (over the state-of-the-art SU-MIMO) while still improving the overall throughput, and taking into account various system constraints.
A note on the multiple-recursive matrix method for generating pseudorandom vectors
Venue: arXiv cs.CR 2017
Year: 2017

The multiple-recursive matrix method for generating pseudorandom vectors was introduced by Niederreiter (Linear Algebra Appl. 192 (1993), 301-328). We propose an algorithm for finding an efficient primitive multiple-recursive matrix method. Moreover, for improving the linear complexity, we introduce a tweak on the contents of the primitive multiple-recursive matrix method.
Online Combinatorial Optimization for Interconnected Refrigeration Systems: Linear Approximation and Submodularity
Venue: arXiv cs.SY 2017
Year: 2017

Commercial refrigeration systems consume 7% of the total commercial energy consumption in the United States. Improving their energy efficiency contributes to the sustainability of global energy systems and the supermarket business sector. This paper proposes a new control method that can save the energy consumption of multi-case supermarket refrigerators by explicitly taking into account their interconnected and switched system dynamics. Its novelty is a bilevel combinatorial optimization formulation to generate ON/OFF control actions for expansion valves and compressors. The inner optimization module keeps display case temperatures in a desirable range and the outer optimization module minimizes energy consumption. In addition to its energy-saving capability, the proposed controller significantly reduces the frequency of compressor switchings by employing a conservative compressor control strategy. However, solving this bilevel optimization problem associated with interconnected and switched systems is a computationally challenging task. To solve the problem in near real time, we propose two approximation algorithms that can solve both the inner and outer optimization problems at once. The first algorithm uses a linear approximation, and the second is based on the submodular structure of the optimization problem. Both are (polynomial-time) scalable algorithms and generate near-optimal solutions with performance guarantees. Our work complements existing optimization-based control methods (e.g., MPC) for supermarket refrigerators, as our algorithms can be adopted as a tool for solving combinatorial optimization problems arising in these methods.
Effect of User Mobility on the Performance of Device-to-Device Networks with Distributed Caching
Venue: arXiv cs.IT 2017
Year: 2017

We consider a distributed caching device-to-device (D2D) network in which a user's file of interest is cached as several portions in the storage of other devices in the network. Assuming that the user needs to obtain all these file portions, the portions cached farther away naturally become the performance bottleneck. This is due to the fact that dominant interferers may be closer to the receiver than the serving device. Using a simple stochastic geometry model, we concretely demonstrate that this bottleneck can be loosened if the users are mobile. Gains obtained from mobility are quantified in terms of coverage probability.
Modeling and Efficient Verification of Wireless Ad hoc Networks
Venue: arXiv cs.NI 2017
Year: 2017

Wireless ad hoc networks, in particular mobile ad hoc networks (MANETs), are growing very fast as they make communication easier and more available. However, their protocols tend to be difficult to design due to topology dependent behavior of wireless communication, and their distributed and adaptive operations to topology dynamism. Therefore, it is desirable to have them modeled and verified using formal methods. In this paper, we present an actor-based modeling language with the aim to model MANETs. We address main challenges of modeling wireless ad hoc networks such as local broadcast, underlying topology, and its changes, and discuss how they can be efficiently modeled at the semantic level to make their verification amenable. The new framework abstracts the data link layer services by providing asynchronous (local) broadcast and unicast communication, while message delivery is in order and is guaranteed for connected receivers. We illustrate the applicability of our framework through two routing protocols, namely flooding and AODVv2-11, and show how efficiently their state spaces can be reduced by the proposed techniques. Furthermore, we demonstrate a loop formation scenario in AODV, found by our analysis tool.
Learning Arbitrary Sum-Product Network Leaves with Expectation-Maximization
Venue: arXiv cs.LG 2017
Year: 2017

Sum-Product Networks with complex probability distribution at the leaves have been shown to be powerful tractable-inference probabilistic models. However, while learning the internal parameters has been amply studied, learning complex leaf distribution is an open problem with only few results available in special cases. In this paper we derive an efficient method to learn a very large class of leaf distributions with Expectation-Maximization. The EM updates have the form of simple weighted maximum likelihood problems, allowing to use any distribution that can be learned with maximum likelihood, even approximately. The algorithm has cost linear in the model size and converges even if only partial optimizations are performed. We demonstrate this approach with experiments on twenty real-life datasets for density estimation, using tree graphical models as leaves. Our model outperforms state-of-the-art methods for parameter learning despite using SPNs with much fewer parameters.