Learning User Clicks in Web Search
Machine learning for predicting user clicks in Web-based search offers automated explanation of user activity. We address click prediction in the Web search scenario by introducing a method for click prediction based on observations of past queries and the clicked documents. Due to the sparsity of the problem space, commonly encountered when learning for Web search, new approaches to learn the probabilistic relationship between documents and queries are proposed. Two probabilistic models are developed, which differ in the interpretation of the query-document co-occurrences. A novel technique, namely, conditional probability hierarchy, flexibly adjusts the level of granularity in parsing queries, and, as a result, leverages the advantages of both models.

title: Asymptotic Performance of Vector Quantizers with a Perceptual Distortion Measure
abstract: Gersho's (1979) bounds on the asymptotic performance of vector quantizers are valid for vector distortions which are powers of the Euclidean norm. Yamada, Tazaki, and Gray (1980) generalized the results to distortion measures that are increasing functions of the norm of their argument. In both cases, the distortion is uniquely determined by the vector quantization error, i.e., the Euclidean difference between the original vector and the codeword into which it is quantized. We generalize these asymptotic bounds to input-weighted quadratic distortion measures and measures that are approximately output-weighted-quadratic when the distortion is small, a class of distortion measures often claimed to be perceptually meaningful. An approximation of the asymptotic distortion based on Gersho's conjecture is derived as well. We also consider the problem of source mismatch, where the quantizer is designed using a probability density different from the true source density. The resulting asymptotic performance in terms of distortion increase in decibels is shown to be linear in the relative entropy between the true and estimated probability densities.

title: A source coding approach to classification by vector quantization and the principle of minimum description length
abstract: An algorithm for supervised classification using vector quantization and entropy coding is presented. The classification rule is formed from a set of training data {(X/sub i/, Y/sub i/)}/sub i=1//sup n/, which are independent samples from a joint distribution P/sub XY/. Based on the principle of minimum description length (MDL), a statistical model that approximates the distribution P/sub XY/ ought to enable efficient coding of X and Y. On the other hand, we expect a system that encodes (X, Y) efficiently to provide ample information on the distribution P/sub XY/. This information can then be used to classify X, i.e., to predict the corresponding Y based on X. To encode both X and Y, a two-stage vector quantizer is applied to X and a Huffman code is formed for Y conditioned on each quantized value of X. The optimization of the encoder is equivalent to the design of a vector quantizer with an objective function reflecting the joint penalty of quantization error and misclassification rate. This vector quantizer provides an estimation of the conditional distribution of Y given X, which in turn yields an approximation to the Bayes classification rule. This algorithm, namely discriminant vector quantization (DVQ), is compared with learning vector quantization (LVQ) and CART/sup R/ on a number of data sets. DVQ outperforms the other two on several data sets. The relation between DVQ, density estimation, and regression is also discussed.

title: Real-Time Computerized Annotation of Pictures
abstract: Developing effective methods for automated annotation of digital pictures continues to challenge computer scientists. The capability of annotating pictures by computers can lead to breakthroughs in a wide range of applications, including Web image search, online picture-sharing communities, and scientific experiments. In this work, the authors developed new optimization and estimation techniques to address two fundamental problems in machine learning. These new techniques serve as the basis for the automatic linguistic indexing of pictures - real time (ALIPR) system of fully automatic and high-speed annotation for online pictures. In particular, the D2-clustering method, in the same spirit as K-Means for vectors, is developed to group objects represented by bags of weighted vectors. Moreover, a generalized mixture modeling technique (kernel smoothing as a special case) for nonvector data is developed using the novel concept of hypothetical local mapping (HLM). ALIPR has been tested by thousands of pictures from an Internet photo-sharing site, unrelated to the source of those pictures used in the training process. Its performance has also been studied at an online demonstration site, where arbitrary users provide pictures of their choices and indicate the correctness of each annotation word. The experimental results show that a single computer processor can suggest annotation terms in real time and with good accuracy.

title: On Zador's entropy-constrained quantization theorem
abstract: Zador's classic result for the asymptotic high-rate behavior of entropy-constrained vector quantization is recast in a Lagrangian form which better matches the Lloyd algorithm used to optimize such quantizers. A proof that the result holds for a general class of distributions is sketched.

title: Unsupervised Multiresolution Segmentation for Images with Low Depth of Field
abstract: Unsupervised segmentation of images with low depth of field (DOF) is highly useful in various applications. This paper describes a novel multiresolution image segmentation algorithm for low DOF images. The algorithm is designed to separate a sharply focused object-of-interest from other foreground or background objects. The algorithm is fully automatic in that all parameters are image independent. A multi-scale approach based on high frequency wavelet coefficients and their statistics is used to perform context-dependent classification of individual blocks of the image. Unlike other edge-based approaches, our algorithm does not rely on the process of connecting object boundaries. The algorithm has achieved high accuracy when tested on more than 100 low DOF images, many with inhomogeneous foreground or background distractions. Compared with he state of the art algorithms, this new algorithm provides better accuracy at higher speed.

title: Compression of Lumigraph with multiple reference frame (MRF) prediction and just-in-time rendering
abstract: In the form of a 2D image array, Lumigraph captures the complete appearance of an object or a scene, and is able to quickly render a novel view independent of the scene/object complexity. Since the data amount of Lumigraph is huge, efficient storage and access for Lumigraph are essential. In this paper, we propose a multiple reference frame (MRF) structure to compress the Lumigraph data. By predicting the Lumigraph view from multiple neighbor views, a higher compression ratio is achieved. We also implement the key functionality of just-in-time (JIT) Lumigraph rendering, in which only a small portion of the compressed bitstream necessary for rendering the current view is accessed and decoded. JIT rendering eliminates the need to predecode the entire Lumigraph data set, thus greatly reduces the memory requirement of Lumigraph rendering. A decoder cache has been implemented to speed up rendering by reusing the decoded data. The trade off between the computational speed and cache size of the decoder is discussed in the paper.

title: The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling
abstract: Two ideas taken from Bayesian optimization and classifier systems are presented for personnel scheduling based on choosing a suitable scheduling rule from a set for each person’s assignment. Unlike our previous work of using genetic algorithms whose learning is implicit, the learning in both approaches is explicit, i.e. we are able to identify building blocks directly. To achieve this target, the Bayesian optimization algorithm builds a Bayesian network of the joint probability distribution of the rules used to construct solutions, while the adapted classifier system assigns each rule a strength value that is constantly updated according to its usefulness in the current situation. Computational results from 52 real data instances of nurse scheduling demonstrate the success of both approaches. It is also suggested that the learning mechanism in the proposed approaches might be suitable for other scheduling problems.

title: Secure outsourcing of sequence comparisons
abstract: Internet computing technologies, like grid computing, enable a weak computational device connected to such a grid to be less limited by its inadequate local computational, storage, and bandwidth resources. However, such a weak computational device (PDA, smartcard, sensor, etc.) often cannot avail itself of the abundant resources available on the network because its data are sensitive. This motivates the design of techniques for computational outsourcing in a privacy-preserving manner, i.e., without revealing to the remote agents whose computational power is being used either one’s data or the outcome of the computation. This paper investigates such secure outsourcing for widely applicable sequence comparison problems and gives an efficient protocol for a customer to securely outsource sequence comparisons to two remote agents. The local computations done by the customer are linear in the size of the sequences, and the computational cost and amount of communication done by the external agents are close to the time complexity of the best known algorithm for solving the problem on a single machine.

title: Code-coverage guided prioritized test generation
abstract: With Internet applications spreading like wildfire, software testing is challenged with new topics related to the distributed nature of Web applications. We apply code based testing techniques to the testing of Web applications, specifically Java programs. Source code based automatic test generation is difficult because most previous methods use constraint satisfaction models as a solution, which is an NP complete problem [M. J. Gallagher et al. (1997)]. We present a method of guiding users through test case generations. Instead of automating the entire procedure, our method aims at generating a framework of test cases and providing instructions for users to instantiate the framework into actual executable test cases. An early experimental study of this method shows the effectiveness of this method.

title: Observations on versioning of off-the-shelf components in industrial projects (short paper)
abstract: Using OTS (Off-The-Shelf) components in software projects has become increasing popular in the IT industry. After project managers opt for OTS components, they can decide to use COTS (Commercial-Off-The-Shelf) components or OSS (Open Source Software) components. We have done a series of interviews and surveys to document and understand industrial practice with OTS-based development in Norwegian, German, and Italian IT industry. The perspective is that of a software architect or system integrator, not a developer or maintainer of such components. The study object is a completed development project using one or several OTS components. This paper reports on the versioning aspects of OTS components in such projects. We found that one third of the COTS components actually provided source code, in addition to all OSS components. However, OTS components were seldom modified (i.e. re-used "as-is"), even if source code was available. Although backward compatibility of new releases did not cause noticeable problems for a single OTS component, using several different OTS components in a project caused difficulties in maintenance planning of asynchronous releases and system integration of new releases. Several new research questions have been formulated based on the results of this study.