Generalized sparse learning of linear models over the complete subgraph feature set
Generalized sparse learning of linear models over the complete subgraph feature set
复制标题
完整子图特征集上线性模型的广义稀疏学习
DOI：
10.1109/tpami.2016.2567399
复制
发表时间：
2017
影响因子：
23.6
通讯作者：
Mamitsuka H
中科院分区：
文献类型：
--
作者：
Takigawa I;Mamitsuka H
图上的有监督学习是一个本质上困难的问题：从完整的子图特征集中同时学习相关特征，其中由于组合爆炸，枚举给定图中出现的所有子图特征实际上是一件棘手的事情。我们证明了：1)现有的图监督学习研究，如Adabost、LPBoost和LARS/Lasso，可以被看作是具有简单界的分支定界算法的变体，我们称之为Morishita-Kudo界：2)我们给出了一种直接稀疏优化算法，用于求解具有任意二次可微损失函数的广义问题，其中Morishita-Kudo界不能直接应用；3)实验表明：1)我们的直接优化方法提高了收敛速度和稳定性；2)L1惩罚Logistic回归(L1-LogReg)在保持竞争性能的情况下识别了一个更小的子图集；3)L1-LogReg学习的子图比竞争方法更平衡，后者偏向于较小的子图。
Supervised learning over graphs is an intrinsically difficult problem: simultaneous learning of relevant features from the complete subgraph feature set, in which enumerating all subgraph features occurring in given graphs is practically intractable due to combinatorial explosion. We show that 1) existing graph supervised learning studies, such as Adaboost, LPBoost, and LARS/LASSO, can be viewed as variations of a branch-and-bound algorithm with simple bounds, which we call Morishita-Kudo bounds; 2) We present a direct sparse optimization algorithm for generalized problems with arbitrary twice-differentiable loss functions, to which Morishita-Kudo bounds cannot be directly applied; 3) We experimentally showed that i) our direct optimization method improves the convergence rate and stability, and ii) L1-penalized logistic regression (L1-LogReg) by our method identifies a smaller subgraph set, keeping the competitive performance, iii) the learned subgraphs by L1-LogReg are more size-balanced than competing methods, which are biased to small-sized subgraphs.