1,721,057 research outputs found
Music Recommendation to Groups
Get PDFFirst we present Unison, a conceptual music recommender system for groups of people; the system aims at generating a playlist that takes musical tastes of all the group members into account. We discuss both theoretical and practical concerns related to such a system. We develop a model of user preferences and discuss how we can shift from individual recommendations to group consensus. In constructing the user preferences model we use an intermediary music track model that combines user-generated tags with a dimensionality reduction technique to build a compact spatial embedding of tracks. Secondly we introduce GroupStreamer, a practical implementation of the system that runs on Android devices. We present the technological choices that were made along the way.INDY
Mobility-centric design of collaborative transportation systems
No full textEmbedded sensors and actuators are revolutionizing the way we perceive and interact with the physical world. Current research on such Cyber-Physical Systems (CPSs) has focused mostly on distributed sensing and data gathering. The next step is to move from passive information extraction from the physical world towards an active framework where information is retrieved, processed, and acted upon in situ. As an example of such sensor-actuator systems that provide large-scale, distributed coordination, we consider Intelligent Transportation Systems (ITSs), with the goal of increasing travel safety and efficiency. The proliferation of wireless technologies enables different actors (e.g., pedestrians, motorists, traffic operators) to communicate with each other cheaply, efficiently, and securely. By embedding computational intelligence, communication and control into such ITSs, it will be possible to build collaborative transportation applications that help solve, for example, congestion and parking problems. This thesis explores the following question: To what extent is it possible to build distributed ITS systems that rely exclusively on local communication between nodes? The potential benefits of building such systems without infrastructure are numerous, including lower fixed and variable costs, avoiding regulatory hurdles, lower entry barriers for new players, and more control over privacy. On the other hand, self-organized ITSs without infrastructure have to operate under challenging conditions: large scale, high mobility, lack of end-to-end connectivity, ephemeral contacts between wireless nodes, and heterogeneous node capabilities. Although the networking research community has invested a significant effort in designing service abstractions that mimic traditional IP connectivity on top of wireless ad hoc networks, the ITS scenarios considered in this work are too challenging to implement such a service model. The main goal of this thesis is to design communication service models and their underlying protocols that can operate in collaborative transportation applications, and to demonstrate their effectiveness through analysis of traffic data and through realistic simulations. A key point is that the ITS applications we consider can rely on more limited service primitives, because they do not require a general any-to-any delivery service with strict performance guarantees. We first define the collaborative transportation applications of interest. Then we quantify their potential benefits and discuss their functional requirements. Next, we focus on the problem of the collection of large-scale mobility data. We propose a new method for collecting such data and introduce a novel mobility data mining framework, which is necessary to study collective mobility patterns in the context of wireless ad hoc networking. Relying on the analysis of real-life mobility traces, we find that despite the high node mobility, clusters of time-stable connectivity emerge and last at specific locations. Outside such clusters the connectivity between nodes remains sparse. This leads us to the proposal of a new mobility model that captures in an elegant way two phenomena observed in reality, i.e., emergence of stable clusters and network partitioning. This mobility model, called Heterogeneous Random Walk (HRW), appears to be the worst-case mobility model for many mobility-assisted protocols. Moreover, we show that the HRW mobility model predicts the performance of an epidemic dissemination protocol more accurately than other, similarly parsimonious models. Based on the lessons learned from the mobility data analysis, we propose a new abstraction that allows us to capture collective mobility patterns. This abstraction, called a Mobility Map, can be shared globally among mobile nodes and it can be used to improve communication in mobile partitioned networks (MPNs). Notably, we present a new geocasting protocol called GeoMobCast, which uses Mobility Maps to minimize message delay. This protocol is designed to provide the users of the collective transportation applications with the required communication service. Finally, we turn our attention on the real-life implementation of the distributed ITS that leverage short-range wireless communication. To this extent, we present the results of our experimental work with wireless sensor network technologies. We also present the necessary simulation toolbox designed to implement and evaluate collaborative transportation applications.INDY
Network Alignment: Theory, Algorithms, and Applications
Get PDFNetworks are central in the modeling and analysis of many large-scale human and technical systems, and they have applications in diverse fields such as computer science, biology, social sciences, and economics. Recently, network mining has been an active area of research. In this thesis, we study several related network-mining problems, from three different perspectives: the modeling and theory perspective, the computational perspective, and the application perspective. In the bulk of this thesis, we focus on network alignment, where the data provides two (or more) partial views of the network, and where the node labels are sometimes ambiguous. Network alignment has applications in social-network reconciliation and de-anonymization, protein-network alignment in biology, and computer vision. In the first part of this thesis, we investigate the feasibility of network alignment with a random-graph model. This random-graph model generates two (or several) correlated networks, and lets the two networks to overlap only partially. For a particular alignment, we define a cost function for structural mismatch. We show that the minimization of the proposed cost function (assuming that we have access to infinite computational power), with high probability, results in an alignment that recovers the set of shared nodes between the two networks, and that also recovers the true matching between the shared nodes. The most scalable network-alignment approaches use ideas from percolation theory, where a matched node-couple infects its neighboring couples that are additional potential matches. In the second part of this thesis, we propose a new percolation-based network-alignment algorithm that can match large networks by using only the network structure and a handful of initially pre-matched node-couples called seed set. We characterize a phase transition in matching performance as a function of the seed-set size. In the third part of this thesis, we consider two important application areas of network mining in biology and public health. The first application area is percolation-based network alignment of protein-protein interaction (PPI) networks in biology. The alignment of biological networks has many uses, such as the detection of conserved biological network motifs, the prediction of protein interactions, and the reconstruction of phylogenetic trees. Network alignment can be used to transfer biological knowledge between species. We introduce a new global pairwise-network alignment algorithm for PPI networks, called PROPER. The PROPER algorithm shows higher accuracy and speed compared to other global network-alignment methods. We also extend PROPER to the global multiple-network alignment problem. We introduce a new algorithm, called MPROPER, for matching multiple networks. Finally, we explore IsoRank, one of the first and most referenced global pairwise-network alignment algorithms. Our second application area is the control of epidemic processes. We develop and model strategies for mitigating an epidemic in a large-scale dynamic contact network. More precisely, we study epidemics of infectious diseases by (i) modeling the spread of epidemics on a network by using many pieces of information about the mobility and behavior of a population; and by (ii) designing personalized behavioral recommendations for individuals, in order to mitigate the effect of epidemics on that network.INDY
Collaborative routing in mobile partitioned networks
Get PDFEmbedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spatially heterogeneous node distributions, which may cause network partitions. In this thesis, we consider the problem of routing in mobile networks under such challenging conditions. More specifically, we endeavor to identify features of mobility common to different applications, in order to devise routing methods that are tailored to exploit these features. We explore two features in particular, (i) predictability and (ii) stable and heterogeneous spatial node distribution. A mobility process is predictable if the future location of a node can be well estimated, given knowledge of its current and past locations and possibly other statistics. We show how the performance of routing can be improved by explicitly incorporating mobility prediction. Specifically, we consider the performance of Last Encounter Routing (LER) under a simple synthetic random waypoint (RWP) mobility model. We extend the LER algorithm so that it takes into account predicted node trajectories when making routing decisions, and we show that this significantly improves its performance. A mobility process has a stable spatial node distribution if, informally, the node density remains the same over time, even though individual nodes are not constrained in space. This is a common feature of many mobility patterns because the spatial distribution is determined by the natural or constructed environment, regardless of the behavior of individual nodes. This typically leads to heterogeneous connectivity and to network partition, where highly connected clusters are interspersed with low-connectivity regions. We model such a situation with a set of stable concentration points (CPs) characterized by high node density, and with a mobility process that describes how nodes move between these islands of connectivity. We study two instances of this model: the G-model, where the CPs and the flow of nodes are abstracted as a graph, and the H-model, where nodes perform heterogeneous random walks on the plane. We exploit the presence of this stable CP topology in order to develop an efficient routing algorithm under these two mobility models. Our routing algorithm, Island Hopping (IH), exploits knowledge of the CP topology to make routing decisions. IH achieves a very good delay-throughput trade-off compared with several other existing routing algorithms, and it scales well with the network size. In many situations, it would be unrealistic to assume that CPs and the flows of mobile nodes among them are known a-priori. We develop methods, collectively called Collaborative Graph Discovery (COGRAD), that allow the nodes to discover the CP graph without any explicit signals from the environment (such as GPS coordinates or fixed beacons). We show that COGRAD can replace an oracle with knowledge of the CP topology after a sufficient warm-up period, allowing IH to operate even in scenarios without any cues from the environment.INDY
Learning Self-Exciting Temporal Point Processes Under Noisy Observations
No full textUnderstanding the diffusion patterns of sequences of interdependent events is a central question for a variety of disciplines. Temporal point processes are a class of elegant and powerful models of such sequences; these processes have become popular across multiple fields of research due to the increasing availability of data that captures the occurrence of events over time. A notable example is the Hawkes process. It was originally introduced by Alan Hawkes in 1971 to model the diffusion of earthquakes and was subsequently applied across fields such as epidemiology, neuroscience, criminology, finance, genomic, and social-network analysis.
A central question in these fields is the inverse problem of uncovering the diffusion patterns of the events from the observed data. The methods for solving this inverse problem assume that, in general, the data is noiseless. However, real-world observations are frequently tainted by noise in a number of ways. Most existing methods are not robust against noise and, in the presence of even a small amount of noise in the data, they might completely fail to recover the underlying dynamics. In this thesis, we remedy this shortcoming and address this problem for several types of observational noise.
First, we study the effects of small event-streams that are known to make the learning task challenging by amplifying the risk of overfitting. Using recent advances in variational inference, we introduce a new algorithm that leads to better regularization schemes and provides a measure of uncertainty on the estimated parameters.
Second, we consider events corrupted by unknown synchronized time delays. We show that the so-called synchronization noise introduces a bias in the existing estimation methods, which must be handled with care. We provide an algorithm to robustly learn the diffusion dynamics of the underlying process under this class of synchronized delays.
Third, we introduce a wider class of random and unknown time shifts, referred to as random translations, of which synchronization noise is a special case. We derive the statistical properties of Hawkes processes subject to random translations. In particular, we prove that the cumulants of Hawkes processes are invariant to random translations and we show that cumulant-based algorithms can be used to learn their underlying causal structure even when unknown time shifts distort the observations.
Finally, we consider another class of temporal point processes, the so-called Wold process that solves a computational limitation of the Bayesian treatment of Hawkes processes while retaining similar properties. We address the problem of learning the parameters of a Wold process by relaxing some of the restrictive assumptions made in the state of the art and by introducing a Bayesian approach for inferring its parameters.
In summary, the results presented in this dissertation highlight the shortcomings of standard inference methods used to fit temporal point processes. Consequently, these results deepen our ability to extract reliable insights from networks of interdependent event streams.INDY
Stochastic Models for Comparison-based Search
No full textIn this thesis we study a problem of searching in a space of objects using comparisons. To navigate through the space to the target object , we ask a sequence of questions of the form ``which object or is closer to ?'' for which we observe noisy answers. We propose two new probabilistic models for triplet comparisons , which fit the real world data better than the state-of-the-art. We study theoretical properties of these models and for both derive search algorithms that are scalable in the number of objects and that have convergence guarantees. Finally, we conduct two experiments with real users, in which we demonstrate the efficiency of the proposed methods.INDY
Efficient Learning from Comparisons
Get PDFHumans are comparison machines: comparing and choosing an item among a set of alternatives (such as objects or concepts) is arguably one of the most natural ways for us to express our preferences and opinions. In many applications, the analysis of data consisting of comparisons enables finding valuable information. But datasets often contain inconsistent comparison outcomes, because human preferences shift and observations are tainted by noise. A principled approach to dealing with intransitive data is to posit a probabilistic model of comparisons. In this thesis, we revisit Luce's choice model, the study of which began almost a century ago, in the context of large-scale online data collection. We set out to learn a ranking over a set of items from comparisons in a computationally, statistically and data efficient way.
First, we consider the algorithmic problem of estimating model parameters from choice data, and we seek to improve upon the computational and statistical efficiency of existing methods. Our contribution is to show that it is possible to express the maximizer of the model's likelihood function as the stationary distribution of a Markov chain. This enables the use of fast linear solvers or well-studied iterative methods for Markov chains for parameter inference in Luce's model.
Second, we develop a data-efficient method for learning a ranking, by adaptively choosing pairs of items to compare, based on previous comparison outcomes. We begin by showing that Quicksort, a widely-known sorting algorithm, works well even if comparison outcomes are noisy. Under distributional assumptions on model parameters, we provide asymptotic bounds on the quality of the ranking it recovers. Building on this result, we use sorting algorithms as a basis for a simple, practical active-learning method that performs well on real-world datasets, at a small fraction of the computational cost of competing methods.
Third, we focus on structured choices in a network. In particular, we study a model where users navigate in a network (e.g., following links on the Web) and set out to estimate transition probabilities along the edges of the network from limited observations. We show that if transitions follow Luce's axiom, their probability can be inferred using only data consisting of the (marginal) traffic at each node of the network.
We propose a robust inference algorithm that admits a computationally-efficient implementation. Our method scales to networks with billions of nodes and achieves good predictive performance on clickstream data.
Beyond human preferences, probabilistic models of pairwise comparisons can also be applied to sports. Consider football: two teams are compared against each other, and the better one wins. In the last part of this thesis, we look at a concrete application of pairwise comparison models and tackle the task of predicting outcomes of matches between national football teams. These teams play only a few matches every year, hence it is difficult to accurately assess their strength. Noting that national team players also compete against each other in clubs, we propose a way to overcome this challenge by taking into account outcomes of matches between clubs, of which there are plenty. We do so by embedding all matches in player space, and devise a computationally-efficient inference procedure. The resulting model predicts international tournament results more accurately than those using only national team results.LCA
Mining, Modeling and Predicting Mobility
Get PDFMobility is a central aspect of our life, and our movements reveal much more about us than simply our whereabouts. In this thesis, we are interested in mobility and study it from three different perspectives: the modeling perspective, the information-theoretic perspective, and the data mining perspective. For the modeling perspective, we represent mobility as a probabilistic process described by both observable and latent variables, and we introduce formally the notion of individual and collective dimensions in mobility models. Ideally, we should take advantage of both dimensions to learn accurate mobility models, but the nature of data might limit us. We take a data-driven approach to study three scenarios, which differ on the nature of mobility data, and present, for each scenario, a mobility model that is tailored for it. The first scenario is individual-specific as we have mobility data about individuals but are unable to cross reference data from them. In the second scenario, we introduce the collective model that we use to overcome the sparsity of individual traces, and for which we assume that individuals in the same group exhibit similar mobility patterns. Finally, we present the ideal scenario, for which we can take advantage of both the individual and collective dimensions, and analyze collective mobility patterns in order to create individual models. In the second part of the thesis, we take an information-theoretic approach in order to quantify mobility uncertainty and its evolution with location updates. We discretize the userâ s world to obtain a map that we represent as a mobility graph. We model mobility as a random walk on this graph â equivalent to a Markov chain â and quantify trajectory uncertainty as the entropy of the distribution over possible trajectories. In this setting, a location update amounts to conditioning on a particular state of the Markov chain, which requires the computation of the entropy of conditional Markov trajectories. Our main result enables us to compute this entropy through a transformation of the original Markov chain. We apply our framework to real-world mobility datasets and show that the influence of intermediate locations on trajectory entropy depends on the nature of these locations. We build on this finding and design a segmentation algorithm that uncovers intermediate destinations along a trajectory. The final perspective from which we analyze mobility is the data mining perspective: we go beyond simple mobility and analyze geo-tagged data that is generated by online social medias and that describes the whole user experience. We postulate that mining geo-tagged data enables us to obtain a rich representation of the user experience and all that surrounds its mobility. We propose a hierarchical probabilistic model that enables us to uncover specific descriptions of geographical regions, by analyzing the geo-tagged content generated by online social medias. By applying our method to a dataset of 8 million geo-tagged photos, we are able to associate with each neighborhood the tags that describe it specifically, and to find the most unique neighborhoods in a city.INDY
Privacy and Dynamics of Social Networks
Get PDFOver the past decade, investigations in different fields have focused on studying and understanding real networks, ranging from biological to social to technological. These networks, called complex networks, exhibit common topological features, such as a heavy-tailed degree distribution and the small world effect. In this thesis we address two interesting aspects of complex, and more specifically, social networks: (1) users’ privacy, and the vulnerability of a network to user identification, and (2) dynamics, or the evolution of the network over time. For this purpose, we base our contributions on a central tool in the study of graphs and complex networks: graph sampling. We conjecture that each observed network can be treated as a sample from an underlying network. Using this, a sampling process can be viewed as a way to observe dynamic networks, and to model the similarity of two correlated graphs by assuming that the graphs are samples from an underlying generator graph. We take the thesis in two directions. For the first, we focus on the privacy problem in social networks. There have been hot debates on the extent to which the release of anonymized information to the public can leak personally identifiable information (PII). Recent works have shown methods that are able to infer true user identities, under certain conditions and by relying on side information. Our approach to this problem relies on the graph structure, where we investigate the feasibility of de-anonymizing an unlabeled social network by using the structural similarity to an auxiliary network. We propose a model where the two partially overlapping networks of interest are considered samples of an underlying graph. Using such a model, first, we propose a theoretical framework for the de-anonymization problem, we obtain minimal conditions under which de-anonymization is feasible, and we establish a threshold on the similarity of the two networks above which anonymity could be lost. Then, we propose a novel algorithm based on a Bayesian framework, which is capable of matching two graphs of thousands of nodes - with no side information other than network structures. Our method has several potential applications, e.g., inferring user identities in an anonymized network by using a similar public network, cross-referencing dictionaries of different languages, correlating data from different domains, etc. We also introduce a novel privacy-preserving mechanism for social recommender systems, where users can receive accurate recommendations while hiding their profiles from an untrusted recommender server. For the second direction of this work, we focus on models for network growth, more specifically where the number of edges grows faster than the number of nodes, a property known as densification. The densification phenomenon has been recently observed in various real networks, and we argue that it can be explained simply through the way we observe (sample) networks. We introduce a process of sampling the edges of a fixed graph, which results in the super-linear growth of edges versus nodes, and show that densification arises if and only if the graph has a power-law degree distribution.INDY
Discrete-Choice Mining of Social Processes
No full textPoor decisions and selfish behaviors give rise to seemingly intractable global problems, such as the lack of transparency in democratic processes, the spread of conspiracy theories, and the rise in greenhouse gas emissions. However, people are more predictable than we think, and with machine-learning algorithms and sufficiently large datasets, we can design accurate models of human behavior in a variety of settings. In this thesis, to gain insight into social processes, we develop highly interpretable probabilistic choice-models. We draw from the econometrics literature on discrete-choice models and combine them with matrix factorization methods, Bayesian statistics, and generalized linear models. These predictive models enable interpretability through their learned parameters and latent factors.
First, we study the social dynamics behind group collaborations for the collective creation of content, such as in Wikipedia, the Linux kernel, and the European Union law-making process. By combining the Bradley-Terry and Rasch models with matrix factorization and natural language processing, we develop a model of edit acceptance in peer-production systems. We discover controversial components (e.g., Wikipedia articles and European laws) and influential users (e.g., Wikipedia editors and parliamentarians), as well as features that correlate with a high probability of edit acceptance. The latent representations capture non-linear interactions between components and users, and they cluster well into different topics (e.g., historical figures and TV characters in Wikipedia, business and environment in European laws).
Second, we develop an algorithm for predicting the outcome of elections and of referenda by combining matrix factorization and generalized linear models. Our algorithm learns representations of votes and regions, which capture ideological and cultural voting patterns (e.g., liberal/conservative, rural/urban), and it predicts the vote results in unobserved regions from partial observations. We test our model on voting data in Germany, Switzerland, and the US, and we deploy it on a Web platform to predict Swiss referendum votes in real-time. On average, our predictions reach a mean absolute error of 1% after observing only 5% of the regions.
Third, we study how people perceive the carbon footprint of their day-to-day actions. We cast this problem as a comparison problem between pairs of actions (e.g., the difference between flying across continents and using household appliances), and we develop a statistical model of relative comparisons reminiscent of the Thurstone model in psychometrics. The model learns the usersâ perception as the parameters of a Bayesian linear regression, which enables us to derive an active-learning algorithm to collect data efficiently. Our experiments show that users overestimate the emissions of low-footprint actions and underestimate those of high-footprint actions.
Finally, we design a probabilistic model of pairwise-comparison outcomes that capture a wide range of time dynamics. We achieve this by replacing the static parameters of a class of popular pairwise-comparison models with continuous-time Gaussian processes. We also develop an efficient inference algorithm that computes, with only a few linear-time iterations over the data, an approximate Bayesian posterior distribution.INDY
- …
