OpenRaiser/Intern-Atlas huggingface dataset:
Joint Source-Channel Decoding of Polar Codes for Language-Based Source
Venue: arXiv cs.IT 2016
Year: 2016

We exploit the redundancy of the language-based source to help polar decoding. By judging the validity of decoded words in the decoded sequence with the help of a dictionary, the polar list decoder constantly detects erroneous paths after every few bits are decoded. This path-pruning technique based on joint decoding has advantages over stand-alone polar list decoding in that most decoding errors in early stages are corrected. In order to facilitate the joint decoding, we first propose a construction of dynamic dictionary using a trie and show an efficient way to trace the dictionary during decoding. Then we propose a joint decoding scheme of polar codes taking into account both information from the channel and the source. The proposed scheme has the same decoding complexity as the list decoding of polar codes. A list-size adaptive joint decoding is further implemented to largely reduce the decoding complexity. We conclude by simulation that the joint decoding schemes outperform stand-alone polar codes with CRC-aided successive cancellation list decoding by over 0.6 dB.
Syntax and Semantics of Abstract Binding Trees
Venue: arXiv cs.LO 2016
Year: 2016

The contribution of this paper is the development of the syntax and semantics of multi-sorted nominal abstract binding trees (abts), an extension of second order universal algebra to support symbol-indexed families of operators. Nominal abts are essential for correctly treating the syntax of languages with generative phenomena, including exceptions and mutable state. Additionally we have developed the categorical semantics for abstract binding trees formally in Constructive Type Theory using the Agda proof assistant. Multi-sorted nominal abts also form the syntactic basis for the upcoming version of the JonPRL proof assistant, an implementation of an extensional constructive type theory in the Nuprl tradition.
Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications
Venue: arXiv cs.NI 2016
Year: 2016

Cloud-based computing infrastructure provides an efficient means to support real-time processing workloads, e.g., virtualized base station processing, and collaborative video conferencing. This paper addresses resource allocation for a computing system with multiple resources supporting heterogeneous soft real-time applications subject to Quality of Service (QoS) constraints on failures to meet processing deadlines. We develop a general outer bound on the feasible QoS region for non-clairvoyant resource allocation policies, and an inner bound for a natural class of policies based on dynamically prioritizing applications' tasks by favoring those with the largest (QoS) deficits. This provides an avenue to study the efficiency of two natural resource allocation policies: (1) priority-based greedy task scheduling for applications with variable workloads, and (2) priority-based task selection and optimal scheduling for applications with deterministic workloads. The near-optimality of these simple policies emerges when task processing deadlines are relatively large and/or when the number of compute resources is large. Analysis and simulations show substantial resource savings for such policies over reservation-based designs.
Fast Binary Embedding via Circulant Downsampled Matrix -- A Data-Independent Approach
Venue: arXiv cs.IT 2016
Year: 2016

Binary embedding of high-dimensional data aims to produce low-dimensional binary codes while preserving discriminative power. State-of-the-art methods often suffer from high computation and storage costs. We present a simple and fast embedding scheme by first downsampling N-dimensional data into M-dimensional data and then multiplying the data with an MxM circulant matrix. Our method requires O(N +M log M) computation and O(N) storage costs. We prove if data have sparsity, our scheme can achieve similarity-preserving well. Experiments further demonstrate that though our method is cost-effective and fast, it still achieves comparable performance in image applications.
Progress on High-rate MSR Codes: Enabling Arbitrary Number of Helper Nodes
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a construction for high-rate MDS codes that enable bandwidth-efficient repair of a single node. Such MDS codes are also referred to as the minimum storage regenerating (MSR) codes in the distributed storage literature. The construction presented in this paper generates MSR codes for all possible number of helper nodes $d$ as $d$ is a design parameter in the construction. Furthermore, the obtained MSR codes have polynomial sub-packetization (a.k.a. node size) $α$. The construction is built on the recent code proposed by Sasidharan et al. [1], which works only for $d = n-1$, i.e., where all the remaining nodes serve as the helper nodes for the bandwidth-efficient repair of a single node. The results of this paper broaden the set of parameters where the constructions of MSR codes were known earlier.
Your Interests According to Google - A Profile-Centered Analysis for Obfuscation of Online Tracking Profiles
Venue: arXiv cs.CY 2016
Year: 2016

Profiling users for the purpose of targeted advertisements or other kinds of personalization is very popular on the internet. But besides the benefits of individually tailored news feeds and shopping recommendation research has shown that many users consider this practice as privacy infringement. Profiling is often conducted without consent and services offer neither information about what the profile looks like nor which effects it might have. In this paper we argue that understanding profiling and thus interacting with the resulting profiles fosters a privacy literacy that is necessary for users to stay autonomous in the information society. We analyze the extent of interest profiling by google and develop a countermeasures that helps to obfuscate these profiles. To do so we analyzed a links lists from a social bookmarking service with regard to the interests they reveal. We found that, although the profiling by google is very unstable we can still use the information to obfuscate the profile.
On Caching with More Users than Files
Venue: arXiv cs.IT 2016
Year: 2016

Caching appears to be an efficient way to reduce peak hour network traffic congestion by storing some content at the user's cache without knowledge of later demands. Recently, Maddah-Ali and Niesen proposed a two-phase, placement and delivery phase, coded caching strategy for centralized systems (where coordination among users is possible in the placement phase), and for decentralized systems. This paper investigates the same setup under the further assumption that the number of users is larger than the number of files. By using the same uncoded placement strategy of Maddah-Ali and Niesen, a novel coded delivery strategy is proposed to profit from the multicasting opportunities that arise because a file may be demanded by multiple users. The proposed delivery method is proved to be optimal under the constraint of uncoded placement for centralized systems with two files, moreover it is shown to outperform known caching strategies for both centralized and decentralized systems.
Novel Lower Bounds on the Entropy Rate of Binary Hidden Markov Processes
Venue: arXiv cs.IT 2016
Year: 2016

Recently, Samorodnitsky proved a strengthened version of Mrs. Gerber's Lemma, where the output entropy of a binary symmetric channel is bounded in terms of the average entropy of the input projected on a random subset of coordinates. Here, this result is applied for deriving novel lower bounds on the entropy rate of binary hidden Markov processes. For symmetric underlying Markov processes, our bound improves upon the best known bound in the very noisy regime. The nonsymmetric case is also considered, and explicit bounds are derived for Markov processes that satisfy the $(1,\infty)$-RLL constraint.
Secure Computation of Randomized Functions
Venue: arXiv cs.CR 2016
Year: 2016

Two user secure computation of randomized functions is considered, where only one user computes the output. Both the users are semi-honest; and computation is such that no user learns any additional information about the other user's input and output other than what cannot be inferred from its own input and output. First we consider a scenario, where privacy conditions are against both the users. In perfect security setting Kilian [STOC 2000] gave a characterization of securely computable randomized functions, and we provide rate-optimal protocols for such functions. We prove that the same characterization holds in asymptotic security setting as well and give a rate-optimal protocol. In another scenario, where privacy condition is only against the user who is not computing the function, we provide rate-optimal protocols. For perfect security in both the scenarios, our results are in terms of chromatic entropies of different graphs. In asymptotic security setting, we get single-letter expressions of rates in both the scenarios.
Is swarm intelligence able to create mazes?
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, the idea of applying Computational Intelligence in the process of creation board games, in particular mazes, is presented. For two different algorithms the proposed idea has been examined. The results of the experiments are shown and discussed to present advantages and disadvantages.
Expected Similarity Estimation for Large-Scale Batch and Streaming Anomaly Detection
Venue: arXiv cs.LG 2016
Year: 2016

We present a novel algorithm for anomaly detection on very large datasets and data streams. The method, named EXPected Similarity Estimation (EXPoSE), is kernel-based and able to efficiently compute the similarity between new data points and the distribution of regular data. The estimator is formulated as an inner product with a reproducing kernel Hilbert space embedding and makes no assumption about the type or shape of the underlying data distribution. We show that offline (batch) learning with EXPoSE can be done in linear time and online (incremental) learning takes constant time per instance and model update. Furthermore, EXPoSE can make predictions in constant time, while it requires only constant memory. In addition, we propose different methodologies for concept drift adaptation on evolving data streams. On several real datasets we demonstrate that our approach can compete with state of the art algorithms for anomaly detection while being an order of magnitude faster than most other approaches.
Capturability-based Analysis of Legged Robot with Consideration of Swing Legs
Venue: arXiv cs.RO 2016
Year: 2016

Capturability of a robot determines whether it is able to capture a robot within a number of steps. Current capturability analysis is based on stance leg dynamics, without taking adequate consideration on swing leg. In this paper, we combine capturability-based analysis with swing leg dynamics. We first associate original definition of capturability with a time-margin, which encodes a time sequence that can capture the robot. This time-margin capturability requires consideration of swing leg, and we therefore introduce a swing leg kernel that acts as a bridge between step time and step length. We analyze N-step capturability with a combined model of swing leg kernels and a linear inverted pendulum model. By analyzing swing leg kernels with different parameters, we find that more powerful actuation and longer normalized step length result in greater capturability. We also answer the question whether more steps would give greater capturability. For a given disturbance, we find a step sequence that minimizes actuation. This step sequence is whether a step time sequence or a step length sequence, and this classification is based on boundary value problem analysis.
A Perceptually Motivated Filter Bank with Perfect Reconstruction for Audio Signal Processing
Venue: arXiv cs.SD 2016
Year: 2016

Many audio applications rely on filter banks (FBs) to analyze, process, and re-synthesize sounds. To approximate the auditory frequency resolution in the signal chain, some applications rely on perceptually motivated FBs, the gammatone FB being a popular example. However, most perceptually motivated FBs only allow partial signal reconstruction at high redundancies and/or do not have good resistance to sub-channel processing. This paper introduces an oversampled perceptually motivated FB enabling perfect reconstruction, efficient FB design, and adaptable redundancy. The filters are directly constructed in the frequency domain and linearly distributed on a perceptual frequency scale (e.g. ERB, Bark, or Mel scale). The proposed design allows for various filter shapes, uniform or non-uniform FB setting, and large down-sampling factors. For redundancies $\geq$ 3 perfect reconstruction is achieved by computing the canonical dual FB analytically. For lower redundancies perfect reconstruction is achieved using an iterative method. Experiments show performance improvements of the proposed approach when compared to the gammatone FB in terms of reconstruction error and resistance to sub-channel processing, especially at low redundancies.
Upper Bounds on the Capacity of 2-Layer $N$-Relay Symmetric Gaussian Network
Venue: arXiv cs.IT 2016
Year: 2016

The Gaussian parallel relay network, in which two parallel relays assist a source to convey information to a destination, was introduced by Schein and Gallager. An upper bound on the capacity can be obtained by considering broadcast cut between the source and relays and multiple access cut between relays and the destination. Niesen and Diggavi derived an upper bound for Gaussian parallel $N$-relay network by considering all other possible cuts and showed an achievability scheme that can attain rates close to the upper bound in different channel gain regimes thus establishing approximate capacity. In this paper we consider symmetric layered Gaussian relay networks in which there can be many layers of parallel relays. The channel gains for the channels between two adjacent layers are symmetrical (identical). Relays in each layer broadcast information to the relays in the next layer. For 2-layer $N$-relay Gaussian network we give upper bounds on the capacity. Our analysis reveals that for the upper bounds, joint optimization over correlation coefficients is not necessary for obtaining stronger results.
50+ Metrics for Calendar Mining
Venue: arXiv cs.OH 2016
Year: 2016

In this report we propose 50+ metrics which can be measured by organizations in order to identify improvements in various areas such as meeting efficiency, capacity planning or leadership skills, just to new a few. The notion of calendar mining is introduced and support is provided for performing the measurement by a reference data model and queries for all metrics defined.
A Robust UCB Scheme for Active Learning in Regression from Strategic Crowds
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of training an accurate linear regression model by procuring labels from multiple noisy crowd annotators, under a budget constraint. We propose a Bayesian model for linear regression in crowdsourcing and use variational inference for parameter estimation. To minimize the number of labels crowdsourced from the annotators, we adopt an active learning approach. In this specific context, we prove the equivalence of well-studied criteria of active learning like entropy minimization and expected error reduction. Interestingly, we observe that we can decouple the problems of identifying an optimal unlabeled instance and identifying an annotator to label it. We observe a useful connection between the multi-armed bandit framework and the annotator selection in active learning. Due to the nature of the distribution of the rewards on the arms, we use the Robust Upper Confidence Bound (UCB) scheme with truncated empirical mean estimator to solve the annotator selection problem. This yields provable guarantees on the regret. We further apply our model to the scenario where annotators are strategic and design suitable incentives to induce them to put in their best efforts.
A Utility Optimization Approach to Network Cache Design
Venue: arXiv cs.NI 2016
Year: 2016

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.
Battery-Powered Devices in WPCNs
Venue: arXiv cs.IT 2016
Year: 2016

Wireless powered communication networks are becoming an effective solution for improving self sustainability of mobile devices. In this context, a hybrid access point transfers energy to a group of nodes, which use the harvested energy to perform computation or transmission tasks. While the availability of the wireless energy transfer mechanism opens up new frontiers, an appropriate choice of the network parameters (e.g., transmission powers, transmission duration, amount of transferred energy, etc.) is required in order to achieve high performance. In this work, we study the throughput optimization problem in a system composed of an access point which recharges the batteries of two devices at different distances. In the literature, the main focus so far has been on slot-oriented optimization, in which all the harvested energy is used in the same slot in which it is harvested. However, this approach is strongly sub-optimal because it does not exploit the possibility to store the energy and use it at a later time. Thus, instead of considering the slot-oriented case, we address the long-term maximization. This assumption greatly increases the optimization complexity, requiring to consider, e.g., the channel state realizations, its statistics and the batteries evolution. Our objective is to find the best scheduling scheme, both for the energy transferred by the access point and for the data sent by the two nodes. We discuss how to perform the maximization with optimal as well as approximate techniques and show that the slot-oriented policies proposed so far are strongly sub-optimal in the long run.
A Survey on Artificial Intelligence and Data Mining for MOOCs
Venue: arXiv cs.AI 2016
Year: 2016

Massive Open Online Courses (MOOCs) have gained tremendous popularity in the last few years. Thanks to MOOCs, millions of learners from all over the world have taken thousands of high-quality courses for free. Putting together an excellent MOOC ecosystem is a multidisciplinary endeavour that requires contributions from many different fields. Artificial intelligence (AI) and data mining (DM) are two such fields that have played a significant role in making MOOCs what they are today. By exploiting the vast amount of data generated by learners engaging in MOOCs, DM improves our understanding of the MOOC ecosystem and enables MOOC practitioners to deliver better courses. Similarly, AI, supported by DM, can greatly improve student experience and learning outcomes. In this survey paper, we first review the state-of-the-art artificial intelligence and data mining research applied to MOOCs, emphasising the use of AI and DM tools and techniques to improve student engagement, learning outcomes, and our understanding of the MOOC ecosystem. We then offer an overview of key trends and important research to carry out in the fields of AI and DM so that MOOCs can reach their full potential.
Echo State Networks for Self-Organizing Resource Allocation in LTE-U with Uplink-Downlink Decoupling
Venue: arXiv cs.IT 2016
Year: 2016

Uplink-downlink decoupling in which users can be associated to different base stations in the uplink and downlink of heterogeneous small cell networks (SCNs) has attracted significant attention recently. However, most existing works focus on simple association mechanisms in LTE SCNs that operate only in the licensed band. In contrast, in this paper, the problem of resource allocation with uplink-downlink decoupling is studied for an SCN that incorporates LTE in the unlicensed band (LTE-U). Here, the users can access both licensed and unlicensed bands while being associated to different base stations. This problem is formulated as a noncooperative game that incorporates user association, spectrum allocation, and load balancing. To solve this problem, a distributed algorithm based on the machine learning framework of echo state networks is proposed using which the small base stations autonomously choose their optimal bands allocation strategies while having only limited information on the network's and users' states. It is shown that the proposed algorithm converges to a stationary mixed-strategy distribution which constitutes a mixed strategy Nash equilibrium for the studied game. Simulation results show that the proposed approach yields significant gains, in terms of the sum-rate of the 50th percentile of users, that reach up to 60% and 78%, respectively, compared to Q-learning and Q-learning without decoupling. The results also show that ESN significantly provides a considerable reduction of information exchange for the wireless network.
Identification and classification of TCM syndrome types among patients with vascular mild cognitive impairment using latent tree analysis
Venue: arXiv cs.AI 2016
Year: 2016

Objective: To treat patients with vascular mild cognitive impairment (VMCI) using TCM, it is necessary to classify the patients into TCM syndrome types and to apply different treatments to different types. We investigate how to properly carry out the classification using a novel data-driven method known as latent tree analysis. Method: A cross-sectional survey on VMCI was carried out in several regions in northern China from 2008 to 2011, which resulted in a data set that involves 803 patients and 93 symptoms. Latent tree analysis was performed on the data to reveal symptom co-occurrence patterns, and the patients were partitioned into clusters in multiple ways based on the patterns. The patient clusters were matched up with syndrome types, and population statistics of the clusters are used to quantify the syndrome types and to establish classification rules. Results: Eight syndrome types are identified: Qi Deficiency, Qi Stagnation, Blood Deficiency, Blood Stasis, Phlegm-Dampness, Fire-Heat, Yang Deficiency, and Yin Deficiency. The prevalence and symptom occurrence characteristics of each syndrome type are determined. Quantitative classification rules are established for determining whether a patient belongs to each of the syndrome types. Conclusions: A solution for the TCM syndrome classification problem associated with VMCI is established based on the latent tree analysis of unlabeled symptom survey data. The results can be used as a reference in clinic practice to improve the quality of syndrome differentiation and to reduce diagnosis variances across physicians. They can also be used for patient selection in research projects aimed at finding biomarkers for the syndrome types and in randomized control trials aimed at determining the efficacy of TCM treatments of VMCI.