OpenRaiser/Intern-Atlas huggingface dataset:
ICE: A General and Validated Energy Complexity Model for Multithreaded Algorithms
Venue: arXiv cs.DC 2016
Year: 2016

Like time complexity models that have significantly contributed to the analysis and development of fast algorithms, energy complexity models for parallel algorithms are desired as crucial means to develop energy efficient algorithms for ubiquitous multicore platforms. Ideal energy complexity models should be validated on real multicore platforms and applicable to a wide range of parallel algorithms. However, existing energy complexity models for parallel algorithms are either theoretical without model validation or algorithm-specific without ability to analyze energy complexity for a wide-range of parallel algorithms. This paper presents a new general validated energy complexity model for parallel (multithreaded) algorithms. The new model abstracts away possible multicore platforms by their static and dynamic energy of computational operations and data access, and derives the energy complexity of a given algorithm from its work, span and I/O complexity. The new model is validated by different sparse matrix vector multiplication (SpMV) algorithms and dense matrix multiplication (matmul) algorithms running on high performance computing (HPC) platforms (e.g., Intel Xeon and Xeon Phi). The new energy complexity model is able to characterize and compare the energy consumption of SpMV and matmul kernels according to three aspects: different algorithms, different input matrix types and different platforms. The prediction of the new model regarding which algorithm consumes more energy with different inputs on different platforms, is confirmed by the experimental results. In order to improve the usability and accuracy of the new model for a wide range of platforms, the platform parameters of ICE model are provided for eleven platforms including HPC, accelerator and embedded platforms.
Theano-MPI: a Theano-based Distributed Training Framework
Venue: arXiv cs.LG 2016
Year: 2016

We develop a scalable and extendable training framework that can utilize GPUs across nodes in a cluster and accelerate the training of deep learning models based on data parallelism. Both synchronous and asynchronous training are implemented in our framework, where parameter exchange among GPUs is based on CUDA-aware MPI. In this report, we analyze the convergence and capability of the framework to reduce training time when scaling the synchronous training of AlexNet and GoogLeNet from 2 GPUs to 8 GPUs. In addition, we explore novel ways to reduce the communication overhead caused by exchanging parameters. Finally, we release the framework as open-source for further research on distributed deep learning
Distributed Gauss-Newton Method for AC State Estimation: A Belief Propagation Approach
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a solution to an AC state estimation problem in electric power systems using a fully distributed Gauss-Newton method. The proposed method is placed within the context of factor graphs and belief propagation algorithms and closed-form expressions for belief propagation messages exchanged along the factor graph are derived. The obtained algorithm provides the same solution as the conventional weighted least-squares state estimation. Using a simple example, we provide a step-by-step presentation of the proposed algorithm. Finally, we discuss the convergence behaviour using the IEEE 14 bus test case.
Agent-based model of information spread in social networks
Venue: arXiv cs.SI 2016
Year: 2016

We propose evolution rules of the multiagent network and determine statistical patterns in life cycle of agents - information messages. The main discussed statistical pattern is connected with the number of likes and reposts for a message. This distribution corresponds to Weibull distribution according to modeling results. We examine proposed model using the data from Twitter, an online social networking service.
A Feature based Approach for Video Compression
Venue: arXiv cs.CV 2016
Year: 2016

It is a high cost problem for panoramic image stitching via image matching algorithm and not practical for real-time performance. In this paper, we take full advantage ofHarris corner invariant characterization method light intensity parallel meaning, translation and rotation, and made a realtime panoramic image stitching algorithm. According to the basic characteristics and performance FPGA classical algorithm, several modules such as the feature point extraction, and matching description is to optimize the feature-based logic. Real-time optimization system to achieve high precision match. The new algorithm process the image from pixel domain and obtained from CCD camera Xilinx Spartan-6 hardware platform. After the image stitching algorithm, will eventually form a portable interface to output high-definition content on the display. The results showed that, the proposed algorithm has higher precision with good real-time performance and robustness.
Networks of Gratitude: Structures of Thanks and User Expectations in Workplace Appreciation Systems
Venue: arXiv cs.CY 2016
Year: 2016

Appreciation systems--platforms for users to exchange thanks and praise--are becoming common in the workplace, where employees share appreciation, managers are notified, and aggregate scores are sometimes made visible. Who do people thank on these systems, and what do they expect from each other and their managers? After introducing the design affordances of 13 appreciation systems, we discuss a system we call Gratia, in use at a large multinational company for over four years. Using logs of 422,000 appreciation messages and user surveys, we explore the social dynamics of use and ask if use of the system addresses the recognition problem. We find that while thanks is mostly exchanged among employees at the same level and different parts of the company, addressing the recognition problem, managers do not always act on that recognition in ways that employees expect.
SNN: Stacked Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

It has been proven that transfer learning provides an easy way to achieve state-of-the-art accuracies on several vision tasks by training a simple classifier on top of features obtained from pre-trained neural networks. The goal of this work is to generate better features for transfer learning from multiple publicly available pre-trained neural networks. To this end, we propose a novel architecture called Stacked Neural Networks which leverages the fast training time of transfer learning while simultaneously being much more accurate. We show that using a stacked NN architecture can result in up to 8% improvements in accuracy over state-of-the-art techniques using only one pre-trained network for transfer learning. A second aim of this work is to make network fine- tuning retain the generalizability of the base network to unseen tasks. To this end, we propose a new technique called "joint fine-tuning" that is able to give accuracies comparable to finetuning the same network individually over two datasets. We also show that a jointly finetuned network generalizes better to unseen tasks when compared to a network finetuned over a single task.
Stochastic Online Control for Energy-Harvesting Wireless Networks with Battery Imperfections
Venue: arXiv cs.IT 2016
Year: 2016

In energy harvesting (EH) network, the energy storage devices (i.e., batteries) are usually not perfect. In this paper, we consider a practical battery model with finite battery capacity, energy (dis-)charging loss, and energy dissipation. Taking into account such battery imperfections, we rely on the Lyapunov optimization technique to develop a stochastic online control scheme that aims to maximize the utility of data rates for EH multi-hop wireless networks. It is established that the proposed algorithm can provide a feasible and efficient data admission, power allocation, routing and scheduling solution, without requiring any statistical knowledge of the stochastic channel, data-traffic, and EH processes. Numerical results demonstrate the merit of the proposed scheme.
Energy-Efficient Resource Allocation for Mobile-Edge Computation Offloading (Extended Version)
Venue: arXiv cs.IT 2016
Year: 2016

Mobile-edge computation offloading (MECO) offloads intensive mobile computation to clouds located at the edges of cellular networks. Thereby, MECO is envisioned as a promising technique for prolonging the battery lives and enhancing the computation capacities of mobiles. In this paper, we study resource allocation for a multiuser MECO system based on time-division multiple access (TDMA) and orthogonal frequency-division multiple access (OFDMA). First, for the TDMA MECO system with infinite or finite computation capacity, the optimal resource allocation is formulated as a convex optimization problem for minimizing the weighted sum mobile energy consumption under the constraint on computation latency. The optimal policy is proved to have a threshold-based structure with respect to a derived offloading priority function, which yields priorities for users according to their channel gains and local computing energy consumption. As a result, users with priorities above and below a given threshold perform complete and minimum offloading, respectively. Moreover, for the cloud with finite capacity, a sub-optimal resource-allocation algorithm is proposed to reduce the computation complexity for computing the threshold. Next, we consider the OFDMA MECO system, for which the optimal resource allocation is formulated as a non-convex mixed-integer problem. To solve this challenging problem and characterize its policy structure, a sub-optimal low-complexity algorithm is proposed by transforming the OFDMA problem to its TDMA counterpart. The corresponding resource allocation is derived by defining an average offloading priority function and shown to have close-to-optimal performance by simulation.
Distributed controller-estimator for target tracking of networked robotic systems under sampled interaction
Venue: arXiv cs.SY 2016
Year: 2016

This paper investigates the target tracking problem for networked robotic systems (NRSs) under sampled interaction. The target is assumed to be time-varying and described by a second-order oscillator. Two novel distributed controller-estimator algorithms (DCEA), which consist of both continuous and discontinuous signals, are presented. Based on the properties of small-value norms and Lyapunov stability theory, the conditions on the interaction topology, the sampling period, and the other control parameters are given such that the practical stability of the tracking error is achieved and the stability region is regulated quantitatively. The advantages of the presented DCEA are illustrated by comparisons with each other and the existing coordination algorithms. Simulation examples are given to demonstrate the theoretical results.
Boosting Question Answering by Deep Entity Recognition
Venue: arXiv cs.CL 2016
Year: 2016

In this paper an open-domain factoid question answering system for Polish, RAFAEL, is presented. The system goes beyond finding an answering sentence; it also extracts a single string, corresponding to the required entity. Herein the focus is placed on different approaches to entity recognition, essential for retrieving information matching question constraints. Apart from traditional approach, including named entity recognition (NER) solutions, a novel technique, called Deep Entity Recognition (DeepER), is introduced and implemented. It allows a comprehensive search of all forms of entity references matching a given WordNet synset (e.g. an impressionist), based on a previously assembled entity library. It has been created by analysing the first sentences of encyclopaedia entries and disambiguation and redirect pages. DeepER also provides automatic evaluation, which makes possible numerous experiments, including over a thousand questions from a quiz TV show answered on the grounds of Polish Wikipedia. The final results of a manual evaluation on a separate question set show that the strength of DeepER approach lies in its ability to answer questions that demand answers beyond the traditional categories of named entities.
I Accidentally the Whole Internet
Venue: arXiv cs.NI 2016
Year: 2016

Whether as telecommunications or power systems, networks are very important in everyday life. Maintaining these networks properly functional and connected, even under attacks or failures, is of special concern. This topic has been previously studied with a whole network robustness perspective,modeling networks as undirected graphs (such as roads or simply cables). This perspective measures the average behavior of the network after its last node has failed. In this article we propose two alternatives to well-known studies about the robustness of the backbone Internet: to use a supply network model and metrics for its representation (we called it the Go-Index), and to use robustness metrics that can be calculated while disconnections appear. Our research question is: if a smart adversary has a limited number of strikes to attack the Internet, how much will the damage be after each one in terms of network disconnection? Our findings suggest that in order to design robust networks it might be better to have a complete view of the robustness evolution of the network, from both the infrastructure and the users perspective.
Fingerprintability of WebRTC
Venue: arXiv cs.CR 2016
Year: 2016

We examine WebRTC's suitability as a means of Internet censorship circumvention. WebRTC is a framework and suite of protocols for peer-to-peer communication between web browsers. We analyze the implementation differences in instantiations of WebRTC that make it possible to "fingerprint" implementations--potentially distinguishing circumvention-related uses from ordinary ones. This question is relevant to Snowflake, an upcoming circumvention system that uses WebRTC to turn web browsers into temporary peer-to-peer proxies. We conduct a manual analysis of WebRTC-using applications in order to map the space of distinguishing implementation features. We run a fingerprinting script on a day's worth of network traffic in order to quantify WebRTC's prevalence and diversity. Throughout, we find pitfalls that indicate that resisting fingerprinting in WebRTC is likely to be non-trivial.
Approximation of barter exchanges with cycle length constraints
Venue: arXiv cs.GT 2016
Year: 2016

We explore the clearing problem in the barter exchange market. The problem, described in the terminology of graph theory, is to find a set of vertex-disjoint, length-restricted cycles that maximize the total weight in a weighted digraph. The problem has previously been shown to be NP-hard. We advance the understanding of this problem by the following contributions. We prove three constant inapproximability results for this problem. For the weighted graphs, we prove that it is NP-hard to approximate the clearing problem within a factor of 14/13 under general length constraints and within a factor of 434/433 when the cycle length is not longer than 3. For the unweighted graphs, we prove that this problem is NP-hard to approximate within a factor of 698/697. For the unweighted graphs when the cycle length is not longer than 3, we design and implement two simple and practical algorithms. Experiments on simulated data suggest that these algorithms yield excellent performances.
Logic of Local Inference for Contextuality in Quantum Physics and Beyond
Venue: arXiv cs.LO 2016
Year: 2016

Contextuality in quantum physics provides a key resource for quantum information and computation. The topological approach in [Abramsky and Brandenburger, New J. Phys., 2011, Abramsky et al., CSL 2015, 2015] characterizes contextuality as "global inconsistency" coupled with "local consistency", revealing it to be a phenomenon also found in many other fields. This has yielded a logical method of detecting and proving the "global inconsistency" part of contextuality. Our goal is to capture the other, "local consistency" part, which requires a novel approach to logic that is sensitive to the topology of contexts. To achieve this, we formulate a logic of local inference by using context-sensitive theories and models in regular categories. This provides a uniform framework for local consistency, and lays a foundation for high-level methods of detecting, proving, and moreover using contextuality as computational resource.
2-Dimensional Finite Impulse Response Graph-Temporal Filters
Venue: arXiv cs.SY 2016
Year: 2016

Finite impulse response (FIR) graph filters play a crucial role in the field of signal processing on graphs. However, when the graph signal is time-varying, the state of the art FIR graph filters do not capture the time variations of the input signal. In this work, we propose an extension of FIR graph filters to capture also the signal variations over time. By considering also the past values of the graph signal, the proposed FIR graph filter extends naturally to a 2-dimensional filter, capturing jointly the signal variations over the graph and time. As a particular case of interest we focus on 2-dimensional separable graph-temporal filters, which can be implemented in a distributed fashion at the price of higher communication costs. This allows us to give filter specifications and perform the design independently in the graph and temporal domain. The work is concluded by analyzing the proposed approach for stochastic graph signals, where the first and second order moments of the output signal are characterized.
SUIS: An Online Graphical Signature-Based User Identification System
Venue: arXiv cs.CR 2016
Year: 2016

Humans possess a large amount of, and almost limitless, visual memory, that assists them to remember pictures far better than words. This phenomenon has recently motivated the computer security researchers' in academia and industry to design and develop graphical user identification systems (GUISs). Cognometric GUISs are more memorable than drawmetric GUISs, but takes more time to authenticate. None of the previously proposed GUISs combines the advantages of both cognometric and drawmetric systems. A signature personify a person and a graphical signature is easier to recall than other drawings. This paper proposes a new graphical Signature-based User Identification System named SUIS. It is based on a 2D grid technology, that is used to draw, digitize and store the signature for user identification. SUIS is categorized as both a cognometric and drawmetric system. Unlike other systems that use 2D grid: We take one cell in a grid as one pixel in the drawing; for signature matching, the signature drawn has to follow the same grid cells as the signature stored, independent of the sequence; and that the system is not based on any machine learning model. Increasing the number of grid cells increases the password space, and decreasing the size of the grid cell increases the precision of the signature. These characteristics makes SUIS: (1) Rigorous enough to be a password system, but easy enough to be usable. (2) Independent of the language and device used to draw the signature. (3) Efficient and practical to be used for online authentication systems.
Predicting Personal Traits from Facial Images using Convolutional Neural Networks Augmented with Facial Landmark Information
Venue: arXiv cs.CV 2016
Year: 2016

We consider the task of predicting various traits of a person given an image of their face. We estimate both objective traits, such as gender, ethnicity and hair-color; as well as subjective traits, such as the emotion a person expresses or whether he is humorous or attractive. For sizeable experimentation, we contribute a new Face Attributes Dataset (FAD), having roughly 200,000 attribute labels for the above traits, for over 10,000 facial images. Due to the recent surge of research on Deep Convolutional Neural Networks (CNNs), we begin by using a CNN architecture for estimating facial attributes and show that they indeed provide an impressive baseline performance. To further improve performance, we propose a novel approach that incorporates facial landmark information for input images as an additional channel, helping the CNN learn better attribute-specific features so that the landmarks across various training images hold correspondence. We empirically analyse the performance of our method, showing consistent improvement over the baseline across traits.
One-Pass Learning with Incremental and Decremental Features
Venue: arXiv cs.LG 2016
Year: 2016

In many real tasks the features are evolving, with some features being vanished and some other features augmented. For example, in environment monitoring some sensors expired whereas some new ones deployed; in mobile game recommendation some games dropped whereas some new ones added. Learning with such incremental and decremental features is crucial but rarely studied, particularly when the data coming like a stream and thus it is infeasible to keep the whole data for optimization. In this paper, we study this challenging problem and present the OPID approach. Our approach attempts to compress important information of vanished features into functions of survived features, and then expand to include the augmented features. It is the one-pass learning approach, which only needs to scan each instance once and does not need to store the whole data, and thus satisfy the evolving streaming data nature. The effectiveness of our approach is validated theoretically and empirically.
Zigzag Decodable Fountain Codes
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a fountain coding system which has lower space decoding complexity and lower decoding erasure rate than the Raptor coding systems. The main idea of the proposed fountain code is employing shift and exclusive OR to generate the output packets. This technique is known as the zigzag decodable code, which is efficiently decoded by the zigzag decoder. In other words, we propose a fountain code based on the zigzag decodable code in this paper. Moreover, we analyze the overhead for the received packets, decoding erasure rate, decoding complexity, and asymptotic overhead of the proposed fountain code. As the result, we show that the proposed fountain code outperforms the Raptor codes in terms of the overhead and decoding erasure rate. Simulation results show that the proposed fountain coding system outperforms Raptor coding system in terms of the overhead and the space decoding complexity.