【情報に関する理論】符号理論、述語論理、オートマトンなど

符号理論、述語論理、オートマトン、形式言語、計算量、人工知能（AI）、知識工学、学習理論、コンパイラ理論、プログラミング言語論・意味論についてまとめました。

【符号理論】
【述語論理】
【オートマトン】
【形式言語】
【計算量】
【人工知能（AI）】
【知識工学】
【学習理論】
【コンパイラ理論】
【プログラミング言語論・意味論】
【機械学習】教師あり学習、教師なし学習、強化学習

【符号理論】

用語	概要
標本化定理	アナログ信号をディジタル信号に変換する際、アナログ信号の最高周波数の２倍以上でサンプリングしないと元のアナログ信号を再現できないという定理です。

【述語論理】

用語	概要
アスキーコード	ASCII（アスキー）とは、英語等のラテン文字を中心とした文字コード(コンピュータで文字を扱うときの「文字」と「文字に割り当てる番号」の対応表)。例えば、ASCIIコードでは「a」という文字を「97」という数値で表します。
ハフマン符号化	可変長の符号化方式で、出現確率が高いデータには短い符号を、低いデータには長い符号を与えることで圧縮を効率よく行う方法です。符号化のビット列に全く同じ符号の並びが存在しないように、ある文字に対応する符号が、他の文字に対応する符号の接頭辞にならないように設定されます。これにより単純に先頭から読んでいくだけでデコードができます。
UTF-8	ASCIIと同じ文字は1バイト、その他の文字については2～6バイトを用いて世界中の文字を表現する文字符号化形式。

【オートマトン】

オートマトンは、現在の状態と入力信号の組合せだけによって次に遷移する状態が決まるモデルです。

【形式言語】

用語	概要
ワイルドカード	「*」「?」の2種類の記号で、文字列の集合を表現
正規表現	ワイルドカードの「*」「?」に加えて、さらに他の記号を使ってより文字列の集合を表現

【計算量】

【人工知能（AI）】

G検定にも頻出な内容です。

用語	概要
人工知能	コンピュータによる知的な情報処理システムを設計、または実現するための研究分野。
機械学習	人間の学習・予測能力をコンピュータで実現するための技術や手法の総称。「明示的にプログラムせずに学習する能力をコンピュータに与える研究分野」というアーサー・サミュエルによる定義もありあます。コンピュータに大量の学習データを与え、自律的にデータの特徴点を抽出し、コンピュータにパターン認識や分類能力をもたせる学習です。教師あり学習、教師なく学習、強化学習などの種類があります。
深層学習	ディープにーラルネットワークを用いて学習を行う機械学習アルゴリズムの１つ。層数を増やすほど、複雑な関数を近似できる特徴をもつが、過学習や高賠償質問っ題が起こりやすくなったり、事前に調整するハイパパラメータが多いという欠点がある。
人工生命	コンピュータ、機械などを使って生命現象や進化のプロセスを再現する技術です。
エキスパートシステム	特定の分野の専門知識をコンピュータに入力し、入力された知識を用いてコンピュータが推論する技術です。機械学習とは違い、判断式を人間が事前に与える必要があります。一般常識を知識ベース化するCycプロジェクトは1984年から続けられており、2001年からOpenCycとして一部が一般公開されている。
エドテック	人が双方向学習を行うために、Webシステムなどの情報技術を用いて教材や学習管理能力をコンピュータにもたせるための技術です。
チューリングテスト	ある機械が人工知能かどうか判定するテスト。1950年にアラン・チューリングが論文で発表。人間の審査員が、機械であることを知らずに機械と対話させ、どの程度の割合で機械と人間との確実な区別ができないかをテストする。
ELIZA	1966年に発表された自然言語処理プログラム。複数の審査員が人間と会話していると判定し、チューチングテストで合格する機械を実現する可能性を示した。
RAPPY	ELIZAのあとに開発された自然言語処理プログラム。こちらも複数の審査員が人間と会話していると判定し、チューチングテストで合格する機械を実現する可能性を示した。また、ELIZAとRAPPYは何度か会話を行い、最初の会話がRFC439に記録されている。
ディープブルー	IBM社が開発したチェスAI。力任せの探索ですが、1996年にチェスの世界チャンピオンに勝利している。
AlphaGo	Googleが開発した囲碁AIで2015年にプロ棋士に勝利する。
Ponanza	将棋AIで2013年以降に電王戦でプロ棋士に勝利する。
TAY	MICROSOFT社が開発したボット。ツイッターで公開されたが、不適切な言動を繰り替したためサービス停止となった。
第1次AIブーム	1950年後半～1960年代にかけて「推論と探索」によるAI（人工知能）がブームとなる。「推論と探索」は、事前に決まっているルールとゴールの枠組みの中で、コンピュータが最短・最速でゴールに到達する選択を行う。現実の問題は、様々な要素が複雑に絡むため解くことができない（おもちゃの問題：トイプロブレムを解くのに限られる）ため、ブームが終了。
第2次AIブーム	1980年代にエキスパートシステム（特定の分野の専門知識をコンピュータに入力し、入力された知識を用いてコンピュータが推論する技術）が台頭。知識ベース（知識のあつまり）と推論エンジン（推論を行うプログラム）で構成。機械学習とは違い、判断式を人間が事前に与える必要があり、様々な要素が複雑に絡むため解くことができなず、専門家の膨大な知識の定式化するのも困難であったため、ブームが終了。この問題に対応するためナレッジエンジニアとよばれる専門職がうまれた。
第3次AIブーム	2000年代以降に機械学習と深層学習が台頭。
ニューラルネットワーク	多数のニューロンを結合して構成される予測器。
ニューロン	ニューラルネットワークの最小単位。単純な数値予測を行う。入力に対して以下の処理を行う。・与えられた入力から、総入力（=入力の重み付き和+バイアス）を計算・活性化関数で出力を計算
LeNet	ヤン・ルカンが考案したニューラルネットワーク。
ILSVRC	2010年から開催されている、ImageNetデータセットを用いた画像認識の精度を競うコンペティション。
AlexNet	ILSVRC 2012で圧倒的な精度の高さで優勝した「ジェフリー・ヒントン」率いるチームが利用したディープラーニング（AlexNetと呼ばれる8層の畳み込みニューラルネットワークの1つ）がきっかけで深層学習と第３次AIブームが活発になる。前年度までの優勝モデルはサポートベクタマシンであったが、それを遥かに凌駕する結果だったため一気に注目された。パラメータ数は約60,000,000個、バーニーおじさんのルールによると、学習に必要なデータサンプル数は10倍の約600,000,000個と見積もれる。
GoogLeNet	ILSVRC 2014で優勝した22層の深層学習モデル。
ResNet	ILSVRC 2015で優勝した152層の深層学習モデル。
WAVENET	GOOGLE DEEPMIND社が2016年に開発した、サンプリングされた系列点としての音声をDNNで処理し、従来手法の近似や調整の作業が不要となり、より自然な発音が実現できた。
フレーム問題	AIが抱える本質的な問題。人が課題解決する際は、無意識に問題に関連する情報を選択・抽出するが、無限の可能性からの探索なのでAIが同じことを行うのが難しいという問題。何を考慮すべき・すべきでないかを判断するのに有限な計算資源しかもたないAIは膨大な時間がかかってしまう。これを打破できれば、自ら判断して様々な問題を解くAIができるとされている。第3次AIブームでの克服が期待されている問題。
強いAI（汎用AI）	フレーム問題を解決し、人間のようにあらゆる問題を解決できるようなAI。
弱いAI（特化型AI）	フレーム問題により、特定の問題解決しかできないようなAI。
シンギュラリティ	技術的特異点（人工知能が人間を越えて文明の中心的存在となる時点）。
バーニーおじさんのルール	バーニーおじさんのルール(定理). 機械学習において学習に必要なデータ数は説明変数の数の10倍必要であるというルール。
ノーフリーランチ定理	全て問題に対して万能に対処できる高性能なアルゴリズムは存在しないという定理。ディープラーニングも例外ではない。
みにくいアヒルの子定理	純粋に客観的な立場からは、どんなものを比較しても同程度に似ているとしか言えない。という定理。
モベラックスのパラドックス	伝統的な前提に反して「高度な推論よりも感覚運動スキルの方が多くの計算資源を要する」というもの。
オントロジー	–
ヘビーウェイトオントロジー	–
ライトウェイトオントロジー	–
レコメンデーションシステム	情報収集や買い物を行うユーザーに対し、機械学習でユーザーが好みそうな情報や商品を推薦するシステムの総称。米ゼロックスパロアルト研究所の「Tapestry」（1992年）が、協調フィルタリングの考え方で構築したものから、「レコメンデーション・システム＝協調フィルタリング」と見なされることもある。
協調ベースフィルタリング	ユーザーの購買履歴から商品を推薦する。
内容ベースフィルタリング	閲覧・購入した商品の特徴から、別の商品を推薦する。
言語モデル	人間の言語を確率的にモデル化したもの。力技で設定するのはパターンが膨大で困難なため、ニューラルネットワークによって近似されたニューラル言語モデルが用いられることが多い。
アンサンブル学習	複数のモデルを作り、分類は多数決、回帰は平均などを結果として採用する手法。安定した精度や、過学習の抑制のために用いられる。代表的な手法としてバギングとブースティングがあるバギング：各モデルを並列に学習・ブースティング：各モデルを逐次的に学習
中国製造2025	2015年5月に発表された2025年までの中国の製造業発展ロードマップ。ドイツの産業改革プロジェクト「インダストリー4.0」の影響を受けており、特にAI技術の取り組みを強化することが名言されている。
LAWS	自律型致死性兵器といい、人工知能などで完全自律で強力な殺傷能力をもつ兵器。現時点では存在しないが、将来的に開発されると民間人や味方を攻撃しかねない危険性があることから、専門家の間で議論が続いている。2017年2月に発表された「アシロマAI原則」で、AIによる軍拡競争は避けるべきだと明示されている。

【知識工学】

【学習理論】

【コンパイラ理論】

【プログラミング言語論・意味論】

【機械学習】教師あり学習、教師なし学習、強化学習

機械学習とは、学習方法をプログラムしたコンピュータに大量の訓練データを与えることで、コンピュータ自らに事象の認識や分類方法を学習させ、未知のデータに対しても学習結果に基づく推論を行うシステムを作る手法の総称です。
機械学習は、訓練データの性質によって「教師あり学習」「教師なし学習」「強化学習」の3つに大別できます。

用語	概要
教師あり学習	訓練データとして、ラベル(正解)付きデータを使用する学習方法。学習を行うことで未知のサンプルの正解ラベルを予測できる。入力に対する正しい出力の例を与えることで、入力と出力の関係を学習させる。回帰と分類に大別される。
教師なし学習	訓練データとして、ラベルなしデータを使用する学習方法。既知のデータの本質的な構造を浮かび上がらせることもできる。クラスタリングなどのためにデータ構造を学習させる。クラスタリングと次元削減に大別される。
強化学習	正解データの代わりに、与えられた環境における個々の行動に対して得点や報酬を与える学習方法。一連の行動に対して評価値を与えることで、高い得点を取る、すなわち最良の行動を自律的に学習させる。
ホールドアウト法	教師あり学習において、訓練データ（学習に用いるデータ）とテストデータ（未知データへの予測性能を調べるための教師データ）にわけ、「訓練データで学習→テストデータ」で検証という流れで学習と性能検証を行う手法。
交差検証	教師データをk個に分割し、テストデータを順番に移動させながらk個のモデルを生成する。それぞれのモデルの精度を平均して、精度を測定する。未知データに対する汎化性能を効率よく安定的に計測できる。すべてのデータをまんべんなく、訓練データ、テストデータとして使用するので、教師データ数が少ない場合も安定して精度を測れる利点がある。ハイパーパラメータのグリッドサーチにも応用される。
グリッドサーチ	事前に設定したハイパパラメータの各候補に対して交差検証で精度を計算し、最も精度が高いハイパパラメータの組を採用すること。手間と計算量はかかるが、ある程度自動化ができるためよく利用される。
スパースなデータ	ほとんど０の値が並んでいるデータ。スパース性を用いて計算量を削減することができる。
次元の呪い	機械学習でデータの次元が増え、さまざまな不都合が生じること。