图核函数研究现状与进展
|
摘要
核方法具有坚实的理论基础和广泛的应用,已引起了各领域的关注.基于核的机器学习方法不仅适用于以特征向量表示的模式,也适用于结构化数据的模式.前者对应的是向量核方法,后者对应的是图核方法.图核对结构化数据具有强大而灵活的表示形式,其不仅能描述研究对象或模式的特性,还能反映构成这个物体不同部分之间的结构信息.目前,基于图核的机器学习方法在模式识别、机器学习、机器视觉、数据挖掘等相关研究领域得到了极为广泛的关注与应用,已成为结构数据描述方法和应用领域的一个重要研究方向.论文从使用最为广泛的基于R-convolution的图核谈起,总结了图核研究的意义,着重回顾和讨论图核函数的基本理论、基本分类、国内外研究现状,并进一步指出图核研究的发展方向.
Graph kernels were powerful tools for structural analysis in machine learning and pattern recognition.In this paper,we commenced by reviewing the basic theory of kernel methods.Furthermore,we introduced a family of state-of-the-art graphs kernels that are instances of the kernels based on the R-convolution.Finally,we provided theoretical analysis of existing graph kernels and their future developments.
Graph kernels were powerful tools for structural analysis in machine learning and pattern recognition.In this paper,we commenced by reviewing the basic theory of kernel methods.Furthermore,we introduced a family of state-of-the-art graphs kernels that are instances of the kernels based on the R-convolution.Finally,we provided theoretical analysis of existing graph kernels and their future developments.
引文
[1]BHADESHIA H K D H.Neural networks in materials science[J].ISIJ International,1999,39(10):966-979.
[2]CORTES C,VAPNIK V.Support-vector networks[J].In Machine Learning,1995,20(3):273-276.
[3]HOFMANN T,SCHOLKOPF B,SMOLA A J.Kernel methods in machine learning[J].Annals of Statistics,2008,36(3):1171-1220.
[4]JOLLIFFE I T.Principle component analysis[M].Berlin:Springer-Verlag,2002.
[5]BISHOP C M.Pattern recognition and machine learning[M].Cambirdge:Camberidge University Press,2006.
[6]FREEDMAN D A.Statistical models:theory and practice,revised edition[M].Camberidge:Camberidge University Press,2009.
[7]GANESHAPILLAI G,GUTTAG J V,LO A.Learning connections in financial time series[C]//In Proceedings of International Conference of Machine Learning(ICML),2013:109-117.
[8]TANG B.Research on quantitative investment by machine learning[M].Beijing:Publishing House of Electronics Industry,2014.
[9]WANG L,ZHU J.Financial market forecasting using a two-step kernel learning method for the support vector regression[J].Annals of Operations Research,2010,174(1):103-120.
[10]BUNKE H,RIESEN K.Graph classification and clustering based on dissimilarity space embedding[M].Singapore:World Scientific Publishing Company,2010.
[11]MERCER J.Functions of positive and negative type,and their connection with the theory of integral equations[J].In Philosophical Transactions of the Royal Society,London,1909,209:415-446.
[12]AZIZ F,WILSON R C,HANCOCK E R.Backtrackless walks on graphs[J].IEEE Trans Neural Netw Learning Syst,2013,24(6):977-989.
[13]GOULD R.Graph theory[M].New York:Dover Publications Inc,2012.
[14]BACH F R.Graph kernel between point clouds[C]//In Proceedings of ICML,2008:25-32.
[15]SHERVASHIDZE N,VISHWANATHAN S V N,PETRI T,et al.Efficient graphlet kernels for large graph comparison[J].Journal of Machine Learning Research,2009,5:488-495.
[16]FU Y.Graph embedding for pattern analysis[M].Berlin:Springer,2013.
[17]LUO B,WILSON R C,HANCOCK E R.Spectral embedding of graphs[J].Pattern Recognition,2003,36:2213-2230.
[18]HAUSLER D.Convolution kernels on discrete structures[C]//In Technical Report UCS-CRL-99-10,UC Santa Cruz,1999.
[19]BAI L,ROSSI L,TORSELLO A,et al.A quantum jensen-shannon graph kernel for unattributed graphs[J].Pattern Recognition,2015,48(2):344-355.
[20]GARTNER T,FLACH P A,WROBEL S.On graph kernels:hardness results and efficient alternatives[C]//In Proceedings of COLT,2003:129-143.
[21]KASIMA H,TSUDA K,INOKUCHI A.Marginalized kernels between labeled graphs[C]//In Proceedings of ICML,2003:1-8.
[22]BORGWARDT K M,KRIEGEL H P.Shortest-path kernels on graphs[C]//In Proceedings of ICDM,2005:74-81.
[23]ALVAREZ M A,QI X,YAN C.A shortest-path graph kernel for estimathing gene product semantic similarity[J].J Biomedical Semantics,2011,2:3.
[24]SHERVASHIDZE N,SCHWEITZER P,LEEUWEN E J,et al.Weisfeiler-lehman graph kernels[J].Journal of Machine Learning Research,2010,1:1-48.
[25]SHERVASHIDZE N,VISHWANATHAN S V N,PETRI T,et al.Efficient graphlet kernels for large graph comparison[C]//AISTATS,2009:488-495.
[26]WANG L,SAHBI H.Directed acyclic graph kernels for action recognition[C]//In Proceedings of ICCV,2013:3168-3175.
[27]HARCHAOUI Z,BACH F R.Image classification with segmentation graph kernels[C]//In Proceedings of CVPR,2007:1-8.
[28]KRIEGE N,MUTZEL P.Subgraph matching kernels for attributed graphs[C]//In Proceedings of ICML2012:1-8.
[29]XU L,NIU X,XIE J,et al.A local-global mixed kernel with reproducing property[J].Neurocomputing,2015,168:190-199.
[30]COSTA F,GRAVE K D.Fast neighborhood subgraph pairwise distance kernel[C]//In Proceedings of ICML,2010:255-262.
[31]BAI L,HANCOCK E R.Graph kernels from the jensen-shannon divergence[J].Journal of Mathematical Imaging and Vision,2013,47(1/2):60-69.
[32]BAI L,HANCOCK E R.Fast depth-based subgraph kernels for unattributed graphs[J].Pattern Recognition,2016,50:233-245.
[33]BAI L,ROSSI L,ZHANG Z,et al.An aligned subtree kernel for weighted graphs[C]//In Proceedings of ICML,2015:30-39.
[34]BAI L,HANCOCK E R.Depth-based complexity traces of graphs[J].Pattern Recognition,2014,47(3):1172-1186.
[35]BAI L,ROSSI L,BUNKE H,et al.Attributed graph kernels using the jensen-tsallis q-differences[C]//In Proceedings of ECML-PKDD(1),2014:99-114.
[36]FERAGEN A,KASENBURG N,PETERSEN J,et al.Scalable kernels for graphs with continuous attributes[C]//In Proceedings of NIPS,2013:216-224.
[37]BAI L,REN P,HANCOCK E R.A hypergraph kernel from isomorphism tests[C]//In Proceedings of ICPR,2014:3880-3885.
[2]CORTES C,VAPNIK V.Support-vector networks[J].In Machine Learning,1995,20(3):273-276.
[3]HOFMANN T,SCHOLKOPF B,SMOLA A J.Kernel methods in machine learning[J].Annals of Statistics,2008,36(3):1171-1220.
[4]JOLLIFFE I T.Principle component analysis[M].Berlin:Springer-Verlag,2002.
[5]BISHOP C M.Pattern recognition and machine learning[M].Cambirdge:Camberidge University Press,2006.
[6]FREEDMAN D A.Statistical models:theory and practice,revised edition[M].Camberidge:Camberidge University Press,2009.
[7]GANESHAPILLAI G,GUTTAG J V,LO A.Learning connections in financial time series[C]//In Proceedings of International Conference of Machine Learning(ICML),2013:109-117.
[8]TANG B.Research on quantitative investment by machine learning[M].Beijing:Publishing House of Electronics Industry,2014.
[9]WANG L,ZHU J.Financial market forecasting using a two-step kernel learning method for the support vector regression[J].Annals of Operations Research,2010,174(1):103-120.
[10]BUNKE H,RIESEN K.Graph classification and clustering based on dissimilarity space embedding[M].Singapore:World Scientific Publishing Company,2010.
[11]MERCER J.Functions of positive and negative type,and their connection with the theory of integral equations[J].In Philosophical Transactions of the Royal Society,London,1909,209:415-446.
[12]AZIZ F,WILSON R C,HANCOCK E R.Backtrackless walks on graphs[J].IEEE Trans Neural Netw Learning Syst,2013,24(6):977-989.
[13]GOULD R.Graph theory[M].New York:Dover Publications Inc,2012.
[14]BACH F R.Graph kernel between point clouds[C]//In Proceedings of ICML,2008:25-32.
[15]SHERVASHIDZE N,VISHWANATHAN S V N,PETRI T,et al.Efficient graphlet kernels for large graph comparison[J].Journal of Machine Learning Research,2009,5:488-495.
[16]FU Y.Graph embedding for pattern analysis[M].Berlin:Springer,2013.
[17]LUO B,WILSON R C,HANCOCK E R.Spectral embedding of graphs[J].Pattern Recognition,2003,36:2213-2230.
[18]HAUSLER D.Convolution kernels on discrete structures[C]//In Technical Report UCS-CRL-99-10,UC Santa Cruz,1999.
[19]BAI L,ROSSI L,TORSELLO A,et al.A quantum jensen-shannon graph kernel for unattributed graphs[J].Pattern Recognition,2015,48(2):344-355.
[20]GARTNER T,FLACH P A,WROBEL S.On graph kernels:hardness results and efficient alternatives[C]//In Proceedings of COLT,2003:129-143.
[21]KASIMA H,TSUDA K,INOKUCHI A.Marginalized kernels between labeled graphs[C]//In Proceedings of ICML,2003:1-8.
[22]BORGWARDT K M,KRIEGEL H P.Shortest-path kernels on graphs[C]//In Proceedings of ICDM,2005:74-81.
[23]ALVAREZ M A,QI X,YAN C.A shortest-path graph kernel for estimathing gene product semantic similarity[J].J Biomedical Semantics,2011,2:3.
[24]SHERVASHIDZE N,SCHWEITZER P,LEEUWEN E J,et al.Weisfeiler-lehman graph kernels[J].Journal of Machine Learning Research,2010,1:1-48.
[25]SHERVASHIDZE N,VISHWANATHAN S V N,PETRI T,et al.Efficient graphlet kernels for large graph comparison[C]//AISTATS,2009:488-495.
[26]WANG L,SAHBI H.Directed acyclic graph kernels for action recognition[C]//In Proceedings of ICCV,2013:3168-3175.
[27]HARCHAOUI Z,BACH F R.Image classification with segmentation graph kernels[C]//In Proceedings of CVPR,2007:1-8.
[28]KRIEGE N,MUTZEL P.Subgraph matching kernels for attributed graphs[C]//In Proceedings of ICML2012:1-8.
[29]XU L,NIU X,XIE J,et al.A local-global mixed kernel with reproducing property[J].Neurocomputing,2015,168:190-199.
[30]COSTA F,GRAVE K D.Fast neighborhood subgraph pairwise distance kernel[C]//In Proceedings of ICML,2010:255-262.
[31]BAI L,HANCOCK E R.Graph kernels from the jensen-shannon divergence[J].Journal of Mathematical Imaging and Vision,2013,47(1/2):60-69.
[32]BAI L,HANCOCK E R.Fast depth-based subgraph kernels for unattributed graphs[J].Pattern Recognition,2016,50:233-245.
[33]BAI L,ROSSI L,ZHANG Z,et al.An aligned subtree kernel for weighted graphs[C]//In Proceedings of ICML,2015:30-39.
[34]BAI L,HANCOCK E R.Depth-based complexity traces of graphs[J].Pattern Recognition,2014,47(3):1172-1186.
[35]BAI L,ROSSI L,BUNKE H,et al.Attributed graph kernels using the jensen-tsallis q-differences[C]//In Proceedings of ECML-PKDD(1),2014:99-114.
[36]FERAGEN A,KASENBURG N,PETERSEN J,et al.Scalable kernels for graphs with continuous attributes[C]//In Proceedings of NIPS,2013:216-224.
[37]BAI L,REN P,HANCOCK E R.A hypergraph kernel from isomorphism tests[C]//In Proceedings of ICPR,2014:3880-3885.