[4I3-J-2] Machine learning: analysis and buliding of basic models

[4I3-J-2-04] Entire regularization path for sparse nonnegative interaction model

〇Mirai Takayanagi¹, Yasuo Tabei², Hiroto Saigo¹ (1. Kyushu University, 2. RIKEN Center for Advanced Intelligence Project)

Keywords:LASSO, Itemset mining, Nonnegative least square, LARS, Regularization path

Building sparse combinatorial model with non-negative constraint is essential in solving real-world problems such as in biology, where the target response is often formulated by additive linear combination of features. This paper presents a solution by combining itemset mining with non-negative least squares. Our contribution is a proposal of novel bounds specifically designed for the feature search problem. In synthetic dataset, the proposed method is demonstrated to run orders of magnitudes faster than a naive counterpart without employing tree pruning. We also empirically show that non-negativity constraints reduce the number of active features much less than that of LASSO, leading to significant speed-ups in pattern search. In experiments using HIV-1 drug resistance dataset, the proposed method successfully model the rapidly increasing drug resistance triggered by accumulation of mutations in HIV-1 genetic sequences. We also demonstrate the effectiveness of non-negativity constraints in suppressing false positive features.