1,721,156 research outputs found
Local Rules for Global MAP: When Do They Work?
No full textWe consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within n log2 n iterations with high probability for any n node pair-wise MRF with geometry (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood – this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry
Scaling Laws for Heterogeneous Wireless Networks
Full text linkThesis Supervisor: Devavrat Shah
Title: Associate Professor
Thesis Supervisor: Gregory W. Wornell
Title: ProfessorThis thesis studies the problem of determining achievable rates in heterogeneous wireless
networks. We analyze the impact of location, traffic, and service heterogeneity.
Consider a wireless network with n nodes located in a square area of size n communicating
with each other over Gaussian fading channels. Location heterogeneity is
modeled by allowing the nodes in the wireless network to be deployed in an arbitrary
manner on the square area instead of the usual random uniform node placement. For
traffic heterogeneity, we analyze the n × n dimensional unicast capacity region. For
service heterogeneity, we consider the impact of multicasting and caching. This gives
rise to the n × 2n dimensional multicast capacity region and the 2n × n dimensional
caching capacity region. In each of these cases, we obtain an explicit informationtheoretic
characterization of the scaling of achievable rates by providing a converse
and a matching (in the scaling sense) communication architecture.National Science Foundation. DARPA, and Hewlett-Packard under the MIT/HP Alliance
eCMT-SCTP: Improving Performance of Multipath SCTP with Erasure Coding Over Lossy Links
Full text linkPerformance of transport protocols on lossy links is a well-researched topic, however there are only a few proposals making use of the opportunities of erasure coding within the multipath transport protocol context. In this paper, we investigate performance improvements of multipath CMT-SCTP with the novel integration of the on-the-fly erasure code within congestion control and reliability mechanisms. Our contributions include: integration of transport protocol and erasure codes with regards to congestion control; proposal for a variable retransmission delay parameter (aRTX) adjustment; performance evaluation of CMT-SCTP with erasure coding with simulations. We have implemented the explicit congestion notification (ECN) and erasure coding schemes in NS-2, evaluated and demonstrated results of improvement both for application goodput and decline of spurious retransmission. Our results show that we can achieve from 10% to 80% improvements in goodput under lossy network conditions without a significant penalty and minimal overhead due to the encoding-decoding process
Compute Choice (Invited Talk)
No full textIn this talk, we shall discuss the question of learning distribution over permutations of n choices based on partial observations. This is central to capturing the so called "choice" in a variety of contexts: understanding preferences of consumers over a collection of products based on purchasing and browsing data in the setting of retail and e-commerce, learning public opinion amongst a collection of socio-economic issues based on sparse polling data, and deciding a ranking of teams or players based on outcomes of games. The talk will primarily discuss the relationship between the ability to learn, nature of partial information and number of available observations. Connections to the classical theory of social choice and behavioral psychology, as well as modern literature in Statistics, learning theory and operations research will be discussed
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Distributed averaging in dynamic networks
No full textThesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (p. 39-40).The question of computing average of numbers present at nodes in a network in a distributed manner using gossip or message-passing algorithms has been of great recent interest across disciplines -- algorithms, control and robotics, estimation, social networks, etc. It has served as a non-trivial, representative model for an important class of questions arising in these disciplines and thus guiding intellectual progress over the past few decades. In most of these applications, there is inherent dynamics present, such as changes in the network topology in terms of communication links, changes in the values of numbers present at nodes, and nodes joining or leaving. The effect of dynamics in terms of communication links on the design and analysis of algorithms for averaging is reasonably well understood, e.g. [14][2][8][4]. However, little is known about the effect of other forms of dynamics. In this thesis, we study the effect of such types of dynamics in the context of maintaining average in the network. Specifically, we design dynamics-aware message-passing or gossip algorithm that maintains good estimate of average in presence of continuous change in numbers at nodes. Clearly, in presence of such dynamics the best one can hope for is a tradeoff between the accuracy of each node's estimate of the average at each time instant and the rate of dynamics. For our algorithm, we characterize this tradeoff and establish it to be near optimal. The dependence of the accuracy of the algorithm on the rate of dynamics as well as on the underlying graph structure is quantified.by Shreevatsa Rajagopalan.S.M
Sequential data inference via matrix estimation : causal inference, cricket and retail
Full text linkThesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (pages 185-193).This thesis proposes a unified framework to capture the temporal and longitudinal variation across multiple instances of sequential data. Examples of such data include sales of a product over a period of time across several retail locations; trajectories of scores across cricket games; and annual tobacco consumption across the United States over a period of decades. A key component of our work is the latent variable model (LVM) which views the sequential data as a matrix where the rows correspond to multiple sequences while the columns represent the sequential aspect. The goal is to utilize information in the data within the sequence and across different sequences to address two inferential questions: (a) imputation or "filling missing values" and "de-noising" observed values, and (b) forecasting or predicting "future" values, for a given sequence of data. Using this framework, we build upon the recent developments in "matrix estimation" to address the inferential goals in three different applications. First, a robust variant of the popular "synthetic control" method used in observational studies to draw causal statistical inferences. Second, a score trajectory forecasting algorithm for the game of cricket using historical data. This leads to an unbiased target resetting algorithm for shortened cricket games which is an improvement upon the biased incumbent approach (Duckworth-Lewis-Stern). Third, an algorithm which leads to a consistent estimator for the time- and location-varying demand of products using censored observations in the context of retail. As a final contribution, the algorithms presented are implemented and packaged as a scalable open-source library for the imputation and forecasting of sequential data with applications beyond those presented in this work.by Muhammad Jehangir Amjad.Ph. D
- …
