鐸周大字望一日

全文

(1)理工学研究科酢U. 0002514511. R. 静岡大学. 博士論文. 帰納アプリケーション構築支援環境に関する研究. 鐸周大字望一日. 平成12年2月大学院理工学研究科博士後期課程. 設計科学専攻. 酢山明弘.

(2) 論文概要. 近年，データマイニングや知識発見の研究が大きな広がりをみせつつあるが，これは，単一の要素技術の進展というよりは，複数の要素技術が有機的に関連して進展してきた側面が大きい．すなわち，帰納学習，統計学，データベース技術などが相互に関連して進展してきている．結果として，多様な問題領域に対応することができる利点を持つが，その反面，ある特定の問題領域に最適な技術を構成・選択する問題が深刻になってきている．伝統的に，エンドユーザがこの間題を解決するために，試行錯誤的手法を利用するか，コンサルタントへの依頼という手段を利用する．しかしながら，前者の方法は，多くのコストがかかり，かつ信頼性がなく，後者の方法は，専門家のもつノウハウ（マイニングアルゴリズム選択表など）に依存しすぎることが課題であり，どちらの方法もデータマイニングを含めた帰納アプリケーションの構築支援環境が必要になってきている．以上の背景から，近年，機械学習のコミュニティでは，機械学習アプリケーションを開発するための方法論の整備や，その開発プロセスを自動化するメタ学習プロセスに関心が寄せられている・本論文では，知識発見システムの性能に影響を与える要因（バイアス）である「学習アルゴリズム」と「概念記述言語（属性集合）」に着目し，データや問題領域の特性を考慮して，有用な知識発見につながる，帰納アプリケーションをデータセット毎に探索（自動合成）する枠組みについて検討することを目的とする．具体的には，スターアルゴリズム，バージョン空間法，決定木学習，遺伝的アルゴリズムに基づく分類器学習，ブーステイング，バッギングなどの帰納学習アルゴリズムを分析し，帰納メソッド群を「データセット生成法」「分類器集合生成法」「データセットと分類器集合の評価法」「データセット更新法」 1.

(3) 11. 「分類器集合更新法」の5つのグループに分けた後に，帰納学習メソッドの仕様を決定して，帰納学習メソッドの体系（プロセスオントロジー）を構築する．同様にしてメソッドの操作対象物（情報）に対しても，操作対象物の体系（オブジェクトオントロジー）を構築する・2つのオントロジーを構築した後，帰納アプリケーションの初期仕様を構築するフェーズ（コンストラクション），所与のデータセットを使って初期仕様を具象化するフェーズ（インスタンシエーション），具象化された仕様をプログラムライブラリーを使用して実行可能コードに変換するフェーズ（コンパイレーション），実行コードがユーザが与えた精度を満足するかどうかを判定するフェーズ（テスト），精度を満足しない時，初期仕様を変更（その後，再度インスタンシエーションから処理を繰り返す）するフェーズ（リファインメント）という5つのフェーズにより，帰納アプリケーションを自動合成する枠組CAMLETの基本設計を行う．さらに，・リファインメントフェーズを帰納学習メソッドの組み合わせ探索問題として定式化し，計算コストの観点から，超並列計算機を利用して適切な帰納アプリケーションを効率的に探索する枠組についての考察も行う．上記で述べたCAMLETをC言語を用いて実装し，機械学習の研究評価のためによく利用されているデータであるUCIデータリポジトリの内，14種類の異なるデータを対象にして，分析で用いた代表的な帰納学習システムとの比較実験を行った結果・帰納学習メソッドの組合せレベルで，従来とは異なった新しい帰納アプリケーションを自動生成するとともに，過去の代表的な帰納学習システムと比較して高い性能を示すことが証明できた．また，島根医科大学の津本助教授より提供して頂いた髄膜脳炎データベースを対象にして，知識発見（埋もれたルールの発見）に対する有用性について考察を行った結果，専門家により妥当と判断された知識を供給するものの，埋もれた知識の発見に関しては・予測精度のみによる帰納アプリケーションの探索では限界があり，ユーザを満足させる知識を供給できない可能性があることが判明した・以上の結果から，CAMLETを進展させる方向として，予測精度による単眼的な評価基準から帰納アプリケーションを構築するのではなく，ルールの理解容易性や学習モードなど複眼的な評価基準から帰納アプリケーションを構築する環境に関して考察する．.

(4) 目次. 1序論 2 関連研究. 5. 2．1緒言. 5. 2・2 帰納学習／データマイニング. 5. 2．2．1 決定木学習．．．．. 7. 2．2．2 仮説空間を利用した学習 2．2．3. ニューラルネットワーク. 2．2．4. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. 強化学習．‥．‥．‥．. ●. ●. ●. ●. ●. ．‥‥‥‥‥. 2．2．5 コミッティ学習. 19. 27. 2．3．1 タスク指向ユーザガイダンス. 2・3・3. 15. 24. 2．3 データマイニング構築支援. 2・3・2. 11. 27. 知識レベルモデリング…………． MLC＋＋……………………．. 29 31. 2．4 結言. 3 オントロジーに基づく帰納アプリケーション構築支援環境. 33. 3．1緒言. 33. 3．2 帰納学習におけるオントロジーの構築. 34. 3．2．1 概念の切り出し. 35. 3．2．2 概念定義と概念の階層化. 36. 3・3 3・4. 帰納アプリケーションの合成手順………… 帰納アプリケーション構築支援実験と評価……．. 3・4・1機械学習共通データへの適用 111. ………. 39 46 46.

(5) 目次. lV. 3．4．2. 髄膜脳炎データベースへの適用. …………‥. 50. 3．5 結言. 4 帰納アプリケーション仕様探索の効率化. 4．1緒言 4．2. 並列処理による仕様探索の効率化…‥ 4．2．1. 基本設計…. 4．2．2. …. …. …. …. 超並列計算機上での実現法. 4．2．3 実験. ●. ●. 4．2．4 評価. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. 58. ●. ●. ●. ●. ●. …. …. …‥. 58. …… ●. ●. ●. ●. ●. ●. ●. 60 ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. ●. 4．3 3次元遷移行列探索による仕様探索の効率化． 4．3．1. CAMLETにおける仕様探索の問題点．. 4．3．2 4．3．3 4．4. 63 ．．…．63. 新しい探索法の検討………………‥. 3次元遷移行列探索による仕様探索実験と評価……. 結言. …………………‥. 64 67 70. 5 タスク知識に基づく帰納アプリケーション自動構築環境. 5．1緒言 5．2. 帰納アプリケーション評価の多様化………． 5．2．1 5．2．2. 予測精度… 学習モード…. 5．2．3. 5．2．4. 5．3. 5．4. …. …. 74. …. 74. 知識表現……………．コンパクト性. 5．2．6. 理解容易性…. 5．2．8. …. ………．. 計算コスト……………………．75. 5．2．5. 5．2．7. ……. 74. 意外性. …. …. コミッアイ. … …. … …. … …. 75 …. …. …. …. ‥. …. 76. ‥ …. 76. 77 …. オントロジーの再設計……. …. …. …. 5．3．1. オブジェクトオントロジー. 5．3．2. プロセスオントロジー…. 帰納アプリケーション合成法. …. … …. ……. …. …. …. …. …．77. …. …. ‥. 77. …. …. …. …．77. …. …. …. …．78. …. …. …. …．82.

(6) 目次. Ⅴ. 5．5 結言. 85. 6 結論. 87. 謝辞. 91. 参考文献. 93. 論文目録. 97. A CAMLETオントロジー概念定義. 101. B 髄膜脳炎データベース. 107. C CAMLET Ver．2の定義. 111. C．1プロセスオントロジーの概念定義… C．2. タスク定義知識. C．3. タスク分解知識. …. …. …. …. … …. … …. …. …. ‥111. ……. ‥116. ………. …120.

(7) 第1章序論. 近年，多量のデータ処理を必要とするデータベース応用分野が拡大しており，無作為に蓄えられた過去のデータを効率良く活用するためのシステム構築を進める技術の必要性が非常に高まってきている．そこで，データベースに蓄積されたノイズを含む生データから，高いレベルで記述された価値ある情報を発掘することを目的とした，データベースからの知識発見（KDD：KnowledgeDis− COVeryinDatabases）に関する研究が盛んになっている． KDDは，新しい技術というよりは，機械学習，統計学，データベース，データ可視化などの技術が融合した分野とみなすことができる．KDDのプロセスは，大きくデータ前処理とデータマイニング（DM：DataMining）に二分される・一般的に，ノイズが多く含まれる生データをどんなに優れたDM技術に適用したとしても，期待通りの結果は得られない．そこでデータ前処理では， DMによる規則発見をより効率的に行わせるために，目的に従ってデータベース中の生データを整理する．一方，データマイニングは，データ中に埋もれた規則性を発見するプロセスであり，目的に適した機械学習，統計学などの技術が利用される．データマイニングは，KDDプロセスの中でも非常に興味深いプロセスであるため，それぞれの分野で多くの技術が開発されている．機械学習（ML：MachineLearning）は，データマイニングに最も貢献する技術の一つであり，帰納学習のアルゴリズムを提供する．帰納学習とは，入力した事例集合を一般化することにより規則性を見つける学習アルゴリズムであり，決定木学習，バージョン空間による学習，ニューラルネットワークによる学習など多くの研究がなされている．一般的に，あらゆる問題に対してユニバー.

(8) 2. 第1章序論. サルに優位を示すML技術が存在しないため・データマイニングの構築時には， ML技術の選択という問題が生じる・伝統的に，専門知識をもたない利用者は，試行錯誤的に最適なML技術を見つけるか・マイニングに関して専門知識をもつコンサルタントへ依頼という手段をとる・このとき，前者はMいこ関する知識をほとんど持っていない場合が多く・すべてのML技術が探索対象になるであろう・一方，後者でも，ある程度ML技術の探索対象を絞り込むことができるものの最終的には試行錯誤的な選択が必要である・このように，MLアプリケーションは仕様を修正されながら何度も構築されるのが普通であるため，ML 技術がさらに多様化しつつある現在，データマイニング構築支援環境が必要になってきている・近年，以上のことから，MLのコミュニティにおいてもML アプリケーションを開発するための方法論の整備やその開発プロセスを自動化するメタ学習プロセスに関心が寄せられるようになり，1998年の機械学習国際会議（ICML98）では，DevelopingMLApplications：ProgramDefimition 恥skDecompositionandTechniqueSelectionというワークショップが開催さ. 本論文では，以上の背景のもと・与えられたデータ集合対して適切な帰納アプリケーションを自動的に構築できる，帰納アプリケーション構築支援環掛こ関する研究について述べる・本研究は，帰納学習の諸概念（帰納メソッド群）に対して体系化を行うオントロジー工学と，帰納メソッドを組み合わせて適切な帰納アプリケーションの自動合成を行うソフトウェア工学を結びつけたメタ学習機構に独自性があり・上述のML技術選択問題に応える研究として意義付けられる・また，帰納学習システムを帰納メソッドに分解し，メソッドを再合成する本研究の枠組は，その組み合わせレベルで新規的な帰納アプリケーションを合成する能力がある点からも興味深いといえる．具体的には，スターアルゴリズム，バージョン空間法，決定木学習，遺伝的アルゴリズムに基づく分類器学習，ブーステイング，バッギングなどの代表的な帰納学習アルゴリズムを分析して・組み合わせレベルで新規的な帰納アプリケーションを合成する能力を持ち・かつ・帰納アプリケーションを円滑に自動構築できるようなオントロジー（帰納メソッドの抽出と階層および定義を与える）の構築と，仕様とコードを切り離してソフトウェアを段階的に開発するソフトウェア工学の技術を応用し，オントロジーに定義されている仕様レベルの.

(9) 3. 帰納メソッドを組み合わせることで，利用者の要求を満たす帰納アプリケーション（コード）を自動合成する枠組の構築を目的とする．データマイニング構築支援の研究では，帰納アプリケーションを自動合成する研究が行われていないことから，本研究は今後の研究を進めるうえでの第一段階として有用であると考えられる．また，本帰納アプリケーション構築支援環境によって構築される可能性がある帰納メソッドの組み合わせレベルでの新しい帰納アプリケーションは，将来的に有用なパターンを提供すると考えられ，その点からも十分に意義があると考えられる．以下，本論文において，第2章では，本研究で分析を行った8つの帰納学習／データマイニイングに関する説明とデータマイニング構築支援環境に関する研究動向を述べる．第3章では，帰納学習における概念を体系化したオントロジーの構築と所与のデータセットから有用な知識を学習する帰納アプリケーション合成問題をオントロジーとして整備された帰納学習概念の組み合わせ探索問題として定式化し，適切な帰納アプリケーションを効率的に探索する枠組みについて考察する．第4章では，第3章で考察した枠組の中核をなす仕様探索の効率化について検討する．第5章は，利用者の多様な要求を満たすことができるように，第3章で考察した枠組を拡張した枠組の基本設計について述べる・第6章は結論であり，本研究を総括する．.

(10) 第2章関連研究. 2．1 緒言データマイニング（DM）に貢献する技術の中で，非常に多様な技術を提供する機械学習（特に帰納学習）は重要な技術であるといえる．一般的に，どのような問題に対しても最適となるような帰納学習システムが存在しないため， DMにはアルゴリズム選択問題が必ず生ずる．また，所与のデータの部分集合に対して的確に振舞う学習アルゴリズムが，他の部分集合では，適切に振舞わない場合もあり，いくつかの異なるアルゴリズムを混成することも必要である．データベースにおける知識発見（KDD）では，実際にテストを行うまで結果が分からないという場合が多いため，データベース中のデータを目的に沿って整理するデータ前処理と知識発見を行うDMが通常何度も繰り返し行われる．したがって，DMアルゴリズムの構築問題は，KDDプロセスのボトルネックの一つと考えられ，データマイニング構築支援の研究が進められている．本章では，2・2節で，本研究で分析を行っている帰納学習／データマイニングアルゴリズムについて紹介し，2．3節で，データマイニング構築支援の現状について述べる．. 2・2 帰納学習／データマイニング人間は，同じような出来事を二度三度経験したり，同じような事実を何度も観測したりすると，また似たようなことが起こる（観察される）のではないか 5.

(11) 6. 第2章関連研究. 表2．1：レストラン問題例（データ）. 手芸三云木石竺㍗ご完. A九. 月dr nJ．. 仇乱. Y. N. N. Y. Y. N. N. Y. タαL Phce. 月din．. Some H‡. N. F山1. N. ‡. Rej・. 円伊e. 励. Y Frencム. N. ．. 0＿10. Thd. 30＿60. Y N. N. Y. N. N. Some. ‡. N. Y. N. Y. Y. mll. ‡. N. Y. N. Y. N. mll H‡. N. Y French. ＞60. N. N. Y. N. Y. Some. Y. Y Italiam. 0−10. Y. N. Y. N. N. None. N Burger. 0−10. Y. Y Th扇. 0＿10. Y. ＞60. N. N. N. N N. Y. ‡. Some. H. Y. Y. Y. Y. Y. Y. N. N. N. N. None. ‡. N. Y. Y. Y. Y. Fbll. ‡. N. Ftlll. ‡. Y. N. Y. F山l. H. H‡. Y N. N BurgeI N. Thd. 0−10 10＿30. N Bmge− Y. Itdian. N Th扇 N Burger. lO＿30. Y Y. N. 0＿10. N. 30−60. Y. と推測する・このような・与えられた個々の事例からそれを説明する一般的な規則を導き出す推論および過程を帰納推論と呼び，この推論を用いた学習法を帰納学習と呼ぶ・帰納学習の最も重要な特徴は，有限個の事例から一般的な規則を導き出すことによって・まだ与えられていない，今後観測されるかも知れない事例，しかも無限個の事例を説明できる能力にある．一方，データマイニングとは，データ中に非明示的に埋め込まれている有益なパターンを発見することである・学習は非常に広い概念であるが，データマイニングの観点からはデータ中のパターンの発見のための主要技術として位置付けられる．本節では，レストランの席を待っか否かを決める問題（表2．1）を例として，帰納学習／データマイニングで利用される用語について説明し，決定木による学習，仮説空間を利用した学習，ニューラルネットワークによる学習，強化学習，コミッティ学習に関する基礎的な技術を述べる．例（データ）は，属性に対する値の並びと目標述語の値によって記述される．目標述語はその例の分類（クラス）と呼ばれる・ある例に対して目標述語が真であるとき・その例は正例と呼ばれる・そうでなければ，負例と呼ばれる．レストラン問題に対する例の集合ズ1，…ズ12を表2・1に示す・例耳は，ある人が.

(12) 2．2．帰納学習／データマイニング. 7. レストラン盲に行ったときの状況を表している．例の集合全体を訓練集合（訓練データ集合）と呼ぶ・ここでの目的は，目標述語柿旬甘仲厄記の定義を学習することである・ここに，属性のリストに関する補足説明を以下に述べておく． 1．A娠r−1αfe：近くに他のレストランが存在するか否か． 2．月α〔待っている間，快適に過ごすことができるバーがあるか否か． 3．舟吏〝df：金曜日，土曜日であったか否か． 4．仇明叩：空腹か否か． 5・Patrons：客がどの程度いるか（None，Some，Fbn）． 6・P膏ce‥価格帯（＄，＄＄，＄＄＄）． 7．凡止血叩：雨が降っていたか否か． 8．月egerVQ扇on：予約をしたか否か． 9・Tbpe：レストランの種類（French，Italian，Thai，Burger）．. 10・押流紹加加M加：ホストによる待ち時間の予測値（0−10分，10−30，30−60，＞60）. 2．2．1 決定木学習決定木の帰納学習は，学習アルゴリズムの中で最も単純であるが，それにも関わらず最もうまくいっている学習法の一つである．決定木学習は，帰納学習の分野に対する格好の導入の役割を果たすばかりでなく，その実装も容易である・決定木による学習システムの代表的なものとして，QuinlanのID3，その発展型であるC4．5というシステムがある．本節では，決定木構築の基本動作となるTDIDT法とID3，C4．5の動作について説明する． ID3，C4・5で利用されている決定木構築方法は，TDIDT（TbpDownIn− ductionofDecisionTree）法とよばれ，決定木の構築を根から始めてトップダウンに行なう．また決定木のトップダウンの構築中に，バックトラックなどの後戻りをしないため，非常に効率がよい．属性が二値の場合におけるTDIDT 法による学習アルゴリズム（CLS）を図2．1，レストラン問題（表2．1）に対する決定木の構築例を図2．2に示す．TDIDT法では，決定木の構築中における.

(13) 第2章関連研究. 8. 凡乃Cfj0m：CLS. 九野山：事例集合か，属性集合ダ仇郎融：決定木me ifDが全て同じクラスに分類されたthen return根ノードだけの決定木升ee； else. hr（五＝吊＜＝γ再＋＋）タα叫朗を計算；卵血を最大にする属性んl弧を選択；ダ′←属性集合ダから属性ん旧を削除； hr（J＝1万＜＝γ豆＋＋）（. 巧←β中の事例で属性ん弧の値がJである集合；升e勺＝CLS（巧，ダ）；／／mejはmeの部分木）. return. 升ee. 図2．1：決定木を学習する再帰的アルゴリズム内部ノードに対する属性の選択が，最終的に得られる分類木の精度に大きく影響する・CLSにおける属性選択は，情報利得（informationgain）を最大にする属性を選択する．情報利得は，テスト前の必要情報量（ェントロピー）とテスト後の必要情報量の差として，以下のように求められる．ここでは簡単のために，クラスは2倍（正例P，負例N）とし，その個数をそれぞれp，犯とする．このとき，クラスを同定するのに必要なェントロピー. 軸可＝一志〜092妄莞一議隼㌫また，データかを属性力の値（ん，ん，…，ん）で分類してできるテスト後のエントロピーは，. β（封. ㌔鋸j＋几ん p＋几. 柏ん，几ん）・. したがって，情報利得は，卵血（封＝J（p，几）一月（邦．と定義することができ，TDIDT法では，分割することによる情報利得関数（gain）が最大になる属性九を順次選択する．.

(14) 2．2．帰納学習／データマイニング. 9. Patrons. 図2．2：CLSアルゴリズムによって得られた決定木の例. CLSアルゴリズムでは，事例集合が所与であることを前提としているが，事例集合が大規模である場合，事例集合より訓練集合を選択，更新していく方法を必要とする．ID3は訓練集合を更新する方法を与えるものである・ ID3学習アルゴリズム CLSアルゴリズムでは，全ての事例集合をアクセスして，取り出す必要がある．これは解決できる問題の大きさに実用上の制限を与える．ID3アルゴリズムは非常に大きな事例集合の問題を扱えるようCLSを拡張したアルゴリズムである．ID3アルゴリズムでは，能動的な実験計画のアプローチにより，事例集合のよい部分集合が選び出され，事例の全集合は順アクセスできるだけでよい．ID3アルゴリズムの概要は次の通りである．訓練集合Tの更新方法にはいくつかの代替案が存在する．例えば，（1）Tの事例はそのまま残し，且より一定数の事例を加え，新しいTとする・（2）T の事例は決定木の各末端に1つずつ残し，他は捨て去り，これを且より補充する．（3）決定木の各末端に対し反例となっている事例を且より1つずつ選.

(15) 10. 第2章関連研究. 凡乃Cfわれ：ID3. 座視f：事例集合か，属性集合ダ仇埠血：決定木乃℃e r←事例集合かからサンプリング；8−Tはテスト事例集合；. While（1）（. 升ee＝CLS（r，巧； 8−rを用いて升eeをテスト； if反例がないthenreturn升ee； else†. 反例集合且を登録； r←Tと且より吏新；. 図2．3：ID3学習アルゴリズム. び・これをrに加え，新しいTとする．などがある．. C4．5. C4・5は，学習アルゴリズム的にはID3と同じである・その違いは評価関数にある・すなわち，ID3は情報利得を評価関数として，これが最大となる属性を順次選択しているが・この基準では値の種類が多い属性が選ばれやすいという欠点があるため，C4・5は情報量DIで規格化した情報利得比（informa＿ tiongainratio）を用いている．. 叫封＝−宣 J. 裾j＋花山 p＋乃. J￣. p＋乃. 決定木の学習は，実用的に最も成功している機械学習の方法の一つであり，実際に・診断型エキスパートシステムの開発や大規模データベースからの知識獲得などに用いられている・前者の例としては・医療診断システムや保険商品選択システムなどがあり・後者の例としては，遺伝子データベースからの知識発見などがある．.

(16) ・2．2．帰納学習／データマイニング. 11. C. ▲. G G e n e r. T − 1 C. f. C. e. P S. S. 図2．4：バージョン空間表現. 2．2．2 仮説空間を利用した学習仮説空間を利用した学習は，最も古くから研究された学習法であり，帰納学習を「選ばれた表現言語によって定義される仮説空間と呼ばれる膨大な空間の中から良い仮説を見つける過程である」と解釈する考えに基づいている．本節では・代表的なアプローチであるバージョン空間法，AQ15について述べる．. バージョン空間法バージョン空間法【Mitche1182】は，Mitchellにより提案されたデータ駆動型と単一表現のアプローチをとる概念獲得方法である．バージョン空間法とは， 1）概念と例を表現するための言語，2）訓練のための正と負の例，が与えられたとき，全ての正の例をカバーし，負の例を一つもカバーしないような唯一の概念（記述）を発見するものである・言語としては，特徴ベクトル（属性／属性値のリスト）の連言記述や論理記述がよく使われる．バージョン空間の表現は，例を最も特殊な仮説とし，空の記述（全ての条件が落された記述）を最も一般的な仮説とし，全ての仮説を一般化の半順序関係を用いて表現する．「今までのデータにより除外されていない仮説」の集合H は，Hの中でも一般的な要素（G集合）と，最も特殊な要素の集合（S集合）とによってはさまれた領域として表現される（図2．4参照）．正と負の事例を訓練例として与えた時，可能な仮説の候補を絞る方法を候補.

(17) 12. 第2章関連研究. hLnCtion：EliminateCandidate. 九甲山：事例集合か 0現車祝亡：仮説H. 仮説集合Hの初期化；／／G集合は空の記述とし，S集合を最初の一つの正の例に設定 for each事例dinDdo elseifG＝SかつHが単一要素thenreturnH elSe（. ifdが正例then（その例をカバーしない仮説をGから全て取り除く； Update−Sルーチンを呼び出す；）elSei／／dが負例この例をカバーする仮説をSや、ら全て取り除く； Update−Gルーチンを呼び出す；. return H. 図2．5：候補削除アルゴリズム. 削除学習アルゴリズムという．このアルゴリズムの最終結果として，仮説H （GまたはS）を出力する．このアルゴリズムで使われる一般化／特殊化の手続きとしては，表現言語の具体的な形式にも依存するが，条件削除／付加，変数化／定数化，言語の上位概念／下位概念，区間連続化規則などがある．具体的には，一般化手続きであるUpdate−Sは，その例と今までのSとの間で一般化を施し，その中で最も特殊な仮説を全て含むようにSを更新する・逆に，特殊化であるUpdate−Gは，負の例を含まないようにGを特殊化し，その中で最も一般的な仮説を全て含むようにGを更新する・この一般化／特殊化手続きが，記述の半順序関係，即ち，全ての可能な仮説空間を作りだし，候補消去アルゴリズムはこの可能な仮説空間の一点を選択する．従って，選択的帰納推論と呼ばれる．バージョン空間法のUpdate−Sは，他の方法に比べて強力で，訓練例の与え方によって学習の結果が変わらない斬新的学習を実現している．また一般的な方法論であるため，表現言語，一般化法にさまざまな変更が可能で，いろいろな応用ができる・しかしながら，誤った訓練例（ノイズ）に弱く，選言（論理.

(18) 13. 2．2．帰納学習／データマイニング凡mCわれ：Star 劇町扉. ‥事例集合か，正例ID. O坤uf：仮説H repeat. d←クの正例からランダムに選ぶ； star←dをカバーし負例を含まない，最も一般的なルール； starから最適なルールを選ぶ；このルールによってカバーされる例をpから削除する； unti17）が空. 図2．6：スターアルゴリズム. 和）を含む概念を扱えないなどの短所もある．また多くの特徴記述を扱う大規模な概念の学習は，その仮説空間が巨大なため計算が困難になる．. AQ15 Michalskiのグループは，分類規則の集合（分類器）を学習するためのいくつかの技法を開発している・AQ15tMichalski861は，クラスciの訓練例を他のすべてのクラスり（壱≠J）から識別するようなルールの中で最も一般的なルールを学習する． AQ15は，ルールの総合的な明快さ，評価／記憶コストのようなユーザ定義された（あるいはデフォルトの）パフォーマンス基準を満たすルールを最適化することができる．AQ15のメイン関数は，正例／負例事例の集合から概念記述を構築するAqアルゴリズムが基になっている． Aqアルゴリズムは，候補削除アルゴリズムを繰り返し適用するのとほぼ等しい．AQ15はルールを学習する問題を一連の単一概念学習の問題に変換する・クラスC. のルールを見つけるためには，クラスC. に属するすべての事例を. 正例と考え，他のすべてのクラスに属する事例を負例として考える．そして， Aqを適用することにより，すべての正の概念（正例）をカバーし，負の概念（負例）を一つもカバーしないルールを見つける．AQ15は，そのようなルールの中で最も一般的なものを求めるスターアルゴリズム（図2．6）を利用する．これは，クラスに属するための必要粂件を求めることになる．図2．7は，それ.

(19) 14. 第2章関連研究. 図2．7：スターアルゴリズムによるルールの獲得. ぞれのクラスciについてスターアルゴリズムを実行した結果を図式的に示したものであり，●，▲，■は各クラスの事例を表し，楕円はクラスqをカバーする最も一般的なルールを表すものとする．しかし，単純にそれぞれのクラスC に対してスターアルゴリズムを適用しただけでは，未知の事例の領域で識別のためのルールは互いに重複する．AQ15 では重複しないルールを発見するために，次のような工夫がなされている・C拍≠ J）中のすべての与えられた事例に加え，既に学習したすべてのクラスC轟く可のルールを満たす概念を負例として与える．結果として図2．8のような重複のないルールが生成される（cl，C2，C3の順で学習）．このとき，未知の領域では，まずclを識別するルールが一番大きな領域を占め，残りの部分からC2，さらにその残りからC3を識別するルールの領域が割り当てられる． AQ15のスターアルゴリズムは，候補削除アルゴリズム以上の計算量を必要するため，大規模な学習データ集合に関するルールの発見に適していない．また，候補削除アルゴリズム同様ノイズに弱く，線形分離不可能なデータ集合に関しては，訓練事例に対する過度の学習（オーバーフィッティング）を引き起こす問題が残っている．.

(20) 2．2．帰納学習／データマイニング. 15. 図2．8：重複のないルールの獲得. 2．2．3 ニューラルネットワーク. ニューラルネットワークは，互いに結合し合らた複数のユニットで構成される・どの結合も関係を数量で表した重みを持つ．重みはニューラルネットワークの中で長期の記憶装置のための基本となる要素である．学習は一般的に，重みを更新することによって位置づけられる．ユニットのいくつかは外的環境に接続しており，入出力ユニットとして設計されている．重みは，ネットワークの入出力の振舞いが入力を支える環境が示すそれとできるだけ合致するように修正される．ニューラルネットワークには，非常に多くの種類のネットワーク構造が存在するが，その中で最もポピュラーなのは多階層フィードフォワードネットワーク【Hinton86］である．多階層フィードフォワードネットワークは，明確に区別された入力層，出力層そして1層以上の隠れ層からなる階層構造を持つ．各ユニットは次の層へだけ結合されており，同じ層の中のユニット間や，飛び越えた層には結合されていない．どのユニットも他のユニットからの入力の結合集合と，他のユニットへの出力の結合集合，現在の活性化レベル（内部情報）を持っている．また，次のステップでの入力と重みが，与えられた活性化レベルの計算につながる．すなわち，互いのユニットが入力を基本にして局所的に.

(21) 第2章関連研究. 16. 出力層. 隠れ層. 入力膚. 図2．9：レストラン問題におけるニューラルネットワーク. 計算する．図2．9は，レストラン問題（表2．1）における多階層フィードフォワードネットワークを表している．このようなニューラルネットワークを構築するには最初に，いくつのユニットが使われるかを決定しなければならない．それから，そのネットワークの重みを初期化し，訓練する例の集合が与えられ，学習アルゴリズムを使って重みを訓練する．本節では，代表的な学習アルゴリズムである誤差逆伝搬学習について説明する．誤差逆伝搬学習多階層フィードフォワードネットワークは，入力層に与えた信号が結合の重みによって変換されながら出力層のユニットの値として出力される前向きの信号伝搬を行なう（フォワードプロパゲーション）．しかしこれだけでは，ただ入力パターンからある決まった出力パターンが出るだけである．問題は入力パターンに対して望ましい出力が出るようにネットワークの学習を行なうことである・この学習の代表的なものが誤差逆伝搬学習（バックプロパグーション）である・判断が入力層から出力層へのフォワードプロパゲーションだとしたら，バックプロパゲーションによる学習は，出力層での誤差を入力層へ向かって伝搬させることで達成される．フォワードプロパグーションは，生体のニューロンを近似したものである．各ユニットの多数の入力に結合の重みをかけ総和し，活性化関数Jと呼ばれる非線形関数を通して単一の出力を出力層の方向へ伝搬していくことにより実現し.

(22) 2．2．帰納学習／データマイニング. 17. 第n層におけるユニット. 内 h︑■Lr∴・已・−卜∴■I．I. 入力層. 隠れ層. 出力層. 図2．10：フォワードプロパグーション. 第n層におけるユニット. 図2．11：バックプロパグーション. ている（図2・10参照）・活性化関数はシグモイド関数（sigmoid）が利用されることが一般的である・ここで，第m層のi番目のユニットの内部情報を彿出力値を考，第m−1層のj番目のユニットから第m層のi番目のユニットへの重みを昭誉れとすると，第m層のi番目のユニットの出力値考は次の式で求められる．. 埠＝∑呵㌃1，れ・ギ￣l J. Xr＝Sigmoid（uT）＝. 1＋e−牢. バックプロパゲーションは，実現すべき入出力関係の訓練例が与えられた時，それを実現するようにネットワーク中の各結合の重みを調整していく手法である・その指針は，ネットワークが計算した出力と目標出力との二乗誤差を小さくすることであり，勾配法を用いて修正量が求められる（図2．11参照）．.

(23) 第2章関連研究. 18. 凡mCわ0m：BackProp J如祝f：〃eねノ0γた，事例集合か仇郎融：（重みが変更された）〃eh〃0γた for eachdin7）do O←FowardProp（D）；. if（出力層の出力と目標出力の二乗誤差＞閲値）thenbreak； E〃＝t−0. for each階層inNetworkdo. 町＝埠（1−埠）∑メⅥ莞叫軍＋1 △昭予れ（t）＝賭場￣1＋α△明予れ（ト1）明予れ（け1）＝W肯1，れ（t）＋△明予れ（t）. end end return Network. 図2．12：誤差逆伝搬学習アルゴリズムバックプロパグーションの特色は，フォワードプロパグーションに用いるネットワークの結合構造をそのまま利用して，出力側から入力側に向けて教師情報（誤差情報）を伝搬している点で，伝搬後，結合の両側に存在する情報だけを使って，その結合の重みの修正量を決定できる．したがって，教師情報伝達用の特殊な通信を必要としない学習法となっている．ここに，目標出力をt，出力層から出力への結合の重みを1，第n層のi番目のユニットが伝搬する誤差情報を町，とすると，誤差逆伝搬学習のアルゴリズムは図2．12で表される．この時，. ギ＝項1−埠）∑Ⅵ莞叫ぢ＋1 は，誤差情報且を現在のユニットの内部情報（可と結合の重みを利用し，出力層から入力層へ逆伝搬するものである．以上のようにして誤差情報が伝搬されると， △明予れ（t）＝賭場￣1＋α△明㌻，れ（七一1）を利用して次に結合の重みの修正量を決定する・△明予れ（f）はれ−1層のユニットたとれ層のユニット盲との間の結合の重みに対する修正量を示し，.

(24) 2．2．帰納学習／データマイニング. 19. △昭予れ（ト1）は前回の修正量を示す・恒は学習定数で収束の速さに関係する1．0以下の正の実数・αは安定化定数で，前回の重みの修正量を使い，収束時の振動を抑える効果がある1．0以下の正の実数である．修正量が求まると，明言，れ（Hl）＝明予れ（t）＋△明言，れ（f）により，結合の重みを修正する．ニューラルネットワークは，分類クラスではなく実際の値を予測するために使うことができる・しかし，分類問題では，予測されたクラスを何らかの方法で必要である・例えば，クラスの数が2ト1と2もの間にある場合を考える．このとき，クラスを識別するためにも個の出力ユニットを与え，それぞれの出力を0，1として表す方法がある．ニューラルネットワークによる学習は，非常に大きな訓練事例が必要であるという問題点を抱えている．また，ニューラルネットワークによる学習は確かに与えた事例から予測や分類を行うことができるが，ニューラルネットワーク自体は単純なブラックボックスに等しく，予測や分類をどのようにしたかという明確なルールを提供しない．. 2．2．4 強化学習前節までに，例題から学習する帰納学習法について説明した．その主旨は，環境から入力（属性値の並び）と出力（クラス）の組を与えられたとき，学習タスクは，入力から対応する出力を生成することが可能な概念（ルール）を学ぶことであった．このような教師つきの学習法は，教師が正しい値を与える場合に適切である．また，その関数の出力が未来に関する予測を表現している場合にも，次の時間ステップにおいて成否が判断しうるゆえに，適切である．しかし，実際問題として入力に対する出力が与えられていない教師なしの場合も多く存在している．このような環境の下では，学習タスクは試行錯誤的にルールを生成し，結果的にそのルールが良かったか悪かったかという情報のみから学習しなければならない．そのような情報を総称して報酬と呼ぶ．強化学習とは，報酬という特別な入力を手がかりに環境に適応したルールを学習する教師なし機械学習である．.

(25) 20. 第2章関連研究. 図2．13：分類システム. 強化学習として良く知られたアルゴリズムには，Q学習，バケツリレーなどがある・また，一般的に強化学習では，非常に膨大な探索空間を必要とするため，効率的な探索空間の局所化を行うために遺伝的アルゴリズム（Gen。ti。 Algorithm）を用いるケースが多い・本節では，バケツリレーによる強化学習と遺伝的アルゴリズムによる探索空間の遷移を統合した枠組であるClassifier System（分類システム）【Booker89】を紹介する．分類システム. Hollandが示した分類システムではメッセージリストを使用し，内部思考的ルールの連鎖においては，原理的に並列発火を提唱している点が特徴的である（図2・13）・この仕組みには大きな可能性があるが，実際問題に適用することを考えると，直感的にみても，ルール間の情報交換の場であるメッセージやルール自身の空間の設計，並列発火やルール連鎖による複雑な処理に対する制御など難しい点が多い・それゆえ，一般的には，分類システムをルールの連鎖による内部思考を持たない単純なシステムとしてとらえて利用する．本節では単純な分類システムの詳細について説明する．ルールのシンタックスには広いバリエーションがあるが，一般的に次のように表すことが出来る．.

(26) 2．2．帰納学習／データマイニング. 21. 凡nction：Classifier−System 血町扉：事例集合か，分類器の要素数几仇ゆ融：分類器C. 航：圭禁誓葦｛ if（i＝1）thenCt←ランダム生成（n）； elseif（i＞1）thenCt＝GeneticAlgorithm（Ct−1，Ft）；. for eachdinDdo end. ifCtが目標を満たすthenbreak；）. Ci←BucketBrigade（Ct，d，Ri−1）；. returnCf. 図2．14：分類システムのアルゴリズム. if＜condition＞then＜action＞．. このルールの意味は，COnditionが満たされたときにactionを行うことができる（発火する）ということである．分類システムでは，学習されるルールセットを母集団と呼び，学習の第一段階では母集団のirtbenルールをランダムに発生させる．初期生成された母集団は，各ルールの良し悪しを測る尺度が存在しないため，強化プロセスBu。k● etBrigade（バケツリレー）アルゴリズムを実行し，どのルールが環境に適しているか学習する．しかしながら，現実的な母集団サイズでは，環境に対するすべての空間を表現することは不可能であるため，遺伝的アルゴリズム（GA）により効率的な空間探索を行うことを試みる（図2．14参照）．ルールの連鎖による内部思考を持たない単純なモデルのバケツリレーアルゴリズムでは，まず，入力された事例dに照合する複数のルールから，発火する唯一のルールを選択する（競合解消）．競合解消では，特殊性が高いルールほど選択されるようにするため，競合解消の指標となる提示（bid）は，強度だけではなく特殊性を取り入れた計算によって決定される（式2．1）．一般的には・事例にマッチしたルールは式2．2によって。最dを計算し，最高値を出した.

(27) 22. 第2章関連研究. ルールを発火させるものとする．最d＝ e玩d. ＝. qdX（古記1×sp＋最d2）×且最d＋noise桓）. ここでq闇はビッド係数であり1・0以下の正の実数，最1，最d2は最dlx条件部長の最大値＋鮎d2＝1. を満たす正の実数・射ま分類器の現在の強度，nOis中日ま確率分布. P（車完expト（；）2）にしたがう乱数とする． 1つの事例が入り，競合解消を行なった後，発火して正しい答を出したルール（成功したルール）は，鮎dを支払って報酬を受けとり，量を増加させる．発火したが間違った答を出したルール（失敗したルール）は，最dを支払うだけである・そのため，このルールは晶が減少する．また，事例に照合したルールはすべて税金を支払う・これは，照合するだけで競合解消に生き残れないような粗悪なルールを，早く淘汰するためである・また，すべてのルールから，別の種類の税金をとる・これは・有効なルールならば問題にならないほど小さいものだが，事例に全く照合しないような役に立たないルールが，自然に淘汰されていくようにするためである・上記のモデルを評価式として表現したものを式2．3−2．6に与える．成功の場合 St＋1＝（1・0−Thd−nife）×St−bid＋PAYOFF. （2．3）. 失敗の場合 ∫叶1＝（1・0一花d一端Je）×筑−ゐ五d. （2・4）. マッチのみの場合晶＋1＝（1・0−孔d一端Je）×島. （2・5）. 量＋1＝（1・0一端Je）×gf. （2．6）. マッチしない場合.

(28) 2．2．帰納学習／データマイニング. 23. 凡nction：GeneticAlgorithm htput：分類器C，FitnessFunctionFi 仇ゆ雨：分類器C repeat ︐︶ ● l. だ嵩認霊漂霊. until. return C. 図2．15：遺伝的アルゴリズム. ここで島，烏＋1は現在の強度と評価後の強度を表し，孔d，孔Jeはそれぞれビッド税と存在税，PAYOFFは成功報酬を表す．強化学習は，与えられた探索空間の中で環境に適応する関数（ルール）を強化する学習法であるため，通常，非常に膨大な探索空間を必要とする．しかし，膨大な探索空間は計算コストを非常に大きくする要因となるため，効率的な探索空間の局所化を行うために遺伝的アルゴリズム（GA）を利用するのが一般的である． GAには，大別するとミシガンアプローチとビッツアプローチの2つがある．ミシガンアプローチは各ルールを一つの個体とし，その集合を母集団と呼んでいる・そして遺伝的アルゴリズムのオペレータはルールに対して行われる．具体的には，ルールの条件部に対して交叉を行ったり，突然変異を行ったりする．つまり一つのルールを一つの染色体（遺伝子の配列）と見なすものである．一方，ビッツアプローチは，母集団を一つの個体として扱い複数の母集団で遺伝子操作を行う．このとき評価は各ルールではなく各母集団に対して行う．一般に分類システムで利用されるのがミシガンアプローチである．分類システムの遺伝的アルゴリズムを図2．15に示す．適合関数（Fitness＿ Function）は分類器の強度の関数として表現され，線形スケーリング，シグマ切断，べき乗スケーリングなどがある．Selection（選択交配）は，どの個体同士を交配させるか決定するプロセスである・Reproduction（再生）では，交叉，突然変異とよばれる生物の進化をモデル化した操作が行われる．交叉は， 2つの親の染色体を組み替えて子の染色体を作る操作である．突然変異は，遺.

(29) 24. 第2章関連研究. 伝子を一定の確率で変化させる操作である．突然変異は，あまり大きな変異確率に設定するとランダムサーチ化する危険性を含んでいるが，ある程度の変異は必要である・突然変異がない場合には，初期の遺伝子の組み合わせ以外の空間を探索することができなくなるため，求められる解の質に限界がでてくる． 2．2．5 コミツティ学習着実な技術進展はあるものの，決定木を代表とする個別の分類器の精度向上はほぼ限界に達している．さらに精度をあげるため，データの分布を変え，同じ種類の分類器を何度も生成してコミッティを形成し，メンバの総意（投票）で結論を出す手法が広く受け入れられつつある．本節では，訓練データの重複サンプルから分類器（ルール集合，決定木など）のコミッティを形成するbagging（バッギング），誤分類されたデータの重みを増加して次のデータを作成し分類器コミッティを形成するboosting（ブーステイング）について説明する．. バッギングバッギング（bootstrapandaggregating）は，ある集合をブートストラップ集合に分解し，その各々に対して分析を行い統計をとるという統計技術の一手法を指す・ただし，一般的にデータマイニングでは，帰納学習システムと融合したコミッティ学習を意味する場合が多いため，本論文において単にバッギングと記述してある場合，コミッティ学習を意味するバッギングを指す．バッギングの特色としては，わずかな差異をもつ，いくつかの学習集合を連続して学習システムに与え，それぞれの結果（分類器）を統合することにより，一つのより良い分類器を得るところにある（図2．16）．具体的には，図2．17に与えるように，入力された事例集合かからブートストラップ集合を生成する．ブートストラップ集合の要素となる各事例集合月か（各々の事例集合はそれぞれ差異を持つ）に対して，任意の学習アルゴリズムを実行し，分類器コミッティの七番目の分類器Ctを得る．図2．17により得られた分類器のコミッティは，環境から事例が与えられると，各分類器に入力事例に対する解（クラス）を投票させ，最も多いクラスを.

(30) 2．2．帰納学習／データマイニング. 25. Classifier ＆action. Boobtraped dab8et8. 図2．16：バッギング凡nction：Bagglng. 座視f：事例集合か，属性集合ダ 0祝砂山：分類器のコミッティComm招ee ブートストラップされたp集合←boostrap（p）； foreachBDinブートストラップされたD集合do Ct＝学習アルゴリズム（月か，ダ）； end. return Comm招ee；. 図2．17：バッギングアルゴリズム. 最終的なクラスとして出力する．ブーステイングブーステイングとは，数多くの精度の低いルールを組み合わせて非常に精度の高いルールを得るための，汎用的かつ理論的な性能保証のある統計技術である．現在，様々なブーステイング法が提案されているが，本節では最も一般的に利用されるAdaboostlFreund95】について説明する． Adaboostは，与えられた学習アルゴリズムを，各々一回実行するラウンドをr回繰り返す（f＝1，‥，r）．ここで，鍵になるアイデアは，事例集合（訓練集合）上に定義された確率分布（あるいは重み）のリサンプリングを行うことである．ここで，t回目の試行における事例几（れ＝1，．．，Ⅳ）の重みを戒とする．これらの重みは初期値として全て等しく設定されるが，各ラウンドに.

(31) 第2章関連研究. 26. D：data（withweight） Set. Class捕er ＆action. 図2．18：ブーステイング. おいて誤って分類された事例の重みが増やされることにより，学習アルゴリズムがより難しい事例に集中して学習することができる（図2．18）．具体的には，図2．19に示すアルゴリズムに従い動作を行う．まず，入力として事例集合かおよび，属性集合ダを受け取る．事例の重みの初期値として全て等しい値を設定する．次に，以下の動作をr回繰り返す．学習アルゴリズムを実行し，tラウンドの分類器Ctを学習する．ここで，efをCtが誤って分類した事例の重みの総和とする．このとき，t＋1ラウンドの各事例の重みは，. W㌃1−. 戒e￣dtd（正）. により算出される・αt＝主軸（宇）・中日ま，分類器が事例を正しく分類した場合は1，誤った場合は0の値をとる関数であり，易は，七十1回目の事例の重みの総和を1にするための正規化係数である．最後に投票では，各分類器の一票の価値を吋字，（t＝1，‥，r）として考え，投票結果が最も高い分類クラスを出力する．. コミッティ学習は，学習精度の向上が期待できる代わりに，学習にかかる時間的コストが非常に大きくなる欠点を持っている．基本的に学習精度を高めることと学習時間を短くすることはトレードオフの関係があるため，学習システムを利用する利用者の目的により決定されるべきである．.

(32) 27. 2．3．データマイニング構築支援. 凡nction：Boosting 劇『扉：事例集合か，属性集合ダ. hr（t＝1；t＜＝. Ct＝学習アルゴリ for eachdin Ddo. 告知. 0JL. p. for eachdin. dT. 0坤uf：分類器のコミッティComm招ee l. ／Nend. t. （か，ダ）. 祀1−廿とe可（王） Zt end ）. return Committee. 図2．19：ブーステイングアルゴリズム. 2．3 データマイニング構築支援データマイニング構築支援は，適当な粒度（ビルディングブロック）に分解されたデータマイニングに関する概念部品を知識として持ち，利用者の要求や入力されたデータの特徴に合わせ，部品を合成することでデータマイニングシステムを再構築するメタ学習システムである．本節では，このようなデータマイニング構築支援の研究の具体例として，Robert Engelsのタスク指向ユーザガイダンス（TaskOrientedUser−Guidance）【Engels96］， CilineRouveirolらの知識レベルモデリング（KnowledgeLevelModeling） lRouveiro194］，RonnyKohaviらのMLC＋＋を示す・. 2．3．1 タスク指向ユーザガイダンス目標が何であれ，複雑なタスクを実行する際に，人はタスクの構造を分類できなければならない．これは，機械学習，統計学および知識獲得の分野の技術が統合された分野であるKDDでも同様のことがいえる．現在，莫大なデータを扱うことが出来るより効率的なアルゴリズムの必要性が高まっている一方で，専門家ではない利用者を支援するために，タスクに応じて適切な技術を選択できる方法を提供する必要がある．タスク指向ユーザガイダンス【Engels96】は，典型的なKDDタスクの構造を分類する際に利用者をガイドし，ML技術を選.

(33) 第2章関連研究. ぎ⁝ud−dP3u￠TOJ明d↑ Solution. 図2．20：タスク指向プランニング. 択／使用する場合に利用者を支援する戦略コンポーネントのためのフレームワークを提供する・戦略コンポーネントの目的は，開発時間を短縮するためのタスクコンポーネントの再利用と・KDDプロセスを定義する過程の単純化，典型的なKDDタスク構造を分類するためのタスク指向プランニング，評価を支援することである．図2・20は，タスク指向ユーザガイダンスのメインフレームであるタスク指向プランニングを示している・ここに，T誠k（タスク）とは，ある状態を別の状態に変化させる一連の推論機構であり，PSM（問題解決手法：Problem SoIvingMethod）とは・あるタスクを分解したときに生成されるサブタスク列を制御フローを使って定義したものである・また，Tbchnique（技術）はコードレベルのアルゴリズムに相当する．タスク指向プランニングの概要は・トップレベルのタスク（【Engels96】では， KDD）をPSM／タスクと技術との間に1対1の写像ができるまで段階的に分解し・写像された技術のシーケンスを解（KDDプロセスのコードレベルのアルゴリズム）するものである・タスク指向プランニングにおける利用者への支援は次の通りである・まず，事前知識として，KDDに関するあらゆる分解段階のPSM／タスクの定義を行う・このとき，PSM／タスクの分解パターンは複数定義されている・利用者は，この知識に基づいた分解パターンの中から，.

(34) 2．3．データマイニング構築支援. 29. 目標を達成できるタスクの選択を行う．この選択は，ただ1つに決定する必要はなく，妥当であると思われるタスクを複数選択できる．その結果，解となるコードレベルのアルゴリズムは複数生成される．タスク指向プランニングでは，複数生成されたKDDプロセスは，すべて利用者に提示される．最適なKDD プロセスを選択する作業は，評価の支援を行うフレームワークに委託される．このように，タスク指向ユーザガイダンスは，目的のタスクを分解して実行レベルのKDDプロセスに変換する過程で，分解における選択パターンを限定することで利用者をガイドするという支援方法をとっている．しかし，示された選択パターンの中で，妥当と思われるPSM／サブタスクを選択は利用者が行うのでKDDや機械学習の分野を専門としない利用者を対象とした場合，この方法による支援はあまり有益でないと思われる． 2．3．2 知識レベルモデリング知識レベルモデリングは，生成とテスト戦略に従って構成できる学習システムの知識レベルモデルを利用することで，利用者の要求に適した学習ツールの構成を支援する環境である【Rouveiro194ト知識レベルモデルは，学習ツールの明示的な基本相関関係（学習操作）と，学習プリミティブの制御（バイアス）と，学習プリミティブの異なるいくつかの実装法を生成することができる．提案されたモデルはKADSlShreiber92］の推論構造形式に基づいており，利用者とのインタラクションの時にインタフェースとして利用される．この学習操作の明示的な表現と関連するバイアスは，知識ベースアプリケーションを開発する知識エンジニアが最適な学習ツールを見つけるために様々な学習ツールを構成する作業を容易にすることが可能である．この環境の目的は，利用者の要求にあった機械学習アルゴリズムをサポートできる機械学習ツールを提供し，利用者がそのツールをグラフィカルに構成することができることである．その利点は以下の通りである．. 適応性目的，環境や事例の複雑さ，利用できるドメインセオリーのタイプに依存して，利用者が問題の適性にあった学習関数の集合を集めることができ，制御パラメータの定義を具象化することができる．これにより，様々な学習アルゴリズムの構築を容易にする．.

(35) 30. 第2章関連研究. 単一性・同一性与えられた学習システムの構成は，あらかじめ定義された学習集合を集め，選ばれた要素に関連するバイアスをインスタンシエーション（具象化）することによって生成される・学習アルゴリズムを構成するまでの各々のステップにおける表現はCommonKADSにより統一されているため，直観的な方法で与えられた構成をグラフィカルに仕様化することを可能にする．. 知識レベルモデリングの支援の手順は次に示す通りである．まず，利用者が目的，事例集合，利用可能なドメインセオリーなどを支援環境に入力する．支援環境は，あらかじめ定義された学習関数の適性に関する知識を利用して，問題の適性にあった学習関数を選択し利用者に提示する（ただし，【Rouveiro194】では・ここまでのプロセスは具体的に述べられていない）・学習関数は，以下に示す5つのエンティティから構成される．学習操作学習アルゴリズムによって具現化された換作・これらの操作は，コードの一部に対応するプリミティブかも知れないし，あるいは抽象操作に分解されるかもしれない抽象換作に対応するかもしれない．学習操作の可能な分解ある抽象操作を実装するための異なる方法．学習操作間のデータフローある分解の中での換作間の連結を表現．制御パラメータ（バイアス）これらのパラメータは学習操作の振舞いを制御する．. 分解を制御している制約これらのエンティティは与えられた分解に付与された条件を表現する．利用者は・選択された学習関数の制御パラメータ（バイアス）を具象化する．このプロセスは・グラフィカルインタフェースを通して行われる．バイアスに関しては，バイアスオントロジーが提供されている（図2．21）．利用者は，問題に適するように，オントロジー中の概念の選択を行う・最後に，支援環境は上記のエンティティの制約に基づき，選択された学習関数からいくつかの異なる学習アルゴリズムを構成し，適切な学習アルゴリズムを利用者に提示する．.

(36) 2．3．データマイニング構築支援. 31. Pahialder orTC Vocabularyor. hnguage. hy匹theSi8. bias. SynbはOr hypothesiS／ COnCept. 霊慧∠二二：：ニご Exhau5tive G一＆．T. barmng bi88eS. Searc bias. くBeamさearCh Dichotomy. Hillclimbing. ci血tion∠慧：ニ芸慧. く：. neralization. Yalidity CdtedombrTC. Ab80rption Literal dropplng. Yaliditycritehon hrhypothesi80r HS. 慧datioく慧≡f te5tingexampleS. 図2．21：バイアスオントロジー. このように，知識レベルモデリングでは，妥当と思われるバイアスオントロジーの概念を利用者が選択することで，目標を達成する学習アルゴリズムを半自動的に構築することができる．しかしながら，タスク指向ユーザガイダンス同様，機械学習の専門知識をもたない利用者の場合，バイアスの選択は困難なタスクとなるので，大きな効果が期待できないと思われる．. 2．3．3. MIC＋＋. RonnyKohaviにより提案されたMLC＋＋は，プログラム言語C＋＋で構築された機械学習ライブラリであり，グラフィカルインタフェースを利用した次の2つの機能が備わっている．（1）数十種類の既存の学習システムを選択するだけにより実行することができる．（2）新たな学習システムをMLC＋＋ライブラリに追加できる．MLC＋＋を利用することで，利用者は学習システムをインプリメントするという煩わしさから解放され，与えられた問題に対して適切と思われる既存の学習システムを選択するだけで，目的の学習システムを獲得することが可能となる．このように，MLC＋十は前節までに述べた2つの支援環境とは異なり，学習アルゴリズム選択問題に関する支援は全く行っていない．専門知識をもたな.

(37) 32. 第2章関連研究. い利用者を支援対象とした場合，そのような利用者はガイドもなく妥当な学習システムの選択や学習パラメータの決定をすることは非常に困難であることから，大きな効果は期待できないと思われる．. 2．4 結言本章では，2・2節で，代表的な帰納学習／データマイニングシステムについて述べた・ここで述べた以外にも非常に多くの帰納学習／データマイニングシステムが存在し，現在も増加の傾向にある・ところが，所与のデータに対して，常に最良のパフォーマンスを提供する学習アルゴリズムが存在しないことから，利用者が所与のデータに適する学習アルゴリズムを選択するという問題が生じる・このような問題を解決するために，学習アルゴリズム構築支援環境が必要になってきおり，2・3節で述べた学習システムの専門家をターゲットとした学習アルゴリズム構築支援環境が研究されている・しかし，データから知識を発見することを望んでいる利用者は，その多くが専門知識を持たない利用者である・したがって，そのような利用者を想定した場合，現状における支援環境では不十分であると考えられる・したがって，専門知識を持たないユーザを対象とした帰納アプリケーション構築支援環境の構築が必要であると思われる．.

(38) 第3章オントロジーに基づく帰納アプリケーション構築支援環境. 3．1 緒言機械学習（ML）と知識発見（DM）技術が，急速に成長しつつあり，既に多くの知識発見ツールを利用することができる．しかし，機械学習の専門知識をもたない利用者（ノービスユーザ）がそのようなツールを利用するには，まだまだ負担が大きい・これは，MUDMシステムの数の急激な増加に伴い， ML／DM技術を必要とする利用者（ユーザ）が「ML／DMアルゴリズムの選択」と「データ前処理」という2つの問題に直面しているからである．すなわち，（a）与えられたアプリケーションで利用する最も適切なアルゴリズムを選択し，（b）このアルゴリズムに対してどのように効果的なデータの前処理を実施するかという2つの問題である．伝統的に，ノービスユーザがこの間題を解決するために，試行錯誤的手法を利用するか，コンサルタントへの依頼という手段を利用する．しかしながら，前者の方法は，多くのコストがかかり，かつ信頼性がなく，後者の方法は，専門家のもつノウハウ（マイニングアルゴリズム選択表など）に依存しすぎることが課題であり，どちらの方法もMUDM技術の適用支援環境が必要になってきている．以上の背景から，近年，MLのコミュニティではMLアプリケーションを開発するための方法論の整備やその開発プロセスを自動化するメタ学習プロセス 33.

(39) 34. 第3章オントロジーに基づく帰納アプリケーション構築支援環境. に関心が寄せられている（ECML98，AAAI98＆ICML98）．本来，（a）（b）のどちらの問題に対しても支援できることが望ましいが，まず（a）のアルゴリズムの選択問題だけを支援する環境についてアプローチすることにする．本章では，データマイニングに貢献する技術の中で最も大きな割合を占める帰納学習システムを分析して，帰納学習システムを構成する帰納学習法を抽出・体系化することにより，帰納学習アプリケーションを自動合成するメタ学習システムについて検討する・本章で述べる帰納学習法を合成する方法論は，単に与えられた問題に対して有効な帰納アプリケーション選択するだけではなく，その組み合わせによっては新たな帰納アプリケーションを構築する可能性もあり，その点からも興味深いと思われる．以下，3・2節で，帰納学習アルゴリズムを構成する部品（帰納メソッド，あるいは学習プロセスと呼ぶ）体系「プロセスオントロジー」と帰納メソッドで扱われる様々な情報体系「オブジェクトオントロジー」の構築法について述べた後，3・3節で，2つのオントロジーを利用した帰納アプリケーション構築支援環境CAMLETの基本設計について述べる．最後に，3．4節では，CAMLET の構築支援結果および評価・考察を述べる．. 3・2 帰納学習におけるオントロジーの構築近年，知識システムは知識モデリング技術に基づき，部品合成により開発されることが多くなってきている【vHeかt95】．特に，再利用可能な知識要素を活用するために，多くの研究では高い抽象度で問題解決法（PSM）を活用する立場をとっている（GenericTaskslBylander87］，PROTEGE−IIlMusen92】，. Common−KADSlBreuker94】）．PSMは実装の詳細とは独立した問題解決プロセスの仕様である・現在，その研究はPSMとともにオントロジー工学に移行しつつある・オントロジーとは概念化の明示的な仕様【Gruber921であり，［vHeOst95】にしたがえば，多数のドメインにおいて利用できる一般的な概念に関する汎用オントロジー，ドメイン知識の構造と内容の制約を与えるドメインオントロジーなどに分類される．オントロジーの構築に重要なことは，タスクを円滑に行うための概念の切り出しと階層化である．本節では，本研究におけるタスクである「帰納アプリケー.

鐸 周 大 字 望 一 日

鐸周大字望一日