G検定カンペ用語集

自分用G検定用チートシート。

2022年07月


すべてのタスクに対して、常に他より高精度である万能なアルゴリズムは存在しないことを主張する定理。





既知の知識をもとに、未知の出来事を推測すること。
分類や識別をしたいデータを、学習済みの推論モデルに当てはめ、結果を導く。

たとえば、未知の写真の特徴を抽出し、推論モデルで照合する。
パンダの特徴の組み合せパターンから作られた推論モデルが、最もその特徴パターンに近いと判断されれば、その写真はパンダの写真であるという推論結果が出力される。




イライザ(ELIZA)と共に有名な、初期の会話ボット。
1972年、コンピューターサイエンスと人工知能の精神医学への理論・応用を専門とするアメリカの精神科医ケネス・コルビーが作った。
イライザ(ELIZA) が来談者中心療法のセラピストのからかい半分のシミュレーションであったのに対して、パリー(PARRY)は偏執病的統合失調症患者をシミュレートしようとしたものである。

偏執病的統合失調症患者の振る舞いを大雑把にモデル化したもので、概念、概念化、信念(概念化についての判断: 受容、拒絶、中間)などに基づいている。
会話戦略も組み込まれていて、イライザ(ELIZA) よりもずっと真面目で進んだプログラムだった。

パリー(PARRY)とイライザ(ELIZA)は何度か対話をしたことがある。
最も有名な会話は ICCC 1972 でのものである。




計算機科学において、特定のキーを特定するために使用される木構造のこと。
その木構造が平衡(全ての葉ノードまでの深さがほぼ等しい状態)である場合、効率的にそのキーを探索できる。
連想配列の実装によく用いられる。

探索木には様々な種類がある。

●二分探索木
ノードベースのデータ構造。各ノードは左右で2つの部分木を持つ。
二分探索木のノードの検索にかかる計算は木の深さであるため、n 個の要素を持つ二分探索木でノードの検索を行うと O(log n)程度の時間がかかる。
ただし、最悪の場合には深さは n になるため、検索時間もO(n)となる。
このような場合を防ぐために、平衡を保つような工夫が行われる。

●B木
二分探索木をより一般化した、多分岐の探索木。
多分岐であるため、全てのキーに値が格納されているとは限らない。
したがってB木は、多少容量を無駄に消費する。
他の平衡木と比べて平衡を保つための処理を行う頻度が低いというメリットがある。
ノードの長さが可変であるため、大きなデータを読み取るシステムに最適。
データ管理システムによく使われる。

●a-b木
全てのノードの深さが等しい探索木。

●三分探索木
トライ木の一種。
左ノード・中央ノード・右ノードの3個の子ノードを持つことができる探索木。
各ノードは1文字を格納し、二分探索木と同じような順序でデータを格納する。
ただし、三分探索木は3つ目のノードを持つことができる。



第一次AIブームの時代を代表する研究分野。
最初に与えられた状態から目的の状態に至るまでの道筋を、場合分けや試行錯誤をしながら探っていくこと。
迷路を解くイメージ。
ノードを動線で繋いだ、木のような構造で表現される(探索木)。
ノードを進める順番が、道筋のパターンを表現する。
言いかえると、場合分けを通じて最も効率的な道筋を見つけるための手段。

●幅優先探索
同じ階層をしらみつぶしに当たってから、次の階層に進む方法。
最短距離の解が必ず見つかるが、一層ずつ進み、途中のノードの情報をすべて記憶に保持するため、メモリ消費が大きく記憶容量を超えてしまう危険性がある。


●深さ優先探索
出発点から深さ方向に行けるところまで掘り下げて、ゴールが見つからない場合は引き返して次の枝に移る方法。
深さ方向に進み、ダメなら戻って次の分岐を試すため、メモリを節約しやすい
運が良ければ、枝を何本も試さずにゴールにたどり着ける。
運が悪ければ、遠回りになって時間がかかる。




↑このページのトップヘ