大規模線性分類資料低階多項式映射中雜湊函數之應用

Hash Functions for Polynomial Feature Mapping in Large Scale Linear Classification

周驍聰(Xiaocong Zhou)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701597

摘要

無資料

關鍵字

低階多項式映射 ； 雜湊函數

並列摘要

Nonlinear mappings have long been used in data classification to handle linearly inseparable problems. Low-degree polynomial mappings are a widely used one among them, which enjoys less time and space consumption and may sometimes achieve accuracy close to that of using highly nonlinear kernels. However, the explicit form of polynomially mapped data for large data sets can also meet memory or computational difficulties. To solve this, hash functions like murmur and fnv hash are used in some packages like vowpal wabbit to have flexible memory usage. In this thesis, we propose a new hash function which is faster and could achieve the same performance. The results are validated in experiments on many datasets.

並列關鍵字

low-degree polynomial mapping ； hash functions

參考文獻

A. Appleby. Murmurhash 2.0, 2008.

C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273– 297, 1995.

Q. Dang, T. Polk, and D. R. Brown. Internet x. 509 public key infrastructure: Additional algorithms and identifiers for dsa and ecdsa. 2010.

R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. Liblinear: A library for large linear classification. Journal of machine learning research, 9 (Aug):1871–1874, 2008.

H.-Y. Huang and C.-J. Lin. Linear and kernel classification: When to use which? In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 216–224. SIAM, 2016.