OpenRaiser/Intern-Atlas huggingface dataset:
Hardware-Based Linear Program Decoding with the Alternating Direction Method of Multipliers
Venue: arXiv cs.IT 2016
Year: 2016

We present a hardware-based implementation of Linear Program (LP) decoding for binary linear codes. LP decoding frames error-correction as an optimization problem. In contrast, variants of Belief Propagation (BP) decoding frame error-correction as a problem of graphical inference. LP decoding has several advantages over BP-based methods, including convergence guarantees and better error-rate performance in high-reliability channels. The latter makes LP decoding attractive for optical transport and storage applications. However, LP decoding, when implemented with general solvers, does not scale to large blocklengths and is not suitable for a parallelized implementation in hardware. It has been recently shown that the Alternating Direction Method of Multipliers (ADMM) can be applied to decompose the LP decoding problem. The result is a message-passing algorithm with a structure very similar to BP. We present new intuition for this decoding algorithm as well as for its major computational primitive: projection onto the parity polytope. Furthermore, we present results for a fixed-point Verilog implementation of ADMM-LP decoding. This implementation targets a Field-Programmable Gate Array (FPGA) platform to evaluate error-rate performance and estimate resource usage. We show that Frame Error Rate (FER) performance well within 0.5dB of double-precision implementations is possible with 10-bit messages. Finally, we outline a number of research opportunities that should be explored en-route to the realization of an Application Specific Integrated Circuit (ASIC) implementation capable of gigabit per second throughput.
A Dissection of the Test-Driven Development Process: Does It Really Matter to Test-First or to Test-Last?
Venue: arXiv cs.SE 2016
Year: 2016

Background: Test-driven development (TDD) is a technique that repeats short coding cycles interleaved with testing. The developer first writes a unit test for the desired functionality, followed by the necessary production code, and refactors the code. Many empirical studies neglect unique process characteristics related to TDD iterative nature. Aim: We formulate four process characteristic: sequencing, granularity, uniformity, and refactoring effort. We investigate how these characteristics impact quality and productivity in TDD and related variations. Method: We analyzed 82 data points collected from 39 professionals, each capturing the process used while performing a specific development task. We built regression models to assess the impact of process characteristics on quality and productivity. Quality was measured by functional correctness. Result: Quality and productivity improvements were primarily positively associated with the granularity and uniformity. Sequencing, the order in which test and production code are written, had no important influence. Refactoring effort was negatively associated with both outcomes. We explain the unexpected negative correlation with quality by possible prevalence of mixed refactoring. Conclusion: The claimed benefits of TDD may not be due to its distinctive test-first dynamic, but rather due to the fact that TDD-like processes encourage fine-grained, steady steps that improve focus and flow.
Annex: Radon - Rapid Discovery of Topological Relations
Venue: arXiv cs.DB 2016
Year: 2016

Datasets containing geo-spatial resources are increasingly being represented according to the Linked Data principles. Several time-efficient approaches for discovering links between RDF resources have been developed over the last years. However, the time-efficient discovery of topological relations between geospatial resources has been paid little attention to. We address this research gap by presenting Radon, a novel approach for the rapid computation of topological relations between geo-spatial resources. Our approach uses a sparse tiling index in combination with minimum bounding boxes to reduce the computation time of topological relations. Our evaluation of Radon's runtime on 45 datasets and in more than 800 experiments shows that it outperforms the state of the art by up to 3 orders of magnitude while maintaining an F-measure of 100%. Moreover, our experiments suggest that Radon scales up well when implemented in parallel.
Faster variational inducing input Gaussian process classification
Venue: arXiv cs.LG 2016
Year: 2016

Gaussian processes (GP) provide a prior over functions and allow finding complex regularities in data. Gaussian processes are successfully used for classification/regression problems and dimensionality reduction. In this work we consider the classification problem only. The complexity of standard methods for GP-classification scales cubically with the size of the training dataset. This complexity makes them inapplicable to big data problems. Therefore, a variety of methods were introduced to overcome this limitation. In the paper we focus on methods based on so called inducing inputs. This approach is based on variational inference and proposes a particular lower bound for marginal likelihood (evidence). This bound is then maximized w.r.t. parameters of kernel function of the Gaussian process, thus fitting the model to data. The computational complexity of this method is $O(nm^2)$, where $m$ is the number of inducing inputs used by the model and is assumed to be substantially smaller than the size of the dataset $n$. Recently, a new evidence lower bound for GP-classification problem was introduced. It allows using stochastic optimization, which makes it suitable for big data problems. However, the new lower bound depends on $O(m^2)$ variational parameter, which makes optimization challenging in case of big m. In this work we develop a new approach for training inducing input GP models for classification problems. Here we use quadratic approximation of several terms in the aforementioned evidence lower bound, obtaining analytical expressions for optimal values of most of the parameters in the optimization, thus sufficiently reducing the dimension of optimization space. In our experiments we achieve as well or better results, compared to the existing method. Moreover, our method doesn't require the user to manually set the learning rate, making it more practical, than the existing method.
Parallelizing Word2Vec in Multi-Core and Many-Core Architectures
Venue: arXiv cs.DC 2016
Year: 2016

Word2vec is a widely used algorithm for extracting low-dimensional vector representations of words. State-of-the-art algorithms including those by Mikolov et al. have been parallelized for multi-core CPU architectures, but are based on vector-vector operations with "Hogwild" updates that are memory-bandwidth intensive and do not efficiently use computational resources. In this paper, we propose "HogBatch" by improving reuse of various data structures in the algorithm through the use of minibatching and negative sample sharing, hence allowing us to express the problem using matrix multiply operations. We also explore different techniques to distribute word2vec computation across nodes in a compute cluster, and demonstrate good strong scalability up to 32 nodes. The new algorithm is particularly suitable for modern multi-core/many-core architectures, especially Intel's latest Knights Landing processors, and allows us to scale up the computation near linearly across cores and nodes, and process hundreds of millions of words per second, which is the fastest word2vec implementation to the best of our knowledge.
Spikes as regularizers
Venue: arXiv cs.NE 2016
Year: 2016

We present a confidence-based single-layer feed-forward learning algorithm SPIRAL (Spike Regularized Adaptive Learning) relying on an encoding of activation spikes. We adaptively update a weight vector relying on confidence estimates and activation offsets relative to previous activity. We regularize updates proportionally to item-level confidence and weight-specific support, loosely inspired by the observation from neurophysiology that high spike rates are sometimes accompanied by low temporal precision. Our experiments suggest that the new learning algorithm SPIRAL is more robust and less prone to overfitting than both the averaged perceptron and AROW.
A Novel Single-Source Surface Integral Method to Compute Scattering from Dielectric Objects
Venue: arXiv cs.CE 2016
Year: 2016

Using the traditional surface integral methods, the computation of scattering from a dielectric object requires two equivalent current densities on the boundary of the dielectric. In this paper, we present an approach that requires only a single current density. Our method is based on a surface admittance operator and is applicable to dielectric bodies of arbitrary shape. The formulation results in four times lower memory consumption and up to eight times lower time to solve the linear system than the traditional PMCHWT formulation. Numerical results demonstrate that the proposed technique is as accurate as the PMCHWT formulation.
Content-Centric and Software-Defined Networking with Big Data
Venue: arXiv cs.NI 2016
Year: 2016

Many communities have researched the application of novel network architectures such as Content-Centric Networking (CCN) and Software-Defined Networking (SDN) to build the future Internet. Another emerging technology which is big data analysis has also won lots of attentions from academia to industry. Many splendid researches have been done on CCN, SDN, and big data, which all have addressed separately in the traditional literature. In this paper, we propose a novel network paradigm to jointly consider CCN, SDN, and big data, and provide the architecture internal data flow, big data processing and use cases which indicate the benefits and applicability. Simulation results are exhibited to show the potential benefits relating to the proposed network paradigm. We refer to this novel paradigm as Data-Driven Networking (DDN).
Towards a Complete Framework for Virtual Data Center Embedding
Venue: arXiv cs.DC 2016
Year: 2016

Cloud computing is widely adopted by corporate as well as retail customers to reduce the upfront cost of establishing computing infrastructure. However, switching to the cloud based services poses a multitude of questions, both for customers and for data center owners. In this work, we propose an algorithm for optimal placement of multiple virtual data centers on a physical data center. Our algorithm has two modes of operation - an online mode and a batch mode. Coordinated batch and online embedding algorithms are used to maximize resource usage while fulfilling the QoS demands. Experimental evaluation of our algorithms show that acceptance rate is high - implying higher profit to infrastructure provider. Additionaly, we try to keep a check on the number of VM migrations, which can increase operational cost and thus lead to service level agreement violations.
Geometrically exact beam elements and smooth contact schemes for the modeling of fiber-based materials and structures
Venue: arXiv cs.CE 2016
Year: 2016

Recently, the authors have proposed a novel all-angle beam contact (ABC) formulation that combines the advantages of existing point and line contact models in a variationally consistent manner. However, the ABC formulation has so far only been applied in combination with a special torsion-free beam model, which yields a very simple and efficient finite element formulation, but which is restricted to initially straight beams with isotropic cross-sections. In order to abstain from these restrictions, the current work combines the ABC formulation with a geometrically exact Kirchhoff-Love beam element formulation that is capable of treating even the most general cases of slender beam problems in terms of initial geometry and external loads. While the neglect of shear deformation that is inherent to this formulation has been shown to provide considerable numerical advantages in the range of high beam slenderness ratios, alternative shear-deformable beam models are required for examples with thick beams. The current contribution additionally proposes a novel geometrically exact beam element based on the Simo-Reissner theory. Similar to the torsion-free and the Kirchhoff-Love beam elements, also this Simo-Reissner element is based on a C1-continuous Hermite interpolation of the beam centerline, which will allow for smooth contact kinematics. For this Hermitian Simo-Reissner element, a consistent spatial convergence behavior as well as the successful avoidance of membrane and shear locking will be demonstrated numerically. All in all, the combination of the ABC formulation with these different beam element variants (i.e.~the torsion-free element, the Kirchhoff-Love element and the Simo-Reissner element) results in a very flexible and modular simulation framework that allows to choose the optimal element formulation for any given application in terms of accuracy, efficiency and robustness.
A Class of Two-Weight and Three-Weight Linear Codes and Their Duals
Venue: arXiv cs.IT 2016
Year: 2016

The objective of this paper is to construct a class of linear codes with two nonzero weights and three nonzero weights by using the general trace functions, which weight distributions has been determined. These linear codes contain some optimal codes, which meets certain bound on linear codes. The dual codes are also studied and proved to be optimal or almost optimal. These codes may have applications in authentication codes, secret sharing schemes and strongly regular graphs.
Efficient Stochastic Inference of Bitwise Deep Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

Recently published methods enable training of bitwise neural networks which allow reduced representation of down to a single bit per weight. We present a method that exploits ensemble decisions based on multiple stochastically sampled network models to increase performance figures of bitwise neural networks in terms of classification accuracy at inference. Our experiments with the CIFAR-10 and GTSRB datasets show that the performance of such network ensembles surpasses the performance of the high-precision base model. With this technique we achieve 5.81% best classification error on CIFAR-10 test set using bitwise networks. Concerning inference on embedded systems we evaluate these bitwise networks using a hardware efficient stochastic rounding procedure. Our work contributes to efficient embedded bitwise neural networks.
FURL: Fixed-memory and Uncertainty Reducing Local Triangle Counting for Graph Streams
Venue: arXiv cs.DS 2016
Year: 2016

How can we accurately estimate local triangles for all nodes in simple and multigraph streams? Local triangle counting in a graph stream is one of the most fundamental tasks in graph mining with important applications including anomaly detection and social network analysis. Although there have been several local triangle counting methods in a graph stream, their estimation has a large variance which results in low accuracy, and they do not consider multigraph streams which have duplicate edges. In this paper, we propose FURL, an accurate local triangle counting method for simple and multigraph streams. FURL improves the accuracy by reducing a variance through biased estimation and handles duplicate edges for multigraph streams. Also, FURL handles a stream of any size by using a fixed amount of memory. Experimental results show that FURL outperforms the state-of-the-art method in accuracy and performs well in multigraph streams. In addition, we report interesting patterns discovered from real graphs by FURL, which include unusual local structures in a user communication network and a core-periphery structure in the Web.
On Selecting a Conjunction Operation in Probabilistic Soft Logic
Venue: arXiv cs.LO 2016
Year: 2016

Probabilistic Soft Logic has been proposed and used in several applications as an efficient way to deal with inconsistency, uncertainty and relational representation. In several applications, this approach has led to an adequate description of the corresponding human reasoning. In this paper, we provide a theoretical explanation for one of the semi-heuristic choices made in this approach: namely, we explain the choice of the corresponding conjunction operations. Our explanation leads to a more general family of operations which may be used in future applications of probabilistic soft logic.
Estimation of respiratory pattern from video using selective ensemble aggregation
Venue: arXiv cs.CV 2016
Year: 2016

Non-contact estimation of respiratory pattern (RP) and respiration rate (RR) has multiple applications. Existing methods for RP and RR measurement fall into one of the three categories - (i) estimation through nasal air flow measurement, (ii) estimation from video-based remote photoplethysmography, and (iii) estimation by measurement of motion induced by respiration using motion detectors. These methods, however, require specialized sensors, are computationally expensive and/or critically depend on selection of a region of interest (ROI) for processing. In this paper a general framework is described for estimating a periodic signal driving noisy LTI channels connected in parallel with unknown dynamics. The method is then applied to derive a computationally inexpensive method for estimating RP using 2D cameras that does not critically depend on ROI. Specifically, RP is estimated by imaging the changes in the reflected light caused by respiration-induced motion. Each spatial location in the field of view of the camera is modeled as a noise-corrupted linear time-invariant (LTI) measurement channel with unknown system dynamics, driven by a single generating respiratory signal. Estimation of RP is cast as a blind deconvolution problem and is solved through a method comprising subspace projection and statistical aggregation. Experiments are carried out on 31 healthy human subjects by generating multiple RPs and comparing the proposed estimates with simultaneously acquired ground truth from an impedance pneumograph device. The proposed estimator agrees well with the ground truth device in terms of correlation measures, despite variability in clothing pattern, angle of view and ROI.
Crowd Counting by Adapting Convolutional Neural Networks with Side Information
Venue: arXiv cs.CV 2016
Year: 2016

Computer vision tasks often have side information available that is helpful to solve the task. For example, for crowd counting, the camera perspective (e.g., camera angle and height) gives a clue about the appearance and scale of people in the scene. While side information has been shown to be useful for counting systems using traditional hand-crafted features, it has not been fully utilized in counting systems based on deep learning. In order to incorporate the available side information, we propose an adaptive convolutional neural network (ACNN), where the convolutional filter weights adapt to the current scene context via the side information. In particular, we model the filter weights as a low-dimensional manifold, parametrized by the side information, within the high-dimensional space of filter weights. With the help of side information and adaptive weights, the ACNN can disentangle the variations related to the side information, and extract discriminative features related to the current context. Since existing crowd counting datasets do not contain ground-truth side information, we collect a new dataset with the ground-truth camera angle and height as the side information. On experiments in crowd counting, the ACNN improves counting accuracy compared to a plain CNN with a similar number of parameters. We also apply ACNN to image deconvolution to show its potential effectiveness on other computer vision applications.
MAP-Me: Managing Anchor-less Producer Mobility in Information-Centric Networks
Venue: arXiv cs.NI 2016
Year: 2016

Mobility has become a basic premise of network communications, thereby requiring a native integration into 5G networks. Despite the numerous efforts to propose and to standardize effective mobility management models for IP, the result is a complex, poorly flexible set of mechanisms. The natural support for mobility offered by ICN (Information Centric Networking), makes it a good candidate to define a radically new solution relieving limitations of traditional approaches. If consumer mobility is supported in ICN by design, in virtue of its connectionless pull-based communication model, producer mobility is still an open challenge. In this work, we propose MAP-Me, an anchor-less solution to manage micro mobility of content producer via ICN name-based data plane, with support for latency-sensitive applications. First, we analyze MAP-Me performance and provide guarantees of correctness and stability. Further, we set up a realistic simulation environment in NDNSim 2.1 for MAP-Me evaluation and comparison against existing solutions: either random waypoint and trace-driven car mobility patterns are considered under 802.11 radio access. Results are encouraging and highlight the superiority of MAP-Me in terms of user performance and of network cost metrics.
Bidirectional Tree-Structured LSTM with Head Lexicalization
Venue: arXiv cs.CL 2016
Year: 2016

Sequential LSTM has been extended to model tree structures, giving competitive results for a number of tasks. Existing methods model constituent trees by bottom-up combinations of constituent nodes, making direct use of input word information only for leaf nodes. This is different from sequential LSTMs, which contain reference to input words for each node. In this paper, we propose a method for automatic head-lexicalization for tree-structure LSTMs, propagating head words from leaf nodes to every constituent node. In addition, enabled by head lexicalization, we build a tree LSTM in the top-down direction, which corresponds to bidirectional sequential LSTM structurally. Experiments show that both extensions give better representations of tree structures. Our final model gives the best results on the Standford Sentiment Treebank and highly competitive results on the TREC question type classification task.
Generalized Dropout
Venue: arXiv cs.LG 2016
Year: 2016

Deep Neural Networks often require good regularizers to generalize well. Dropout is one such regularizer that is widely used among Deep Learning practitioners. Recent work has shown that Dropout can also be viewed as performing Approximate Bayesian Inference over the network parameters. In this work, we generalize this notion and introduce a rich family of regularizers which we call Generalized Dropout. One set of methods in this family, called Dropout++, is a version of Dropout with trainable parameters. Classical Dropout emerges as a special case of this method. Another member of this family selects the width of neural network layers. Experiments show that these methods help in improving generalization performance over Dropout.
Service-Oriented Sharding with Aspen
Venue: arXiv cs.CR 2016
Year: 2016

The rise of blockchain-based cryptocurrencies has led to an explosion of services using distributed ledgers as their underlying infrastructure. However, due to inherently single-service oriented blockchain protocols, such services can bloat the existing ledgers, fail to provide sufficient security, or completely forego the property of trustless auditability. Security concerns, trust restrictions, and scalability limits regarding the resource requirements of users hamper the sustainable development of loosely-coupled services on blockchains. This paper introduces Aspen, a sharded blockchain protocol designed to securely scale with increasing number of services. Aspen shares the same trust model as Bitcoin in a peer-to-peer network that is prone to extreme churn containing Byzantine participants. It enables introduction of new services without compromising the security, leveraging the trust assumptions, or flooding users with irrelevant messages.