「北海道大学大学院情報科学院修士課程入学試験」（令和6年8月実施）の情報理工学コース「人工知能」対策ページです。
分野別対策
人工知能
概説1
- 近年のAI（人工知能）技術の発展は目を見張るものがある。
- ここでは、このAI技術の発展を特に、言語・知識系の研究分野と、その成果を応用した対話システムに注目して概観する。
- ニューラルネットワーク中のどの部分（特定の単語など）に注目するかを動的に決定するアテンション機構が考案され、言語の出力系列生成の品質向上につながった。
- ニューラルネットワーク中のどの部分（特定の単語など）に注目するかを動的に決定するアテンション機構が考案され、言語の出力系列生成の品質向上につながった。
- このアテンション機構を最大限に生かした新しい深層学習モデルとして、2017 年にトランスフォーマーが Google から発表された。
- トランスフォーマーは、RNN(Recurrent Neural Network)やCNN(Convolutional Neural Network)を使わずに、アテンション機構で構成した深層学習モデルである。
- RNNやCNNより計算量が抑えられ、訓練が容易で、並列処理もしやすく、複数の言語現象を効率良く扱えて、文章中の長距離の依存関係も考慮しやすいといった特長を持つ。
- ニューラルネットワークを用いた自然言語処理で高い精度を達成するには、大量の訓練データが必要だが、さまざまなタスクのおのおのについて大量の訓練データを用意することは容易なことではない。
- そこでまず、さまざまなタスクに共通的な汎用性の高いモデルを大量のラベルなしデータで事前学習(Pre-Training)しておき、それをベースに個別のタスクごとに少量のラベル付きデータでの追加学習(Fine Tuning)を行うというアプローチが取られるようになった。
- この事前学習(Pre-Training)で作られたトランスフォーマー型の深層学習モデルは、2018年にGoogle から発表されたBERT以降、自然言語処理においてスタンダードになった。
- 言語モデルの規模を表すパラメータ数は、BERTの場合、3.4 億個であったが、2020年にOpenAIから発表されたGPT-3(Generative Pretrained Transformer)では、事前学習に45TB のデータを用い、モデルのパラメータ数は1750億個となった。
- これらは大規模なパラメータを持つことから大規模言語モデル(Large Language Model: LLM)と呼ばれるが、高い汎用性を示すことから基盤モデル(Foundation Model)とも呼ばれるようになった。
- また、GPT-3(Generative Pretrained Transformer)においては、それまでのGPTアーキテクチャと同様に後続の系列を予測する自己回帰型の自己教師あり学習が用いられた。
- タスクごとの追加学習(Fine Tuning)をせずとも、最初に入力する系列にタスクの記述や事例を含めることを意味するプロンプトにより複数のタスクに対応することをゼロショットと呼び、言語モデルの汎用的な活用が開拓された。
- さらに、2022 年 11 月末に OpenAI からChatGPTがWeb 公開された。
- OpenAI が2020 年 6月に発表したGPT-3.5 に人間のフィードバックを用いた強化学習の一つであるRLHF(Reinforcement Learning from Human Feedback)を加え、対話システムとして追加学習(Fine Tuning)されたものだということである。
- 入力された質問に対してまるで人間が書いたかのような自然な文章で説明を返し、用途に応じたテキスト（論文・電子メール・プログラムコードなど）の作成にも活用できる。
- しかし、その性能に驚く一方、誤った内容をもっともらしく回答するケースも見られ（特に計算や演繹推論で間違うケースが見られる）、誤って信じてしまうリスクやそれが悪用されるリスクが懸念される。
概説2
- ディープラーニングは2012年に開催されたILSVRC (ImageNet Large Scale Visual Recognition Challenge) と呼ばれる画像認識コンテストで顕著な成果を収めたことで一躍有名になった。
- ディープラーニングは、ニューラルネットワークの層を3層以上に多層に積み重ね、オートエンコーダなどの手法を用いて勾配消失問題を克服したもので、ジェフリー・ヒントン教授の研究チームが提唱した。
- 現在、課題別に応じて様々な構造を持つモデルが提案されている。
- 例えば、画像認識によく用いられるモデルとして、ResNetやAlexNetなどの畳み込みネットワークが有名である。
- 基本的な畳み込みネットワークでは、畳み込み層、プーリング層、全結合層を経て入力画像の認識を行う。
- その他、時系列データに対して長期・短期の時間依存性を学習することができるLSTM (Long Short Term Memory)というモデルもある。
- LSTMは内部にループ構造を持つリカレントネットワークの応用であり、忘却ゲート層などを導入することで飛躍的に性能が伸びた。
- 応用面では、囲碁の対決においてDeepMind 社が開発したAlphaGoが2017年に当時世界チャンピオンであった柯潔（カ・ケツ）を打ち負かしたことなどが記憶に新しい。
- このモデルは方策ネットワーク、価値ネットワークからなり、過去の棋譜をベースに教師あり学習を行ったあと、自己対戦による強化学習を行うことによって学習が行われる。
- ディープラーニングの実行には膨大な計算が必要であるが、計算時間を短縮するためにGPU (Graphics Processing Unit)を利用したTensorFlowやPyTorchなどのライブラリが公開されており、これらのライブラリを使うことで効率よくモデルの開発が可能となった。
Q学習
- 具体例
- マルコフ性を満たす環境においてエージェントが意思決定をして状態が確率的に遷移し、状態や行動が有限であるということ。
- 環境がマルコフ性を持つとは、過去の環境の履歴すべてが、現在の環境情報に集約されていることを指す。
-
グリーディ方策
\begin{align} \pi(s, a) = \arg\max\limits_a Q(s, a) \end{align}
-
ε-グリーディ方策
\begin{align} \pi(s, a) = \begin{cases} \arg\max\limits_a Q(s, a) & \text{with probability } 1 - \epsilon \\ \text{random action} & \text{with probability } \epsilon \end{cases} \end{align}
-
ソフトマックス方策
\begin{align} \pi(s, a) = \frac{e^{Q(s, a) / \tau}}{\sum\limits_{b} e^{Q(s, b) / \tau}} \end{align}
-
\begin{align} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( r_{t+1} + \gamma \max\limits_a Q(s_{t+1}, a) - Q(s_t, a_t) \right) \end{align}
- 真の最適行動価値関数に収束する。
- Q学習は、強化学習の代表的なアルゴリズムの一つであり、エージェントが環境と相互作用する中で、最適な行動方策を学習する手法である。環境は有限マルコフ決定過程（MDP）としてモデル化され、エージェントは各時点で状態を観測し、可能な行動を選択する。行動の結果として得られる報酬と次の状態を基に、Q値が更新される。Q値は、ある状態で特定の行動を選択した際に得られる累積報酬の期待値を表し、Q学習ではこの値を徐々に改善していく。
- Q学習の更新則は、ベルマン方程式に基づいており、Q値は以下のように更新される：
\begin{align} Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right] \end{align}
- ここで、\( s \) は現在の状態、\( a \) は選択した行動、\( r \) は得られた報酬、\( s' \) は次の状態、\( a' \) は次に選択される行動、\( \alpha \) は学習率、そして \( \gamma \) は割引率である。この更新により、エージェントは環境との相互作用を通じて、長期的に見て最適な行動を選択するためのQ値を学習していく。
- エージェントが十分に多くのエピソードを経験し、すべての状態-行動ペアを探索することで、Q値は収束し、最適方策が得られる。理論的には、探索が無限に続く場合、適切な学習率と割引率の選択により、Q値は最適な値に収束することが保証されている。ただし、実際の応用においては、エピソード数や探索と活用のバランスが重要である。
- 具体例
- 入力層に入力信号を与えて順方向に中間層の出力を計算し、出力層からの出力を計算する。
- 出力層からの出力と教師信号との誤差から損失関数の値を計算する。
- 誤差逆伝播法を用いて出力層から入力層に向かう逆方向に各ユニット間の重みに対する勾配を計算する。
- 損失関数の値を最小化するために、最急降下法を適用して各ユニット間の重みを更新する。
- 終了条件を満たすまで以上を繰り返す。
-
\begin{align} w_{i+1} &= w_i - \alpha \frac{\partial L}{\partial w_i} \end{align}
- シグモイド関数は非線形な関数であり、ニューラルネットワークに複雑なパターンや関係を学習する能力を持たせることができるから。
- バッチ最急降下法では、すべてのトレーニングデータを使用して勾配を計算するため、各ステップの勾配は安定していて、収束は滑らかだが、計算コストが高く、メモリの使用量も多い。
- 一方、確率的最急降下法ではトレーニングデータからランダムに選んだ1つのサンプルを用いるため、計算コストが低いが、収束が不安定である。
- 活性化関数 \( f \) は恒等関数 \( f(s) = s \) であるため、 \( z^\mu = y^\mu \) となる。したがって、
- 次に、誤差関数 \( E \) を \( b \) で偏微分する。
- これをチェーンルールを用いて計算する。まず、 \( (t^\mu - z^\mu)^2 \) の \( b \) に関する偏微分を求める。
- 次に、 \( \frac{\partial}{\partial b} (t^\mu - z^\mu) \) を求める。
- したがって、
- これを誤差関数 \( E \) の偏微分に戻す。
- まとめると、誤差関数 \( E \) のバイアス \( b \) に関する偏微分は次のようになる。
- シグモイド関数 \( f \) は以下のように定義される。
- 交差エントロピー誤差関数 \( E \) は以下のように定義される。
- ここで、\( z^\mu = f(y^\mu) \) である。次に、誤差関数 \( E \) を \( b \) で偏微分する。
- チェーンルールを用いて計算する。まず、
\( -\sum_\mu \left[ t^\mu \ln z^\mu + (1 - t^\mu) \ln (1 - z^\mu) \right] \)の \( z^\mu \) に関する偏微分を求める。
- 次に、 \( z^\mu \) を \( y^\mu \) で偏微分する。
- したがって、
- 最後に、\( y^\mu \) を \( b \) で偏微分する。
- まとめると、
-
方法1: ドロップアウト（Dropout）
ドロップアウトは、ニューラルネットワークの訓練中にランダムにいくつかのノード（ニューロン）を無効化する（ゼロにする）手法である。 これは、ネットワークが特定のノードやその結合に過度に依存するのを防ぎ、より汎用的な特徴を学習するのを助ける。- 説明:
- 各訓練ステップで、指定された確率（例えば50%）でノードを無効化する。
- テスト時には全てのノードを使用するが、訓練時に無効化した確率に応じてノードの出力をスケールする。
- 説明:
-
方法2: L2正則化（L2 Regularization）
L2正則化は、重みパラメータに対してペナルティを加える手法である。具体的には、損失関数に重みの二乗和を加えることで、大きな重みが成長するのを防ぎ、過学習を抑制する。- 説明:
- 損失関数 \( L \) に対して、以下のようなペナルティ項 \( \lambda \sum w^2 \) を追加する。
- ここで、\( \lambda \) は正則化の強さを制御するハイパーパラメータであり、\( w \) は重みパラメータを表す。
- このペナルティにより、重みが大きくなることを抑制し、モデルの複雑さを制限する。
- 説明:
- シグモイド関数は、次のように定義される活性化関数である：
\begin{align}\sigma(x) = \frac{1}{1 + e^{-ax}}\end{align}
- この関数は、入力 \(x\) に対して、出力が \(0\) から \(1\) の範囲に収まる非線形関数である。パラメータ \(a\) を変化させると、関数の傾きが変わる。
- \(a = 1\) の場合のシグモイド関数のグラフは、典型的なS字形をしており、次のようになる：
\begin{align}\sigma(x) = \frac{1}{1 + e^{-x}}\end{align}
- この場合の概形は、\(x = 0\) で 0.5 となり、\(x\) が正の無限大に近づくと1に、負の無限大に近づくと0に漸近する。
- シグモイド関数の導関数は、次のように表される：
\begin{align}\sigma'(x) = a \sigma(x) (1 - \sigma(x))\end{align}
- この導関数は、シグモイド関数の特性上、活性化関数の出力に基づいて自己調整される形となっている。
- ランプ関数 (ReLU) は、以下のように定義される活性化関数である：
\begin{align}R(x) = \max(0, x)\end{align}
- この関数は、入力が正の場合はそのまま出力され、負の場合は0を出力する。ReLU関数のグラフは、原点を境にして右側が直線（傾き1）、左側がx軸に沿った直線（傾き0）となる。
- ReLUの導関数 \(R'(x)\) は次のように表される：
\begin{align} R'(x) = \begin{cases} 1 & \text{if } x > 0 \\ 0 & \text{if } x \leq 0 \end{cases} \end{align}
- ReLUは、計算が簡単でありながら深層学習において高いパフォーマンスを発揮するため、広く使用されている。
- 深層学習において、中間層が多くなるとシグモイド関数は「勾配消失問題」に直面しやすくなる。 シグモイド関数の出力が0または1に近づくと、その導関数が0に近づき、逆伝播において勾配が極めて小さくなるため、層が深くなるほど勾配が消失してしまう。 この結果、学習が進まなくなることがある。 一方、ランプ関数 (ReLU) は、正の入力に対して勾配が1であるため、勾配が消失する問題が発生しにくい。 また、ReLUは計算コストが低く、学習が高速に進む利点がある。 これらの理由から、深層学習ではシグモイド関数よりもReLUが広く用いられている。
- SGD (Stochastic Gradient Descent) は、確率的勾配降下法と呼ばれる最適化手法であり、大規模データセットを用いた深層学習において広く使用されている。 SGDは、各イテレーションごとにデータセットからランダムに選ばれた一部のサンプル（ミニバッチ）に基づいて勾配を計算し、モデルのパラメータを更新する。 利点としては、全データセットを使う必要がないため、メモリ効率が良く、計算が高速である点が挙げられる。また、局所解から抜け出しやすい。 欠点としては、収束が不安定で、適切な学習率の設定が難しい場合があることが挙げられる。適切なハイパーパラメータの選定が求められる。
- 具体例
- SVMは、データポイントを識別するために識別境界面を見つける。 この識別境界面は、データポイント間のマージンを最大化するように配置される。 マージンとは、識別境界面から最も近いデータポイントまでの「距離」を指し、この距離を最大化することで、分類の信頼性が高まる。
- SVMは、データが低次元空間で線形分離できない場合、カーネルトリックを使用してデータを高次元空間にマッピングする。 これにより、高次元空間ではデータが線形分離可能となり、SVMは効果的に分類を行うことができる。
- 式(b)で等号が成り立つのは、訓練データ \(\mathbf{x}_i\) がマージンの境界上にある場合である。
- つまり、\(\mathbf{x}_i\) がサポートベクターであるときに成り立つ。
- 具体例
- まず、ユークリッド距離を使用して、\(\mathbf{x} = (2, 3)\) から各訓練データ点までの距離を計算する。
- \(\mathbf{x}_1 = (1, 0)\): \(\sqrt{(2-1)^2 + (3-0)^2} = \sqrt{1 + 9} = \sqrt{10}\)
- \(\mathbf{x}_2 = (1, 2)\): \(\sqrt{(2-1)^2 + (3-2)^2} = \sqrt{1 + 1} = \sqrt{2}\)
- \(\mathbf{x}_3 = (3, 3)\): \(\sqrt{(2-3)^2 + (3-3)^2} = \sqrt{1 + 0} = \sqrt{1}\)
- \(\mathbf{x}_4 = (4, 3)\): \(\sqrt{(2-4)^2 + (3-3)^2} = \sqrt{4 + 0} = \sqrt{4}\)
- \(\mathbf{x}_5 = (4, 5)\): \(\sqrt{(2-4)^2 + (3-5)^2} = \sqrt{4 + 4} = \sqrt{8}\)
- 次に、最も近いK個 (K=3) のデータ点を見つける。
- \(\sqrt{1}\) (最も近い) → \(\mathbf{x}_3\) (クラス1)
- \(\sqrt{2}\) (次に近い) → \(\mathbf{x}_2\) (クラス1)
- \(\sqrt{4}\) (3番目に近い) → \(\mathbf{x}_4\) (クラス2)
- 多数決によって、新しいデータ点 \(\mathbf{x} = (2, 3)\) はクラス1に分類される。
- 近傍のサイズKを訓練データと同数の5にした場合、すべての訓練データ点が考慮される。 この場合、クラス1のデータ点が3つ、クラス2のデータ点が2つ存在する。
- クラス1: \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\)
- クラス2: \(\mathbf{x}_4, \mathbf{x}_5\)
- K=5では常にクラス1のデータ点が多数派となるため、任意の新しい点はクラス1に分類される。 したがって、この方法では訓練データのクラス比率が分類に強く影響を与えることになる。
- ノンパラメトリック法は、訓練時の計算量は少ないが、予測時の計算量が大きくなる。
- また、ノンパラメトリック法はデータセット全体を保存する必要があるため、記憶量が大きくなる。
- 具体例
- 具体例
状態遷移が有限マルコフ決定過程であるとはどういうことか。
式を用いて方策\(\pi(s, a)\)の例を示せ。
エージェントが状態\(s_t\)において取った行動を\(a_t\)とするとき、行動価値\(Q(s_t, a_t)\)の更新を式で表せ。
すべての状態と行動の組が無限に繰り返されて行動価値が更新されるとき、最終的に行動価値はどのような値に収束するか。
強化学習の一つであるQ学習の概略、および学習時におけるQ値の収束性について、次の語句を用いて300字程度で説明せよ。（状態、行動、Q値、報酬、エピソード、方策、有限マルコフ決定過程）
ニューラルネットワーク
ニューラルネットワークの教師あり学習における学習プロセスを説明せよ。
上記の学習プロセスにおいて更新する重みを\(w_i\)、学習率を\(\alpha\)、損失関数を\(L(\cdot)\)とするとき、偏微分を用いて最急降下法による重みの更新式を示せ。
活性化関数にシグモイド関数がよく使われるのはなぜか。
最急降下法は使用するサンプルの数により、バッチ最急降下法と確率的最急降下法がある。その違い、およびそれぞれメリットとデメリットを簡単に説明せよ。
\( K \) 次元入力で、1 次元出力の中間層のないニューラルネットワークによる回帰問題を考える。
サンプル \(\mu \) において、 \( j \) 番目の入力を \( x_j^\mu \) (\( j = 1, ..., K \))、
出力を \( z^\mu \)、出力と入力との間の結合重みを \( w_j \)、出力のバイアスを \( b \)、
出力の目標値を \( t^\mu \) とする。
出力の入力の総和 \( y^\mu \) は、式 (1.1) で計算され、最終的な出力は、
活性化関数 \( f \) を用いて式 (1.2) で計算される。ここでは、活性化関数は恒等関数 \( f(s) = s \) とする。
\( z^\mu = \sum_{j=1}^K w_j x_j^\mu + b \)
\( \frac{\partial E}{\partial b} = \frac{\partial}{\partial b} \left( \frac{1}{2} \sum_\mu (t^\mu - z^\mu)^2 \right) \)
\( \frac{\partial}{\partial b} (t^\mu - z^\mu)^2 = 2 (t^\mu - z^\mu) \left( \frac{\partial}{\partial b} (t^\mu - z^\mu) \right) \)
\( \frac{\partial}{\partial b} (t^\mu - z^\mu) = \frac{\partial}{\partial b} \left( t^\mu - \left( \sum_{j=1}^K w_j x_j^\mu + b \right) \right) = -1 \)
\( \frac{\partial}{\partial b} (t^\mu - z^\mu)^2 = 2 (t^\mu - z^\mu) (-1) = -2 (t^\mu - z^\mu) \)
\( \frac{\partial E}{\partial b} = \frac{1}{2} \sum_\mu \frac{\partial}{\partial b} (t^\mu - z^\mu)^2 = \frac{1}{2} \sum_\mu (-2) (t^\mu - z^\mu) = -\sum_\mu (t^\mu - z^\mu) \)
\( \frac{\partial E}{\partial b} = -\sum_\mu (t^\mu - z^\mu) \)
【2】【1】のモデルを使って、２クラス分類問題を考える。入力\(x^\mu\)に対する正解ラベルは\(t^\mu \in {0, 1}\)とする。
活性化関数\(f\)を式(2.1)で示すシグモイド関数にして、誤差関数\(E\)に式(2.2)で示す交差エントロピーを用いた時の\(\frac{\partial E}{\partial b}\)を導出せよ。
ただし、\(\ln\)はネイピア数\(e\)を底とする自然対数である。
\( f(y^\mu) = \frac{1}{1 + e^{-y^\mu}} \tag{2.1} \)
\( E = -\sum_\mu \left[ t^\mu \ln z^\mu + (1 - t^\mu) \ln (1 - z^\mu) \right] \tag{2.2} \)
\( \frac{\partial E}{\partial b} = \frac{\partial}{\partial b} \left( -\sum_\mu \left[ t^\mu \ln z^\mu + (1 - t^\mu) \ln (1 - z^\mu) \right] \right) \)
\( \frac{\partial}{\partial z^\mu} \left[ -t^\mu \ln z^\mu - (1 - t^\mu) \ln (1 - z^\mu) \right] = -\frac{t^\mu}{z^\mu} + \frac{1 - t^\mu}{1 - z^\mu} \)
\( \frac{\partial z^\mu}{\partial y^\mu} = z^\mu (1 - z^\mu) \)
\( \frac{\partial E}{\partial y^\mu} = \left( -\frac{t^\mu}{z^\mu} + \frac{1 - t^\mu}{1 - z^\mu} \right) z^\mu (1 - z^\mu) = z^\mu - t^\mu \)
\( \frac{\partial y^\mu}{\partial b} = 1 \)
\( \frac{\partial E}{\partial b} = \sum_\mu (z^\mu - t^\mu) \)
【3】中間層を持つ多層のニューラルネットワークの学習において、訓練データにはよく適合するが、訓練データではない未知のデータ（テストデータ）には適合しない過学習の状態に陥ることがある。この過学習を抑制する方法を2つ挙げ、その方法について説明せよ。
活性化関数として、シグモイド関数 \(\sigma(x)\) が用いられることがある。パラメータを \(a\) としたシグモイド関数 \(\sigma(x)\) の式を \(a\) を使って表し、\(a = 1\) の場合の概形を図示せよ。また、その導関数 \(\sigma'(x)\) を \(a\) と \(\sigma(x)\) を用いて表わせ（ただし、導出過程は省略しても良い）。
活性化関数として、ランプ関数 \(R(x)\) (Rectified Linear Unit: ReLU) が用いられることも多い。ランプ関数 \(R(x)\) の式を示しその概形を図示せよ。また、その導関数 \(R'(x)\) を求めよ。
深層学習において、中間層が多くなるにつれ、活性化関数としてシグモイド関数よりもランプ関数の方が学習効率が良いことが知られている。その理由について300字程度で述べよ。
深層学習における最適化手法の一つとして知られているSGD (Stochastic Gradient Descent) について説明し、その利点と欠点を合わせて300字程度で述べよ。
問題
多層階層型ニューラルネットワークによる教師あり学習の計算手順について、次の語句を用いて概要を説明せよ。
(損失関数、誤差、教師信号、誤差逆伝播法、勾配、最急降下法)
解答
多層階層型ニューラルネットワークによる教師あり学習では、入力データに対する予測と教師信号との間の誤差を損失関数で定量化し、誤差逆伝播法を用いて損失関数の勾配を計算し、最急降下法によりこの勾配に基づいてネットワークのパラメータを更新して誤差を最小化することで、モデルの精度を向上させる。
サポートベクターマシン
サポートベクターマシン（SVM）は、パターン識別用の教師あり機械学習の方法であり、局所解収束の問題がないという長所がある。 特に、マージン最大化という手法で汎化能力も高め、現在知られている方法としては、優秀なパターン識別能力を持つとされている。 また、カーネルトリックという巧妙な方法を用いることにより、応用範囲が格段に広がっている。
マージン最大化について説明せよ。
カーネルトリックについて説明せよ。
以下の式(a)と(b)は、SVMにおいて解を得る際の目的関数と制約条件を表している。
式(b)で等号が成り立つのはどのような場合かを\(x_i\)を用いて説明せよ。
K近傍法
２クラス分類におけるK近傍法は、分類したいデータ点\(\mathbf{x}\)が与えられたとき、訓練データ中で\(\mathbf{x}\)から最も近いK個のデータ点（K近傍と呼ぶ）を探し、それらの中の多数派が属するクラスを\(\mathbf{x}\)のクラスとする。 ２次元平面乗の５つのデータ点からなる訓練データ\(\mathbf{x}_1 = (1, 0)\), \(\mathbf{x}_2 = (1, 2)\), \(\mathbf{x}_3 = (3, 3)\), \(\mathbf{x}_4 = (4, 3)\), \(\mathbf{x}_5 = (4, 5)\)において、\(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\)はクラス1に、\(\mathbf{x}_4, \mathbf{x}_5\)はクラス2に属しているとする。 新しいデータ点\(\mathbf{x} = (2, 3)\)をどちらのクラスに分類するか、\(K=3\)としたK近傍法により決定せよ。 ただし、データ点間の距離はユークリッド距離で測ることとする。
近傍のサイズKを大きくして訓練データと同数にした場合、任意の点はどのように分類されるかを考察せよ。
K近傍法に代表されるノンパラメトリック法を、線形識別モデルに代表されるパラメトリック法と比較した場合の問題点について、必要な計算量と記憶量の点から考察せよ。
ゲーム理論
問題
人工知能技術の一つにゲームプレイングがある。 いま、チェスやオセロのように、二人のプレイヤーが交互に指し手を選択して勝敗を争う完全情報ゲームを計算機にプレイさせるものとし、 この技術の概略について、次の5つの語句をすべて用いて、400字程度で説明せよ。
【語句】評価値（または効用値、利得）、ゲーム木、ミニマックス法、静的評価関数（または評価関数）、アルファベータ法
解答
ゲームプレイング技術とは、チェスやオセロのごとき二人のプレイヤーが交互に手を選択し、勝敗を競う完全情報ゲームを計算機にプレイさせる技術のことを指す。 この技術においては、まずゲームの全ての可能な状態と指し手を網羅したゲーム木が用いられる。 ゲーム木とは、各ノードがゲームの状態を表し、枝がその状態からの可能な指し手を示すものである。 この木の探索において、プレイヤーは自らの勝利を最大化し、相手の勝利を最小化することを目指す。 これを実現するために用いられるのがミニマックス法である。 ミニマックス法では、終端ノードに到達した際に、そのノードに評価値（または効用値、利得）を割り当て、逆方向に木をたどり最適な手を選択する。
しかし、全てのノードを評価することは計算量の点で非効率的であるため、ここでアルファベータ法が導入される。 この手法により、必要のない枝を剪定し、計算量の削減が図られる。 具体的には、現在の評価値が一定の条件を満たす場合、その枝以降の探索を打ち切ることで効率化を達成する。
これらの技術を支えるのが静的評価関数（または評価関数）である。 静的評価関数は、ゲームの任意の局面を数値的に評価し、その局面の良否を定量化するための関数である。 この関数により、ゲーム木の終端ノードに到達せずとも途中で局面を評価し、最善手を選択することが可能となる。
探索
問題
(4)人工知能における状態空間の探索において,探索ノードを順次展開し子ノードを生成しながら探索を行う探索アルゴリズムの特徴について,次の語句を全て 1 回以上用いて,300 字程度で記述せよ.(深さ優先探索,幅優先探索,最良優先探索,A*アルゴリズム,ヒューリスティック関数,探索コスト)
解答
状態空間の探索において、探索ノードを順次展開しながら子ノードを生成するアルゴリズムには、さまざまな方法が存在する。まず、深さ優先探索は、探索の深さを優先し、ノードをできるだけ深く展開する。これに対して、幅優先探索は、現在の深さにあるすべてのノードを先に展開するため、解までの最短経路が見つかりやすい。最良優先探索では、ヒューリスティック関数を用いて、もっとも良さそうなノードから展開を行う。特にA*アルゴリズムは、探索コストとして、実際のコストとヒューリスティック関数の値を組み合わせて評価し、効率的に最短経路を見つける。このように、探索アルゴリズムは探索コストと解の品質のバランスを取りながら、最適な解を見つけることを目指している。