Online Feature Selection and Its Applications

Feature selection is an important technique for data mining before a machine learning algorithm is applied. Despite its importance, most studies of feature selection are restricted to batch learning. Unlike traditional batch learning methods, online learning represents a promising family of efficient and scalable machine learning algorithms for large-scale applications. Most existing studies of online learning require accessing all the attributes/features of training instances. Such a classical setting is not always appropriate for real-world applications when data instances are of high dimensionality or it is expensive to acquire the full set of attributes/features. To address this limitation, we investigate the problem of Online Feature Selection (OFS) in which an online learner is only allowed to maintain a classifier involved only a small and fixed number of features. The key challenge of Online Feature Selection is how to make accurate prediction using a small and fixed number of active features. This is in contrast to the classical setup of online learning where all the features can be used for prediction. We attempt to tackle this challenge by studying sparsity regularization and truncation techniques. Specifically, this article addresses two different tasks of online feature selection: (1) learning with full input where an learner is allowed to access all the features to decide the subset of active features, and (2) learning with partial input where only a limited number of features is allowed to be accessed for each instance by the learner. We present novel algorithms to solve each of the two problems and give their performance analysis. We evaluate the performance of the proposed algorithms for online feature selection on several public datasets, and demonstrate their applications to real-world problems including image classification in computer vision and microarray gene expression analysis in bioinformatics. The encouraging results of our experiments validate the efficacy and efficiency of the proposed techniques.Related Publication: Hoi, S. C., Wang, J., Zhao, P., &amp; Jin, R. (2012). Online feature selection for mining big data. In <em>Proceedings of the 1st International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications</em> (pp. 93-100). ACM. http://dx.doi.org/10.1145/2351316.2351329 Full text available in InK: http://ink.library.smu.edu.sg/sis_research/2402/ Wang, J., Zhao, P., Hoi, S. C., &amp; Jin, R. (2014). Online feature selection and its applications. IEEE Transactions on Knowledge and Data Engineering, 26(3), 698-710. http://dx.doi.org/10.1109/TKDE.2013.32 Full text available in InK: http://ink.library.smu.edu.sg/sis_research/2277/特征选择（Feature selection）是机器学习算法应用前数据挖掘领域的一项关键技术。尽管其重要性不言而喻，但绝大多数特征选择研究均局限于批量学习场景。与传统批量学习方法不同，在线学习（online learning）代表了一类适配大规模应用场景的高效且可扩展的机器学习算法家族。现有在线学习研究大多要求访问训练实例的全部属性/特征，而当数据实例维度极高，或获取完整属性/特征集的成本高昂时，这种经典设定并不总能适配真实应用场景。为解决这一局限，我们研究了在线特征选择（Online Feature Selection, OFS）问题：在线学习者仅被允许维护一个仅使用少量固定数量特征的分类器。在线特征选择的核心挑战在于，如何仅使用少量固定的活跃特征完成精准预测——这与经典在线学习场景中可使用全部特征进行预测的设定截然不同。我们通过研究稀疏正则化与截断技术来应对这一挑战。具体而言，本文针对两类不同的在线特征选择任务展开研究：(1) 全输入学习：学习者可访问全部特征以确定活跃特征子集；(2) 部分输入学习：学习者仅能为每个实例访问有限数量的特征。我们提出了用于解决这两类问题的新颖算法，并给出了相应的性能分析。我们在多个公开数据集上评估了所提在线特征选择算法的性能，并展示了其在真实世界任务中的应用，包括计算机视觉领域的图像分类以及生物信息学领域的微阵列基因表达分析。实验结果令人振奋，验证了所提技术的有效性与高效性。 相关出版物： Hoi, S. C., Wang, J., Zhao, P., & Jin, R. (2012). 面向大数据挖掘的在线特征选择. 发表于<em>第一届大数据、流数据与异构源挖掘国际研讨会论文集：算法、系统、编程模型与应用（Proceedings of the 1st International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications）</em> (pp. 93-100). ACM. http://dx.doi.org/10.1145/2351316.2351329 全文可于InK获取：http://ink.library.smu.edu.sg/sis_research/2402/ Wang, J., Zhao, P., Hoi, S. C., & Jin, R. (2014). 在线特征选择及其应用. <em>IEEE知识与数据工程汇刊（IEEE Transactions on Knowledge and Data Engineering）</em>, 26(3), 698-710. http://dx.doi.org/10.1109/TKDE.2013.32 全文可于InK获取：http://ink.library.smu.edu.sg/sis_research/2277/