木の編集距離尺度の理論的解析(数理モデル一般)
スポンサーリンク
概要
- 論文の詳細を見る
木の近似照合は広い適用領域をもち、半構造化文書やRNA2次構造の類似性判定、XMLのスキーマ発見・統合、プログラムの差分検出をはじめとする様々な分野で、独立に多様なアルゴリズムが提案されている。木の近似照合アルゴリズムの多くは、編集距離による操作的な記述により特徴づけられてきたが、独立して提案されてきたこれらの様々なアルゴリズムの関連性については、ほとんど研究されていない。本論文では、編集距離に基づく既存の様々な木の近似照合を統一的に記述するための数学的モデルを提案する。文字列においては、アラインメントと編集距離が、その計算において等価であるが、これを木に拡張した場合、両者が等価ではなくなることが知られている。本提案モデルを用いて、木のアラインメントと等価な編集距離のクラスを同定する。すなわち、従来、別々のアルゴリズムであると考えられていた木のアラインメントとless-constrainded編集距離が等価であることを示す。
- 社団法人情報処理学会の論文
- 2005-03-09
著者
-
宮原 哲浩
広島市立大学
-
久保山 哲二
東京大学国際・産学共同研究センター
-
久保山 哲二
学習院大学計算機センター
-
Kuboyama Tetsuji
Research Center For Advanced Sciencece And Technology Center For Collaborative Research The Universi
-
久保山 哲二
九州大学大学院システム情報科学研究科知能システム学専攻
-
申 吉浩
東京大学先端科学技術センター
-
久保山 哲二
東京大学生産技術研究所
-
久保山 哲二
九州大学大学院総合理工学研究科雨宮研究室
-
Miyahara Tetsuhiro
The Graduate School Of Information Sciences Hiroshima City University
関連論文
- 自由度1及び2の分割自由カーネル (特集 「諸分野の連携による知識発見」および一般)
- 特許の有効性に影響を与える要因の検討(セッション2)
- 特許の質の機械学習からのアプローチ : 特許の法的有効性判定のための特徴抽出の試み
- 適応共鳴理論を応用した分類規則の学習(学生セッション,大学のAI・企業のAI)
- マルチエージェントシステムにおける利他的な行動規則の獲得(モデル/理論, ソフトウェアエージェントとその応用論文)
- 顔画像の類似度判断における決定木を用いた重要属性の考察
- 遺伝的アルゴリズムの時間割作成問題への適用に関する一考察(人工知能,認知科学)
- 遺伝的ネットワークプログラミングを応用した状態遷移グラフの獲得(「21世紀の知識情報科学に向けて」,及び一般)
- 半構造データからの縮約可能変数つきタグ木パターンの抽出
- 半構造データからの縮約可能変数つきタグ木パターンの抽出(「アクティブマイニング」及び一般)
- 1-215 遺伝的ネットワークプログラミングを利用したマルチエージェントのグループ化
- G-18 決定木による顔画像の類似度判断における重要属性の考察(人工知能(学習),G.人工知能)
- 木構造データからのパターン発見における遺伝的プログラミングの適用
- 顔の類似度における情報処理の適用への一考察
- 半構造データにおける極大頻出タグ木パターンの発見について
- 木構造データのパターンを用いる知識発見について
- 木構造データからの知識発見について
- 時間割作成問題への遺伝アルゴリズムの適用
- ハミング距離空間の次元削減によるインフルエンザウイルス遺伝子変異の解析 (特集 「知識発見の生命科学への応用」および一般)
- 金融工学数学における確率論の教授法 : 高校数学との関連づけ
- The Gram Distribution Kernel: A Tree Kernel for Glycan Classification (テーマ:特集「ウェブデータの知的処理」および一般)
- A spectrum tree kernel (論文特集:データマイニングと統計数理)
- A Theoretical Analysis of Tree Edit Distance Measures
- Measuring Distance and Finding Approximate Common Patterns in Trees--Focus on Edit Distance (特集「人工知能における論理の新たな展開」)
- 繰り返し内部構造変数を持つ木パターンの有限和の質問学習
- Polynomial Time Learnabilities of Tree Patterns with Internal Structured Variables from Queries (New Aspects of Theoretical Computer Science)
- Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data (New Aspects of Theoretical Computer Science)
- Learning of Elementary Formal Systems with Two Clauses using Queries and Their Languages(New Trends in Theory of Computation and Algorithm)
- 帰納的実数値関数の帰納推論における論駁性と信頼性(アルゴリズム一般)
- 帰納的実数値関数の帰納推論における論駁性と信頼性
- Evolution of multiple tree structured patterns using soft clustering (特集 「知識発見の生命科学への応用」および一般)
- Evolution of multiple tree structured patterns using clustering (特集 「大規模データからの機械学習と自然言語処理への応用」および一般)
- A Hierarchy of Tree Edit Distance Measures (Theoretical Computer Science and its Applications)
- 木の編集距離尺度の理論的解析(数理モデル一般)
- 木の編集距離尺度の理論的解析
- Alignable Mapping による Shock Tree の合成(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 半構造データアラインメントによるWebページからのメタデータとコンテンツの抽出 (特集:「アクティブマイニング」および一般) -- (セッション3 Webマイニング)
- 木の編集距離を用いたWebページからの情報抽出(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- 木構造アラインメントのマッピング条件
- アミノ酸の高次元符号化によるインフルエンザウイルスの抗原変異予測 (特集 「脳科学と知識処理」および一般)
- 学会報告 「人工知能学会 第73回人工知能学会基本問題研究会」
- 海外出張報告
- 動的補題生成を用いたモデル生成木の枝刈り手法とその実装
- MGTPにおけるケース分割の重複削除手法とその評価
- 木カーネルの構成のためのフレームワークとサーベイ (特集 「大規模データからの機械学習と自然言語処理への応用」および一般)
- 二分木符号の文字列編集距離による木の編集距離の近似 (特集「知識発見の諸科学への応用」および一般)
- SVMを用いたモブログテキストからの感情抽出(情報抽出,特集「Web情報処理」及び一般)
- 畳み込みカーネルと多項式カーネルの一般化 (特集 「ウェブマイニング」および一般)
- 効率的な無順序木の融合可能性判定アルゴリズム
- 根付き無順序木のフィルタリング (テーマ:特集「ウェブデータの知的処理」および一般)
- Webコンテンツの不整合問題に対するモデレーションモデルの提案
- 木写像のクラス同定
- ラベル無し順序木のqグラム距離
- 半構造データ統合のための木構造の近似照合と結合手法(セッション3: メタデータとオントロジ応用)
- 内部変数付き木パターン言語の有限和の質問学習
- On MAX SNP-hard results for unordered tree edit distance (特集 「ベイジアン・ネットワーク」および一般)
- グラフ生成システムFGSによる帰納学習システムについて
- 帰納学習のためのグラフ生成システムFGSのインタプリタについて
- グラフ生成システムFGSの帰納学習 : FGSインタプリタについて
- XMLに基づく対話型文書の構造記述とグラフ文法を用いた罫線文書の構造解析
- 半構造データにおける極大頻出タグ木パターンの発見について
- 半構造データにおける極大頻出タグ木パターンの発見について
- Discovery of Maximally Frequent Tag Tree Patterns in Semistructured Data (New Developments of Theory of Computation and Algorithms)
- Polynomial Time Matching Algorithms for Tree Structured Patterns (Foundations of Computer Science)
- 位置情報をもつグラフデータに対する知識表現言語 : Layout Formal Graph System (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- グラフデータからの知識発見システムKD-FGSについて
- Refutable Inference of Formal Graph Systems and NLC Graph Grammars (Models of Computation and Algorithms)
- フォーマルグラフシステムと頂点ラベル制御グラフ文法
- 金融工学数学のためのグラフィクス教材データベース : Bond Mathematics by Graphics
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 研究解説「セキュリティと利便性の両立をめざしてーパスワード同期とデータベースー」
- 半構造データ統合のための木構造の近似照合と結合手法(セッション3: メタデータとオントロジ応用)
- Alignable Mapping による Shock Tree の合成(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 海外派遣報告書(3件)
- 長時間過分極時のニューロン電位の揺らぎの時系列解析と脳の情報処理における機能的意義
- 文字列の高速類似度計算・検索のための要素技術について─ 系列分割手法─
- 学習管理システムによる自己学習型マルチメディア教育支援体制
- 適応共鳴理論を応用した分類規則の学習(学生セッション,大学のAI・企業のAI)
- MODELING THE USER IN 3D CHARACTER ANIMATION AUTHORING(International Workshop on Advanced Image Technology 2007)
- MODELING THE USER IN 3D CHARACTER ANIMATION AUTHORING
- A MODEL FOR MISMATCH RESOLUTION OF WEB PAGES(International Workshop on Advanced Image Technology 2006)
- A Spectrum Tree Kernel
- 根付き順序木のグラム分散 (テーマ:特集「シンボルグラウンディング問題」および一般)
- 木の編集距離を用いたWebページからの情報抽出(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- 多様化する情報・マルチメディア機器を用いた教育・研究に対する効率的な支援体制の検討
- 木構造間ノード写像の近似照合クラス同定アルゴリズム (テーマ:特集「ベイジアンネットワーク」および一般)
- Alignment of Tree Structures for Generation of Web Wrappers (特集 オントロジー)
- Discovering Knowledge from Graph Structured Data by Using Refutably Inductive Inference of Formal Graph Systems (Special lssue on Selected Papers from LA Synposium)
- 研究の方法と評価
- D-9-21 利用アプリケーションの時系列ログを用いたPCの利用形態分析(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- D-9-22 Webアクセスログからの閲覧者の行動分析(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- PC操作ログからの従業員PC利用パターンのクラスタリング
- 作業ウィンドウの時系列ログデータからの業務遷移パターン抽出 (「メディアとAI」および一般)
- ソーシャルメディアと履歴書情報の照合を通じた個人の言動の推定
- アクティブウィンドウ遷移ログからの企業内PC利用パターン分析(履歴の操作と活用,ライフログ活用技術,オフィスインフォメーションシステム,ライフインテリジェンス,一般)
- PC操作ログからの従業員PC利用パターンのクラスタリング(ログ活用・情報検索,グループウェアとネットワーク,ライフログ活用技術,一般)
- ソーシャルメディアを対象としたマーケティング解析 : 時事問題をきっかけとした想定外の消費行動抽出
- 大規模グラフから抽出したコミュニティの階層化 (特集 「Webと知識連携・統合,発想支援」および一般)