人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

例えば入力として abbccab という順序ありの系列を受け取ったら、
画像のような木を出力する
それを、機械学習的な方法で学習する学習器にはどんなものがありますか?



・a b c などは大小が無い離散値で、これら入力記号の値域は決まっています。
・系列の長さは一定ではありません。

1441082888
●拡大する

●質問者: tak
●カテゴリ:コンピュータ 科学・統計資料
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● opechuman
●50ポイント ベストアンサー

https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90

入力が記号列で出力がツリー型のグラフとなる解析で自分がぱっと思いつくのは言語処理の構文解析器で、教師あり学習が一般的ですが工夫次第では教師なし学習も考えられます。例として次のようなモデルが考えられます。統計学の知識があるなら、従属変数が2値変数のベクトルである回帰モデルを雑なイメージとして想像してもらえればいいと思います。Exyは記号xとyの組み合わせ分存在しうるわけですが、ツリー型という制約があるため全ての組み合わせの連結を評価する必要はない点に注意が必要です。

Exy: 記号xy間の連結の有無
Nxy: 2つの記号の属性や記号間の相対的位置関係
Exy = f(Nxy) + ε
x, y ∈ {a1, b2, b3,...} ※添え字の数字は記号列での順序

このとき、素性N、識別対象Eともに高次元となりがちのため、高次元でも汎化性能の高い手法が望ましいといえます。
近年、研究が日進月歩で進んでおり様々な手法が提案されてますが、それを全てレビューするのは大変だと思います。まずは実績のある手法としてサポートベクターマシンを試すのがいいのではないでしょうか。

また教師なし学習については他の方の回答に期待したいところですが、私の思いつく限りでは、何かしらの仮定を置いてクラスタリングの問題に帰着させることになるだろうと思います。


2 ● dethanc
●50ポイント

木が順序木であるという前提(※1)であればこんな方法もあるかなと。

・abbccabをa→b→b→c→c→a→bとする(この作業実は意味なしですが)
・できあがっている木を根から左側順にたどって
R→N→a→B→b→B→B→N→N→b→B→N→c→B→c→B→B→B→N→a→B→b→B→B→B
と表現。
(Rが根,Nが節,Bが親ノードへ戻る事を意味する)

左側から系列側を2組のペアに分割(※2)
a→b
b→b
b→c
c→c
c→a
a→b

(※2 精度をあげるために3組以上にすることも可能)

系列と木をそれぞれ左からたどって

a→b,a→B→b
b→b,b→B→B→N→N→b
b→c,b→B→N→c
c→c,c→B→c
c→a,c→B→B→B→N→a
a→b,a→B→b
というトランザクションを抽出。

・これらのトランザクションをほかの事例からも集めて、アソシエーションルールを抽出する。
アソシエーションルールについてはこちらを参照
http://bdm.change-jp.com/?p=1341


大抵の問題はただ手法を使うだけでは効果は薄く、※1のような仮定や問題に特化した工夫をする必要があります。


takさんのコメント
アソシエーションルールでは、矛盾するトランザクションが得られたらどうしますか

dethancさんのコメント
アソシエーションルール自体は支持度と確信度がそれぞれのルールごとに得られますので、矛盾したものがあっても割合で評価できるようになってます。AならばBである確率が60%だ、とか。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ