Spring 2012

Abstract: The Kronecker graphs, originally proposed by Leskovec et. al, is a graph model which has been designed to model real-world graphs. These graphs have been shown to have a wide variety of nice properties observed in graph data, and have been successfully fit to many real-world graphs. In this talk, we will look at a specific random variation of the original Kronecker graph and look at the rise of the giant component in this model, obtaining sharp estimates for the size of the component when it exists. An interesting aspect that the analysis must overcome is that the Kronecker graphs do not expand as nicely and uniformly as in the case of the Erdos-Renyi random graphs, in analogy with community clustering in real world networks. A combination of spectral and probabilistic tools are used to establish the result.

Abstract: Traditional supervised learning for training a classfier involves a static set of fully-labeled data. However, labels can be costly to obtain. Active learning often provides lower misclassificiation rates for an equivalent number of labeled datapoints by allowing the learner to choose particularly important points for labeling. Standard paradigms for choosing points to label may be to request points near the decision boundary, or points where uncertainty is maximum. We show how to do directly optimize the target criterion by estimating error reduction directly in a probabilistic framework (the Gaussian Mixture Model) and show that this can lead to the need for significantly fewer labeled training examples in several cases than the maximum uncertainty approach.

Abstract: Prediction markets – betting platforms designed for aggregating information about some uncertain future event from a population of informants (traders) into a quantitative forecast – have gone from novelties to serious platforms that can be useful for policy and decision-making to scientists, the government, the military etc. One of the key challenges to running prediction markets is to provide liquidity which, roughly speaking, refers to the open interest or ongoing activity level in the market. Traditionally this problem has been tackled by using an algorithmic agent called a market maker: an intermediary that is always willing to take one side of the trade at prices dictated by itself. The talk, which is based on my review of relevant literature, is organized in three parts. First, I will discuss the state of the art in prediction markets: inventory-based or cost function-based market making. This is exemplified by Hanson's Logarithmic Market Scoring Rule (LMSR) which is by far the most widely used prediction market mechanism in practice. I will also touch upon an interesting real-life application (Gates Hillman Prediction Market) and other market makers influenced by LMSR. Next, I will present some important results on the operational and informational aspects of speculative markets (that subsume prediction markets) and discuss a novel information-based market making paradigm that builds on these concepts: Bayesian Market Making. Finally, I will point out how market making can be thought of as a problem of online learning from censored noisy data and will describe a few similar problems from diverse fields such as medicine, finance, and computer vision for this line of research has the potential to influence and be influenced by the area of information-based market making.