OpenRaiser/Intern-Atlas huggingface dataset:
Wayfinding and cognitive maps for pedestrian models
Venue: arXiv cs.AI 2016
Year: 2016

Usually, routing models in pedestrian dynamics assume that agents have fulfilled and global knowledge about the building's structure. However, they neglect the fact that pedestrians possess no or only parts of information about their position relative to final exits and possible routes leading to them. To get a more realistic description we introduce the systematics of gathering and using spatial knowledge. A new wayfinding model for pedestrian dynamics is proposed. The model defines for every pedestrian an individual knowledge representation implying inaccuracies and uncertainties. In addition, knowledge-driven search strategies are introduced. The presented concept is tested on a fictive example scenario.
A Comparison of 10 Sampling Algorithms for Configurable Systems
Venue: arXiv cs.SE 2016
Year: 2016

Almost every software system provides configuration options to tailor the system to the target platform and application scenario. Often, this configurability renders the analysis of every individual system configuration infeasible. To address this problem, researchers have proposed a diverse set of sampling algorithms. We present a comparative study of 10 state-of-the-art sampling algorithms regarding their fault-detection capability and size of sample sets. The former is important to improve software quality and the latter to reduce the time of analysis. In a nutshell, we found that sampling algorithms with larger sample sets are able to detect higher numbers of faults, but simple algorithms with small sample sets, such as most-enabled-disabled, are the most efficient in most contexts. Furthermore, we observed that the limiting assumptions made in previous work influence the number of detected faults, the size of sample sets, and the ranking of algorithms. Finally, we have identified a number of technical challenges when trying to avoid the limiting assumptions, which questions the practicality of certain sampling algorithms.
Distributed Fictitious Play for Optimal Behavior of Multi-Agent Systems with Incomplete Information
Venue: arXiv cs.GT 2016
Year: 2016

A multi-agent system operates in an uncertain environment about which agents have different and time varying beliefs that, as time progresses, converge to a common belief. A global utility function that depends on the realized state of the environment and actions of all the agents determines the system's optimal behavior. We define the asymptotically optimal action profile as an equilibrium of the potential game defined by considering the expected utility with respect to the asymptotic belief. At finite time, however, agents have not entirely congruous beliefs about the state of the environment and may select conflicting actions. This paper proposes a variation of the fictitious play algorithm which is proven to converge to equilibrium actions if the state beliefs converge to a common distribution at a rate that is at least linear. In conventional fictitious play, agents build beliefs on others' future behavior by computing histograms of past actions and best respond to their expected payoffs integrated with respect to these histograms. In the variations developed here histograms are built using knowledge of actions taken by nearby nodes and best responses are further integrated with respect to the local beliefs on the state of the environment. We exemplify the use of the algorithm in coordination and target covering games.
Compressive PCA for Low-Rank Matrices on Graphs
Venue: arXiv cs.LG 2016
Year: 2016

We introduce a novel framework for an approxi- mate recovery of data matrices which are low-rank on graphs, from sampled measurements. The rows and columns of such matrices belong to the span of the first few eigenvectors of the graphs constructed between their rows and columns. We leverage this property to recover the non-linear low-rank structures efficiently from sampled data measurements, with a low cost (linear in n). First, a Resrtricted Isometry Property (RIP) condition is introduced for efficient uniform sampling of the rows and columns of such matrices based on the cumulative coherence of graph eigenvectors. Secondly, a state-of-the-art fast low-rank recovery method is suggested for the sampled data. Finally, several efficient, parallel and parameter-free decoders are presented along with their theoretical analysis for decoding the low-rank and cluster indicators for the full data matrix. Thus, we overcome the computational limitations of the standard linear low-rank recovery methods for big datasets. Our method can also be seen as a major step towards efficient recovery of non- linear low-rank structures. For a matrix of size n X p, on a single core machine, our method gains a speed up of $p^2/k$ over Robust Principal Component Analysis (RPCA), where k << p is the subspace dimension. Numerically, we can recover a low-rank matrix of size 10304 X 1000, 100 times faster than Robust PCA.
Harmonic Grammar in a DisCo Model of Meaning
Venue: arXiv cs.AI 2016
Year: 2016

The model of cognition developed in (Smolensky and Legendre, 2006) seeks to unify two levels of description of the cognitive process: the connectionist and the symbolic. The theory developed brings together these two levels into the Integrated Connectionist/Symbolic Cognitive architecture (ICS). Clark and Pulman (2007) draw a parallel with semantics where meaning may be modelled on both distributional and symbolic levels, developed by Coecke et al, 2010 into the Distributional Compositional (DisCo) model of meaning. In the current work, we revisit Smolensky and Legendre (S&L)'s model. We describe the DisCo framework, summarise the key ideas in S&L's architecture, and describe how their description of harmony as a graded measure of grammaticality may be applied in the DisCo model.
A simple method for estimating the fractal dimension from digital images: The compression dimension
Venue: arXiv cs.GR 2016
Year: 2016

The fractal structure of real world objects is often analyzed using digital images. In this context, the compression fractal dimension is put forward. It provides a simple method for the direct estimation of the dimension of fractals stored as digital image files. The computational scheme can be implemented using readily available free software. Its simplicity also makes it very interesting for introductory elaborations of basic concepts of fractal geometry, complexity, and information theory. A test of the computational scheme using limited-quality images of well-defined fractal sets obtained from the Internet and free software has been performed. Also, a systematic evaluation of the proposed method using computer generated images of the Weierstrass cosine function shows an accuracy comparable to those of the methods most commonly used to estimate the dimension of fractal data sequences applied to the same test problem.
Efficient Access of Mobile Flows to Heterogeneous Networks under Flash Crowds
Venue: arXiv cs.NI 2016
Year: 2016

Future wireless networks need to offer orders of magnitude more capacity to address the predicted growth in mobile traffic demand. Operators to enhance the capacity of cellular networks are increasingly using WiFi to offload traffic from their core networks. This paper deals with the efficient and flexible management of a heterogeneous networking environment offering wireless access to multimode terminals. This wireless access is evaluated under disruptive usage scenarios, such as flash crowds, which can mean unwanted severe congestion on a specific operator network whilst the remaining available capacity from other access technologies is not being used. To address these issues, we propose a scalable network assisted distributed solution that is administered by centralized policies, and an embedded reputation system, by which initially selfish operators are encouraged to cooperate under the threat of churn. Our solution after detecting a congested technology, including within its wired backhaul, automatically offloads and balances the flows amongst the access resources from all the existing technologies, following some quality metrics. Our results show that the smart integration of access networks can yield an additional wireless quality for mobile flows up to thirty eight percent beyond that feasible from the best effort standalone operation of each wireless access technology. It is also evidenced that backhaul constraints are conveniently reflected on the way the flow access to wireless media is granted. Finally, we have analyzed the sensitivity of the handover decision algorithm running in each terminal agent to consecutive flash crowds, as well as its centralized feature that controls the connection quality offered by a heterogeneous access infrastructure owned by distinct operators.
Daleel: Simplifying Cloud Instance Selection Using Machine Learning
Venue: arXiv cs.DC 2016
Year: 2016

Decision making in cloud environments is quite challenging due to the diversity in service offerings and pricing models, especially considering that the cloud market is an incredibly fast moving one. In addition, there are no hard and fast rules, each customer has a specific set of constraints (e.g. budget) and application requirements (e.g. minimum computational resources). Machine learning can help address some of the complicated decisions by carrying out customer-specific analytics to determine the most suitable instance type(s) and the most opportune time for starting or migrating instances. We employ machine learning techniques to develop an adaptive deployment policy, providing an optimal match between the customer demands and the available cloud service offerings. We provide an experimental study based on extensive set of job executions over a major public cloud infrastructure.
GDoF of the MISO BC: Bridging the Gap between Finite Precision and Perfect CSIT
Venue: arXiv cs.IT 2016
Year: 2016

For the $K=2$ user MISO BC, i.e., the wireless broadcast channel where a transmitter equipped with $K=2$ antennas sends independent messages to $K=2$ receivers each of which is equipped with a single antenna, the sum generalized degrees of freedom (GDoF) are characterized for arbitrary channel strength and channel uncertainty levels for each of the channel coefficients. The result is extended to $K>2$ users under additional restrictions which include the assumption of symmetry.
A Processing In-Memory Realization Using QCA: Proposal and Implementation
Venue: arXiv cs.ET 2016
Year: 2016

Processing in Memory (PIM) is a computing paradigm that promises enormous gain in processing speed by eradicating latencies in the typical von Neumann architecture. It has gained popularity owing to its throughput by embedding storage and computation of data in a single unit. We portray implementation of Akers array architecture endowed with PIM computation using Quantum-dot Cellular Automata (QCA). We present the proof of concept of PIM with its realization in the QCA designer paradigm. We illustrate implementation of Ex-OR gate with the help of QCA based Akers Array and put forth many interesting potential possibilities.
Secure and Dependable Virtual Network Embedding
Venue: arXiv cs.NI 2016
Year: 2016

One of the fundamental problems in network virtualization is Virtual Network Embedding (VNE). The VNE problem deals with finding an effective mapping of the virtual nodes & links onto the substrate network. The recent advances in network virtualization gave cloud operators the ability to extend their cloud computing offerings with virtual networks. This trend, jointly with the increasing evidence of incidents in cloud facilities demonstrate that security and dependability is becoming a critical factor that should be considered by VNE algorithms. In this abstract we propose a VNE solution that considers security and dependability as first class citizens. The resiliency properties of our solution are enhanced by assuming a multiple cloud provider model.
On Efficient Distributed Construction of Near Optimal Routing Schemes
Venue: arXiv cs.DC 2016
Year: 2016

Given a distributed network represented by a weighted undirected graph $G=(V,E)$ on $n$ vertices, and a parameter $k$, we devise a distributed algorithm that computes a routing scheme in $(n^{1/2+1/k}+D)\cdot n^{o(1)}$ rounds, where $D$ is the hop-diameter of the network. The running time matches the lower bound of $\tildeΩ(n^{1/2}+D)$ rounds (which holds for any scheme with polynomial stretch), up to lower order terms. The routing tables are of size $\tilde{O}(n^{1/k})$, the labels are of size $O(k\log^2n)$, and every packet is routed on a path suffering stretch at most $4k-5+o(1)$. Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were by \cite[STOC 2013]{LP13} and \cite[PODC 2015]{LP15}. The former has similar properties but suffers from substantially larger routing tables of size $O(n^{1/2+1/k})$, while the latter has sub-optimal running time of $\tilde{O}(\min\{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})$.
Scalable Text Mining with Sparse Generative Models
Venue: arXiv cs.IR 2016
Year: 2016

The information age has brought a deluge of data. Much of this is in text form, insurmountable in scope for humans and incomprehensible in structure for computers. Text mining is an expanding field of research that seeks to utilize the information contained in vast document collections. General data mining methods based on machine learning face challenges with the scale of text data, posing a need for scalable text mining methods. This thesis proposes a solution to scalable text mining: generative models combined with sparse computation. A unifying formalization for generative text models is defined, bringing together research traditions that have used formally equivalent models, but ignored parallel developments. This framework allows the use of methods developed in different processing tasks such as retrieval and classification, yielding effective solutions across different text mining tasks. Sparse computation using inverted indices is proposed for inference on probabilistic models. This reduces the computational complexity of the common text mining operations according to sparsity, yielding probabilistic models with the scalability of modern search engines. The proposed combination provides sparse generative models: a solution for text mining that is general, effective, and scalable. Extensive experimentation on text classification and ranked retrieval datasets are conducted, showing that the proposed solution matches or outperforms the leading task-specific methods in effectiveness, with a order of magnitude decrease in classification times for Wikipedia article categorization with a million classes. The developed methods were further applied in two 2014 Kaggle data mining prize competitions with over a hundred competing teams, earning first and second places.
On the Degrees-of-Freedom of the Large-Scale Interfering Two-Way Relay Network
Venue: arXiv cs.IT 2016
Year: 2016

Achievable degrees-of-freedom (DoF) of the large-scale interfering two-way relay network is investigated. The network consists of $K$ pairs of communication nodes (CNs) and $N$ relay nodes (RNs). It is assumed that $K\ll N$ and each pair of CNs communicates with each other through one of the $N$ relay nodes without a direct link between them. Interference among RNs is also considered. Assuming local channel state information (CSI) at each RN, a distributed and opportunistic RN selection technique is proposed for the following three promising relaying protocols: amplify--forward, decode--forward, and compute--forward. As a main result, the asymptotically achievable DoF is characterized as $N$ increases for the three relaying protocols. In particular, a sufficient condition on $N$ required to achieve the certain DoF of the network is analyzed. Through extensive simulations, it is shown that the proposed RN selection techniques outperform conventional schemes in terms of achievable rate even in practical communication scenarios. Note that the proposed technique operates with a distributed manner and requires only local CSI, leading to easy implementation for practical wireless systems.
A Finitely presented group whose word problem has sampleable hard instances
Venue: arXiv cs.CC 2016
Year: 2016

Hard instances of natural computational problems are often elusive. In this note we present an example of a natural decision problem, the word problem for a certain finitely presented group, whose hard instances are easy to find. More precisely the problem has a complexity core sampleable in linear time.
A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups
Venue: arXiv cs.CC 2016
Year: 2016

Baumslag-Solitar groups were introduced in 1962 by Baumslag and Solitar as examples for finitely presented non-Hopfian two-generator groups. Since then, they served as examples for a wide range of purposes. As Baumslag-Solitar groups are HNN extensions, there is a natural generalization in terms of graph of groups. Concerning algorithmic aspects of generalized Baumslag-Solitar groups, several decidability results are known. Indeed, a straightforward application of standard algorithms leads to a polynomial time solution of the word problem (the question whether some word over the generators represents the identity of the group). The conjugacy problem (the question whether two given words represent conjugate group elements) is more complicated; still decidability has been established by Anshel and Stebe for ordinary Baumslag-Solitar groups and for generalized Baumslag-Solitar groups independently by Lockhart and Beeker. However, up to now no precise complexity estimates have been given. In this work, we give a LOGSPACE algorithm for both problems. More precisely, we describe a uniform TC^0 many-one reduction of the word problem to the word problem of the free group. Then we refine the known techniques for the conjugacy problem and show that it can be solved in LOGSPACE. Moreover, for ordinary Baumslag-Solitar groups also conjugacy is AC^0-Turing-reducible to the word problem of the free group. Finally, we consider uniform versions (where also the graph of groups is part of the input) of both word and conjugacy problem: while the word problem still is solvable in LOGSPACE, the conjugacy problem becomes EXPSPACE-complete.
Evaluating e-voting: theory and practice
Venue: arXiv cs.CY 2016
Year: 2016

In the Netherlands as well as many other countries, the use of electronic voting solutions is a recurrent topic of discussion. While electronic voting certainly has advantages over paper voting, there are also important risks involved. This paper presents an analysis of benefits and risks of electronic voting, and shows the relevance of these issues by means of three case studies of real-world implementations. Additionally, techniques that may be employed to improve upon many of the current systems are presented. We conclude that the advantages of E-voting do not outweigh the disadvantages, as the resulting reduced verifiability and transparency seem hard to overcome.
Energy Efficient Video Fusion with Heterogeneous CPU-FPGA Devices
Venue: arXiv cs.AR 2016
Year: 2016

This paper presents a complete video fusion system with hardware acceleration and investigates the energy trade-offs between computing in the CPU or the FPGA device. The video fusion application is based on the Dual-Tree Complex Wavelet Transforms (DT-CWT). In this work the transforms are mapped to a hardware accelerator using high-level synthesis tools for the FPGA and also vectorized code for the single instruction multiple data (SIMD) engine available in the CPU. The accelerated system reduces computation time and energy by a factor of 2. Moreover, the results show a key finding that the FPGA is not always the best choice for acceleration, and the SIMD engine should be selected when the wavelet decomposition reduces the frame size below a certain threshold. This dependency on workload size means that an adaptive system that intelligently selects between the SIMD engine and the FPGA achieves the most energy and performance efficiency point.
Multi-view Kernel Completion
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we introduce the first method that (1) can complete kernel matrices with completely missing rows and columns as opposed to individual missing kernel values, (2) does not require any of the kernels to be complete a priori, and (3) can tackle non-linear kernels. These aspects are necessary in practical applications such as integrating legacy data sets, learning under sensor failures and learning when measurements are costly for some of the views. The proposed approach predicts missing rows by modelling both within-view and between-view relationships among kernel values. We show, both on simulated data and real world data, that the proposed method outperforms existing techniques in the restricted settings where they are available, and extends applicability to new settings.
Improved Bounds for the Excluded Grid Theorem
Venue: arXiv cs.DM 2016
Year: 2016

We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function $f: Z^+\rightarrow Z^+$, such that for all integers $g>0$, every graph of treewidth at least $f(g)$ contains the $(g\times g)$-grid as a minor. Until recently, the best known upper bounds on $f$ were super-exponential in $g$. A recent work of Chekuri and Chuzhoy provided the first polynomial bound, by showing that treewidth $f(g)=O(g^{98}\operatorname{poly}\log g)$ is sufficient to ensure the existence of the $(g\times g)$-grid minor in any graph. In this paper we improve this bound to $f(g)=O(g^{19}\operatorname{poly}\log g)$. We introduce a number of new techniques, including a conceptually simple and almost entirely self-contained proof of the theorem that achieves a polynomial bound on $f(g)$.
Response to "Comment on 'Zero and negative energy dissipation at information-theoretic erasure'"
Venue: arXiv cs.ET 2016
Year: 2016

We prove that statistical information theoretic quantities, such as information entropy, cannot generally be interrelated with the lower limit of energy dissipation during information erasure. We also point out that, in deterministic and error-free computers, the information entropy of memories does not change during erasure because its value is always zero. On the other hand, for information-theoretic erasure - i.e., "thermalization" / randomization of the memory - the originally zero information entropy (with deterministic data in the memory) changes after erasure to its maximum value, 1 bit / memory bit, while the energy dissipation is still positive, even at parameters for which the thermodynamic entropy within the memory cell does not change. Information entropy does not convert to thermodynamic entropy and to the related energy dissipation; they are quantities of different physical nature. Possible specific observations (if any) indicating convertibility are at most fortuitous and due to the disregard of additional processes that are present.
On Sparsity by NUV-EM, Gaussian Message Passing, and Kalman Smoothing
Venue: arXiv cs.IT 2016
Year: 2016

Normal priors with unknown variance (NUV) have long been known to promote sparsity and to blend well with parameter learning by expectation maximization (EM). In this paper, we advocate this approach for linear state space models for applications such as the estimation of impulsive signals, the detection of localized events, smoothing with occasional jumps in the state space, and the detection and removal of outliers. The actual computations boil down to multivariate-Gaussian message passing algorithms that are closely related to Kalman smoothing. We give improved tables of Gaussian-message computations from which such algorithms are easily synthesized, and we point out two preferred such algorithms.