OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Stage Temporal Difference Learning for 2048-like Games
Venue: arXiv cs.LG 2016
Year: 2016

Szubert and Jaskowski successfully used temporal difference (TD) learning together with n-tuple networks for playing the game 2048. However, we observed a phenomenon that the programs based on TD learning still hardly reach large tiles. In this paper, we propose multi-stage TD (MS-TD) learning, a kind of hierarchical reinforcement learning method, to effectively improve the performance for the rates of reaching large tiles, which are good metrics to analyze the strength of 2048 programs. Our experiments showed significant improvements over the one without using MS-TD learning. Namely, using 3-ply expectimax search, the program with MS-TD learning reached 32768-tiles with a rate of 18.31%, while the one with TD learning did not reach any. After further tuned, our 2048 program reached 32768-tiles with a rate of 31.75% in 10,000 games, and one among these games even reached a 65536-tile, which is the first ever reaching a 65536-tile to our knowledge. In addition, MS-TD learning method can be easily applied to other 2048-like games, such as Threes. Based on MS-TD learning, our experiments for Threes also demonstrated similar performance improvement, where the program with MS-TD learning reached 6144-tiles with a rate of 7.83%, while the one with TD learning only reached 0.45%.
Find your Way by Observing the Sun and Other Semantic Cues
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present a robust, efficient and affordable approach to self-localization which does not require neither GPS nor knowledge about the appearance of the world. Towards this goal, we utilize freely available cartographic maps and derive a probabilistic model that exploits semantic cues in the form of sun direction, presence of an intersection, road type, speed limit as well as the ego-car trajectory in order to produce very reliable localization results. Our experimental evaluation shows that our approach can localize much faster (in terms of driving time) with less computation and more robustly than competing approaches, which ignore semantic information.
Generalized Preconditioning and Network Flow Problems
Venue: arXiv cs.DS 2016
Year: 2016

We consider approximation algorithms for the problem of finding $x$ of minimal norm $\|x\|$ satisfying a linear system $\mathbf{A} x = \mathbf{b}$, where the norm $\|\cdot \|$ is arbitrary and generally non-Euclidean. We show a simple general technique for composing solvers, converting iterative solvers with residual error $\|\mathbf{A} x - \mathbf{b}\| \leq t^{-Ω(1)}$ into solvers with residual error $\exp(-Ω(t))$, at the cost of an increase in $\|x\|$, by recursively invoking the solver on the residual problem $\tilde{\mathbf{b}} = \mathbf{b} - \mathbf{A} x$. Convergence of the composed solvers depends strongly on a generalization of the classical condition number to general norms, reducing the task of designing algorithms for many such problems to that of designing a \emph{generalized preconditioner} for $\mathbf{A}$. The new ideas significantly generalize those introduced by the author's earlier work on maximum flow, making them more widely applicable. As an application of the new technique, we present a nearly-linear time approximation algorithm for uncapacitated minimum-cost flow on undirected graphs. Given an undirected graph with $m$ edges labelled with costs, and $n$ vertices labelled with demands, the algorithm takes $ε^{-2}m^{1+o(1)}$-time and outputs a flow routing the demands with total cost at most $(1+ε)$ times larger than minimal, along with a dual solution proving near-optimality. The generalized preconditioner is obtained by embedding the cost metric into $\ell_1$, and then considering a simple hierarchical routing scheme in $\ell_1$ where demands initially supported on a dense lattice are pulled from a sparser lattice by randomly rounding unaligned coordinates to their aligned neighbors. Analysis of the generalized condition number for the preconditioner follows that of the classical multigrid algorithm for lattice Laplacian systems.
PPM: A Privacy Prediction Model for Online Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

Online Social Networks (OSNs) have come to play an increasingly important role in our social lives, and their inherent privacy problems have become a major concern for users. Can we assist consumers in their privacy decision-making practices, for example by predicting their preferences and giving them personalized advice? To this end, we introduce PPM: a Privacy Prediction Model, rooted in psychological principles, which can be used to give users personalized advice regarding their privacy decision-making practices. Using this model, we study psychological variables that are known to affect users' disclosure behavior: the trustworthiness of the requester/information audience, the sharing tendency of the receiver/information holder, the sensitivity of the requested/shared information, the appropriateness of the request/sharing activities, as well as several more traditional contextual factors.
CUNI System for WMT16 Automatic Post-Editing and Multimodal Translation Tasks
Venue: arXiv cs.CL 2016
Year: 2016

Neural sequence to sequence learning recently became a very promising paradigm in machine translation, achieving competitive results with statistical phrase-based systems. In this system description paper, we attempt to utilize several recently published methods used for neural sequential learning in order to build systems for WMT 2016 shared tasks of Automatic Post-Editing and Multimodal Machine Translation.
Disjunctive Normal Level Set: An Efficient Parametric Implicit Method
Venue: arXiv cs.CV 2016
Year: 2016

Level set methods are widely used for image segmentation because of their capability to handle topological changes. In this paper, we propose a novel parametric level set method called Disjunctive Normal Level Set (DNLS), and apply it to both two phase (single object) and multiphase (multi-object) image segmentations. The DNLS is formed by union of polytopes which themselves are formed by intersections of half-spaces. The proposed level set framework has the following major advantages compared to other level set methods available in the literature. First, segmentation using DNLS converges much faster. Second, the DNLS level set function remains regular throughout its evolution. Third, the proposed multiphase version of the DNLS is less sensitive to initialization, and its computational cost and memory requirement remains almost constant as the number of objects to be simultaneously segmented grows. The experimental results show the potential of the proposed method.
Human-Agent Decision-making: Combining Theory and Practice
Venue: arXiv cs.AI 2016
Year: 2016

Extensive work has been conducted both in game theory and logic to model strategic interaction. An important question is whether we can use these theories to design agents for interacting with people? On the one hand, they provide a formal design specification for agent strategies. On the other hand, people do not necessarily adhere to playing in accordance with these strategies, and their behavior is affected by a multitude of social and psychological factors. In this paper we will consider the question of whether strategies implied by theories of strategic behavior can be used by automated agents that interact proficiently with people. We will focus on automated agents that we built that need to interact with people in two negotiation settings: bargaining and deliberation. For bargaining we will study game-theory based equilibrium agents and for argumentation we will discuss logic-based argumentation theory. We will also consider security games and persuasion games and will discuss the benefits of using equilibrium based agents.
Relating Knowledge and Coordinated Action: The Knowledge of Preconditions Principle
Venue: arXiv cs.MA 2016
Year: 2016

The Knowledge of Preconditions principle (KoP) is proposed as a widely applicable connection between knowledge and action in multi-agent systems. Roughly speaking, it asserts that if some condition is a necessary condition for performing a given action A, then knowing that this condition holds is also a necessary condition for performing A. Since the specifications of tasks often involve necessary conditions for actions, the KoP principle shows that such specifications induce knowledge preconditions for the actions. Distributed protocols or multi-agent plans that satisfy the specifications must ensure that this knowledge be attained, and that it is detected by the agents as a condition for action. The knowledge of preconditions principle is formalised in the runs and systems framework, and is proven to hold in a wide class of settings. Well-known connections between knowledge and coordinated action are extended and shown to derive directly from the KoP principle: a "common knowledge of preconditions" principle is established showing that common knowledge is a necessary condition for performing simultaneous actions, and a "nested knowledge of preconditions" principle is proven, showing that coordinating actions to be performed in linear temporal order requires a corresponding form of nested knowledge.
Announcement as effort on topological spaces
Venue: arXiv cs.LO 2016
Year: 2016

We propose a multi-agent logic of knowledge, public and arbitrary announcements, that is interpreted on topological spaces in the style of subset space semantics. The arbitrary announcement modality functions similarly to the effort modality in subset space logics, however, it comes with intuitive and semantic differences. We provide axiomatizations for three logics based on this setting, and demonstrate their completeness.
One-Bit Compressive Sensing of Dictionary-Sparse Signals
Venue: arXiv cs.IT 2016
Year: 2016

One-bit compressive sensing has extended the scope of sparse recovery by showing that sparse signals can be accurately reconstructed even when their linear measurements are subject to the extreme quantization scenario of binary samples---only the sign of each linear measurement is maintained. Existing results in one-bit compressive sensing rely on the assumption that the signals of interest are sparse in some fixed orthonormal basis. However, in most practical applications, signals are sparse with respect to an overcomplete dictionary, rather than a basis. There has already been a surge of activity to obtain recovery guarantees under such a generalized sparsity model in the classical compressive sensing setting. Here, we extend the one-bit framework to this important model, providing a unified theory of one-bit compressive sensing under dictionary sparsity. Specifically, we analyze several different algorithms---based on convex programming and on hard thresholding---and show that, under natural assumptions on the sensing matrix (satisfied by Gaussian matrices), these algorithms can efficiently recover analysis-dictionary-sparse signals in the one-bit model.
SNAP: A General Purpose Network Analysis and Graph Mining Library
Venue: arXiv cs.SI 2016
Year: 2016

Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an increasing need to analyze and manipulate large networks, only a limited number of tools are available for this task. Here, we describe Stanford Network Analysis Platform (SNAP), a general-purpose, high-performance system that provides easy to use, high-level operations for analysis and manipulation of large networks. We present SNAP functionality, describe its implementational details, and give performance benchmarks. SNAP has been developed for single big-memory machines and it balances the trade-off between maximum performance, compact in-memory graph representation, and the ability to handle dynamic graphs where nodes and edges are being added or removed over time. SNAP can process massive networks with hundreds of millions of nodes and billions of edges. SNAP offers over 140 different graph algorithms that can efficiently manipulate large graphs, calculate structural properties, generate regular and random graphs, and handle attributes and meta-data on nodes and edges. Besides being able to handle large graphs, an additional strength of SNAP is that networks and their attributes are fully dynamic, they can be modified during the computation at low cost. SNAP is provided as an open source library in C++ as well as a module in Python. We also describe the Stanford Large Network Dataset, a set of social and information real-world networks and datasets, which we make publicly available. The collection is a complementary resource to our SNAP software and is widely used for development and benchmarking of graph analytics algorithms.
On (Secure) Information flow for Multiple-Unicast Sessions: Analysis with Butterfly Network
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a class of wireline networks, derived from the well-known butterfly network, over which two independent unicast sessions take place simultaneously. The main objectives are to understand when network coding type of operations are beneficial with and without security considerations and to derive the ultimate gains that cooperation among sources and sinks can bring. Towards these goals, the capacity region of the butterfly network with arbitrary edge capacities is first derived. It is then shown that no rate can be guaranteed over this network under security considerations, when an eavesdropper wiretaps any of the links. Three variants of the butterfly network, such as the case of co-located sources, are analyzed as well and their secure and non-secure capacity regions are characterized. By using the butterfly network and its variants as building blocks, these results can be used to design high-throughput achieving transmission schemes for general multiple-unicast networks.
An Active Machine Hearing System for Auditory Stream Segregation
Venue: arXiv cs.SD 2016
Year: 2016

This study describes a binaural machine hearing system that is capable of performing auditory stream segregation in scenarios where multiple sound sources are present. The process of stream segregation refers to the capability of human listeners to group acoustic signals into sets of distinct auditory streams, corresponding to individual sound sources. The proposed computational framework mimics this ability via a probabilistic clustering scheme for joint localization and segregation. This scheme is based on mixtures of von Mises distributions to model the angular positions of the sound sources surrounding the listener. The distribution parameters are estimated using block-wise processing of auditory cues extracted from binaural signals. Additionally, the proposed system can conduct rotational head movements to improve localization and stream segregation performance. Evaluation of the system is conducted in scenarios containing multiple simultaneously active speech and non-speech sounds placed at different positions relative to the listener.
A Testbed for Transiently Powered Computers
Venue: arXiv cs.ET 2016
Year: 2016

Transiently Powered Computers (TPCs) are novel devices that are battery-less and operate using only ambient energy. Therefore TPCs are prone to frequent power interruptions, and such the need for developing TPC-centric algorithms is a necessity. We advocate that only through a common experimental environment, accessible to everyone, a proper comparison of newly developed algorithms for TPCs can be realized. Moreover, only through access to various TPC testbeds---distributed geographically throughout the world---a proper applications testing and validation are possible. We enlist properties and features that any TPC testbed should have, calling for more coordinated action in this domain of TPC research. Finally, we present (to the best of our knowledge) world's first Internet-accessible testbed for TPCs.
Message-Combining Algorithms for Isomorphic, Sparse Collective Communication
Venue: arXiv cs.DC 2016
Year: 2016

Isomorphic (sparse) collective communication is a form of collective communication in which all involved processes communicate in small, identically structured neighborhoods of other processes. Isomorphic neighborhoods are defined via an embedding of the processes in a regularly structured topology, e.g., $d$-dimensional torus, which may correspond to the physical communication network of the underlying system. Isomorphic collective communication is useful for implementing stencil and other regular, sparse distributed computations, where the assumption that all processes behave (almost) symmetrically is justified. In this paper, we show how efficient message-combining communication schedules for isomorphic, sparse collective communication can easily and efficiently be computed by purely local computations. We give schemes for \emph{isomorphic \alltoall} and \emph{\allgather} communication that reduce the number of communication rounds and thereby the communication latency from $s$ to at most $Nd$, for neighborhoods consisting of $s$ processes with the (small) factor $N$ depending on the structure of the neighborhood and the capabilities of the communication system. Using these schedules, we give \emph{zero-copy implementations} of the isomorphic collectives using MPI and its derived datatypes to eliminate explicit, process-local copy operations. By benchmarking the collective communication algorithms against straightforward implementations and against the corresponding MPI neighborhood collectives, we document significant latency improvements of our implementations for block sizes of up to a few kilobytes. We discuss further optimizations for computing even better schedules, some of which have been implemented and benchmarked.
Collective Semi-Supervised Learning for User Profiling in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

The abundance of user-generated data in social media has incentivized the development of methods to infer the latent attributes of users, which are crucially useful for personalization, advertising and recommendation. However, the current user profiling approaches have limited success, due to the lack of a principled way to integrate different types of social relationships of a user, and the reliance on scarcely-available labeled data in building a prediction model. In this paper, we present a novel solution termed Collective Semi-Supervised Learning (CSL), which provides a principled means to integrate different types of social relationship and unlabeled data under a unified computational framework. The joint learning from multiple relationships and unlabeled data yields a computationally sound and accurate approach to model user attributes in social media. Extensive experiments using Twitter data have demonstrated the efficacy of our CSL approach in inferring user attributes such as account type and marital status. We also show how CSL can be used to determine important user features, and to make inference on a larger user population.
On Lossless Feedback Delay Networks
Venue: arXiv cs.SY 2016
Year: 2016

Lossless Feedback Delay Networks (FDNs) are commonly used as a design prototype for artificial reverberation algorithms. The lossless property is dependent on the feedback matrix, which connects the output of a set of delays to their inputs, and the lengths of the delays. Both, unitary and triangular feedback matrices are known to constitute lossless FDNs, however, the most general class of lossless feedback matrices has not been identified. In this contribution, it is shown that the FDN is lossless for any set of delays, if all irreducible components of the feedback matrix are diagonally similar to a unitary matrix. The necessity of the generalized class of feedback matrices is demonstrated by examples of FDN designs proposed in literature.
Modelling User Preferences using Word Embeddings for Context-Aware Venue Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Venue recommendation aims to assist users by making personalised suggestions of venues to visit, building upon data available from location-based social networks (LBSNs) such as Foursquare. A particular challenge for this task is context-aware venue recommendation (CAVR), which additionally takes the surrounding context of the user (e.g. the user's location and the time of day) into account in order to provide more relevant venue suggestions. To address the challenges of CAVR, we describe two approaches that exploit word embedding techniques to infer the vector-space representations of venues, users' existing preferences, and users' contextual preferences. Our evaluation upon the test collection of the TREC 2015 Contextual Suggestion track demonstrates that we can significantly enhance the effectiveness of a state-of-the-art venue recommendation approach, as well as produce context-aware recommendations that are at least as effective as the top TREC 2015 systems.
FPMax: a 106GFLOPS/W at 217GFLOPS/mm2 Single-Precision FPU, and a 43.7GFLOPS/W at 74.6GFLOPS/mm2 Double-Precision FPU, in 28nm UTBB FDSOI
Venue: arXiv cs.AR 2016
Year: 2016

FPMax implements four FPUs optimized for latency or throughput workloads in two precisions, fabricated in 28nm UTBB FDSOI. Each unit's parameters, e.g pipeline stages, booth encoding etc., were optimized to yield 1.42ns latency at 110GLOPS/W (SP) and 1.39ns latency at 36GFLOPS/W (DP). At 100% activity, body-bias control improves the energy efficiency by about 20%; at 10% activity this saving is almost 2x. Keywords: FPU, energy efficiency, hardware generator, SOI
Finding the Topic of a Set of Images
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we introduce the problem of determining the topic that a set of images is describing, where every topic is represented as a set of words. Different from other problems like tag assignment or similar, a) we assume multiple images are used as input instead of single image, b) Input images are typically not visually related, c) Input images are not necessarily semantically close, and d) Output word space is unconstrained. In our proposed solution, visual information of each query image is used to retrieve similar images with text labels (tags) from an image database. We consider a scenario where the tags are very noisy and diverse, given that they were obtained by implicit crowd-sourcing in a database of 1 million images and over seventy seven thousand tags. The words or tags associated to each query are processed jointly in a word selection algorithm using random walks that allows to refine the search topic, rejecting words that are not part of the topic and produce a set of words that fairly describe the topic. Experiments on a dataset of 300 topics, with up to twenty images per topic, show that our algorithm performs better than the proposed baseline for any number of query images. We also present a new Conditional Random Field (CRF) word mapping algorithm that preserves the semantic similarity of the mapped words, increasing the performance of the results over the baseline.
XML Entity Architecture for Efficient Software Integration
Venue: arXiv cs.SE 2016
Year: 2016

This paper proposed xml entities based architectural implementation to improve integration between multiple third party vendor software systems with incompatible xml schema. The xml entity architecture implementation showed that the lines of code change required for mapping the schema between in house software and three other vendor schema, decreased by 5.2%, indicating an improvement in quality. The schema mapping development time decreased by 3.8% and overall release time decreased by 5.3%, indicating an improvement in productivity. The proposed technique proved that using xml entities and XSLT transforms is more efficient in terms of coding effort and deployment complexity when compared to mapping the schema using object oriented scripting language such as C#.