---
# System prepended metadata

title: 人工知能まとめノート

---

# 人工知能まとめノート

## lec 1

### quiz
- 研究分野としてのAIとは
    - 部分的または完全にインテリジェントなシステムを取得するための理論と技術の研究を行う。
- 探索とは？
    - 初期状態からスタートし、現在状態を遷移させながら、目標状態をみつけること(教科書　p15右下参照)
- 学習モデルの例
    - サポートベクターマシーン(support-vector machine, SVM)
    - k近傍法( k-nearest neighbor algorithm, k-NN)
    - GAN(敵対的生成ネットワーク)
- 知識獲得のための３つのMAP
    - 現実世界からマインドモデルへの入力（input）
    - マインドモデルから現実世界への出力(output)
    - inputとoutputの関係(relation)

## lec 2
### resume
ツリー構造(tree)
- ツリーは一連のノードと一連のエッジで構成
    - ノード: 点
    - エッジ: 線
    - ツリーのレベル: ルートノードからカレントノードまでのパスに含まれるエッジの数
    - ツリーの高さ: ルートノードから終点ノードまでのレベル 


ツリートラバーサル(走査)
- ツリーの全てのノードに繰り返すことなく、アクセスするプロセス
    1. pre-order(深さ優先探索): ルートから開始し、(再帰的に)現在のノード→左側のノード→右側のノードの順にアクセスする
    https://yutaka-watanobe.github.io/star-aida/1.0/algorithms/btree_preorder/anim.html
    3. in-order(深さ優先探索): 左側のノード→現在のノード→右側のノード
    https://yutaka-watanobe.github.io/star-aida/1.0/algorithms/btree_inorder/anim.html
    5. post-order(深さ優先探索): ルートから開始→左側のノード→右側のノード→現在のノード
     https://yutaka-watanobe.github.io/star-aida/1.0/algorithms/btree_postorder/anim.html
    5. level-order(幅優先探索): レベル順にトラバースする
    https://yutaka-watanobe.github.io/star-aida/1.0/algorithms/btree_levelorder/anim.html
### quiz
- 迷路問題の初期状態と目標状態
    - 初期状態:(0,0)
    - 目標状態:(2,2)
- グラフを定義するための2つのセットは何か。G = (V,E)
    - Vはノードセット
    - Eはエッジセット
- ~~与えられたグラフに対して正しいかどうか~~→定義書きます
    - 連結グラフ: 任意の２つのノードの間にパスがあるグラフ
    - 無向グラフ： エッジに方向のないグラフ
    - 重み付きグラフ：　辺に重み（コスト）がついているグラフ
    - spanning tree(全域木): 全てのノードにアクセス可&閉路無し
         = 閉路を持たないグラフ
## lec3
### resume
- オープンリスト
    - ノード展開において、得られたこノードを保存しておくリスト
        - まだ訪問していない(次に到達可能な)ノードを含んだリスト
    - 実装例
        - スタックを用いて、オープンリストを実装
            - 深さ優先探索
        - キューを用いて、オープンリストを実装
            - 幅優先探索
- クローズドリスト
    - 到達済みのノードを含んだリスト
- **均一コスト検索(uniform cost search)**
    - 最短経路問題の1つの解法
    - 最初のノードから現在のノードまでの最適なパスを常に見つけることができる
### quiz
- ランダム探索の問題点
    - 必ずしもターゲットノードに到達するとは限らない
- クローズドリストによる検索の問題点
    - ターゲットノードに到達しない可能性がある
- 幅優先探索を行う場合、オープンリストを実装するにはどうすればいいか
    - オープンリストをキューで実装する
- 均一コスト探索と幅優先探索の関係は？
    - 均一コスト探索はオープンリストを優先度付きキューで実装する
    →幅優先探索と似た実装になる

## lec4
### resume
- **最良優先探索(best first search)**
    - 何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択する
    - ゴールへ到達するのに予想されるコスト(ヒューリスティック値 heuristic value)を最小化するように選択する
        - ゴール状態に最も近いと判断した状態へ到達するまでのコストを見積もりする
- **A*アルゴリズム F(x) = C(x) + H(x)**
    - 実際コストと推定コストの両方を利用して、ノードのコストを評価する
- 目的関数(objective function)
    - 状態ｘが最良の状態であるかを確認するためのもの
- 最適化(Optimization)
### quiz
- 均一コスト探索と最良優先探索の主な違い
    - 均一コスト探索で考慮するコストは実際のコストに対して、最良優先探索のコストは実際のコストに加えて、ヒューリスティックによる推定コストも考慮して評価する。
- 均一コスト探索と比較した時、最良優先探索のメリット・デメリット
    - メリット：探索する時間が短い
    - デメリット：使用するコスト（推定コスト）が誤っている可能性があるため、最適な解かどうか保証できない
        - 推定するコストが可能な限り最良な値より、大きい場合、最善の解が得られるとは限らない
- A*アルゴリズムを使用する場合、最適解を保証するために必要な条件は何か
    - 予測コストH(x)が最適値H*(x)より大きくない
    - x が最適解
- 局所最適解と大局最適解の定義
    - 局所的最適解(local optimal solution):ある範囲では最適解だが，実行可能領域全体では最適とは限らない解
    - 大局最適解(global optimal solution):実行可能領域全体で最も良いことが保証された解

## lec5
### resume
- **知識ベース(knowledge base)**: システムを設計する段階で、その時までわかっている知識の集まり
- ワーキングメモリ：　観測事実と推論の中間結果を保存する場所

- 推論エンジン(inference engine): 知識ベースと観測事実をもとに、意味のある結果を導くための手段
    - **前向き推論(forward reasoning)**：観測事実から出発し、知識ベースにあるルールに従って次々と推論結果を出していく過程。
        - **LEX戦略(lexicofraphic sort)**
            - 基本的な考え方
                - 新しい事実を生み出せないルールは削除 
                - 推論によってわかった最新事実を優先的に利用
                - 最も具体的な結論が出せるルールを利用すること
            - 4ヶ条
                1. すでに実行したルールを競合集合から削除する
                2. より新しいデータにマッチするルールを選択する
                3. 条件部の詳細度が大きいルールを選択する
                4. 任意のルールを削除
        - 最良優先探索
    - **後向き推論(backward reasoning)**: 結論を先に予測して観測事実と知識をもとに検証
### quiz
- 生産システムの主要コンポーネント
    - 知識ベース
    - 推論システム(reasoning system)
    - ワーキングメモリ
- 前向き推論：観測事実から出発し、知識ベースにあるルールに従って次々と推論結果を出していく過程。
- 後ろ向き推論：結論を先に予測して、観測事実と知識をもとに検証していく過程
- 競合解決のためのLEX戦略
    - 競合集合から、最も良さそうなルールを１つだけ選び、それを優先的に実行する方法
- AND/OR木「The man made a desk」

## lec6
### resume
- **オントロジー(ontology)**
    - 対象世界をどの様に捉えた（概念化した）かを記述するもの
    - 知識をグラフで表現
- **セマンティックネットワーク**
    - **有向グラフ(directed graph)**
    - 推論
        - グラフマッチング
- **フレーム**
    - セマンティックネットワークの発展
    - クラスに似た概念→メンバやメソッド
    - 推論
        - 一致しないときは継承に基づいて判断（親と一致するか調べる）
    - プロパティ
        - 必要に応じて新しい知識を生成
    - デーモン(またはエージェント)
        - フレームに使用されている手続き(関数、メソッド)。
        - 一定の条件が満たされると自動的に実行される。

### quiz
- セマンティックネットワークにおける「ノード」と「エッジ」の意味
    - ノード: 概念(コンセプト)
    - エッジ: ノード間の関係性
- コンセプトの定義
    - **コンセプト名**
    - **属性(Attributes)**
    - **属性値**
- セマンティックネットワークとフレームシステムの主な違い
    - フレームシステムはデーモン(エージェントor関数orメソッド)を利用して、新しい知識(手続き型の知識)を生成することができるが、セマンティックネットワークは宣言的知識(既存の知識の推論)しか表現することができない。
        - フレームシステムはセマンティックネットワーク同様、宣言的知識も表現することができる
- フレームにおける「demon」
    - 特定の条件を満たした時に自動的に発揮される機能。「agent」とも呼ばれる。
        - demonはフレーム特有の機能。セマンティックには存在しません


## lec7
### resume
- 命題論理
    - **基本命題(primitive propositions)**
        - 分解できない
    - **複合命題(compound propositions)**
        - 分解できる
    - **素式(atomic formulas)**
        - 基本命題を表す記号,PとかQとか
    - **論理式(logic formulas)**
        - 複合命題に対応する
- 記号
![](https://i.imgur.com/pOnIBXz.png)

![](https://i.imgur.com/Db7BpLc.png)
Implication: 含意
Equivalence: 等価
Commutative laws: 交換法則
Associative laws: 結合則
Distributive laws:　分配法則

- 解釈(interpretation)
    - 審議を判断する

- 論理式の種類
    - **トートロジー(恒真式: tautology)**
        - 真偽に関係なく常に真
    - **恒偽式(Contradiction)**
        - 真偽に関係なく常に偽
    - **充足可能(Satisfiable)**
        - 論理式を常に真する素式の値セットが存在する

- **literal(リテラル)**
    - 素式とその否定
- **clause(節)**
    - リテラルの論理和
- **節形式(clausal form) or 連言標準形(conjunctive canonical (normal) form)**
    - 節の集まった論理式
    - 論理式は節形式に変換できる

- 推論
    - **演繹的推論(deductive reasoning)**
        - すでに存在する知識から推論
    - **帰納的推論(inductive reasoning)**
        - 結論についての推論
- **Logical consequence(論理的帰結)**
    - 全部真なら真(含意)
- **Formal proof (形式的証明)**
    - 公理(常に真な条件、前提条件)と推論規則に基づいて「定理」と呼ばれる有効な式を導く

### quiz
- 基本命題(primitive propositions)： 最も基本的な命題、分解不可能な命題
- 素式(atomic formulas): 原始式を記号で表現
- 二重否定: ¬(¬P)=P
- 分配法則: P∧(Q∨R)=(P∧Q)∨(P∧R) ・ P∨(Q∧R)=(P∨Q)∧(P∨R)
- リテラル: 原子式とその否定
- いくつかのリテラルの論理和: 節(clause)
- 任意の論理式: 節形式(clausal form)
- 形式的証明を行うのに必要なもの
    - Set of Axioms（公理系のセット）
    - Reasoning rules（推論規則）
- 証明可能なB: ⊢B


## lec8
### resume
- **述語論理(Predicate logic)**
    - 命題を主語、述語などに細かく細分化
    - 様々な事象を論理式の形で記述可
- **一階述語論理(1st order predicate logic)**
    - 人が猫を飼っている→xがyを飼っている。
- **Individual constant (個体定数)**
    - 命題論理と同じような使い方
    - a,b,c Taro,Hanako
- **Individual variable(個体変数)**
    - まだ修正されていないものを表す使い方
    - x,y,z Aさん,Bさん
- **Functional symbol (関数記号)**
    - 個体間の関係を表すもの。
    - `f`,`g`,`h`などの英文字で表され、入力・出力どちらも個体。
        - `y=f(x)`という式において`f`が父親の名前を求める関数の場合、`ｙ`は親の名前、`ｘ`が子供の名前になる
        - mother(x): xの母を見つける(1つの個体を返す)
        - brother(x): xの兄弟を見つける(個体の集合を返す)
- **Predicate symbol (述語記号)**
    - 個体の性質または個体間の関係を表す
    - 入力は個体、出力は真偽
        - Human(x): xが人間なら真
        - Mother(x,y): yがxの母なら真

- **Quantifier (限量記号)**
    - 個体変数の範囲を示す
        - **∀(全称記号: universal quantifier)** → ALL
            - ∀xH(x) ⇒ C(x)
        - **∃(存在記号: existential quantifier)** → EXISTENCE
- 述語論理の論理式を定義する。
    - 項を定義する。　→ 論理式の定義
- term (項)
    - 個体定数、個体変数は項である。
    - `t1,t2,...,tn`が項であり、`f`がn変数の関数である時、`f(t1,t2,...,tn)`は項である
- **atomic formulas(素式)**
    - 述語論理式の最小単位（命題論理式と同じ）
    - 項によって定義され、真偽どちらかの値をとる
        - 項が $t_1,t_2……,t_n$ の時の $P(t_1,t_2……,t_n)$ が素式
- **logical formulas(論理式)**
    - 素式は論理式の一つである。
    - P,Qが論理式である時、¬P,P∧Q,P∨Q,P=>Q,P<=>Qは論理式。
    - Pが論理式でxが個体変数である時、∀xP,∃xPは論理式。
以上の定義によって構成された論理式が整式(wff)である.

- **clausal form(節形式)**
    - **꧁閉式(closed formula)꧂**
        - 全ての変数がquantifierによって束縛される→自由変数がない
    - 自由変数
        - 存在範囲がフリーダム
    - 束縛変数
        - 変数の存在範囲を決定させるもの。
        - ∑,∏,∫,lim,∀,∃など
- 論理式を節形式に変形する。
    - ⇒と⇔をなくす。
    - 素式の前に¬をつける. = 二重否定やド・モルガン、¬∀xP(x) = ∃x(P(x))といった法則によって肯定リテラルの直前に持ってくる。
    - ∀←こいつ一つに対しての変数を一つにする
        - ∀xP(x) ∨ ∀xQ(x) = ∀xP(x) ∨ ∀yQ(y)
    - ∀で括る。 = ∀x∀y[P(x)Q(y)]
    - ∃を消す。:  ∃xP(x) = P(a), ∀x∃yP(x,y) = ∀xP(x,f(x))
        - ここで現れる`a`を**スコーレム定数**という 
        - ここで現れる`f(x)`を**スコーレム関数**という。mock化に近しい。
- **単一子(unifre)**
- **単一化(unification)**
### quiz
- 一時述語論理では、**対象領域の個体**(individuals in the universe of discourse)を変数にできる
- 述語論理での関数の戻り値： {True Faulse}**真偽値を返す**
- 　∀: **全称記号**。変数のスコープを指定する限量記号。
- 論理式の最小単位：**素式**
- **スコーレム定数**を使用し、存在記号を消し去る
- 統一後、**複数のホーン節**から解決節を導き出すことができる。
- ホーン節は**単一化可能な**正のリテラルを持つ節。
- prologは**Programing in logic**の略


## lec9
### resume
X:university of discourse(全体集合).

$A=\{x|μ(x)=T∧x in X\}$
- メンバーシップ関数: μ(x)
    - μ(x)が真ならAに属す、偽ならAに属さない
- ファジー集合の演算方法について
![](https://i.imgur.com/ynvyPAy.png)

- **反駁証明(prove by refutation)**: 与えられた論理式を否定するために、論理式の否定を仮定し、矛盾を導く


### quiz
![](https://i.imgur.com/jbP0808.png)


## lec10
### resume
- Conncept learning(概念学習)
    - **宣言的知識(declarative knowledge)**: 概念と概念の関係によって表現できる知識
        - セマンティックネットワークのようなグラフィックモデル
    - **手続的知識(procedural knowledge)**: あるグループ概念から別のグループ概念への**変換**
        - 「建築材料」から「家」への変換
    - 概念(concept)とは
        - 全体集合の部分集合
            - 全体集合: 人間
            - 部分集合: 学生とか
        - $A = {x|μA(x) = True ∧ x ∈　X} = {X|μA(x)}$
            - X が全体集合
            - μA(x)は概念のメンバーシップ関数[0,1]
        - 一つの論理式は一つの概念に対応する。
        - 別名: クラス、カテゴリ、グループ、クラスター
- **パターン分類(pattern classfication)**： 特定の集合をさまざまな意味のある概念に分割するプロセス
- **パターン認識(pattern recognition)**: 観察されたデータがどの概念に属しているかを判断するプロセス

- コンピューターでオブジェクトを分類する
    - オブジェクトをベクトルに変換する
        - **x** = (x1,x2,...,xn)^t (n次元ベクトル)
            - x1,x2...,xn: 特徴
            - **x**: 特徴ベクトル 
            - **x**の集合: 特徴空間
- 特徴量エンジニアリング
    - 機械学習モデルの性能を高めるために、既存の特徴量から、新しい特徴量を作成すること
        - 特徴量 = 属性　＋　属性値
- 概念を学習することは、概念のメンバーシップ関数を決定するプロセス
    - 任意の学習パターンにおいて、ユークリッド距離を使用してその近傍を定義
    - $d(x,q) = ||x-q|| = √Σ[j=1,n](xj-qj)^2$
        - ユークリッド距離(２点間の距離)
        - **距離が小さいほどqはxに似ている**
    - 学習が2クラス問題の場合→検出するパターン
        - ラベルが{-1,1}, {false,true}
    - **NNC(nearest neighbor classifier)**
        - 2つ以上の目的クラスを区別しながら、以前に見たことのないクエリーオブジェクトにラベルを付けることを目的とした機械学習手法
        - **教師あり学習**:学習データにトレーニングデータや教師データなどと呼ばれる正解を与えた状態で学習させる手法
        - 　分類方法(最近傍法)
            1. 画像に命題を満たすラベルを貼る。(-1,1とかで)←訓練データ
            正パターン、負パターンに分ける。
            2. 画像らを訓練集合Ωにまとめる。
            3. Ω(=p)をプロトタイプ集合として任意の新しい画像xに対して下記の式に従って認識する。
- 学習セット: 学習に使用されるデータセット
    - 各データ→学習データ or 学習パターン
    - 各学習パターンにはラベルがある
        - ラベル: 教師信号 or グランドトゥルース（正解）
        - ラベルを定義するプロセスをラベルづけ(labelling, annotation)
- プロトタイプとは、クラスを代表する特徴
    ![](https://i.imgur.com/cDI5PBZ.png)
    *argmin: 最小値を与える値の集合
### quiz
- パターン分類の目的: **特定の集合をさまざまな意味のあるクラスターに分割すること**
- パターン認識の目的: **観察されたデータがどのクラスターに属しているかを判別するプロセス**
- 2クラス問題について、2クラスは**正(ポジティブ)** と**負(ネガティブ)** に分けられる
- NNCでは与えられたパターンxの**ラベル**を求めることで認識を行う
- **代表点**(representatives): NNCの推論コストを削減するために利用できる
- **教師あり学習(Supervised learning)**: 目的のクラスラベルが書くトレーニングデータで利用できる学習
    - 教師なし学習(Un-supervised learning): ラベルが使えない
    →ラベル関係なしで分類(クラスター分類など)
- **パラメトリック学習(parametric learning)**: 学習者または学習モデルが一連のパラメータによって決定される学習

## lec11
### resume
- **distance-based supervised learning(遠隔監視学習)**
    - **最近傍分類器(NNC)** のニューラルネットワークを実装した学習
        - ニューラルネットワーク: 入力を線形変換する処理単位がネットワーク状に結合した数理モデル
    - 学習ベクトル量子化(LVQ:Lerning Vector Quantization)
    ![](https://i.imgur.com/vtjEwgC.png)
        * α∈(0,1)は学習率
        * initialize: 初期化
        * 勝者のプロトタイプのみ変更
- **KNN(Kohonen neural network)**: 教師あり学習の一手法であり，クラス未知のサンプルのクラスラベルを近傍サンプルk個による多数決で決めようというシンプルな手法
    - NNCの拡張
    - 抽象化されたパターン(例:笑顔)の代表点を学習によって取得できる
    - **勝者独占学習(Winner-take-all Learning)**: 勝者を入力パターンに移動し、同様のパターンが提供された場合により高い確率で再び勝つようにする学習
        - WTA戦略=自己組織アルゴリズム
        - 教師なし学習
- R4-rule(R4規則)
![](https://i.imgur.com/R5eaujm.png)
1. **Recognition（認識）**: 観測データを用いて現在システムの性能と書くプロトタイプの重要度をテストする。
    1. 勝者の決定: プロトタイプpが観測データと同じラベルを持つ。または違うクラスラベルを持つどのプロトタイプよりも観測データに近い場合、プロトタイプpは高い重要度を持つ
    2. 重要度の更新: 勝者であるpの重要度を少し上げる。
2. **Remenbarance（記憶）**: 認識できないパターン(新しいパターンや難しいパターンなど)の一部を記録する
    - 通常、一度に認識できないパターンの１つだけを記録する
4. **Reduction（忘却）**: 不要なニューロンを削除する
    - 適応度の低いニューロンの１つを選択して削除する
    - システムの小型化を図る
5. **Review(復習)**： LVQを利用して、現在のシステムを更新する
    - レビューの実装で、任意のLVQアルゴリズムを利用
    - システムの小型化を図る 
- アルゴリズムの評価
    - テストデータ: 学習アルゴリズムのパフォーマンスを評価するためのデータセット
        - テストデータに対するモデルのパフォーマンスは、モデルの"いっぱんk能力を確認するために使用する"
### quiz
- KNN: kohonen neural network
- WTA: Winner-Take-All
- LVQ: Learning Vector Quantization
- R4ルール
    - 認識(recognition)
    - 記憶(Remenbrance)
    - 忘却(Reduction)
    - 復習(Review)
- **WTAアルゴリズム**:勝者を入力パターンに移動し、同様のパターンが提供された場合により高い確率で再び勝つようにするアルゴリズム
- KNNがNNCよりスマートな理由 → NCCは全ての情報を覚えたうえで１つの最近傍の情報だけを用いるが、KNNはｋ個の近傍の情報だけを用いることで覚えるデータ量が少なくなるため。

### アルゴリズムアサインメント
![](https://i.imgur.com/rPMAo09.png)
![](https://i.imgur.com/6qze24s.png)
<x1,p1>: x１とp１の内積って意味
内積を取る理由: x1もp1も正規化されているのでノルムは1.
$cos =  <x1,p1>/||x1||^2||p1||^2 = <x1,p1>;$

## lec12
### resume
- McCulloch
- Pitts Model
- ![](https://i.imgur.com/vvKVPCU.png)
    - w: 重み・・・入力の重要度
    - θ: バイアス・・・1出現度の調整
- ![](https://i.imgur.com/0IAg3PU.png)
    - 単極シグモイド関数 双極シグモイド関数
- ニューロン学習規則
    - ![](https://i.imgur.com/tYyWk8R.png)

- パーセプトロン学習規則
    - ![](https://i.imgur.com/1NS0nJC.png)
        - c: 学習定数
        - d: 教師信号の値
        - y: 実際の値
        - x: テストデータ
    - 参考 https://qiita.com/FukuharaYohei/items/410655034fdef5204879
- デルタ学習
    - ![](https://i.imgur.com/pxwWpmf.png)
    - 誤差逆伝播法
- **多層パーセプトロン(Multilayer perceptron)**
    - 出力層(output)
        - 各出力ニューロンの重みはデルタ学習規則を仕様して決定
    - 隠れ層(hidden)
        - 中間層のこと
        - 隠れニューロン
    - Summary of BP-based learning (BP→誤差逆伝播法)
        - 出力ノードの学習信号から逆算して、中間ノードの学習信号を逆算す流ことによって、中間ノードの結合荷重を更新する方法
        - https://www.yukisako.xyz/entry/backpropagation
        - ![](https://i.imgur.com/GzEB5B7.png)

 
### algorithm assignment
- effective input(効果的入力)
    - ニューロンへの入力
- desired output
    - 教師データ
- actual output
    - 実際の出力
- error signal
- **error back propagation(誤差逆伝播法)**の3つのレイヤー
- 誤差逆伝播法とは
    - 重みパラメータにおける損失関数の勾配を求め、重みパラメータを更新を効率良く行うための手法
    - 出力層から入力層に向かって、逆の順番に計算する。
        - 出力層から計算していくので計算量が少ない.


## lec13
### resume
- 二分探索木
    - 左側のノードキー: 常に親より小さい
    - 右側のノードキー: 常に親より大きい
    - log2nで追加・検索・削除
- ヒープ(優先度付きキュー)
    - O(log2n)で追加・削除
    - ヒープソート: O(nlog2n)
    - オープンリストをヒープで実装することで均一コスト・A*アルゴリズムの効率を向上
- APDT
- ODT
- NNTree: 中間ノードに(MLP(多層パーセプトロン)←ニューラルネットワーク)を利用する木
    - 同じクラスラベルを持つデータはすべて同じグループに入れる
    - 近いデータ同士を同じグループに入れる
- NNTreeの利点
    - 適応性(Adaptability)
    - 理解しやすさ(Comprehensibility)
    - 迅速な判断(Quicker decision)
### quiz
- 決定木には非終端ノード(non-terminal nodes)と終端ノード(terminal nodes)
- 従来の決定木の非終端（内部）ノードの単純なテスト関数は$f(x)=x_i-a_i$
    - $f(x)<0$の時は左側のノードにアクセス
- 決定木の誘導における3つのタスクにおいて最も重要であり時間が掛かるのは**ノードの分割**である。
    - ノードの分割
        - いいテスト関数を見つける.
            - テスト関数: 中間ノードの判断条件。決定木において、次の子へ行くための条件
            - 例: もし a < 10 ならA, a >= 10 ならノード3へ
    - どのノードがターミナルか判断する
    - ターミナルノードのクラスラベルの割り当て
- APDTs:axis-parallel decision tree　← decision tree
- ODT: oblique decision tree
    - 多変量決定関数を使って、ツリーサイズを縮小する
- NNTree: 各非終端ノードはニューラルネットワークである

## lec14
### resume
- 遺伝的アルゴリズム(Genetic algorithm (GA))
    - 個体の遺伝情報を基にした探索を行い、問題の最適解を求める
    - GAの性質
        - population-based
        - generate-and-test algorithm
        - history preserving
    - **遺伝子型(genotype)**
    - **表現型(phenotype)**
    - **適応度(fitness)**
    - **遺伝子操作(genetic operations)**
        - 選択(Selection)
        - 交叉(Crossover)
        - 突然変異(Mutation)
    - Operator
        - 切り捨て選択
        - ワンポイントクロスオーバー
        - ビットごとの突然変異
- 量子群最適化(Particle Swarm Optimization (PSO))
    - 探索空間の全ての可能な解を探索することで、問題の最適解を求める
    - 非ダーウィン進化アルゴリズム
    - 比較的固定された環境に適している。
    - 集団: スウォーム(swarm)
    - 個々の個体: パーティクル
        -　現在の位置
        -　これまでに見つかった最良の位置
        -　速度(velocity)
    - 郡全体
        - これまでに見つかった最良のパーティクル(グローバルリーダー)を記録する。
- GAとPSOの違い
    - 探索単位: 個体と粒子
    - 操作の違い: 交叉や突然変異などと粒子の速度
- PSOの物理的意味
    - 各粒子はリーダーから学習するだけではなく、それ自体の最適な位置も学習する。
### quiz
- 遺伝的アルゴリズムを使用するには、通常、（遺伝子型の表現が２進数であるため）解または個体をバイナリ文字列にエンコードする。解決策の良さを評価するには、遺伝子型を**表現型**にデコードする必要があります。
- 解の良し悪しは**適応度(fitness)** と呼ばれる。与えられた解の適合度を評価する方法が必要である。この方法は、閉形式で与えられるとは限りません。
- GAには3つの遺伝子操作、すなわち、**選択・交叉・突然変異**がある.突然変異は人口の多様性を維持するのに重要である。
- PSO では、各解の候補を**粒子**と呼ぶ。粒子の現在の位置と速度を維持したまま探索を行う必要がある。
- PSOでは、各パーティクルが自ら学習していきます。学習には主に2つの要因がある。一つは個人的な要因であり、もう一つは**社会的要因**である。後者は「情報共有」のために重要である。
    - 粒子同士が相互に影響を与えあうことで、学習を促進するために重要。
    - 粒子同士が情報を共有することで、解を探索する際に、より多くの情報を用いることができる。
