b-Bit Minwise Hashing for Large-Scale Linear SVM

Details b-Bit Minwise Hashing for Large-Scale Linear SVM b-Bit Minwise Hashing for Large-Scale Linear SVM

2011-05-23

arxiv.org/abs/1105.4385v1

Computer Science

Learning

Scientific paper

In this paper, we propose to (seamlessly) integrate b-bit minwise hashing with linear SVM to substantially improve the training (and testing) efficiency using much smaller memory, with essentially no loss of accuracy. Theoretically, we prove that the resemblance matrix, the minwise hashing matrix, and the b-bit minwise hashing matrix are all positive definite matrices (kernels). Interestingly, our proof for the positive definiteness of the b-bit minwise hashing kernel naturally suggests a simple strategy to integrate b-bit hashing with linear SVM. Our technique is particularly useful when the data can not fit in memory, which is an increasingly critical issue in large-scale machine learning. Our preliminary experimental results on a publicly available webspam dataset (350K samples and 16 million dimensions) verified the effectiveness of our algorithm. For example, the training time was reduced to merely a few seconds. In addition, our technique can be easily extended to many other linear and nonlinear machine learning applications such as logistic regression.

Affiliated with

Also associated with

No associations

Rating

b-Bit Minwise Hashing for Large-Scale Linear SVM does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with b-Bit Minwise Hashing for Large-Scale Linear SVM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and b-Bit Minwise Hashing for Large-Scale Linear SVM will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21896