CiteULike: mukundn's library [187 articles]

Untitled

2006-08-10T00:36:34-00:00

Maximum Entropy Modeling: A Suitable Framework to Learn Context-Dependent Lexicon Models for Statistical Machine Translation: Basic Instructions

Ismael Garcia-Varea — 2005-08-25T19:05:38-00:00

Machine Learning, Vol. 60, No. 1-3. (September 2005), pp. 135-158.

Ranking and Reranking with Perceptron

Libin Shen — 2005-08-25T19:05:39-00:00

Machine Learning, Vol. 60, No. 1-3. (September 2005), pp. 73-96.

Generalized Low Rank Approximations of Matrices

Jieping Ye — 2006-01-12T19:09:55-00:00

Machine Learning, Vol. 61, No. 1-3. (November 2005), pp. 167-191.

Mutual Information, Fisher Information, and Population Coding

Nicolas Brunel — 2006-03-28T15:48:39-00:00

In the context of parameter estimation and model selection, it is only quite recently that a direct link between the Fisher information and information theoretic quantities has been exhibited. We give an interpretation of this link within the standard framework of information theory. We show that in the context of population coding, the mutual information between the activity of a large array of neurons and a stimulus to which the neurons are tuned is naturally related to the Fisher...

Relations between Kullback-Leibler distance and Fisher information

Anand Dabak — 2006-03-28T15:47:26-00:00

The Kullback-Leibler distance between two probability densities that are parametric perturbations of each other is related to the Fisher information. We generalize this relationship to the case when the perturbations may not be small and when the two densities are non-parametric.

SALSA: the stochastic approach for link-structure analysis

R Lempel — 2005-10-03T10:44:42-00:00

ACM Trans. Inf. Syst., Vol. 19, No. 2. (April 2001), pp. 131-160.

Updating the Stationary Vector of an Irreducible Markov Chain

With Eye — 2005-09-23T14:08:09-00:00

An iterative algorithm based on aggregation/disaggregation principles is presented for updating the stationary distribution of a finite homogeneous irreducible Markov chain. The focus is on largescale problems of the kind that are characterized by Google's PageRank application, but the algorithm is shown to work well in general contexts. The algorithm is flexible in that it allows for changes to the transition probabilities as well as for the creation or deletion of states. In addition to...

PageRank, HITS and a Unified Framework for Link Analysis

Chris Ding — 2005-10-03T10:38:25-00:00

No. 49372. (2002)

Two popular webpage ranking algorithms are HITS and PageRank. HITS emphasizes mutual reinforcement between authority and hub webpages, while PageRank emphasizes hyperlink weight normalization and web surfing based on random walk models. We systematically generalize /combine these concepts into a unified framework. The ranking framework contains a large algorithm space

Using PageRank to Characterize Web Structure

Gopal Pandurangan — 2005-09-29T14:43:45-00:00

(2002)

Recent work on modeling the Web graph has dwelt on capturing the degree distributions observed on the Web. Pointing out that this represents a heavy reliance on "local" properties of the Web graph, we study the distribution of PageRank values (used in the Google search engine) on the Web. This distribution is of independent interest in optimizing search indices and storage. We show that PageRank values on the Web follow a power law. We then develop detailed models for the Web graph that explain ...

Criterion functions for document clustering: Experiments and analysis

Y Zhao — 2006-02-27T16:11:33-00:00

(2001)

In recent years, we have witnessed a tremendous growth in the volume of text documents available on the Internet, digital libraries, news sources, and company-wide intranets. This has led to an increased interest in developing methods that can help users to effectively navigate, summarize, and organize this information with the ultimate goal of helping them to find what they are looking for. Fast and high-quality document clustering algorithms play an important role towards this goal as...

A Peer-to-Peer Advertising Game

Paolo Avesani — 2006-02-28T17:44:58-00:00

(2003)

Probabilistic counting algorithms for data base applications

Philippe Flajolet — 2006-02-09T09:50:53-00:00

J. Comput. Syst. Sci., Vol. 31, No. 2. (September 1985), pp. 182-209.

Link analysis ranking: algorithms, theory, and experiments

Allan Borodin — 2005-07-28T14:13:57-00:00

ACM Trans. Inter. Tech., Vol. 5, No. 1. (February 2005), pp. 231-297.

Matrices, Vector Spaces, and Information Retrieval

Michael Berry — 2005-10-12T09:41:00-00:00

SIAM Rev., Vol. 41, No. 2. (June 1999), pp. 335-362.

Random projection in dimensionality reduction: applications to image and text data

Ella Bingham — 2005-11-30T19:42:27-00:00

(2001), pp. 245-250.

The Use of the Linear Algebra by Web Search Engines

Amy Langville — 2005-10-07T03:45:57-00:00

Scalable Techniques for Clustering the Web

Taher Haveliwala — 2005-12-21T17:24:48-00:00

(2000), pp. 129-134.

Clustering is one of the most crucial techniques for dealing with the massive amount of information present on the web. Clustering can either be performed once offline, independent of search queries, or performed online on the results of search queries. Our offline approach aims to efficiently cluster similar pages on the web, using the technique of Locality-Sensitive Hashing (LSH), in which web pages are hashed in such a way that similar pages have a much higher probability of collision than...

PageRank without hyperlinks: structural re-ranking using links induced by language models

Oren Kurland — 2005-11-21T09:37:48-00:00

(2005), pp. 306-313.

Frequency of occurrence of numbers in the World Wide Web

S Dorogovtsev — 2005-04-28T06:43:31-00:00

(26 April 2005)

The distribution of numbers in human documents is determined by a variety of diverse natural and human factors, whose relative significance can be evaluated by studying the numbers' frequency of occurrence. Although it has been studied since the 1880's, this subject remains poorly understood. Here, we obtain the detailed statistics of numbers in the World Wide Web, finding that their distribution is a heavy-tailed dependence which splits in a set of power-law ones. In particular, we find that the frequency of numbers associated to western calendar years shows an uneven behavior: 2004 represents a `singular critical' point, appearing with a strikingly high frequency; as we move away from it, the decreasing frequency allows us to compare the amounts of existing information on the past and on the future. Moreover, while powers of ten occur extremely often, allowing us to obtain statistics up to the huge 10^127, `non-round' numbers occur in a much more limited range, the variations of their frequencies being dramatically different from standard statistical fluctuations. These findings provide a view of the array of numbers used by humans as a highly non-equilibrium and inhomogeneous system, and shed a new light on an issue that, once fully investigated, could lead to a better understanding of many sociological and psychological phenomena.

The structure of broad topics on the web

Soumen Chakrabarti — 2006-03-09T16:43:31-00:00

(2002), pp. 251-262.

Deeper Inside PageRank

Amy Langville — 2005-09-22T16:05:34-00:00

Internet Mathematics, Vol. 1, No. 3. (2003), pp. 335-380.

This paper serves as a companion or extension to the "Inside PageRank” paper by Bianchini et al. It is a comprehensive survey of all issues associated with PageRank, covering the basic PageRank model, available and recommended solution methods, storage issues, existence, uniqueness, and convergence properties, possible alterations to the basic model, suggested alternatives to the traditional solution methods, sensitivity and conditioning, and finally the updating problem. We introduce a few new results, provide an extensive reference list, and speculate about exciting areas of future research.

Power laws, Pareto distributions and Zipf's law

MEJ Newman — 2004-12-29T16:08:05-00:00

Contemporary Physics, Vol. 46 (1 December 2005), pp. 323-351.

When the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the Pareto distribution. Power laws appear widely in physics, biology, earth and planetary sciences, economics and finance, computer science, demography and the social sciences. For instance, the distributions of the sizes of cities, earthquakes, forest fires, solar flares, moon craters and people's personal fortunes all appear to follow power laws. The origin of power-law behaviour has been a topic of debate in the scientific community for more than a century. Here we review some of the empirical evidence for the existence of power-law forms and the theories proposed to explain them.

Counting large numbers of events in small registers

Robert Morris — 2006-02-03T17:22:11-00:00

Commun. ACM, Vol. 21, No. 10. (October 1978), pp. 840-842.

A Brief History of Generative Models for Power Law and Lognormal Distributions.

Michael Mitzenmacher — 2005-11-08T16:25:20-00:00

Internet Mathematics, Vol. 1, No. 2. (2004), pp. 226-251.

Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these distributions to settle the question, I found a rich and long history, spanning many fields. Indeed, several recently proposed models from the computer science community have antecedents in work from decades ago. Here, I briefly survey some of this history, focusing on underlying generative models that lead to these distributions. One finding is that lognormal and power law distributions connect quite naturally, and hence, it is not surprising that lognormal distributions have arisen as a possible alternative to power law distributions across many fields.

PageRank Revisited

Michael Brinkmeier — 2005-07-04T16:30:38-00:00

ACM Transaction on Internet Technologies, Vol. 6, No. 3. (2006), pp. 257-279.

How dynamic is the web?

Brian Brewington — 2005-06-30T10:32:44-00:00

(May 2000)

Topic-sensitive PageRank

Taher Haveliwala — 2006-02-27T16:43:42-00:00

(May 2002)

In the original PageRank algorithm for improving the ranking of search-query results, a single PageRank vector is computed, using the link structure of the Web, to capture the relative "importance" of Web pages, independent of any particular search query. To yield more accurate search results, we propose computing a set of PageRank vectors, biased using a set of representative topics, to capture more accurately the notion of importance with respect to a particular topic. By using these...

Revisitation Patterns in World Wide Web Navigation

Linda Tauscher — 2005-02-01T10:05:39-00:00

(1997)

We report on users' revisitation patterns to World Wide Web pages, and use these to lay an empirical foundation for the design of history mechanisms in web browsers. Through history, a user can return quickly to a previously visited page, possibly reducing the cognitive and physical overhead required to navigate to it from scratch. We analyzed 6 weeks of usage data collected from 23 users of a commercial browser. We found that 58% of an individual's pages are revisits, and that users...

Relevance Feedback Techniques in Interactive Content-Based Image Retrieval

Yong Rui — 2004-12-13T15:16:28-00:00

(1998), pp. 25-36.

Content-Based Image Retrieval #CBIR# has become one of the most active research areas in the past few years. Many visual feature representations have been explored and many systems built. While these research e#orts establish the basis of CBIR, the usefulness of the proposed approaches is limited. Speci#cally, these e#orts have relatively ignored two distinct characteristics of CBIR systems: #1# the gap between high level concepts and low level features; #2# subjectivityofhuman perception of...

Object Recognition from Local Scale-Invariant Features

David Lowe — 2006-02-28T17:45:58-00:00

(1999), pp. 1150-1157.

An object recognition system has been developed that uses a new class of local image features. The features are invariant to image scaling, translation, and rotation, and partially invariant to illumination changes and affine or 3D projection. These features share similar properties with neurons in inferior temporal cortex that are used for object recognition in primate vision. Features are efficiently detected through a staged filtering approach that identifies stable points in scale space....

The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank

Mathew Richardson — 2005-10-03T10:41:59-00:00

(2002)

The PageRank algorithm, used in the Google search engine, greatly improves the results of Web search by taking into account the link structure of the Web. PageRank assigns to a page a score proportional to the number of times a random surfer would visit that page, if it surfed indefinitely from page to page, following all outlinks from a page with equal probability. We propose to improve PageRank by using a more intelligent surfer, one that is guided by a probabilistic model of the relevance of ...

Splines minimizing rotation-invariant semi-norms in sobolev spaces

J Duchon — 2006-03-13T22:22:49-00:00

Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation

Michael Luby — 2006-03-08T00:16:48-00:00

No. TR-97-044. (1997)

We construct new families of low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct more errors than previously known low-density codes. Our improved performance comes from using codes based on irregular random bipartite graphs, based on the work of [2]. Previously studied lowdensity codes have been derived from regular bipartite graphs. Initial experimental results for our irregular codes suggest that, with improvements,...

Codes and Graphs

Amin Shokrollahi — 2006-03-08T00:10:32-00:00

Lecture Notes in Computer Science, Vol. 1770 (2000), pp. 1-??.

. In this paper, I will give a brief introduction to the theory of low-density parity-check codes, and their decoding. I will emphasize the case of correcting erasures as it is still the best understood and most accessible case. At the end of the paper, I will also describe more recent developments. 1 Introduction In this paper, I want to give a brief introduction to the theory of low-density parity-check codes, or LDPC codes, for short. These codes were first introduced in the early...

Fortified-descent simplicial search method: A general approach

P Tseng — 2006-03-02T21:32:33-00:00

SIAM Journal on Optimization, Vol. 10(1) (2000), pp. 269-288.

We propose a new simplex-based direct search method for unconstrained minimization of a realvalued function f of n variables. As in other methods of this kind, the intent is to iteratively improve an n-dimensional simplex through certain reflection/expansion/contraction steps. The method has three novel features. First, a user-chosen integer m k specifies the number of "good" vertices to be retained in constructing the initial trial simplices--reflected, then either expanded or contracted--at...

Direct search methods: Once scorned, now respectable

M Wright — 2006-03-02T21:31:37-00:00

(1995)

The need to optimize a function whose derivatives are unknown or non-existent arises in many contexts, particularly in real-world applications. Various direct search methods, most notably the Nelder-Mead `simplex' method, were proposed in the early 1960s for such problems, and have been enormously popular with practitioners ever since. Nonetheless, for more than twenty years these methods were typically dismissed or ignored in the mainstream optimization literature, primarily because of the...

Exact logistic regression: theory and examples.

CR Mehta — 2005-11-23T00:17:33-00:00

Stat Med, Vol. 14, No. 19. (15 October 1995), pp. 2143-2160.

We provide an alternative to the maximum likelihood method for making inferences about the parameters of the logistic regression model. The method is based appropriate permutational distributions of sufficient statistics. It is useful for analysing small or unbalanced binary data with covariates. It also applies to small-sample clustered binary data. We illustrate the method by analysing several biomedical data sets.

Unsupervised models for named entity classification

M Collins — 2005-03-29T19:02:37-00:00

(1999)

This paper discusses the use of unlabeled examples for the problem of named entity classification. A large number of rules is needed for coverage of the domain, suggesting that a fairly large number of labeled examples should be required to train a classi- tier. However, we show that the use of unlabeled data can reduce the requirements for supervision to just 7 simple "seed" rules. The approach gains leverage from natural redundancy in the data: for many named-entity instances both the...

PAC Generalization Bounds for Co-Training

Sanjoy Dasgupta — 2005-10-09T12:08:47-00:00

(2001)

On Generalization Error Bounds Using Unlabeled Data

Matti Kääriäinen — 2005-06-16T01:01:08-00:00

(March 2005)

We present two new methods for obtaining generalization error bounds in a semi-supervised setting. Both methods are based on approximating the disagreement probability of pairs of classifiers using unlabeled data. The first method works in the realizable case. It suggests how the ERM principle can be refined using unlabeled data and has provable optimality guarantees when the number of unlabeled examples is large. Furthermore, the technique extends easily to cover active learning. A downside is that the method is of little use in practice due to its limitation to the realizable case. The idea in our second method is to use unlabeled data to transform bounds for randomized classifiers into bounds for simpler deterministic classifiers. As a concrete example of how the general method works in practice, we apply it to a bound based on cross-validation. The result is a semi-supervised bound for classifiers learned based on all the labeled data. The bound is easy to implement and apply and should be tight whenever cross-validation makes sense. Applying the bound to SVMs on the MNIST benchmark data set gives results that suggest that the bound may be tight enough to be useful in practice.

Analyzing the Effectiveness and Applicability of Co-training

Kamal Nigam — 2005-03-29T20:46:17-00:00

(2000), pp. 86-93.

Recently there has been significant interest in supervised learning algorithms that combine labeled and unlabeled data for text learning tasks. The co-training setting [1] applies to datasets that have a natural separation of their features into two disjoint sets. We demonstrate that when learning from labeled and unlabeled data, algorithms explicitly leveraging a natural independent split of the features outperform algorithms that do not. When a natural split does not exist, co-training...

Semi-supervised learning on directed graphs

D Zhou — 2006-02-19T17:39:06-00:00

Unsupervised Word Sense Disambiguation Rivaling Supervised Methods

David Yarowsky — 2005-03-29T19:19:17-00:00

(1995), pp. 189-196.

This paper presents an unsupervised learning algorithm for sense disambiguation that, when trained on unannotated English text, rivals the performance of supervised techniques that require time-consuming hand annotations. The algorithm is based on two powerful constraints -- that words tend to have one sense per discourse and one sense per collocation -- exploited in an iterative bootstrapping procedure. Tested accuracy exceeds 96%. 1 Introduction This paper presents an unsupervised algorithm ...

Combining Labeled and Unlabeled Data with Co-training

Avrim Blum — 2005-03-25T18:29:37-00:00

(1998)

We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a problem setting motivated by the task of learning to classify web pages, in which the description of each example can be partitioned into two distinct views. For example, the description of a web page can be partitioned into the words occurring on that page, and the words occurring in hyperlinks that point to...

Learning from Labeled and Unlabeled Data Using Graph Mincuts

Avrim Blum — 2006-02-19T17:31:36-00:00

(2001), pp. 19-26.

Many application domains suffer from not having enough labeled training data for learning. However, large amounts of unlabeled examples can often be gathered cheaply. As a result, there has been a great deal of work in recent years on how unlabeled data can be used to aid classification. We consider an algorithm based on finding minimum cuts in graphs, that uses pairwise relationships among the examples in order to learn from both labeled and unlabeled data.

Semi-Supervised Support Vector Machines

K Bennett — 2006-02-19T17:31:12-00:00

(1998)

We introduce a semi-supervised support vector machine (S 3 VM) method. Given a training set of labeled data and a working set of unlabeled data, S 3 VM constructs a support vector machine using both the training and working sets. We use S 3 VM to solve the transduction problem using overall risk minimization (ORM) posed by Vapnik. The transduction problem is to estimate the value of a classification function at the given points in the working set. This contrasts with the standard...

Competitive on-line learning with a convex loss function

Vladimir Vovk — 2006-02-19T17:27:40-00:00

(2 Sep 2005)

We consider the problem of sequential decision making under uncertainty in which the loss caused by a decision depends on the following binary observation. In competitive on-line learning, the goal is to design decision algorithms that are almost as good as the best decision rules in a wide benchmark class, without making any assumptions about the way the observations are generated. However, standard algorithms in this area can only deal with finite-dimensional (often countable) benchmark classes. In this paper we give similar results for decision rules ranging over an arbitrary reproducing kernel Hilbert space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first $N$ observations, does not exceed the average loss of the best decision rule with a bounded norm plus $O(N^-1/2)$. Our proof technique is very different from the standard ones and is based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have good resolution in the long run, we use the expected loss minimization principle to find a suitable decision.

Information Theory - The Bridge Connecting Bounded Rational Game Theory and Statistical Physics

David Wolpert — 2006-02-19T17:25:58-00:00

(19 Feb 2004)

A long-running difficulty with conventional game theory has been how to modify it to accommodate the bounded rationality of all real-world players. A recurring issue in statistical physics is how best to approximate joint probability distributions with decoupled (and therefore far more tractable) distributions. This paper shows that the same information theoretic mathematical structure, known as Product Distribution (PD) theory, addresses both issues. In this, PD theory not only provides a principled formulation of bounded rationality and a set of new types of mean field theory in statistical physics. It also shows that those topics are fundamentally one and the same.

Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions

Zhu — 2006-02-18T23:26:58-00:00