OpenRaiser/Intern-Atlas huggingface dataset:
Homomorphic Encryption Experiments on IBM's Cloud Quantum Computing Platform
Venue: arXiv cs.CR 2017
Year: 2017

Quantum computing has undergone rapid development in recent years. Owing to limitations on scalability, personal quantum computers still seem slightly unrealistic in the near future. The first practical quantum computer for ordinary users is likely to be on the cloud. However, the adoption of cloud computing is possible only if security is ensured. Homomorphic encryption is a cryptographic protocol that allows computation to be performed on encrypted data without decrypting them, so it is well suited to cloud computing. Here, we first applied homomorphic encryption on IBM's cloud quantum computer platform. In our experiments, we successfully implemented a quantum algorithm for linear equations while protecting our privacy. This demonstration opens a feasible path to the next stage of development of cloud quantum information technology.
Demo: WiSCoP - Wireless Sensor Communication Prototyping Platform
Venue: arXiv cs.NI 2017
Year: 2017

To enhance system performance of future heterogeneous wireless networks the co-design of PHY, MAC, and higher layer protocols is inevitable. In this work, we present WiSCoP - a novel embedded platform for experimentation, prototyping and implementation of integrated cross-layer network design approaches. WiSCoP is built on top of a Zynq hardware platform integrated with FMCOMMS1/2/4 RF front ends. We demonstrate the flexibility of WiSCoP by using it to prototype a fully standard compliant IEEE 802.15.4 stack with real-time performance and cross-layer integration.
Principles for Measurability in Protocol Design
Venue: arXiv cs.NI 2017
Year: 2017

Measurement has become fundamental to the operation of networks and at-scale services---whether for management, security, diagnostics, optimization, or simply enhancing our collective understanding of the Internet as a complex system. Further, measurements are useful across points of view---from end hosts to enterprise networks and data centers to the wide area Internet. We observe that many measurements are decoupled from the protocols and applications they are designed to illuminate. Worse, current measurement practice often involves the exploitation of side-effects and unintended features of the network, or, in other words, the artful piling of hacks atop one another. This state of affairs is a direct result of the relative paucity of diagnostic and measurement capabilities built into today's network stack. Given our modern dependence on ubiquitous measurement, we propose measurability as an explicit low-level goal of current protocol design, and argue that measurements should be available to all network protocols throughout the stack. We seek to generalize the idea of measurement within protocols, e.g., the way in which TCP relies on measurement to drive its end-to-end behavior. Rhetorically, we pose the question: what if the stack had been built with measurability and diagnostic support in mind? We start from a set of principles for explicit measurability, and define primitives that, were they supported by the stack, would not only provide a solid foundation for protocol design going forward, but also reduce the cost and increase the accuracy of measuring the network.
#HashtagWars: Learning a Sense of Humor
Venue: arXiv cs.CL 2017
Year: 2017

In this work, we present a new dataset for computational humor, specifically comparative humor ranking, which attempts to eschew the ubiquitous binary approach to humor detection. The dataset consists of tweets that are humorous responses to a given hashtag. We describe the motivation for this new dataset, as well as the collection process, which includes a description of our semi-automated system for data collection. We also present initial experiments for this dataset using both unsupervised and supervised approaches. Our best supervised system achieved 63.7% accuracy, suggesting that this task is much more difficult than comparable humor detection tasks. Initial experiments indicate that a character-level model is more suitable for this task than a token-level model, likely due to a large amount of puns that can be captured by a character-level model.
Knowledge Elicitation via Sequential Probabilistic Inference for High-Dimensional Prediction
Venue: arXiv cs.AI 2017
Year: 2017

Prediction in a small-sized sample with a large number of covariates, the "small n, large p" problem, is challenging. This setting is encountered in multiple applications, such as precision medicine, where obtaining additional samples can be extremely costly or even impossible, and extensive research effort has recently been dedicated to finding principled solutions for accurate prediction. However, a valuable source of additional information, domain experts, has not yet been efficiently exploited. We formulate knowledge elicitation generally as a probabilistic inference process, where expert knowledge is sequentially queried to improve predictions. In the specific case of sparse linear regression, where we assume the expert has knowledge about the values of the regression coefficients or about the relevance of the features, we propose an algorithm and computational approximation for fast and efficient interaction, which sequentially identifies the most informative features on which to query expert knowledge. Evaluations of our method in experiments with simulated and real users show improved prediction accuracy already with a small effort from the expert.
Kernel-based Reconstruction of Space-time Functions on Dynamic Graphs
Venue: arXiv cs.LG 2017
Year: 2017

Graph-based methods pervade the inference toolkits of numerous disciplines including sociology, biology, neuroscience, physics, chemistry, and engineering. A challenging problem encountered in this context pertains to determining the attributes of a set of vertices given those of another subset at possibly different time instants. Leveraging spatiotemporal dynamics can drastically reduce the number of observed vertices, and hence the cost of sampling. Alleviating the limited flexibility of existing approaches, the present paper broadens the existing kernel-based graph function reconstruction framework to accommodate time-evolving functions over possibly time-evolving topologies. This approach inherits the versatility and generality of kernel-based methods, for which no knowledge on distributions or second-order statistics is required. Systematic guidelines are provided to construct two families of space-time kernels with complementary strengths. The first facilitates judicious control of regularization on a space-time frequency plane, whereas the second can afford time-varying topologies. Batch and online estimators are also put forth, and a novel kernel Kalman filter is developed to obtain these estimates at affordable computational cost. Numerical tests with real data sets corroborate the merits of the proposed methods relative to competing alternatives.
On the SNR Variability in Noisy Compressed Sensing
Venue: arXiv cs.IT 2017
Year: 2017

Compressed sensing (CS) is a sampling paradigm that allows to simultaneously measure and compress signals that are sparse or compressible in some domain. The choice of a sensing matrix that carries out the measurement has a defining impact on the system performance and it is often advocated to draw its elements randomly. It has been noted that in the presence of input (signal) noise, the application of the sensing matrix causes SNR degradation due to the noise folding effect. In fact, it might also result in the variations of the output SNR in compressive measurements over the support of the input signal, potentially resulting in unexpected non-uniform system performance. In this work, we study the impact of a distribution from which the elements of a sensing matrix are drawn on the spread of the output SNR. We derive analytic expressions for several common types of sensing matrices and show that the SNR spread grows with the decrease of the number of measurements. This makes its negative effect especially pronounced for high compression rates that are often of interest in CS.
Spreadsheet Guardian: An Approach to Protecting Semantic Correctness throughout the Evolution of Spreadsheets
Venue: arXiv cs.SE 2017
Year: 2017

Spreadsheets are powerful tools which play a business-critical role in many organizations. However, many bad decisions taken due to faulty spreadsheets show that these tools need serious quality assurance. Furthermore, while collaboration on spreadsheets for maintenance tasks is common, there has been almost no support for ensuring that the spreadsheets remain correct during this process. We have developed an approach named Spreadsheet Guardian which separates the specification of spreadsheet test rules from their execution. By automatically executing user-defined test rules, our approach is able to detect semantic faults. It also protects all collaborating spreadsheet users from introducing faults during maintenance, even if only few end-users specify test rules. To evaluate Spreadsheet Guardian, we implemented a representative testing technique as an add-in for Microsoft Excel. We evaluated the testing technique in two empirical evaluations with 29 end-users and 42 computer science students. The results indicate that the technique is easy to learn and to apply. Furthermore, after finishing maintenance, participants with spreadsheets "protected" by the technique are more realistic about the correctness of their spreadsheets than participants who employ only "classic", non-interactive test rules based on static analysis techniques. Hence, we believe Spreadsheet Guardian can be of use for business-critical spreadsheets.
Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)
Venue: arXiv cs.LG 2017
Year: 2017

Tensor decompositions have rich applications in statistics and machine learning, and developing efficient, accurate algorithms for the problem has received much attention recently. Here, we present a new method built on Kruskal's uniqueness theorem to decompose symmetric, nearly orthogonally decomposable tensors. Unlike the classical higher-order singular value decomposition which unfolds a tensor along a single mode, we consider unfoldings along two modes and use rank-1 constraints to characterize the underlying components. This tensor decomposition method provably handles a greater level of noise compared to previous methods and achieves a high estimation accuracy. Numerical results demonstrate that our algorithm is robust to various noise distributions and that it performs especially favorably as the order increases.
Restless Video Bandits: Optimal SVC Streaming in a Multi-user Wireless Network
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we consider the problem of optimal scalable video delivery to mobile users in wireless networks given arbitrary Quality Adaptation (QA) mechanisms. In current practical systems, QA and scheduling are performed independently by the content provider and network operator, respectively. While most research has been focused on jointly optimizing these two tasks, the high complexity that comes with a joint approach makes the implementation impractical. Therefore, we present a scheduling mechanism that takes the QA logic of each user as input and optimizes the scheduling accordingly. Hence, there is no need for centralized QA and cross-layer interactions are minimized. We model the QA-adaptive scheduling and the jointly optimal problem as a Restless Bandit and a Multi-user Semi Markov Decision Process, respectively in order to compare the loss incurred by not employing a jointly optimal scheme. We then present heuristic algorithms in order to achieve the optimal outcome of the Restless Bandit solution assuming the base station has knowledge of the underlying quality adaptation of each user (QA-Aware). We also present a simplified heuristic without the need for any higher layer knowledge at the base station (QA-Blind). We show that our QA-Aware strategy can achieve up to two times improvement in user network utilization compared to popular baseline algorithms such as Proportional Fairness. We also provide a testbed implementation of the QA-Blind scheme in order to compare it with baseline algorithms in a real network setting.
Avoiding communication in primal and dual block coordinate descent methods
Venue: arXiv cs.DC 2017
Year: 2017

Primal and dual block coordinate descent methods are iterative methods for solving regularized and unregularized optimization problems. Distributed-memory parallel implementations of these methods have become popular in analyzing large machine learning datasets. However, existing implementations communicate at every iteration which, on modern data center and supercomputing architectures, often dominates the cost of floating-point computation. Recent results on communication-avoiding Krylov subspace methods suggest that large speedups are possible by re-organizing iterative algorithms to avoid communication. We show how applying similar algorithmic transformations can lead to primal and dual block coordinate descent methods that only communicate every $s$ iterations--where $s$ is a tuning parameter--instead of every iteration for the \textit{regularized least-squares problem}. We show that the communication-avoiding variants reduce the number of synchronizations by a factor of $s$ on distributed-memory parallel machines without altering the convergence rate and attains strong scaling speedups of up to $6.1\times$ on a Cray XC30 supercomputer.
Information Extraction with Character-level Neural Networks and Free Noisy Supervision
Venue: arXiv cs.CL 2017
Year: 2017

We present an architecture for information extraction from text that augments an existing parser with a character-level neural network. The network is trained using a measure of consistency of extracted data with existing databases as a form of noisy supervision. Our architecture combines the ability of constraint-based information extraction systems to easily incorporate domain knowledge and constraints with the ability of deep neural networks to leverage large amounts of data to learn complex features. Boosting the existing parser's precision, the system led to large improvements over a mature and highly tuned constraint-based production information extraction system used at Bloomberg for financial language text.
How do people explore virtual environments?
Venue: arXiv cs.CV 2017
Year: 2017

Understanding how people explore immersive virtual environments is crucial for many applications, such as designing virtual reality (VR) content, developing new compression algorithms, or learning computational models of saliency or visual attention. Whereas a body of recent work has focused on modeling saliency in desktop viewing conditions, VR is very different from these conditions in that viewing behavior is governed by stereoscopic vision and by the complex interaction of head orientation, gaze, and other kinematic constraints. To further our understanding of viewing behavior and saliency in VR, we capture and analyze gaze and head orientation data of 169 users exploring stereoscopic, static omni-directional panoramas, for a total of 1980 head and gaze trajectories for three different viewing conditions. We provide a thorough analysis of our data, which leads to several important insights, such as the existence of a particular fixation bias, which we then use to adapt existing saliency predictors to immersive VR conditions. In addition, we explore other applications of our data and analysis, including automatic alignment of VR video cuts, panorama thumbnails, panorama video synopsis, and saliency-based compression.
Predicting Process Behaviour using Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

Predicting business process behaviour is an important aspect of business process management. Motivated by research in natural language processing, this paper describes an application of deep learning with recurrent neural networks to the problem of predicting the next event in a business process. This is both a novel method in process prediction, which has largely relied on explicit process models, and also a novel application of deep learning methods. The approach is evaluated on two real datasets and our results surpass the state-of-the-art in prediction precision.
Defining the Pose of any 3D Rigid Object and an Associated Distance
Venue: arXiv cs.CV 2017
Year: 2017

The pose of a rigid object is usually regarded as a rigid transformation, described by a translation and a rotation. However, equating the pose space with the space of rigid transformations is in general abusive, as it does not account for objects with proper symmetries -- which are common among man-made objects.In this article, we define pose as a distinguishable static state of an object, and equate a pose with a set of rigid transformations. Based solely on geometric considerations, we propose a frame-invariant metric on the space of possible poses, valid for any physical rigid object, and requiring no arbitrary tuning. This distance can be evaluated efficiently using a representation of poses within an Euclidean space of at most 12 dimensions depending on the object's symmetries. This makes it possible to efficiently perform neighborhood queries such as radius searches or k-nearest neighbor searches within a large set of poses using off-the-shelf methods. Pose averaging considering this metric can similarly be performed easily, using a projection function from the Euclidean space onto the pose space. The practical value of those theoretical developments is illustrated with an application of pose estimation of instances of a 3D rigid object given an input depth map, via a Mean Shift procedure.
Cloud Dictionary: Sparse Coding and Modeling for Point Clouds
Venue: arXiv cs.CV 2017
Year: 2017

With the development of range sensors such as LIDAR and time-of-flight cameras, 3D point cloud scans have become ubiquitous in computer vision applications, the most prominent ones being gesture recognition and autonomous driving. Parsimony-based algorithms have shown great success on images and videos where data points are sampled on a regular Cartesian grid. We propose an adaptation of these techniques to irregularly sampled signals by using continuous dictionaries. We present an example application in the form of point cloud denoising.
Coupling Adaptive Batch Sizes with Learning Rates
Venue: arXiv cs.LG 2017
Year: 2017

Mini-batch stochastic gradient descent and variants thereof have become standard for large-scale empirical risk minimization like the training of neural networks. These methods are usually used with a constant batch size chosen by simple empirical inspection. The batch size significantly influences the behavior of the stochastic optimization algorithm, though, since it determines the variance of the gradient estimates. This variance also changes over the optimization process; when using a constant batch size, stability and convergence is thus often enforced by means of a (manually tuned) decreasing learning rate schedule. We propose a practical method for dynamic batch size adaptation. It estimates the variance of the stochastic gradients and adapts the batch size to decrease the variance proportionally to the value of the objective function, removing the need for the aforementioned learning rate decrease. In contrast to recent related work, our algorithm couples the batch size to the learning rate, directly reflecting the known relationship between the two. On popular image classification benchmarks, our batch size adaptation yields faster optimization convergence, while simultaneously simplifying learning rate tuning. A TensorFlow implementation is available.
A Phase Vocoder based on Nonstationary Gabor Frames
Venue: arXiv cs.SD 2017
Year: 2017

We propose a new algorithm for time stretching music signals based on the theory of nonstationary Gabor frames (NSGFs). The algorithm extends the techniques of the classical phase vocoder (PV) by incorporating adaptive time-frequency (TF) representations and adaptive phase locking. The adaptive TF representations imply good time resolution for the onsets of attack transients and good frequency resolution for the sinusoidal components. We estimate the phase values only at peak channels and the remaining phases are then locked to the values of the peaks in an adaptive manner. During attack transients we keep the stretch factor equal to one and we propose a new strategy for determining which channels are relevant for reinitializing the corresponding phase values. In contrast to previously published algorithms we use a non-uniform NSGF to obtain a low redundancy of the corresponding TF representation. We show that with just three times as many TF coefficients as signal samples, artifacts such as phasiness and transient smearing can be greatly reduced compared to the classical PV. The proposed algorithm is tested on both synthetic and real world signals and compared with state of the art algorithms in a reproducible manner.
Zero-Collateral Lotteries in Bitcoin and Ethereum
Venue: arXiv cs.CR 2017
Year: 2017

We present cryptocurrency-based lottery protocols that do not require any collateral from the players. Previous protocols for this task required a security deposit that is $O(N^2)$ times larger than the bet amount, where $N$ is the number of players. Our protocols are based on a tournament bracket construction, and require only $O(\log N)$ rounds. Our lottery protocols thus represent a significant improvement, both because they allow players with little money to participate, and because of the time value of money. The Ethereum-based implementation of our lottery is highly efficient. The Bitcoin implementation requires an $O(2^N)$ off-chain setup phase, which demonstrates that the expressive power of the scripting language can have important implications. We also describe a minimal modification to the Bitcoin protocol that would eliminate the exponential blowup.
Cache-Enabled Heterogeneous Cellular Networks: Optimal Tier-Level Content Placement
Venue: arXiv cs.IT 2017
Year: 2017

Caching popular contents at base stations (BSs) of a heterogeneous cellular network (HCN) avoids frequent information passage from content providers to the network edge, thereby reducing latency and alleviating traffic congestion in backhaul links. In general, the optimal strategies for content placement in HCNs remain largely unknown and deriving them forms the theme of this paper. To this end, we adopt the popular random HCN model where $K$ tiers of BSs are modelled as independent Poisson point processes distributed in the plane with different densities. Further, the random caching scheme is considered where each of a given set of $M$ files with corresponding popularity measures is placed at each BS of a particular tier with a corresponding probability, called placement probability. The probabilities are identical for all BSs in the same tier but vary over tiers, giving the name tier-level content placement. We consider the network performance metric, hit probability, defined as the probability that a file requested by the typical user is delivered successfully to the user. We maximize the hit probability over content placement probabilities, which yields the optimal tier-level placement policies. For the case of uniform received signal-to-interference thresholds for successful transmissions for BSs in different tiers, the policy is in closed-form where the placement probability for a particular file is proportional to the square-root of the corresponding popularity measure with an offset depending on BS caching capacities. For the general case of non-uniform SIR thresholds, the optimization problem is non-convex and a sub-optimal placement policy is designed by approximation, which has a similar structure as in the case of uniform SIR thresholds and shown by simulation to be close-to-optimal.