対話型遺伝的アルゴリズムにおける ユーザ負担軽減と多様性維持の検討

Presentation on theme: "対話型遺伝的アルゴリズムにおける ユーザ負担軽減と多様性維持の検討"— Presentation transcript:

1 対話型遺伝的アルゴリズムにおける ユーザ負担軽減と多様性維持の検討
工学研究科 知識工学専攻 知的システムデザイン研究室 2006年度 745番 山川 望

2 研究背景 多くの人がインターネットショッピングを利用 商品提供者は数多くの商品を販売 ユーザは自由に商品を検索，購入

3 研究背景 多くの人がインターネットショッピングを利用 商品提供者は数多くの商品を販売 ユーザは自由に商品を検索，購入
ショッピングサイトにおける商品の提示方法 商品提供者 → 提示できる商品の数の制限 たくさんの商品を販売することができるが， ユーザに対してすべての商品を提示することは困難 ユーザ → 比較操作による疲労 ページ遷移を繰り返すことにより，商品を比較， 購入するかを検討する

4 商品のリコメンデーション 検索・購入履歴や商品の関連性を用いて商品を提示

5 商品のリコメンデーション 検索・購入履歴や商品の関連性を用いて商品を提示 ユーザ：検索することなく関連商品を発見
　　ユーザ：検索することなく関連商品を発見 商品提供者：ユーザが購入しそうな商品を効率的に提示

6 商品のリコメンデーション方法の問題点 商品選択時のユーザの嗜好を商品提示に反映できていない 主にユーザの検索・購入履歴を用いて商品を提示
商品選択時のユーザの選択操作により，ユーザの嗜好を 学習するしくみを利用していない

7 研究目的 商品選択時のユーザの嗜好を商品提示に反映できていない ユーザの選択操作から商品選択時のユーザの嗜好を学習し，
ユーザの嗜好に合った商品提示を行うシステムの構築 選択を繰り返す ユーザの嗜好を 反映した提示 判断・学習

8 対話型遺伝的アルゴリズム(iGA) 遺伝的アルゴリズム(GA)の評価部分を 人間の主観的評価によって行う
人間の好みや印象といった 数式化できないものの解析に利用 様々な分野へ適用されている CGグラフィックス 音楽 服飾デザイン 補聴器フィッティング

9 iGAを用いる際に検討すべきこと ユーザ負担の軽減 入力インタフェースの改善 収束の高速化 評価値予測

10 iGAを用いる際に検討すべきこと ユーザ負担の軽減 入力インタフェースの改善 収束の高速化 評価値予測
提示個体1つ1つに点数付けを行うのではなく， 嗜好に合った個体を選ぶ

11 iGAを用いる際に検討すべきこと ユーザ負担の軽減 入力インタフェースの改善 収束の高速化 評価値予測
提示個体1つ1つに点数付けを行うのではなく， 嗜好に合った個体を選ぶ 多様性の維持

12 iGAを用いる際に検討すべきこと ユーザ負担の軽減 入力インタフェースの改善 収束の高速化 評価値予測
提示個体1つ1つに点数付けを行うのではなく， 嗜好に合った個体を選ぶ 多様性の維持 iGAは単一目的のための最適化手法であるため， 探索終盤では収束する可能性がある

13 iGAを用いた補聴器フィッティング ユーザが最も聴こえやすいと感じる 補聴器パラメータを求めることが目的

14 提示個体を少しずつ最適解に近づいていくため
iGAを用いた補聴器フィッティング ユーザが最も聴こえやすいと感じる 補聴器パラメータを求めることが目的 提示個体を少しずつ最適解に近づいていくため 類似した個体や同じ個体が提示される

15 多様性維持の必要性 商品を探す際に同じ商品を複数提示しても ユーザには不要な情報となる
ユーザの嗜好が複数ある場合には 複数の嗜好に対応した提示を行う必要がある

16 商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合

17 商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合 iGAは1つの解を求めることが目的

18 商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合 ユーザの嗜好が複数の場合 iGAは1つの解を求めることが目的

19 赤色，あるいは青色どちらかのTシャツに収束し，
商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合 ユーザの嗜好が複数の場合 iGAは1つの解を求めることが目的 赤色，あるいは青色どちらかのTシャツに収束し， 同じTシャツを複数提示する可能性がある

20 商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合 ユーザの嗜好が複数の場合 iGAは1つの解を求めることが目的
ユーザの嗜好の多峰性に対応した個体を 生成し，提示する必要がある

21 構築したシステムの概要 Tシャツを対象とした商品選択支援システム 設計変数 色：HSB表色系 形：袖の長さ，襟の形 模様：種類，色

22 HSB表色系 色相(Hue) 色合いを細分化した色相環 彩度(Saturation) 色の鮮やかさの度合い
明度(Brightness) 色の明暗の度合い 人間の色彩感覚に似た色の表現

23 袖の長さと襟の形 袖の長さ 襟の形

24 模様 色：白，黄緑，水色，青，紫，ピンク，赤，黄，黒

25 ユーザによる評価 提示されたTシャツからユーザは好きなTシャツを 10枚以下の任意の数選ぶ

26 システムによる評価・選択 提示した個体の中からユーザが選択した 個体と類似した個体を親個体として選択する 親個体

27 交叉 親個体2個体から形質を引き継いだ子個体2個体を生成 親個体 子個体 親個体 子個体

28 交叉 親個体2個体から形質を引き継いだ子個体2個体を生成 親個体 子個体 親個体 子個体

29 突然変異 突然変異率に基づき，設計変数値をランダムに変化 突然変異前 突然変異後

30 ショッピングサイトにおける商品提示 iGAを用いた場合 ユーザの嗜好に合うものは提示できるが収束する 初期個体 6世代目

31 ショッピングサイトにおける商品提示 iGAを用いた場合 ユーザの嗜好に合うものは提示できるが収束する ランダムに個体を生成し，提示する
初期個体 6世代目 ランダムに個体を生成し，提示する 突然変異率を高くする

32 ショッピングサイトにおける商品提示 iGAを用いた場合 ユーザの嗜好に合うものは提示できるが収束する ランダムに個体を生成し，提示する
初期個体 6世代目 ランダムに個体を生成し，提示する 突然変異率を高くする 多様性は維持できるが嗜好に合った提示は困難

33 ショッピングサイトにおける商品提示 iGAを用いた場合 ユーザの嗜好に合うものは提示できるが収束する ユーザの嗜好を考慮した
初期個体 6世代目 ユーザの嗜好を考慮した 提示個体の多様性維持の方法が必要

34 商品選択時のユーザの嗜好 ユーザの嗜好が1つの場合 ユーザの嗜好が複数の場合 iGAは1つの解を求めることが目的
ユーザの嗜好の多峰性に対応した個体を 生成し，提示する必要がある

35 人の嗜好の多峰性に対応した個体生成(1/2)
ユーザの選択した個体の色相と襟の形の分布に着目

36 人の嗜好の多峰性に対応した個体生成(1/2)
ユーザの選択した個体の色相と襟の形の分布に着目 個体生成範囲 ユーザが選択した個体の分布範囲で個体を生成

37 人の嗜好の多峰性に対応した個体生成(2/2)
ユーザの選択した個体の分布が複数に分かれる場合

38 人の嗜好の多峰性に対応した個体生成(2/2)
ユーザの選択した個体の分布範囲から個体を生成 個体生成範囲

39 人の嗜好の多峰性に対応した個体生成(2/2)
ユーザの選択した個体の分布範囲から個体を生成 個体生成範囲 ユーザの嗜好に合っていない範囲

40 人の嗜好の多峰性に対応した個体生成(2/2)
ユーザの選択した個体の分布範囲から個体を生成 個体生成範囲 ユーザの嗜好に合っていない範囲

41 人の嗜好の多峰性に対応した個体生成(2/2)
ユーザの選択した個体をグループ化する 個体生成範囲 適切にグループ化する必要がある

42 クラスタリング データマイニングの手法の1つ 類似したデータをグループ化し， データ中の価値ある情報を抽出する方法
K-means法 クラスタ数の決定に多目的クラスタリング(MOCK)の 最適クラスタ数自動決定アルゴリズムを利用

43 クラスタリングを用いた個体生成方法(1/2)
ユーザの選択した個体をクラスタリングによりグループ化

44 クラスタリングを用いた個体生成方法(1/2)
生成されたクラスタの範囲からランダムに個体を生成 ランダムに個体を生成

45 評価実験 目的 クラスタリングを用いた個体生成を行うことにより 人の嗜好の多峰性に対応した個体を提示できているかを 検証する 被験者
20歳代の男女20名 教示 ショッピングサイトで好きなTシャツを探す 実験に用いるシステム クラスタリングを行うシステム(提案システム) クラスタリングを行わないシステム(従来システム) 20世代の評価を行い，アンケートを実施

46 実験に用いたシステム 提案システム ユーザは提示された20枚のTシャツから 嗜好に合ったTシャツを10以下の任意の数選択する
10世代目にクラスタリングを行い， 個体を生成し，提示する 従来システム ユーザが行う操作は 提案システムと同様 クラスタリングは行わず， 遺伝的操作のみを行う

47 検討項目 アンケートによる検討 多様性 嗜好性 データによる検討 人の嗜好の多峰性に対応した個体生成

48 いろいろなTシャツが提示されていると感じたか
多様性に関するアンケート結果 どちらのシステムを利用したときの方が いろいろなTシャツが提示されていると感じたか

49 多様性に関するアンケート結果 どちらのシステムを利用したときの方が いろいろなTシャツが提示されていると感じたか
クラスタリングを用いて個体を生成することにより， 多様性を維持した個体を提示できている

50 嗜好性に関するアンケート結果 どちらのシステムを利用したときの方が 好きなTシャツが提示されたか

51 嗜好性に関するアンケート結果 どちらのシステムを利用したときの方が 好きなTシャツが提示されたか
iGAの嗜好を提示に反映するメカニズムに悪影響を与えず， 嗜好に合った個体を生成し，提示できている

52 多様性に関する考察 提案システムの方が多様性を維持した個体を提示したと 回答した被験者のクラスタリング後の提示個体の分布

53 多様性に関する考察 提案システムの方が多様性を維持した個体を提示したと 回答した被験者のクラスタリング後の提示個体 従来システム

54 多様性に関する考察 提案システムの方が多様性を維持した個体を提示したと 回答した被験者のクラスタリング後の提示個体
従来システム 提案システム 多様性を維持し，ユーザの嗜好に合った個体を 提示することができている

55 人の嗜好の多峰性に関する考察 クラスタリング結果が複数に分かれていたユーザの 個体生成範囲とクラスタリング後の提示個体

56 人の嗜好の多峰性に関する考察 クラスタリング結果が複数に分かれていたユーザの 個体生成範囲とクラスタリング後の提示個体

57 人の嗜好の多峰性に関する考察 クラスタリング結果が複数に分かれていたユーザの 個体生成範囲とクラスタリング後の提示個体
ユーザの嗜好の多峰性に対応した 個体を生成し，提示できている

58 まとめ iGAにおいて多様性を維持する方法 → クラスタリングを用いた個体生成
クラスタリングを用いた個体生成が多様性維持に 有効であるかを検証する評価実験 →提示個体の多様性を維持し，人の嗜好の多峰性に　対応した個体を生成し，提示することができた

59 発表論文一覧 山川望，廣安知之，三木光範 「Web上での商品選択のインタフェースの検討 　〜対話型遺伝的アルゴリズムを用いたデザイン支援システムの構築〜」 人工知能学会 第20回人工知能学会全国大会，タワーホール船堀(2006.6) 山川望，廣安知之，三木光範 「対話型遺伝的アルゴリズムを用いたデザイン支援システムの構築」 日本機械学会 第19回計算力学講演会，名古屋大学( ) 山川望，廣安知之，三木光範 「Web上での商品選択のインタフェースの検討」 情報処理学会 インタラクション2007，学術総合センター(2007.3) 山川望，廣安知之，三木光範 「対話型遺伝的アルゴリズムを用いたデザイン支援システムにおける 　ユーザの嗜好情報の抽出と利用」 人工知能学会 第21回人工知能学会全国大会，ワールドコンベンションセンターサミット(2007.6) 山川望，廣安知之，三木光範 「対話型遺伝的アルゴリズムの評価操作におけるユーザの負担軽減の検討」 日本機械学会 第20回計算力学講演会，同志社大学( ) 山川望，廣安知之，三木光範 「対話型遺伝的アルゴリズムにおける多様性維持の検討」 情報処理学会 第67回数理モデル化と問題解決研究会， 産業総合技術研究所( ) 廣安知之，山川望，伊藤冬子，三木光範，佐々木康成 「対話型遺伝的アルゴリズムにおける評価方法と個体生成方法の検討」 情報処理学会 第68回数理モデル化と問題解決研究会， 道後温泉 (2008.3，発表・論文投稿予定)

60

61

62 ユーザの嗜好が複数ある場合 ex.) ユーザが赤色と青色が好きな場合
iGAは単一目的のための最適化手法 → 赤色、あるいは青色どちらかのTシャツに収束し， 　 同じものばかりを提示する可能性がある 人の嗜好は多峰性であるため， 人の嗜好の多峰性に対応した提示が重要

63

64 システムによる評価・選択(1/2) 提示した個体の中からユーザが選択した 個体と類似した個体を親個体として選択する 親個体

65 システムによる評価・選択(2/2) 距離による評価
ユーザが選択した個体と提示されている個体と ユークリッド距離を求め，距離の小さい個体から 親個体として選択する xi：ユーザが選択した個体(i = 0, 1, ・・・，10) yj: 提示されている個体(j = 0, 1, ・・・,20) xh,yh,:色相の値 xs,ys,:彩度の値 xb,yb,:明度の値 xsl,ysl: 袖の長さの値 xc,yc,:襟の形の値 (それぞれの値は正規化した値)

66

67 色相の交叉 色相はHSB表色系において円形で表現されている 距離の小さい方から ランダムに2個体生成

68 彩度，明度の交叉 彩度，明度は0〜100で表現している 親個体の間からランダムに 2個体生成

69 袖の長さと襟の形，模様の交叉 袖の長さ 親個体の袖の長さをそのまま子個体の袖の長さとする 襟の形 色相と同様の交叉方法を用いる
模様，模様の色 親個体の模様，模様の色を そのまま子個体が引き継ぐ

70

71

72 ユーザの選択個体の履歴 類似した形を選択した場合 類似した色を選択した場合 類似した個体を選択しても分布が0と1に 偏ってしまう場合が生じる

73 ユーザの選択個体の履歴 ユーザが評価する際の設計変数の表現と分布をとる際の 表現方法が異なるため
クラスタリングを行うと類似したものであっても 異なるクラスタに分類される

74 データに加える処理 データの最大値と最小値の差が0.5以上の 場合のみ処理を加える
隣り合うデータの差が最大となるとき， 小さい値に差の1/2を加えた値をデータを シフトする基準値とする

75 データに加える処理 データの最大値と最小値の差が0.5以上の 場合のみ処理を加える
隣り合うデータの差が最大となるとき， 小さい値に差の1/2を加えた値をデータを シフトする基準値とする 基準値 差の1/2 差が最大

76 データに加える処理 データの最大値と最小値の差が0.5以上の 場合のみ処理を加える
隣り合うデータの差が最大となるとき， 小さい値に差の1/2を加えた値をデータを シフトする基準値とする 基準値 差の1/2 差が最大

77

78 多目的クラスタリングアルゴリズム MOCK: Multiobjective clustering with automatic k-determination J.Handl, J.Knowlesが2004年に提唱 多くのテストデータおよび実データを用いた実験により 他手法と比較して高いクラスタリング性能が示されている 特徴 多目的最適化の概念を用いる 接続性：Connectivity コンパクト性：Overall Deviation 幅広いクラスタ数を持つ複数の解（解集合）を導出 最適クラスタ数自動決定メカニズムを持つ 他の多くのクラスタリングアルゴリズムは クラスタ数決定機能を持たない

79 ２つの目的関数 Connectivity（最小化） 接続性を評価する目的関数
近傍のデータ同士が異なるクラスタに属する場合ペナルティを与えるペナルティ関数 Overall Deviation（最小化） コンパクト性を評価する目的関数 クラスタ中心と各データの間の距離の総和

80 MOCKで得られる解集合 解集合の特徴 幅広いクラスタ数を持つ解を含む それぞれのクラスタ数では高精度のクラスタ境界が得られている
クラスタ数少 クラスタ数に着目して最終解を決定 → 最適なクラスタ数を決定できる → 最適な分割方法も既に決定している コンパクト性 クラスタ数多 GAP統計を用いて クラスタ数を自動決定 接続性

81 GAP統計ベースのクラスタ数自動決定 GAP統計：クラスタ数を決定するための統計手法
クラスタが存在しないという帰無仮説に基づいたクラスタリング結 果と，実際のクラスタリング結果との差異を計測することにより， 最適クラスタ数を持つクラスタソリューションが存在する場合に両 者の差異が最大となるという予測を用いて最適クラスタ数を決定す る．

82 GAP統計ベースのクラスタ数自動決定の流れ
2nd 1st クラスタリングにより幅広いクラスタ数の解を得る

83 GAP統計ベースのクラスタ数自動決定の流れ
2つのパレートの誤差が最大となる点を最終解として選択 誤差が最大 = 与えられたデータの特性を 最も顕著に示す

84 MOCKの利点 高いクラスタリング性能を持つ
実験によりK-means法や凝集法など 多くのクラスタリングアルゴリズムと比較して 高いクラスタリング性能が示されている 最適クラスタ数自動決定メカニズムを持つ 他の多くのクラスタリングアルゴリズムは 最適クラスタ数の決定機能を持たない (ex. K-means法，群平均法，最短距離法） 適切なクラスタ数・クラスタ境界の双方を一度の探索で発見可能

85

86 提示への反映(1/4) ユーザが評価した個体

87 提示への反映(2/4) ユーザが評価した個体 クラスタリングを行う

88 提示への反映(3/4) ユーザが評価した個体 ランダムに個体生成

89 提示への反映(4/4)従来システム iGAのみを用いた場合 ユーザが評価した個体 クラスタリングを用いた場合

90

91 今後の課題 クラスタリングに関する検討 クラスタリングを行う世代数，回数 クラスタリングの対象とする設計変数
多様性を維持した提示によるユーザ負担への影響 提示個体が収束し，ユーザが選択できる個体が 類似した個体ばかりになるとユーザ負担につながる

92

93 多様性に関する考察(3/3) 従来システムと回答した被験者の結果 提案システムと回答した被験者の結果

94 多様性に関する考察(3/3) 人が見たときの多様性とデータの多様性を考慮した指標 従来システムと回答した被験者の結果
提案システムと回答した被験者の結果 人が見たときの多様性とデータの多様性を考慮した指標