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

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

基本信息

批准号：
17700138
负责人：
久保山哲二
金额：
$ 2.24万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

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

直到上一年，针对树木编辑距离的各种现有算法制定了近似程度。这允许在鸟眼上查看现有树木的编辑距离算法的统一描述，并且还发现有一个自然的类层次结构与近似程度和计算量相对应。该结果表明，即使在基于内核方法的机器学习中，各种用于树编辑距离的算法也可以通过基于两个树结构之间的计数图设计相似性函数来用作内核函数。在今年，最初的计划是一旦建立了匹配树木的理论框架，就可以应用网页树结构的信息提取，但是由于理论更有趣，并获得了一般结果，因此进行了理论研究。具体而言，根据上一年的研究结果，我们研究了现有的卷积内核的特性，不仅针对树结构，而且针对其他离散结构（例如字符串）。结果，发现有许多内核偏离了卷积内核的定义，而不是对“共同亚结构的加权计数”的概念理解。这样的内核函数不能保证半阳性的确定值，因此有必要确认其有效性。这项研究还表明，基于对两个树结构之间内核函数设计的计数映射的内核函数设计方法是有效的。我们还提出了一个多项式摘要内核，该内核概括了多项式内核，并表明这是一种包含各种现有框架的方法。也就是说，多项式内核被定义为有限形式的多项式，但这是针对更通用的多项式定义的，并且给出了变为核函数的条件。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Spectrum Tree Kernel

DOI：
10.1527/tjsai.22.140
发表时间：
2007
期刊：
Transactions of The Japanese Society for Artificial Intelligence
影响因子：
0
作者：
Tetsuji Kuboyama;Kouichi Hirata;H. Kashima;Kiyoko F. Aoki-Kinoshita;H. Yasuda
通讯作者：
Tetsuji Kuboyama;Kouichi Hirata;H. Kashima;Kiyoko F. Aoki-Kinoshita;H. Yasuda

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

卷积核和多项式核的推广

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
久保山哲二;申吉浩
通讯作者：
申吉浩

A q-Grams Based Distance for Ordered Labeled Trees

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

DOI：
发表时间：
2006
期刊：
Proc.of 4th Workshop on Learning with Logics and Logics for Learning
影响因子：
0
作者：
T.Kuboyama;K.Hirata;N.Ohkura;M.Harao
通讯作者：
M.Harao

A Theoretical Analysis of Alignment and Edit Problems for Trees

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

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

Flexible tree kernels based on counting the number of tree mappings

基于计算树映射数量的灵活树核

DOI：
发表时间：
2006
期刊：
Proc.of 4th International Workshop on Mining and Learning with Graphs
影响因子：
0
作者：
T.Kuboyama;K.Shin;H.Kashima
通讯作者：
H.Kashima

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

久保山哲二其他文献

Enumeration of Maximally Frequent Ordered Tree Patterns with Height-Constrained Variables for Trees

具有树高度约束变量的最大频繁有序树模式的枚举

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
鈴木祐介;宮原哲浩;正代隆義;内田智之;松本哲志;久保山哲二
通讯作者：
久保山哲二

女子師範学校・高等女学校における女子体操服

女子师范学校和女子高中的女子体操服

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
徳永弘子;久保山哲二;木村敦;武川直樹;吉田雅典，髙子雄一朗，小野遥香，鈴木崚太;Hideyuki Tomosaka; Khulan Enkhbayar; Yuki Kakinuma; Ruriko Suto;滝沢隆,及川裕子,野呂千鶴子,日比野直子,藤木真由美,高橋幸子;亀谷英杏，大住晏陽，金井博幸，若月薫，森川英明;城戸千晶・久保博子・東実千代・佐々尚美・磯田憲生;難波知子
通讯作者：
難波知子