close
1.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 文字列学理論に基づいた高速知識発見システムの開発に関する基盤研究
稲永 俊介
研究期間: 2005-2007
本文を見る:
概要: 文字列学理論に基づいた高速知識発見システムの開発に関する基盤研究として,本年度は1)データ圧縮,2)索引構造,3)知識発見,に関する研究を行った. 1)データ圧縮に関する研究は,1970年代から今日まで盛んに行われている.本研究では,長さ優先置換法と呼ばれるデータ圧縮技法に対し,線形時間・領域で動作するアルゴリズムを提案した.また,この技法を改良し,より高い圧縮率を実現するアルゴリズムを与えた.この改良版アルゴリズムも線形時間・領域で動作する.さらに,長さ優先置換法と頻度優先置換法の比較実験を行い,データによっては長さ優先置換法がより優れていることを示した. 2)1973年にWeinerによって提案された接尾辞木をはじめとして,文字列データに対する様々な索引構造が提案されている,本研究では,疎接尾辞木という単語の切れ目に着目した索引構造を,線形時間で構築する初のアルゴリズムを開発した.また,疎有向無閉路文字列グラフ,疎圧縮有向無閉路文字列グラフという新たな索引構造を提案し,これらを線形時間で構築するアルゴリズムを与えた. 3)機械可読なデータの多くは,文字列として表現されている.情報爆発時代と呼ばれる昨今において,巨大データから有用な知識だけを半自動的に抽出する手法の開発は,緊急課題のひとつとなっている.本研究では,正例と負例という二つの文字列集合が与えられたとき,これらを最も端的に弁別する文字列分類機を効率よく発見するアルゴリズムを提案した.文字列分類機は,文字列パタン発見における既存のパタンクラスの自然な拡張になっている.最適な文字列分類機を発見する問題がNP困難であることを示した上で,高速な文字列照合技法と効率的な枝刈り手法を組み合わせることで,実用的な知識発見アルゴリズムを設計した. 続きを見る
2.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 巨大学術社会情報からの知識発見に関する基礎研究 — Foundations of Knowledge Discovery from Science and Business Information
有川 節夫 ; ARIKAWA Setsuo
研究期間: 1998-2001
本文を見る:
概要: 特定領域研究(A)「巨大学術社会情報からの知識発見に関する基礎研究(略称:発見科学)」の総括班として、領域全体の企画・調整・評価を行い、さらに、各研究項目を横断する基礎研究を行うのが主な目的である。平成10年度から12年度の3年間、以下のような研究活動を行った。 (1)総括班会議:毎年3回会議を開き、全体会議の企画、研究成果報告書、翌年の研究活動基本計画、国際会議Discovery Science開催計画、研究活動・成果の評価と総括、翌年の研究計画の調整等を行った。 (2)国際会議:毎年1回外国の著名な研究者数名を招待し、約150人の参加を得て開催した。同時に、参加した外国人研究者に本特定領域研究の成果に関する意見を求めた。国際会議「発見科学」の論文集をドイツのSpringer-Verlag社から出版した。 (3)チュートリアル:チュートリアルをセミナーの形で開催し、研究分野の啓蒙と研究成果のフィールドへの普及を図った。 (4)研究成果の発表とレビュー:発見科学に関連のある外国での国際会議等に研究者数名を派遣し、本特定領域研究による研究成果を発表し、外国における最新の研究状況を調査し、同時に研究成果のレビューを受けた。 (5)研究成果発表会:3月に全研究者参加による公開の研究成果発表会を開催し、研究成果報告書を刊行した。 (6)ニュースレター:研究活動状況を周知させるために、本特定領域研究のホームページを開設し、ニュースレターを発行した。 (7)プログレスレポート:外国人研究者によるレビューのために、英文による研究計画、進捗状況の概要をまとめたProgress Reportを発行した。 (8)横断的研究:設定した5つの研究項目に誇る横断的な研究として、「知識科学としての発見科学」、「言語データからの知識発見」及び「画像データからの知識発見」というテーマで研究を展開した。(大須賀、辻井、鳥脇) 続きを見る
3.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of リンク情報からの知識網構成に関する研究
廣川 佐千男
研究期間: 1998
本文を見る:
概要: 毎日増加し続けるインターネットのホームページから役に立つ情報が選択され、分かり易く見易くい形で表現されたとき、インターネット上の知識と呼ぶことができる。このような情報の取捨選択と配置を通じて、まとまりのある統一的な知識が出来上がるメカニズムを解明し、システムとして実現することが本研究のテーマである。 本年度は、まず知識網としてのリンク構造をWWWブラウザ上で表現する方式を検討した。我々が開発してきた、ネットワーク上のアイデアプロセッサZKを、この目的で利用できるようにした。ZKの特徴はブラウザ画面での配置にあった。しかし、リンクを辿りノードを増やしていく作業は、ZKの内部表現であるZKスクリプトを直接編集しなければならなかった。そこで本年度は、URLのリンクを1段階辿り、結果を再びZK画面に表示するリンク・トレース機能を開発した。 インターネットで調べ事をするときに、一番使っているのは検索エンジンである。特に、何らかの背景的知識はあっても、インターネット上でどこにその情報があるか知らないときには、検索エンジンは必須であり有効である。初期の「KN on ZK」においてノードを増やす際には、システムの外部で検索エンジンを利用して作業を進めていた。そこで、検索エンジンによる検索結果を取り込みむための仕組みを開発した。これにより、検索エンジンとの結合による知識網の発展が可能となった。 続きを見る
4.
助成・補助金
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およびタンパク質の塩基配列を入力とする実験を行ない,核となる並列探索アルゴリズムの実験的有効性を確かめた. 続きを見る
5.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 科学的知識獲得のための並列探索アルゴリズムの研究
正代 隆義
研究期間: 1996
本文を見る:
概要: 本課題では,科学的知識獲得のための並列探索アルゴリズムの研究を行ない,次の成果を得た. 近年,盛んに研究がなされている帰納学習あるいは例からの概念学習とよばれる学習方式を,知識獲得システムとして構築するには探索方式の確立が不可避である.特に,「並列」を知識獲得の観点から論ずる場合, 1.知識獲得システムのコアとなる検索アルゴリズムの並列化による高速化, 2.各種多様なデータに対応できる複数の異なるビューを持ったシステムの構築, を明らかにする必要がある.本研究では,多種多様なデータからinterestingな知識を発見するため,新しいデータマイニングの開発とグラフを表現とした知識発見の2つの研究を行った. データマイニングのおおまかな枠組はIBMのAgrawalらによって確立され,最近盛んに研究されている.我々は,知識の表現の一つである結合ルールに関して研究を行い,結合ルールでは表現し得ない知識の発見を行うため,2分ダイアグラム結合ルールを定義した.さらに,このルールをデータから探索する際に現れる問題に関して計算理論的な考察を行い,遂次および並列計算に関して,いくつかの発見的アルゴリズムを提案した.現在,このルールに基づいたデータマイニングのプロトタイプ作成を行い,ゲノムデータを対象として成果を得ている. また,我々は離散的構造を持ったデータからの知識発見のためにグラフをその知識表現として採用した.実際,RNAやタンパク質の立体構造をグラフで表すいくつかの研究がなされている.本研究では,グラフで表現されたいくつかのデータからそれらに共通したある特徴をもつグラフを発見する問題を帰納推論の枠組で論じた.我々は,内田(広島市立大学)らが定義した項グラフをその表現として用い,グラフ言語の部分クラスであるいくつかのキャタピラ言語が多項式時間推論可能であることを証明した. 続きを見る
6.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 巨大学術社会情報からの知識発見に関する基礎研究
有川 節夫
研究期間: 1997
本文を見る:
概要: 本基盤研究(企画・調査)は,平成10年度から平成12年度までの3年間にわたって実施する重点領域研究「巨大学術社会情報からの知識発見に関する研究」(略称:発見科学,領域番号294)の準備のための企画・調査を行なうのが主な目的である.本年度は,以下のように行った. (1)巨大学術社会情報の実地調査 平成9年9月6日に領域代表者及びシステム開発を伴う研究班の班長とで,東京大学を訪問し,また,平成10年2月4日に京都大学を訪問し,巨大データとの取り組み状況を実地に調査し,本重点領域研究との連携をはかった. (2)第1回班長会議 平成9年10月5日に仙台東急ホテルにおいて班長会議を開催し,重点領域研究「発見科学」の研究実施の概要を固め,企画を具体化し,調査項目と調査場所等の詳細について検討した. (3)総括班会議平成9年11月27日に東京大学で本研究組織全体会議を開催し,重点領域研究「発見科学」の概要と実施討画案を示し,計画研究に参加しない総括班のメンバーからのアドバイスや指導を得て,実施計画を具体化した.また,同日チュートリアル2件を開催した. (4)欧州での研究打ち合せ平成10年1月27日〜2月1日にヨーロッパのエスプリ計画等の一環として展開中の帰納的諭理プログラム及びデータベースからの知識発見のプロジェクト代表者等を訪問し,欧州における巨大情報からの知識発見研究の実情についての研究打ち合せを行い,同時に,本重点領域研究に対するアドバイス等を得た. (5)哲学・諭理グループとの研究打ち合せ 平成10年2月11日に東北大学において,哲学・諭理グループとの研究打ち合せを行い,今後の研究の方針を具体化した. (6)第2回班長会議 平成10年3月3日に東京で2回目の班長会議を開き,上記の会議及び諸調査に基づき研究実施討画を再検討し,研究活動の詳細を決定した. 続きを見る