2231141
Locally linear metric adaptation for semi-supervised clustering
Many supervised and unsupervised learning algorithms are very sensitive to the choice of an appropriate distance metric. While classification tasks can make use of class label information for metric learning, such information is generally unavailable in conventional clustering tasks. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method which performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present two methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some real data sets.
8902172
Kernel-based distance metric learning for content-based image retrieval
For a specific set of features chosen for representing images, the performance of a content-based image retrieval (CBIR) system depends critically on the similarity or dissimilarity measure used. Instead of manually choosing a distance function in advance, a more promising approach is to learn a good distance function from data automatically. In this paper, we propose a kernel approach to improve the retrieval performance of CBIR systems by learning a distance metric based on pairwise constraints between images as supervisory information. Unlike most existing metric learning methods which learn a Mahalanobis metric corresponding to performing linear transformation in the original image space, we define the transformation in the kernel-induced feature space which is nonlinearly related to the image space. Experiments performed on two real-world image databases show that our method not only improves the retrieval performance of Euclidean distance without distance learning, but it also outperforms other distance learning methods significantly due to its higher flexibility in metric learning.
2846430
Super-resolution through neighbor embedding
In this paper, we propose a novel method for solving single-image super-resolution problems. Given a low-resolution image as input, we recover its high-resolution counterpart using a set of training examples. While this formulation resembles other learning-based methods for super-resolution, our method has been inspired by recent manifold teaming methods, particularly locally linear embedding (LLE). Specifically, small image patches in the lowand high-resolution images form manifolds with similar local geometry in two distinct feature spaces. As in LLE, local geometry is characterized by how a feature vector corresponding to a patch can be reconstructed by its neighbors in the feature space. Besides using the training image pairs to estimate the high-resolution embedding, we also enforce local compatibility and smoothness constraints between patches in the target high-resolution image through overlapping. Experiments show that our method is very flexible and gives good empirical results.
4841642
Locally linear metric adaptation with application to semi-supervised clustering and image retrieval
Many computer vision and pattern recognition algorithms are very sensitive to the choice of an appropriate distance metric. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method that performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present three methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some UCI data sets. Besides applying LLMA to semi-supervised clustering, we have also used it to improve the performance of content-based image retrieval systems through metric learning. Experimental results based on two real-world image databases show that LLMA significantly outperforms other methods in boosting the image retrieval performance.
1730596
A Scalable Kernel-Based Algorithm for Semi-Supervised Metric Learning
In recent years, metric learning in the semisupervised setting has aroused a lot of research interests. One type of semi-supervised metric learning utilizes supervisory information in the form of pairwise similarity or dissimilarity constraints. However, most methods proposed so far are either limited to linear metric learning or unable to scale up well with the data set size. In this paper, we propose a nonlinear metric learning method based on the kernel approach. By applying low-rank approximation to the kernel matrix, our method can handle significantly larger data sets. Moreover, our low-rank approximation scheme can naturally lead to out-of-sample generalization. Experiments performed on both artificial and real-world data show very promising results.
14216000
Robust locally linear embedding
In the past few years, some nonlinear dimensionality reduction (NLDR) or nonlinear manifold learning methods have aroused a great deal of interest in the machine learning community. These methods are promising in that they can automatically discover the low-dimensional nonlinear manifold in a high-dimensional data space and then embed the data points into a low-dimensional embedding space, using tractable linear algebraic techniques that are easy to implement and are not prone to local minima. Despite their appealing properties, these NLDR methods are not robust against outliers in the data, yet so far very little has been done to address the robustness problem. In this paper, we address this problem in the context of an NLDR method called locally linear embedding (LLE). Based on robust estimation techniques, we propose an approach to make LLE more robust. We refer to this approach as robust locally linear embedding (RLLE). We also present several specific methods for realizing this general RLLE approach. Experimental results on both synthetic and real-world data show that RLLE is very robust against outliers.
2551829
Adaptive Schemes for Improving Fractal Block Coding of Images
In this paper, we propose several adaptive methods to improve the fractal block coding (FBC) of still images. First of all, the range of the contrast scaling is adaptively selected according to its statistical property: then, we search for the best quantized value in the selected range. Then, the domain pool of the current range block is predicted using a finite-state method, which uses the information of previous best-match domain blocks and domain pools. The size of the domain pool is automatically adjusted; however, conventional studies can only determine a fixed-size domain pool. Therefore, the search process for finding the best-match domain block in our approach is more flexible. In addition, we propose a finite-state method to estimate the mean (average pixel value) of the current range block by using the means of the previous blocks. From the simulation, we achieve 0.35 dB improvement in peak signal-to-noise ratio and 10.5% reduction in bit rate on average compared with the basic FBC scheme. Finally, the encoding and decoding time of different FBC schemes is also evaluated for completeness.
11911656
802.11 Link Interference: A Simple Model and A Performance Enhancement
Recent findings have revealed that the carrier-sensing range set in current major implementations does not detect all interference signals in 802.11 networks. In this paper, we investigate the effect of interference and develop a mathematical model for it. The accuracy of our model is verified via simulations. Based on an insight from our model, we present a simple protocol that operates on the top of 802.11 MAC layer and achieves more throughput than rate-adjustment schemes.
35414635
Cache-Aware Real-Time Disk Scheduling
Previous real-time disk scheduling algorithms assume that each disk request incurs a physical disk mechanical operation and only consider how to move the disk head under real-time constraints. However, with the increased capacity of on-disk cache, modern disk drives read-ahead data aggressively. Thus, the on-disk cache may service many disk requests without incurring physical disk access. By exploring the design methodology of on-disk cache, in this paper, we propose cacheaware real-time disk scheduling algorithms that take the on-disk cache into consideration during scheduling. Therefore, the scheduling algorithm can help the cache replacement scheme to minimize the cache miss ratio. Besides, the service timing estimation is more accurate in schedulability analysis since the cache effect is considered during scheduling. A simulation-based evaluation shows the proposed scheduling algorithms to be highly successful as compared with the classical real-time disk scheduling algorithms. For example, under sequential workload with 10 sequential streams, the data throughput of our scheme is 1.1 times that of DM-SCAN.
206472390
Gradient match and side match fractal vector quantizers for images
In this paper, we propose gradient match fractal vector quantizers (GMFVQs) and side match fractal vector quantizers (SMFVQs), which are two classes of finite state fractal vector quantizers (FSFVQs), for the image coding framework. In our previous work, we proposed the noniterative fractal block coding (FBC) technique to improve the decoding speed and the coding performance for conventional FBC techniques. To reduce the number of bits for denoting the fractal code of the range block, the concepts of the gradient match vector quantizers (GMVQs) and the side match vector quantizers (SMVQs) are employed to the noniterative FBC technique. Unlike ordinary vector quantizers, the super codebooks in the proposed GMFVQs and SMFVQs are generated from the affine-transformed domain blocks in the noniterative FBC technique. The codewords in the state codebook are dynamically extracted from the super codebook with the side-match and gradient-match criteria. The redundancy in the affine-transformed domain blocks is greatly reduced and the compression ratio can be significantly increased. Our simulation results show that 15%-20% of the bit rates in the noniterative FBC technique are saved by using the proposed GMFVQs.
16045709
A General Model and Analysis of Physical Layer Capture in 802.11 Networks
While packet capture has been observed in real implementations of 802.11 devices, there is a lack of accurate models that describe the phenomenon. We present a general analytical model and an iterative method that predicts error probabilities and throughputs of packet transmissions with multiple senderreceiver pairs. Our model offers a more accurate prediction than previous work by taking into account the cumulative strength of interference signals and using the BER model to convert a signal to interference and noise ratio value to a bit error probability. This permits the analysis of packet reception at any transmission rate with interference from neighbors at any set of locations. We also prove that our iterative method converges, and we verify the accuracy of our model through simulations in Qualnet. Last, we present a rate assignment algorithm to reduce the average delay as an application of our analysis.