木の編集距離による近似パタン発見と半構造データからの情報抽出

使用树编辑距离和半结构化数据信息提取的近似模式发现

• 批准号: 17700138
• 负责人: 久保山 哲二
• 金额: $ 2.24万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700138/
• 关键词: 木の編集距離; カーネル関数; 畳み込みカーネル; 多項式カーネル; 木の近似照合; q-gram; 木のアラインメント; 糖鎖構造; 半構造データ

前年度までに、木の編集距離の様々な既存アルゴリズムを対象に、その近似の度合いを代数的に定式化した。これにより、既存の木の編集距離のアルゴリズムを、統一的に記述し俯瞰することができるようになり、その近似の度合いや計算量に応じた自然なクラス階層が存在することもわかった。この成果は、カーネル法に基づく機械学習においても、2つの木構造間の写像の数え上げをベースにした類似度関数を設計することにより、木の編集距離の様々なアルゴリズムをカーネル関数として利用できることがわかった。本年度は、当初の計画では、木の構造照合に関する理論的な枠組みが出来次第、Webのページの木構造を対象にした情報抽出という応用へ研究を進める予定であったが、理論的により興味深く、かつ一般的な成果が得られたため、理論面の研究を進めた。具体的には、前年度までの研究成果を踏まえて、木構造のみでなく、文字列をはじめとする他の離散構造を対象とした既存の畳み込みカーネルの性質を調べた。その結果、畳み込みカーネルの厳密な定義ではなく「共通部分構造の重みつき数え上げ」という概念的な理解により設計されたカーネルで、畳み込みカーネルの定義を逸脱したものが散見されることが判明した。そのようなカーネル関数では、半正定値性が保証されず、その妥当性を確認する必要が発生する。このようなカーネル関数に対しても、本研究で、2つの木構造間のカーネル関数の設計として構築したマッピングの数え上げに基づくカーネル関数の設計手法が有効であることを示した。また、多項式カーネルを一般化したPolynomial Summaryカーネルを提案し、既存の様々なフレームワークを包括する手法であることを示した。すなわち、多項式カーネルは、限定された形式の多項式で定義されているが、これを、より一般の多項式について定義し、カーネル関数となる条件を与えた。

In the previous year, the format of the previous year's editing set is similar to that of the existing algebra. This is true, the existing editing set is far away from the system, the unified record is overlooking the environment, and the accuracy is in line with the calculation of the volume. On the basis of the results and methods, the system of mechanical engineering, the system of mechanical engineering, the This year, at the beginning of the year, the software group of the planning, engineering and engineering theory was published for the first time, and the Web software was drawn out for the first time, and the research results of the theory were profound, and the general results of the study were improved. Specific information about the results of the research in the previous year, such as the results of the research, the construction of the wood, the creation of the text, the creation of the image, the creation of the existing image, the study of the results of the research in the previous year, the research results of the previous year, the results of the research, the results of the research in the previous year, the results of the research, the The results show that the common part of the system is to understand the concept of information on the number of readings, to understand the concept of information, and to understand the concept of information. Please make sure that it is necessary to do so. In this study, 2-year-old wood structures are used in this study. The design method of this design method is shown in this paper. General Polynomial Summary, polynomial, proposal, existing, existing, including gimmick, gimmick, display. Define, define,

项目成果

A Spectrum Tree Kernel

• DOI: 10.1527/tjsai.22.140
• 发表时间: 2007
• 期刊: Transactions of The Japanese Society for Artificial Intelligence
• 作者: Tetsuji Kuboyama;Kouichi Hirata;H. Kashima;Kiyoko F. Aoki-Kinoshita;H. Yasuda

A gram distribution kernel applied to glycan classification and motif extraction.

• DOI: 10.11234/gi1990.17.2_25
• 发表时间: 2006
• 期刊: Genome informatics. International Conference on Genome Informatics
• 作者: T. Kuboyama;Kouichi Hirata;Kiyoko F. Aoki-Kinoshita;H. Kashima;H. Yasuda

畳み込みカーネルと多項式カーネルの一般化

卷积核和多项式核的推广

• 发表时间: 2007
• 作者: 久保山哲二;申吉浩
• 通讯作者: 申吉浩

A q-Grams Based Distance for Ordered Labeled Trees

基于 q-Gram 的有序标记树距离

• 发表时间: 2006
• 期刊: Proc.of 4th Workshop on Learning with Logics and Logics for Learning
• 作者: T.Kuboyama;K.Hirata;N.Ohkura;M.Harao
• 通讯作者: M.Harao

A Theoretical Analysis of Alignment and Edit Problems for Trees

树的对齐和编辑问题的理论分析

• 发表时间: 2005
• 期刊: Proc.ICTCS 2005, Lecture Notes in Computer Science (Springer-Verlag) 3701
• 作者: 今本 健二;櫻井 幸一;Yoshikazu Shima et al.;Kouichi Hirata et al.;Yoshikazu Shima et al.;Tetsuji Kuboyama et al.;Tetsuji Kuboyama et al.
• 通讯作者: Tetsuji Kuboyama et al.