Source author record

Kishor Barman

Kishor Barman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT Machine Learning

Catalog footprint

What is connected

3works

3topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2011arXiv

Analysis of a Collaborative Filter Based on Popularity Amongst Neighbors

In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your friends? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation (bit error rate (BER)). For a mathematical model introduced in [1],[2], we identify three regimes of operation for our algorithm (named Popularity Amongst Friends (PAF)) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion.

preprint2011arXiv

Clustered regression with unknown clusters

We consider a collection of prediction experiments, which are clustered in the sense that groups of experiments ex- hibit similar relationship between the predictor and response variables. The experiment clusters as well as the regres- sion relationships are unknown. The regression relation- ships define the experiment clusters, and in general, the predictor and response variables may not exhibit any clus- tering. We call this prediction problem clustered regres- sion with unknown clusters (CRUC) and in this paper we focus on linear regression. We study and compare several methods for CRUC, demonstrate their applicability to the Yahoo Learning-to-rank Challenge (YLRC) dataset, and in- vestigate an associated mathematical model. CRUC is at the crossroads of many prior works and we study several prediction algorithms with diverse origins: an adaptation of the expectation-maximization algorithm, an approach in- spired by K-means clustering, the singular value threshold- ing approach to matrix rank minimization under quadratic constraints, an adaptation of the Curds and Whey method in multiple regression, and a local regression (LoR) scheme reminiscent of neighborhood methods in collaborative filter- ing. Based on empirical evaluation on the YLRC dataset as well as simulated data, we identify the LoR method as a good practical choice: it yields best or near-best prediction performance at a reasonable computational load, and it is less sensitive to the choice of the algorithm parameter. We also provide some analysis of the LoR method for an asso- ciated mathematical model, which sheds light on optimal parameter choice and prediction performance.

preprint2010arXiv

Local Popularity Based Collaborative Filters

Motivated by applications such as recommendation systems, we consider the estimation of a binary random field X obtained by row and column permutations of a block constant random matrix. The estimation of X is based on observations Y, which are obtained by passing entries of X through a binary symmetric channel (BSC) and an erasure channel. We focus on the analysis of a specific algorithm based on local popularity when the erasure rate approaches unity at a specified rate. We study the bit error rate (BER) in the limit as the matrix size approaches infinity. Our main result states that if the cluster size (that is, the size of the constancy blocks in the original matrix) is above a certain threshold, then the BER approaches zero, but below the threshold, the BER is lower bounded away from zero. The lower bound depends on the noise level in the observations and the size of the clusters in relation to the threshold. The threshold depends on the rate at which the erasure probability approaches unity.