In recent years social media have become indispensable tools for information dissemination, operating in tandem with traditional media outlets such as newspapers, and it has become critical to understand the interaction between the new and old sources of news. Although social media as well as traditional media have attracted attention from several research communities, most of the prior work has been limited to a single medium. In addition temporal analysis of these sources can provide an understanding of how information spreads and evolves. Modeling temporal dynamics while considering multiple sources is a challenging research problem. In this paper we address the problem of modeling text streams from two news sources - Twitter and Yahoo! News. Our analysis addresses both their individual properties (including temporal dynamics) and their inter-relationships. This work extends standard topic models by allowing each text stream to have both local topics and shared topics. For temporal modeling we associate each topic with a time-dependent function that characterizes its popularity over time. By integrating the two models, we effectively model the temporal dynamics of multiple correlated text streams in a unified framework. We evaluate our model on a large-scale dataset, consisting of text streams from both Twitter and news feeds from Yahoo! News. Besides overcoming the limitations of existing models, we show that our work achieves better perplexity on unseen data and identifies more coherent topics. We also provide analysis of finding real-world events from the topics obtained by our model.

In this paper, we present a system for clustering the search results of a news search engine. The news search interface includes the relevant news articles to a given query organized in terms of related news stories. Here each cluster corresponds to a news story and the news articles are clustered into stories. We present a system that clusters the search results of a news search system in a fast and scalable manner. The clustering system is organized into three components including offline clustering, incremental clustering and realtime clustering. We propose novel techniques for clustering the search results in realtime. The experimental results with large collections of news documents reveal that our system is both scalable and also achieves good accuracy in clustering the news search results.

We propose a novel cost-efficient approach to threshold selection for binary web-page classification problems with imbalanced class distributions. In many binary-classification tasks the distribution of classes is highly skewed. In such problems, using uniform random sampling in constructing sample sets for threshold setting requires large sample sizes in order to include a statistically sufficient number of examples of the minority class. On the other hand, manually labeling examples is expensive and budgetary considerations require that the size of sample sets be limited. These conflicting requirements make threshold selection a challenging problem. Our method of sample-set construction is a novel approach based on stratified sampling, in which manually labeled examples are expanded to reflect the true class distribution of the web-page population. Our experimental results show that using false positive rate as the criterion for threshold setting results in lower-variance threshold estimates than using other widely used accuracy measures such as F1 and precision.

We address the problem of ranking question answerers according to their credibility, characterized here by the probability that a given question answerer (user) will be awarded a best answer on a question given the answerer's question-answering history. This probability (represented by θ) is considered to be a hidden variable that can only be estimated statistically from specific observations associated with the user, namely the number b of best answers awarded, associated with the number n of questions answered. The more specific problem addressed is the potentially high degree of uncertainty associated with such credibility estimates when they are based on small numbers of answers. We address this problem by a kind of Bayesian smoothing. The credibility estimate will consist of a mixture of the overall population statistics and those of the specific user. The greater the number of questions asked, the greater will be the contribution of the specific user statistics relative to those of the overall population. We use the Predictive Stochastic Complexity (PSC) as an accuracy measure to evaluate several methods that can be used for the estimation. We compare our technique (Bayesian Smoothing (BS)) with maximum a priori (MAP) estimation, maximum likelihood (ML) estimation and Laplace smoothing.

We present a risk minimization formulation for learning from both text and graph structures which is motivated by the problem of collective inference for hypertext document categorization. The method is based on graph regularization formulated as a well-formed convex optimization problem. We present numerical algorithms for our formulation, and show that such combination of local text features and link information can lead to improved predictive accuracy.

This paper presents a framework called Structure Sensitive CATegorization(SSCAT), that exploits document structure for improved categorization. There are two parts to this framework, viz. (1) Documents often have layout structure, such that logically coherent text is grouped together into fields using some mark-up language. We use a log-linear model, which associates one or more features with each field. Weights associated with the field features are learnt from training data and these weights quantify the per-class importance of the field features in determining the category for the document. (2) We employ a technique that exploits the parse tree of fields that are phrasal constructs, such as title and associates weights with words in these constructs while boosting weights of important words called focus words. These weights are learnt from example instances of phrasal constructs, marked with the corresponding focus words. The learning is accomplished by training a classifier that uses linguistic features obtained from the text's parse structure. The weighted words, in fields with phrasal constructs, are used in obtaining features for the corresponding fields in the overall framework. SSCAT was tested on the supervised categorization task of over one million products from Yahoo!'s on-line shopping data. With an accuracy of over 90%, our classifier outperforms Naive Bayes and Support Vector Machines. This not only shows the effectiveness of SSCAT but also strengthens our belief that linguistic features based on natural language structure can improve tasks such as text categorization.

Naive Bayes classifier has long been used for text categorization tasks. Its sibling from the unsupervised world, the probabilistic mixture of multinomial models, has likewise been successfully applied to text clustering problems. Despite the strong independence assumptions that these models make, their attractiveness come from low computational cost, relatively low memory consumption, ability to handle heterogeneous features and multiple classes, and often competitiveness with the top of the line models. Recently, there has been several attempts to alleviate the problems of Naive Bayes by performing heuristic feature transformations, such as IDF, normalization by the length of the documents and taking the logarithms of the counts. We justify the use of these techniques and apply them to two problems: classification of products in Yahoo! Shopping and clustering the vectors of collocated terms in user queries to Yahoo! Search. The experimental evaluation allows us to draw conclusions about the promise that these transformations carry with regard to alleviating the strong assumptions of the multinomial model.

A common method for finding information in an organization is to use social networks---ask people, following referrals until someone with the right information is found. Another way is to automatically mine documents to determine who knows what. Email documents seem particularly well suited to this task of "expertise location", as people routinely communicate what they know. Moreover, because people explicitly direct email to one another, social networks are likely to be contained in the patterns of communication. Can these patterns be used to discover experts on particular topics? Is this approach better than mining message content alone? To find answers to these questions, two algorithms for determining expertise from email were compared: a content-based approach that takes account only of email text, and a graph-based ranking algorithm (HITS) that takes account both of text and communication patterns. An evaluation was done using email and explicit expertise ratings from two different organizations. The rankings given by each algorithm were compared to the explicit rankings with the precision and recall measures commonly used in information retrieval, as well as the d' measure commonly used in signal-detection theory. Results show that the graph-based algorithm performs better than the content-based algorithm at identifying experts in both cases, demonstrating that the graph-based algorithm effectively extracts more information than is found in content alone.

In the field of pattern recognition there are many problems that are now familiar to us, in a sense part of a standard problem set. This set includes both supervised and unsupervised learning (e.g. clustering). In fact these are the two major problems addressed by the field. These problems and the general pattern recognition problem have appeared in many domains. They have even appeared in the context of something that is reshaping society and commerce-the world wide web. It is our intent to discuss these two learning problems in that context in the hope of drawing the attention of the pattern recognition community and in the hope of making that community aware of some of the more significant work that had been performed to date attacking these problems in the web context.

In the recent years support vector machines (SVM) have been successfully applied to solve a large number of classification problems. Training an SVM, usually posed as a quadratic programming (QP) problem, often becomes a challenging task for the large data sets due to the high memory requirements and slow convergence. We propose to apply boosting to Platt's sequential minimal optimization (SMO) algorithm (1999) and to use resulting Boost-SMO method for speeding and scaling up the SVM training. Experiments on three commonly used benchmark data sets show that Boost-SMO achieves classification accuracy comparable to conventional SMO but is a factor of 3 to 10 faster. The speed-up could easily be orders of magnitude on the larger data sets.

A major challenge in indexing unstructured hypertext databases is to automatically extract meta-data that enables structured search using topic taxonomies, circumvents keyword ambiguity, and improves the quality of search and profile-based routing and filtering. Therefore, an accurate classifier is an essential component of a hypertext database. Hyperlinks pose new problems not addressed in the extensive text classification literature. Links clearly contain high-quality semantic clues that are lost upon a purely term-based classifier, but exploiting link information is non-trivial because it is noisy. Naive use of terms in the link neighborhood of a document can even degrade accuracy. Our contribution is to propose robust statistical models and a relaxation labeling technique for better classification by exploiting link information in a small neighborhood around documents. Our technique also adapts gracefully to the fraction of neighboring documents having known topics. We experimented with pre-classified samples from Yahoo!1 and the US Patent Database2. In previous work, we developed a text classifier that misclassified only 13% of the documents in the well-known Reuters benchmark; this was comparable to the best results ever obtained. This classifier misclassified 36% of the patents, indicating that classifying hypertext can be more difficult than classifying text. Naively using terms in neighboring documents increased error to 38%; our hypertext classifier reduced it to 21%. Results with the Yahoo! sample were more dramatic: the text classifier showed 68% error, whereas our hypertext classifier reduced this to only 21%.

Minimum Description Length (MDL) estimation has proven itself of major importance in a large number of applications many of which are in the fields of computer vision and pattern recognition. A problem is encountered in applying the associated formulas, however, especially those associated with model cost. This is because most of these are asymptotic forms appropriate only for large sample sizes. J. Rissanen has recently derived sharper code-length formulas valid for much smaller sample sizes. Because of the importance of these results, it is our intent here to present a tutorial description of them. In keeping with this goal we have chosen a simple application whose relative tractability allows it to be explored more deeply than most problems: the segmentation of binary strings based on a piecewise Bernoulli assumption. By that we mean that the strings are assumed to be divided into substrings, the bits of which are assumed to have been generated by a single (within a substring) Bernoulli source.

This research addresses the issue of automatically segmenting color images into foreground (F) and background (B) regions with the assumption that background regions are relatively smooth but may have gradually varying colors or be slightly textured. A multi-level segmentation scheme is used that involves color clustering, unsupervised segmentation using MDL (minimum description length) principle, edge-based F/B separation, integrated initial F/B segmentation, background modeling, and final F/B separation. The approach has been tested on more than 100 images. Some of the experimental results are presented in this paper.

Two sets of measures are proposed in this paper for quantitatively evaluating segmentation results. The first set is designed for the situation where ground truth is available; while the second for the situation where ground truth is not available. Based on a test bank of more than 50 images for which ground truth is available, we computed both sets of evaluation measures and then correlated the two sets. Experimental results show that the first set of measures proposed agree with human (subjective) visual evaluation and the second set of measures correlates well with the first set, an indication of the usefulness of this set of measures in assessing the quality of image segmentation results even when ground truth is not available.

This research addresses the issue of automatically segmenting color images into foreground (F) and back-ground (B) regions with the assumption that background regions are relatively smooth but may have gradually varying colors or be slightly textured. A multi-level segmentation scheme is used that involves color clustering, unsupervised segmentation using MDL (minimum description length) principle, edge-based F/B separation, and integrated F/B segmentation. The approach has been tested on more than 100 images. Some of the experimental results are presented.

We consider the problem of image segmentation and describe an algorithm that is based on the Minimum Description Length (MDL) principle, is fast, is applicable to multi-band images, and guarantees closed regions. We construct an objective function that, when minimized, yields a partitioning of the image into regions where the pixel values in each band of each region are described by a polynomial surface plus noise. The polynomial orders and their coefficients are determined by the algorithm. The minimization is difficult because (1) it involves a search over a very large space and (2) there is extensive computation required at each stage of the search. To address the first of these problems we use a region-merging minimization algorithm. To address the second we use an incremental polynomial regression that uses computations from the previous stage to compute results in the current stage, resulting in a significant speed up over the non-incremental technique. The segmentation result obtained is suboptimal in general but of high quality. Results on real images are shown.>

This paper describes algorithms for automatically inspecting the air-bearing surface (ABS) of disk sliders (heads) for certain types of defects that are global or systematic in the sense that, when they occur, they occur on every slider in a row or, in some cases, on every slider in the entire carrier. These defects are: wrong part, missing rail, geometry error, missing taper, extra taper, misplaced taper, missing poletip and misplaced pole-tip. The inspection system is in production use and has resulted in a significant improvement of the quality of shipped sliders. Here, the associated image-analysis algorithms are described in detail.

A method for detecting curve segments in a digital image is described. The method takes as input a set of edges, and produces as output the number of and parameters for the segments. The method is robust, requiring no thresholds. In place of thresholds, a model class must be provided. Using the information-theoretic minimum description length (MDL) principle, it evaluates each model in the model class, computing the optimal parameters for that model, and selects the best model as the one that gives the shortest encoding of the data and the model. Typical of such methods, the search space is extremely large. It is shown how the Hough transform (HT) may be used to reduce this search space greatly, yielding an efficient (although suboptimal) search. The result is an algorithm in which MDL overcomes standard problems with the HT, while the HT overcomes problems with MDL, and which produces a pleasing set of line segments.>

Considers the problem of unsupervised multiband image segmentation specifically, using the MDL criterion, an associated complexity measure. According to the MDL principle, the best estimates are those that result in the most compact encoding of the image. An important advantage of such an approach is that it is virtually free of the need to choose arbitrary thresholds, which are typical of many segmentation techniques, and which, in many cases, need to be interactively adjusted in order to get satisfactory results.>

The architectural and implementation issues of a prototype of a low-level image segmentation architecture (LISA) are described. LISA performs real-time gray-level image segmentation. A decision-theoretic pattern recognition approach divided into feature extraction and decision analysis parts is used. The feature extraction part is based on extracting local and global descriptions of the image pixels. In the decision analysis part, the pixels are classified into one of the user-selected classes based on the extracted features. One of the main properties of the approach is that the feature extraction and decision analysis are performed in real time. The status of the hardware and software development of the LISA prototype for a variety of industrial inspection applications is described. The LISA architecture is being implemented using state-of-the-art VLSI technology.>

Algorithms for use with a previously published VLSI architecture for pattern classification are presented. This architecture is based on the evaluation of class discriminant functions without cross terms. Tradeoffs in architecture design have been required to allow high throughput, and the decision regions in feature space which can be generated using this architecture therefore form a restricted subset of possible decision regions. The properties of such decision regions and associated classifier training algorithms are investigated. Some experimental results are included.>

An information-theoretic approach is used to derive a new feature selection criterion capable of detecting features that are totally useless. Since the number of useless features is initially unknown, traditional class-separability and distance measures are not capable of coping with this problem. The useless feature-subset is detected by fitting a probability model to a given training set of classified feature-vectors using the minimum-description-length criterion (MDLC) for model selection. The resulting criterion for the Gaussian case is a simple closed-form expression, having a plausible geometric interpretation, and is proved to be consistent, i.e., it yields the true useless subset with probability 1 as the size of the training set grows to infinity. Simulations show excellent results compared to the cross-validation method and other information-theoretic criteria, even for small-sized training sets.>

The application of J. Rissanen's theory (1986) of stochastic complexity to the problem of features selection in statistical pattern recognition (SPR) is discussed. Stochastic complexity provides a general framework for statistical problems such as coding, prediction, estimation, and classification. A brief review of the SPR paradigm and traditional methods of feature selection is presented, followed by a discussion of the basic of stochastic complexity. Two forms of stochastic complexity, minimum description length and an integral form, are applied to the problem of feature selection. Experimental results using simulated data generated with Gaussian distributions are given and compared with results from cross validation, a traditional technique. The stochastic complexity measures give superior results, as measured by their ability to select subsets of relevant features, as well as probability of error computed based on the selected feature subset.>