OpenRaiser/Intern-Atlas huggingface dataset:
On Computation Rates for Arithmetic Sum
Venue: arXiv cs.IT 2016
Year: 2016

For zero-error function computation over directed acyclic networks, existing upper and lower bounds on the computation capacity are known to be loose. In this work we consider the problem of computing the arithmetic sum over a specific directed acyclic network that is not a tree. We assume the sources to be i.i.d. Bernoulli with parameter $1/2$. Even in this simple setting, we demonstrate that upper bounding the computation rate is quite nontrivial. In particular, it requires us to consider variable length network codes and relate the upper bound to equivalently lower bounding the entropy of descriptions observed by the terminal conditioned on the function value. This lower bound is obtained by further lower bounding the entropy of a so-called \textit{clumpy distribution}. We also demonstrate an achievable scheme that uses variable length network codes and in-network compression.
Performance Analysis based on Density Evolution on Fault Erasure Belief Propagation Decoder
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we will present an analysis on the fault erasure BP decoders based on the density evolution. In the fault BP decoder, messages exchanged in a BP process are stochastically corrupted due to unreliable logic gates and flip-flops; i.e., we assume circuit components with transient faults. We derived a set of the density evolution equations for the fault erasure BP processes. Our density evolution analysis reveals the asymptotic behaviors of the estimation error probability of the fault erasure BP decoders. In contrast to the fault free cases, it is observed that the error probabilities of the fault erasure BP decoder converge to positive values, and that there exists a discontinuity in an error curve corresponding to the fault BP threshold. It is also shown that an message encoding technique provides higher fault BP thresholds than those of the original decoders at the cost of increased circuit size.
Living Innovation Laboratory Model Design and Implementation
Venue: arXiv cs.HC 2016
Year: 2016

Living Innovation Laboratory (LIL) is an open and recyclable way for multidisciplinary researchers to remote control resources and co-develop user centered projects. In the past few years, there were several papers about LIL published and trying to discuss and define the model and architecture of LIL. People all acknowledge about the three characteristics of LIL: user centered, co-creation, and context aware, which make it distinguished from test platform and other innovation approaches. Its existing model consists of five phases: initialization, preparation, formation, development, and evaluation. Goal Net is a goal-oriented methodology to formularize a progress. In this thesis, Goal Net is adopted to subtract a detailed and systemic methodology for LIL. LIL Goal Net Model breaks the five phases of LIL into more detailed steps. Big data, crowd sourcing, crowd funding and crowd testing take place in suitable steps to realize UUI, MCC and PCA throughout the innovation process in LIL 2.0. It would become a guideline for any company or organization to develop a project in the form of an LIL 2.0 project. To prove the feasibility of LIL Goal Net Model, it was applied to two real cases. One project is a Kinect game and the other one is an Internet product. They were both transformed to LIL 2.0 successfully, based on LIL goal net based methodology. The two projects were evaluated by phenomenography, which was a qualitative research method to study human experiences and their relations in hope of finding the better way to improve human experiences. Through phenomenographic study, the positive evaluation results showed that the new generation of LIL had more advantages in terms of effectiveness and efficiency.
Fast Integral Image Estimation at 1% measurement rate
Venue: arXiv cs.CV 2016
Year: 2016

We propose a framework called ReFInE to directly obtain integral image estimates from a very small number of spatially multiplexed measurements of the scene without iterative reconstruction of any auxiliary image, and demonstrate their practical utility in visual object tracking. Specifically, we design measurement matrices which are tailored to facilitate extremely fast estimation of the integral image, by using a single-shot linear operation on the measured vector. Leveraging a prior model for the images, we formulate a nuclear norm minimization problem with second order conic constraints to jointly obtain the measurement matrix and the linear operator. Through qualitative and quantitative experiments, we show that high quality integral image estimates can be obtained using our framework at very low measurement rates. Further, on a standard dataset of 50 videos, we present object tracking results which are comparable to the state-of-the-art methods, even at an extremely low measurement rate of 1%.
Quiver: Using Control Perturbations to Increase the Observability of Sensor Data in Smart Buildings
Venue: arXiv cs.SY 2016
Year: 2016

Modern buildings consist of hundreds of sensors and actuators for monitoring and operation of systems such as HVAC, light and security. To enable portable applications in next generation smart buildings, we need models and standardized ontologies that represent these sensors across diverse types of buildings. Recent research has shown that extracting information such as sensor type with available metadata and timeseries data analysis is difficult due to heterogeneity of systems and lack of support for interoperability. We propose perturbations in the control system as a mechanism to increase the observability of building systems to extract contextual information and develop standardized models. We design Quiver, an experimental framework for actuation of building HVAC system that enables us to perturb the control system safely. Using Quiver, we demonstrate three applications using empirical experiments on a real commercial building: colocation of data points, identification of point type and mapping of dependency between actuators. Our results show that we can colocate data points in HVAC terminal units with 98.4 % accuracy and 63 % coverage. We can identify point types of the terminal units with 85.3 % accuracy. Finally, we map the dependency links between actuators with an accuracy of 73.5 %, with 8.1 % and 18.4 % false positives and false negatives respectively.
Evolutionary stability implies asymptotic stability under multiplicative weights
Venue: arXiv cs.GT 2016
Year: 2016

We show that evolutionarily stable states in general (nonlinear) population games (which can be viewed as continuous vector fields constrained on a polytope) are asymptotically stable under a multiplicative weights dynamic (under appropriate choices of a parameter called the learning rate or step size, which we demonstrate to be crucial to achieve convergence, as otherwise even chaotic behavior is possible to manifest). Our result implies that evolutionary theories based on multiplicative weights are compatible (in principle, more general) with those based on the notion of evolutionary stability. However, our result further establishes multiplicative weights as a nonlinear programming primitive (on par with standard nonlinear programming methods) since various nonlinear optimization problems, such as finding Nash/Wardrop equilibria in nonatomic congestion games, which are well-known to be equipped with a convex potential function, and finding strict local maxima of quadratic programming problems, are special cases of the problem of computing evolutionarily stable states in nonlinear population games.
Improving virtual host efficiency through resource and interference aware scheduling
Venue: arXiv cs.DC 2016
Year: 2016

Modern Infrastructure-as-a-Service Clouds operate in a competitive environment that caters to any user's requirements for computing resources. The sharing of the various types of resources by diverse applications poses a series of challenges in order to optimize resource utilization while avoiding performance degradation caused by application interference. In this paper, we present two scheduling methodologies enforcing consolidation techniques on multicore physical machines. Our resource-aware and interference-aware scheduling schemes aim at improving physical host efficiency while preserving the application performance by taking into account host oversubscription and the resulting workload interference. We validate our fully operational framework through a set of real-life workloads representing a wide class of modern cloud applications. The experimental results prove the efficiency of our system in optimizing resource utilization and thus energy consumption even in the presence of oversubscription. Both methodologies achieve significant reductions of the CPU time consumed, reaching up to 50%, while at the same time maintaining workload performance compared to widely used scheduling schemes under a variety of representative cloud platform scenarios.
Graphs of finite algebras, edges, and connectivity
Venue: arXiv cs.LO 2016
Year: 2016

We refine and advance the study of the local structure of idempotent finite algebras started in [A.Bulatov, The Graph of a Relational Structure and Constraint Satisfaction Problems, LICS, 2004]. We introduce a graph-like structure on an arbitrary finite idempotent algebra omitting type 1. We show that this graph is connected, its edges can be classified into 3 types corresponding to the local behavior (semilattice, majority, or affine) of certain term operations, and that the structure of the algebra can be `improved' without introducing type 1 by choosing an appropriate reduct of the original algebra. Then we refine this structure demonstrating that the edges of the graph of an algebra can be made `thin', that is, there are term operations that behave very similar to semilattice, majority, or affine operations on 2-element subsets of the algebra. Finally, we prove certain connectivity properties of the refined structures. This research is motivated by the study of the Constraint Satisfaction Problem, although the problem itself does not really show up in this paper.
Co-Occurrence Patterns in the Voynich Manuscript
Venue: arXiv cs.CL 2016
Year: 2016

The Voynich Manuscript is a medieval book written in an unknown script. This paper studies the distribution of similarly spelled words in the Voynich Manuscript. It shows that the distribution of words within the manuscript is not compatible with natural languages.
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
Venue: arXiv cs.DS 2016
Year: 2016

A central problem in the theory of algorithms for data streams is to determine which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-logarithmic, space. Given a function $g$, we study the space complexity of approximating $\sum_{i=1}^n g(|f_i|)$, where $f\in\mathbb{Z}^n$ is the frequency vector of a turnstile stream. This is a generalization of the well-known frequency moments problem, and previous results apply only when $g$ is monotonic or has a special functional form. Our contribution is to give a condition such that, except for a narrow class of functions $g$, there is a space-efficient approximation algorithm for the sum if and only if $g$ satisfies the condition. The functions $g$ that we are able to characterize include all convex, concave, monotonic, polynomial, and trigonometric functions, among many others, and is the first such characterization for non-monotonic functions. Thus, for nearly all functions of one variable, we answer the open question from the celebrated paper of Alon, Matias and Szegedy (1996).
Analysis and Evaluation for the Performance of the Communication Infrastructure for Real Wide Area Monitoring Systems (WAMS) Based on 3G Technology
Venue: arXiv cs.NI 2016
Year: 2016

Wide Area Monitoring Systems (WAMS) utilizing synchrophasor measurements is considered one of the essential parts in smart grids that enable system operators to monitor, operate, and control power systems in wide geographical area. On the other hand, high-speed, reliable and scalable data communication infrastructure is crucial in both construction and operation of WAMS. Universal mobile Telecommunication System (UMTS), the 3G standard for mobile communication networks, was developed to provide high speed data transmission with reliable service performance for mobile users. Therefore, UMTS is considered a promising solution for providing a communication infrastructure for WAMS. 3G based EWAMS (Egyptian wide area Monitoring System) is designed and implemented in Egypt through deployment a number of frequency disturbance recorders (FDRs) devices on a live 220kV/500kV Egyptian grid in cooperation with the Egyptian Electricity Transmission Company (EETC). The developed EWAMS can gather information from 11 FDRs devices which are geographically dispersed throughout the boundary of the Egyptian power grid and to a remote data management center located at Helwan University. The communication performance for the developed EWAMS in terms of communication time delay, throughput, and percentage of wasted bandwidth are studied in this paper. The results showed that the system can achieve successfully the communication requirements needed by various wide area monitoring applications.
Locally-Supervised Deep Hybrid Model for Scene Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional neural networks (CNN) have recently achieved remarkable successes in various image classification and understanding tasks. The deep features obtained at the top fully-connected layer of the CNN (FC-features) exhibit rich global semantic information and are extremely effective in image classification. On the other hand, the convolutional features in the middle layers of the CNN also contain meaningful local information, but are not fully explored for image representation. In this paper, we propose a novel Locally-Supervised Deep Hybrid Model (LS-DHM) that effectively enhances and explores the convolutional features for scene recognition. Firstly, we notice that the convolutional features capture local objects and fine structures of scene images, which yield important cues for discriminating ambiguous scenes, whereas these features are significantly eliminated in the highly-compressed FC representation. Secondly, we propose a new Local Convolutional Supervision (LCS) layer to enhance the local structure of the image by directly propagating the label information to the convolutional layers. Thirdly, we propose an efficient Fisher Convolutional Vector (FCV) that successfully rescues the orderless mid-level semantic information (e.g. objects and textures) of scene image. The FCV encodes the large-sized convolutional maps into a fixed-length mid-level representation, and is demonstrated to be strongly complementary to the high-level FC-features. Finally, both the FCV and FC-features are collaboratively employed in the LSDHM representation, which achieves outstanding performance in our experiments. It obtains 83.75% and 67.56% accuracies respectively on the heavily benchmarked MIT Indoor67 and SUN397 datasets, advancing the stat-of-the-art substantially.
Discriminative Training of Deep Fully-connected Continuous CRF with Task-specific Loss
Venue: arXiv cs.CV 2016
Year: 2016

Recent works on deep conditional random fields (CRF) have set new records on many vision tasks involving structured predictions. Here we propose a fully-connected deep continuous CRF model for both discrete and continuous labelling problems. We exemplify the usefulness of the proposed model on multi-class semantic labelling (discrete) and the robust depth estimation (continuous) problems. In our framework, we model both the unary and the pairwise potential functions as deep convolutional neural networks (CNN), which are jointly learned in an end-to-end fashion. The proposed method possesses the main advantage of continuously-valued CRF, which is a closed-form solution for the Maximum a posteriori (MAP) inference. To better adapt to different tasks, instead of using the commonly employed maximum likelihood CRF parameter learning protocol, we propose task-specific loss functions for learning the CRF parameters. It enables direct optimization of the quality of the MAP estimates during the course of learning. Specifically, we optimize the multi-class classification loss for the semantic labelling task and the Turkey's biweight loss for the robust depth estimation problem. Experimental results on the semantic labelling and robust depth estimation tasks demonstrate that the proposed method compare favorably against both baseline and state-of-the-art methods. In particular, we show that although the proposed deep CRF model is continuously valued, with the equipment of task-specific loss, it achieves impressive results even on discrete labelling tasks.
Deterministic sub-linear space LCE data structures with efficient construction
Venue: arXiv cs.DS 2016
Year: 2016

Given a string $S$ of $n$ symbols, a longest common extension query $\mathsf{LCE}(i,j)$ asks for the length of the longest common prefix of the $i$th and $j$th suffixes of $S$. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015: 65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and query time. In particular, for a parameter $1 \leq τ\leq n$, their best deterministic solution is a data structure of size $O(n/τ)$ which allows LCE queries to be answered in $O(τ)$ time. However, the construction time for all deterministic versions of their data structure is quadratic in $n$. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of $O(τ\min\{\logτ,\log\frac{n}τ\})$ query time using $O(n/τ)$ space, but significantly improve the construction time to $O(nτ)$.
Extremal Relations Between Shannon Entropy and $\ell_α$-Norm
Venue: arXiv cs.IT 2016
Year: 2016

The paper examines relationships between the Shannon entropy and the $\ell_α$-norm for $n$-ary probability vectors, $n \ge 2$. More precisely, we investigate the tight bounds of the $\ell_α$-norm with a fixed Shannon entropy, and vice versa. As applications of the results, we derive the tight bounds between the Shannon entropy and several information measures which are determined by the $\ell_α$-norm, e.g., Rényi entropy, Tsallis entropy, the $R$-norm information, and some diversity indices. Moreover, we apply these results to uniformly focusing channels. Then, we show the tight bounds of Gallager's $E_{0}$ functions with a fixed mutual information under a uniform input distribution.
Near-Optimal Signal Detector Based on Structured Compressive Sensing for Massive SM-MIMO
Venue: arXiv cs.IT 2016
Year: 2016

Massive spatial modulation (SM)-MIMO, which employs massive low-cost antennas but few power-hungry transmit radio frequency (RF) chains at the transmitter, is recently proposed to provide both high spectrum efficiency and energy efficiency for future green communications. However, in massive SM-MIMO, the optimal maximum likelihood (ML) detector has the prohibitively high complexity, while state-of-the-art low-complexity detectors for conventional small-scale SM-MIMO suffer from an obvious performance loss. In this paper, by exploiting the structured sparsity of multiple SM signals, we propose a low-complexity signal detector based on structured compressive sensing (SCS) to improve the signal detection performance. Specifically, we first propose the grouped transmission scheme at the transmitter, where multiple SM signals in several continuous time slots are grouped to carry the common spatial constellation symbol to introduce the desired structured sparsity. Accordingly, a structured subspace pursuit (SSP) algorithm is proposed at the receiver to jointly detect multiple SM signals by leveraging the structured sparsity. In addition, we also propose the SM signal interleaving to permute SM signals in the same transmission group, whereby the channel diversity can be exploited to further improve the signal detection performance. Theoretical analysis quantifies the performance gain from SM signal interleaving, and simulation results demonstrate the near-optimal performance of the proposed scheme.
Log-Normal Matrix Completion for Large Scale Link Prediction
Venue: arXiv cs.SI 2016
Year: 2016

The ubiquitous proliferation of online social networks has led to the widescale emergence of relational graphs expressing unique patterns in link formation and descriptive user node features. Matrix Factorization and Completion have become popular methods for Link Prediction due to the low rank nature of mutual node friendship information, and the availability of parallel computer architectures for rapid matrix processing. Current Link Prediction literature has demonstrated vast performance improvement through the utilization of sparsity in addition to the low rank matrix assumption. However, the majority of research has introduced sparsity through the limited L1 or Frobenius norms, instead of considering the more detailed distributions which led to the graph formation and relationship evolution. In particular, social networks have been found to express either Pareto, or more recently discovered, Log Normal distributions. Employing the convexity-inducing Lovasz Extension, we demonstrate how incorporating specific degree distribution information can lead to large scale improvements in Matrix Completion based Link prediction. We introduce Log-Normal Matrix Completion (LNMC), and solve the complex optimization problem by employing Alternating Direction Method of Multipliers. Using data from three popular social networks, our experiments yield up to 5% AUC increase over top-performing non-structured sparsity based methods.
Towards the Design of an End-to-End Automated System for Image and Video-based Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Over many decades, researchers working in object recognition have longed for an end-to-end automated system that will simply accept 2D or 3D image or videos as inputs and output the labels of objects in the input data. Computer vision methods that use representations derived based on geometric, radiometric and neural considerations and statistical and structural matchers and artificial neural network-based methods where a multi-layer network learns the mapping from inputs to class labels have provided competing approaches for image recognition problems. Over the last four years, methods based on Deep Convolutional Neural Networks (DCNNs) have shown impressive performance improvements on object detection/recognition challenge problems. This has been made possible due to the availability of large annotated data, a better understanding of the non-linear mapping between image and class labels as well as the affordability of GPUs. In this paper, we present a brief history of developments in computer vision and artificial neural networks over the last forty years for the problem of image-based recognition. We then present the design details of a deep learning system for end-to-end unconstrained face verification/recognition. Some open issues regarding DCNNs for object recognition problems are then discussed. We caution the readers that the views expressed in this paper are from the authors and authors only!
Probabilistic Models for Computerized Adaptive Testing: Experiments
Venue: arXiv cs.AI 2016
Year: 2016

This paper follows previous research we have already performed in the area of Bayesian networks models for CAT. We present models using Item Response Theory (IRT - standard CAT method), Bayesian networks, and neural networks. We conducted simulated CAT tests on empirical data. Results of these tests are presented for each model separately and compared.