Sparse random feature maps for the item-multiset kernel.

Area of Science:

• Machine Learning
• Kernel Methods
• Data Mining

Background:

• Random feature maps are useful for large-scale kernel methods but struggle with sparse datasets due to dense feature generation.
• Factorization machines handle sparse data well but have non-convex optimization problems requiring many iterations.
• Existing random feature maps cannot approximate the proposed item-multiset kernel.

Purpose of the Study:

• To develop efficient random feature maps for approximating the item-multiset kernel on large-scale sparse datasets.
• To enable the use of linear models with item-multiset kernels by converting them to itemset kernels.
• To improve computational speed and memory efficiency compared to existing methods.

Main Methods:

• Defined the item-multiset kernel as a generalization of itemset and dot product kernels.
• Developed a conversion method from item-multiset kernel to itemset kernel.
• Proposed two novel random feature maps for the itemset kernel that generate sparse features for sparse input data.

Main Results:

• The proposed random feature maps are faster and more memory-efficient than existing methods for itemset kernels.
• Generated sparse random features, suitable for linear models on sparse datasets.
• Linear models using the proposed methods achieved 10x to 100x speedup on real-world datasets.

Conclusions:

• The proposed methodology effectively approximates item-multiset kernels using sparse random feature maps.
• Offers a significant computational advantage for large-scale machine learning tasks involving sparse data.
• Enables faster and more memory-efficient training of linear models for kernel methods.