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

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

基本信息

批准号：
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：
发表时间：
2019
期刊：
影响因子：
0
作者：
宇野毅明;武富有香;小林亮太;橋本隆子;久保山哲二;申吉浩;今津麻衣・氏間和仁・田中武志;吉原和明,石川有彩,渡辺健次
通讯作者：
吉原和明,石川有彩,渡辺健次

Analysis of the Characteristics of the Movements of Emergency Medical Service Personnel and the New Uniform Pants Design based on the Results of the Analysis and its Effectiveness

应急医疗人员流动特点分析及基于分析结果的新型制服裤子设计及效果

DOI：
10.5057/jjske.tjske-d-22-00027
发表时间：
2023
期刊：
Transactions of Japan Society of Kansei Engineering
影响因子：
0
作者：
徳永弘子;久保山哲二;木村敦;武川直樹;吉田雅典，髙子雄一朗，小野遥香，鈴木崚太;Hideyuki Tomosaka; Khulan Enkhbayar; Yuki Kakinuma; Ruriko Suto;滝沢隆,及川裕子,野呂千鶴子,日比野直子,藤木真由美,高橋幸子;亀谷英杏，大住晏陽，金井博幸，若月薫，森川英明
通讯作者：
亀谷英杏，大住晏陽，金井博幸，若月薫，森川英明

高齢者の住まい方が寝室温熱環境に及ぼす影響ー奈良県都市部および農村部における夏期・冬期の住宅実測調査ー

老年人的居住安排对其卧室热环境的影响 - 奈良县城乡夏季和冬季住房调查 -

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

Antimutagenic acitivity of constituents of Pyrus communis (pear)

梨成分的抗诱变活性

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
徳永弘子;久保山哲二;木村敦;武川直樹;吉田雅典，髙子雄一朗，小野遥香，鈴木崚太;Hideyuki Tomosaka; Khulan Enkhbayar; Yuki Kakinuma; Ruriko Suto
通讯作者：
Hideyuki Tomosaka; Khulan Enkhbayar; Yuki Kakinuma; Ruriko Suto