close
1.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 構造化ウェブデータからの並列分散データマイニングシステム — Distributed Data Mining Systems for Structured Web Data
正代 隆義 ; SHOUDAI Takayoshi
研究期間: 2002-2004
本文を見る:
概要: 本研究課題の目的は,HTMLやXMLファイルなどのウェブデータから知識発見を行う分散型計算環境に適したデータマイニングシステムの実現と,そのシステムの理論的基礎となる木構造パターンの機械学習理論の構築である. 近年,高速なネットワークと大容量記憶装置の発達を背景として,ウェブページに代表されるテキストデータの利用が急速に進みつつある.とくに,HTMLやXMLデータはテキストデータでありながら,タグを入れ子とする構造を持つので半構造データ,あるいは木構造データとよばれる.本研究課題では,木構造データからのデータマイニングの基礎理論を構築するため,木構造データを非順序木とみなす場合と,順序木とみなす場合の両方について,帰納学習あるいは例からの概念学習とよばれる基礎的研究を行った.また,提案した学習アルゴリズムを用いたデータマイニングシステムを開発した. 木構造データから意味がある知識を抽出するためには,それらに頻出する木構造パターンを発見することが必要である.そこで,まず柔軟性に富む木構造パターンとして項木を定義した.項木は,いくつかの構造的変数と辺ラベルを持つ木構造からなるパターンであり,変数にはあらかじめ定められた条件を満たす非順序木または順序木を代入することができる.我々は,変数の代入条件,項木の表現能力,およびデータ提示および質問に関する様々な設定のもとで,項木言語の多項式時間機械学習アルゴリズムを与えた.また,理論の有効性を確認するため,提案した学習アルゴリズムをエンジンとするメタサーチシステムを開発した.このメタサーチシステムは,タグやキーワードの意味を全く考えず,木の構造だけから自動でラッパーを生成する機能を持つ.このメタサーチシステムにより複数の検索サイトの統合が実現できることを確認した.以上が,本研究課題で得た研究成果の概略である. 続きを見る
2.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 計算科学への圏論の応用
河原 康雄
研究期間: 1987
本文を見る:
概要: 研究課題名「計算科学への圏論の応用」で行われた本研究は, 情報化社会を支える基礎理論である情報科学, 計算科学, ソフトウェア科学への数学的基盤を与えるために計画された研究であった. 以下, 本科学研究費補助金によって実施された研究実績を報告する. 1.研究代表者:河原康雄は, 初等トポスにおけるpushout-complementの存在定理証明し, 有限オートマトンによって受理される言語の基礎的性質をカテゴリー論的に整理すると共に, Arbib-Manes等のプログラム意味論を初等トポスにおいて考察した. これらの成果は従来から研究を蓄積してきた関係計算(relational calculus)を駆使して得られたものであり, 西ドイツのEnrigを中心としたグラフ文法等についての研究に新しい視点を与えるものであり, この分野の基礎を与えるものと期待される. 2.分担者:宮野悟は, 計算量の理論においてP≠NPの仮定のもとで効率よく並列化できると思われる, 即ち, NCアルゴリズムをもつ問題として, 辞書式順序で最初の極大部分グラフを計算する問題について考察した. 3.分担者:藤井一幸は, 古典的によく知られている4次元のCursey modelを任意次元の時空間上に拡大し, そのinstaton(meron-)like configurationsを具体的に構成した. さらに, 従来からの研究で構成していた高次元Skyrme modelsに付随したWess-Zumino termsを高次元hedgehog ansatsを使用して具体的に計算した. 4.分担者:岡崎悦朗は, 位相線形空間上の確率測度の研究を中心に研究を遂行し, 昭和62年8月よりCNRSの招きによりフランス・Paris V大学において研究を継続中である. 5.分担者:土屋卓也は, 境界要素法よって極小曲面を計算機を利用して計算し, 線形常微分方程式の特異点に関する山本範夫の定理を線形代数の範躊において一般化した. 現在, 土屋は米国・Maryiand大学において研究を発展させている. 続きを見る
3.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 学習と教示のアルゴリズム論的研究 — Algorithmic research on computational learning and teaching
宮野 悟 ; MIYANO Satoru
研究期間: 1990-1991
本文を見る:
概要: 本研究では,まず「教示可能性」という概念の定式化に成功し,従来のPAC学習可能性(確率的心似学習)との関係を明らかにした.そして,この枠組みの中で,教示し易いが学習しにくい概念クラスなどを具体的に示した.また,学習のための小さな教材を作成することの困難さについても言及することができた.また類推による教示と学習の研究では,計算量を考えた研究がほとんどなされていない状況であったが,有川・原口の類推機構の中にNP困難な状況が現れることを明らにした.こうして,この類推機構では最も基本的な部分の計算量が大きくなる可能性が強く,この部分を合理的に解決することが新たな課題として生まれた. 教示と学習の研究の中で概念クラスの小さな集合被覆を求める問題が教示可能性と深く関係していることを示したが,そのための並列アルゴリズムの研究を行い極大独立点集合を用いるという着想で極小な集合被覆を求める並列アルゴリズムを得ることができた. 学習の理論を発展させる過程で教示のためのkeyと呼ばれる概念に到達したが,このKeyを発見するための方式を開発することがこの研究を進めるうえで不可欠であることが判明した.そこで研究をこのkey発見のための方式の追求に集中した.その結果,正則パタ-ン上の決定木という概念に到達し,与えられたサンプルからそれを合理的に説明する正則パタ-ン上の決定木を学習するアルゴリズムを開発した.そしてサンプルから正則パタ-ン上の決定木を学習するシステムを試作した.この学習システム上での様々な実験を通して,この方式が他の分野においても極めて有効であることを確認した.また極小な集合被覆を求める近似アルゴリズムを核にして,与えられたサンプルをEFSとして合理的に説明する仮説を作り出す方式をつくり,それに基づいたシステムを試作した.そして,上述の正則パタ-ン上の決定木を学習する方式との比較を行った.その結果,上述の学習システムのほうがより効率的であることが判明した.しかし,EFSに基づく方法はより大きな多様性をもっていることも明らかになった.今回試作した学習システムとこの研究を通して得られた知見はこの様なシステムを構築するための基礎理論と技術を与えるものと確信する. 続きを見る
4.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 二次元メッシュ型バス機械上での極並列アルゴリズムの研究
岩間 一雄
研究期間: 1990
本文を見る:
概要: メッシュバス計算機(MB)はメッシュ計算機(MC)の局所通信機能を,ニ次元メッシュ状に配置されたバスによるグロ-バル通信機能に置き換えた並列モデルである.MBはMCに比べてそれほど劣らないハ-ドウエア的実現性を有しており,実用的には最も有望な極並列ア-キテクチャの一つであろう.本研究の目的は,このMBがどの程度の能力を発揮するかをアルゴリズム論的観点により調べるものであり,以下の成果を得ることが出来た. 1.MBはMCに比べ,グラフ問題等の数多くの問題でMCより格段に速いアルゴリズムを提供してくれる.しかし,ソ-ティング問題に関してはMC上で多くのO(n)時間アルゴリズムが知られているのに対し,MBはMCの様に再帰的な分割統治法が使えそうにないため,同様な時間のMB上でのソ-ティングアルゴリズムの開発が困難視されていた.我々は,MB上で唯一並列にソ-ティングが可能と思われる,行及び列に関するソ-トを基本演算にして,O(n)時間の新しい確率アルゴリズム(2項分布ソ-ト)を開発した.本アルゴリズムは,確率論における2項分布曲線の対称性を積極的に利用するという新しいアイデアによっている.これによって,MBのMCに対する最大の弱点を一応解消することができた. 2.MB上でのラウティング問題も考察し,以下の結果を得た.(1)MCでは2nの自明な下限が存在するのに対し,MB上で1.5n時間のラウティングアルゴリズムを得た.(2)下限としてn時間を得た.(3)デ-タの迂回効果等を調べるために,様々な特殊入力に対して上限を考察し,迂回を実際に生かせる興味深い結果を得た.本考察は上記の上下限の間隙を縮めることへの寄与が期待される. 3.その他,最大値問題に対する対数時間アルゴリズムや,κ番目に大きいデ-タを求めるO(n)のアルゴリズムの開発に成功した. 続きを見る
5.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 探索アルゴリズムの効率化 — STUDY ON EFFICIENT SEARCH ALGORITHMS
宮野 悟 ; MIYANO Satoru
研究期間: 1994-1995
本文を見る:
概要: 本研究課題では,これまで開発されてきた探索技法の有効性と限界を確認し,新たな探索方式の確立と探索アルゴリズムの効率化を計算量理論と実際の両面から行なうことが主な目的であった.この目的に沿って,探索問題を定式化し,探索アルゴリズムの設計とその並列化を行ない,さらに探索方式の現実的検討を行なった.得られた成果は次のようなものである. タンパク質の構造を数学的なグラフとして抽象化し,効率のよい構造探索を行なうための基礎となすために,グラフを項とする論理プログラミングであるFGS (Formal Graph System)の理論を展開した.グラフの認識問題のいくつかは,このFGSの反駁木問題を解くことによって,効率のよい並列アルゴリズムを持つことを証明した。 ある文字列から,それを表現する最も小さいグラフを求める問題は,Walk情報からのグラフ再構成問題として知られている.この問題は,キャタピラグラフを入力としたとき,多項式時間近似アルゴリズムさえ持ちそうにないことを証明した.このことから,タンパク質のような有限長の文字列から,効率のよいグラフ表現を導き出すためには,新しい視点からの近似アルゴリズムの研究が不可欠であることがわかり,現在その研究に着手している. タンパク質の探索の中で最も重要なものはモチーフの探索である.このモチーフを表現するために,従来,知識獲得システムBONSAIで用いていた正規パターンを元にして,正規パターンの曖昧さを表すモチーフ表現を構築した.この表現を用いて,正の例と負の例からの知識獲得実験を行ない,成果を得ている. 本研究の成果は,並列知識獲得システムBONSAI Gardenとしてまとめられ,主にゲノムデータからの知識獲得システムとして多くの研究者に利用されている. 続きを見る
6.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 離散構造の法則を発見する並列機械学習システムの開発
正代 隆義
研究期間: 1999-2000
本文を見る:
概要: 本課題では,離散構造の法則を発見する並列機械学習システムの開発に関する研究を行ない,平成12年度は次の2つの結果を得た. 1.木構造は多くの分野でデータを表現するために使われており,木構造を持つHTML/XMLファイルに代表される半構造データからの知識発見が注目を集めている.項木とは,木構造をしたデータのパターンを表現するための,変数を含むデータ構造であり,項グラフよりも表現力が小さいが,一階項よりも表現力が大きい.仮説としての項木が表すパターンと木の適合可能性を判定することは,仮説のチェックをする際に解くべき基本的な問題であり,その計算量を調べる必要がある.よって,入力である項木と木の構造的複雑さに注目してこの問題の計算量を考察し,この問題がどのような場合に効率よく解けるかどうかを調べて,そのアルゴリズムを提案した. 2.一般に,グラフは事象(頂点)とその関係を表すだけで,事象間の距離は考慮されない.しかし,地図や化学分子など,事象の位置が重要な画像データなどをグラフで表すとき,そのグラフを距離空間上で定義する必要がある.本研究課題では,距離空間上のグラフから効率良く知識を獲得するシステムを設計した.まず,この知識獲得システムの出力である仮説(知識)を表現するために,Layout Formal Graph System(LFGS)を定義した.これは,グラフを項として持つ論理プログラムであるFormal Graph System(FGS)に位置情報を加味した規則である.さらに,LFGSで用いるレイアウト項グラフでの多項式時間同型判定アルゴリズムを与えた.最後に,Brandenburgによって定義されたレイアウトグラフ文法とLFGSとの比較を行い,LFGSがレイアウトグラフ文法より表現力が大きいことを示した. これら2つの理論的結果に基づいて,HTML/XMLといったような半構造を持ったデータを対象とした機械学習システムのプロトタイプを作成し,その有効性を確認した. 続きを見る
7.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 探索アルゴリズムの並列化とその計算量の研究
正代 隆義
研究期間: 1995
本文を見る:
概要: 本課題では,探索アルゴリズムの並列化とその計算量について研究を行ない,次の成果を得た. タンパク質や核酸のデータといったゲノムデータを対象とした探索アルゴリズムの開発は宮野(九州大学)等によってその端緒はつけられており,大量ゲノムデータからの知識獲得システムBONSAIとして大きな成功を納めた.しかし,一方では,多種多様なデータを前にして,逐次的手法による探索方式の限界も指摘されている.また,探索の問題は,純粋に理論面からは,C.H.PapadimitriouやM.Yannakakisらによって局所探索の理論が存在するが,様々な探索方式・問題を捉えるためには不十分である. 本研究では,知識獲得システムの核となる探索アルゴリズムの並列化による効率化を行ない,多様なデータに対応できる並列知識獲得システムBONSAI Gardenの開発を行なった.知識獲得システムBONSAIは正負2つの例から,その例を説明する仮説をアルファベットインデキシングをラベルとする決定木として出力する.このシステムは単一のデータからなる膜貫通領域やシグナルペプチドといったようなタンパク質の説明に成果をあげた.しかしながら,2つ以上のデータが混在した例では,単一のBONSAIシステムで,意味のある小さな仮説を出力するには限界があった.この問題を解決するために,複数のBONSAIを並列に動かすアルゴリズムを設計し,知識探索の並列化を行なった.BONSAI Gardenと呼ばれるこのシステムでは,特殊なプロセスGardenerにより管理された複数のBONSAIプロセスが並列に動作し,効率のよい解空間の探索を行なう。このシステムによって、当初の目的の複数の小さな仮説を出すことに成功した.さらに,DNAおよびタンパク質の塩基配列を入力とする実験を行ない,核となる並列探索アルゴリズムの実験的有効性を確かめた. 続きを見る
8.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 離散構造を学習する並列知識発見しステムの開発
正代 隆義
研究期間: 1997-1998
本文を見る:
概要: 本課題では,離散構造を学習する並列知識発見システムの開発の研究を行ない,平成10年度は次の2つの結果を得た. 1. 大規模なデータベースから知識発見を行うときには,データベースの探索手法の開発とともに,データの見方であるビューの確立が必要である.本課題では,最初に,ビューの数学的定式化を行なった.それに基づいて,多種多様な構造を持つデタに対応できる複数の異なるビューを持った知識発見システムのプロトタイプを作成し,分子生物学的データベースを対象として並列計算機上で実験を行なった.従来のデータマイニングの枠組みでは,より複雑な構造を持つ自然科学のデータベースからうまく知識を得ることが難しい.そこで,我々は,ユーザがビューを自由に設計でき,また必要ならばユーザがプラグインとして新たなビューを追加できる新しい知識発見システムの開発を行った, 2. 本年度は,機能や構造が未知であるデータに対する知識発見方式の定式化に基づいて,項木言語の学習可能性について,昨年度に証明した結果の拡張を行った.これにより,タンパク質やRNAといったような離散構造を持つデータから自明でない特徴を見出すためのビューの確立を目指した.項木とは,変数を持つ辺にラベルを付した木である.これは,文字列パターンと同様に,その変数に任意の木を代入することで,ある複数の部分木を持つすべてのラベル付き木を表現することができる.キャタピラは,タンパク質やRNAのトポロジカルな構造を直感的に表現した木の部分クラスである.本年度は,キャタピラをベースとする項木をビューとして確立するために,昨年度の結果より広いクラスについて,キャタピラの項木言語の機械学習可能性を証明した,また,このビューを用いた知識発見システムを構築するにあたって,そのコアとなる多項式時間探索アルゴリズムのいっそうの効率化を行った. 続きを見る
9.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 科学的知識獲得のための並列探索アルゴリズムの研究
正代 隆義
研究期間: 1996
本文を見る:
概要: 本課題では,科学的知識獲得のための並列探索アルゴリズムの研究を行ない,次の成果を得た. 近年,盛んに研究がなされている帰納学習あるいは例からの概念学習とよばれる学習方式を,知識獲得システムとして構築するには探索方式の確立が不可避である.特に,「並列」を知識獲得の観点から論ずる場合, 1.知識獲得システムのコアとなる検索アルゴリズムの並列化による高速化, 2.各種多様なデータに対応できる複数の異なるビューを持ったシステムの構築, を明らかにする必要がある.本研究では,多種多様なデータからinterestingな知識を発見するため,新しいデータマイニングの開発とグラフを表現とした知識発見の2つの研究を行った. データマイニングのおおまかな枠組はIBMのAgrawalらによって確立され,最近盛んに研究されている.我々は,知識の表現の一つである結合ルールに関して研究を行い,結合ルールでは表現し得ない知識の発見を行うため,2分ダイアグラム結合ルールを定義した.さらに,このルールをデータから探索する際に現れる問題に関して計算理論的な考察を行い,遂次および並列計算に関して,いくつかの発見的アルゴリズムを提案した.現在,このルールに基づいたデータマイニングのプロトタイプ作成を行い,ゲノムデータを対象として成果を得ている. また,我々は離散的構造を持ったデータからの知識発見のためにグラフをその知識表現として採用した.実際,RNAやタンパク質の立体構造をグラフで表すいくつかの研究がなされている.本研究では,グラフで表現されたいくつかのデータからそれらに共通したある特徴をもつグラフを発見する問題を帰納推論の枠組で論じた.我々は,内田(広島市立大学)らが定義した項グラフをその表現として用い,グラフ言語の部分クラスであるいくつかのキャタピラ言語が多項式時間推論可能であることを証明した. 続きを見る