人工知能技術の理論と数学とアルゴリズム

機械学習技術 人工知能技術 自然言語処理技術 確率的生成モデル デジタルトランスフォーメーション技術 アルゴリズム ICT技術 コンピューターアーキテクチャ ITインフラストラクチャ技術 機械学習における数学 深層学習 本ブログのナビ

人工知能技術の理論と基本的なアルゴリズム

人工知能という言葉は1956年のダートマス会議で生まれた。そこから現在までの65年、様々な技術が提案され続けている。機械学習がデータのパターン(意味)を見つけるのに特化した技術であるのに対して、人工知能は知識や知能に関する技術となる。これは具体的には、データをどのように加工して(データのモデリング/構造化)、どのように扱うのか(データ処理のアルゴリズム)を扱うものとなる。

知識は教科書等に文章や図式(何らかのシンボル)として記述されているが、その内容を理解するには、そこに記述されているシンボルの意味を理解する必要がある。シンボルの持つ意味は「コンピューターでシンボルの意味を扱う」にも述べているように、目に見えないダークマターのようなもので、観測可能な現実世界の事物(画像や音声、センサー情報や文字情報等)の裏側にある隠れ変数としてしか扱えない。

これらの知識をコンピューターで扱うようにするためには、観測可能な現実世界の事物を何らかの計算が行えるような形に変形しなければならない。それらの候補としては「言語の意味に対する2つのアプローチ(記号表現と分散表現の融合)」に述べているように、記号表現(グラフや木)と分散表現(ベクトルや行列)がある。

知識のハンドリングの一つの側面として、抽象化や推論がある。抽象化は「具象と抽象 – 自然言語のセマティクスと説明」でも述べているように、多数の事象や事物から共通する特徴量をまとめて一つの概念とするもので、ベクトルや行列を使った機械学習によるパターン認織と共通する機能となる。これに対して推論は、事象や事物の関係性を辿っていくもので、グラフや木を使った論理的(集合論的)機能と同様なものとなる。さらに抽象化と推論を組み合わせたものは、マルコフロジックネットワークや、確率論理プログミングのアプローチ等様々なものがあり、それらの機能を組み合わせることで、知能の活動が実現されているものと考えられる。

本ブログで紹介する人工知能技術としては、人が発する情報(言語情報)を機械が扱えるようなデータに変換する自然言語処理技術、データとデータの意味関係を使って様々なデータを自動生成するセマンティックウェブ技術、人の代わりに機械に会話させるチャットボット技術、様々な推論を行う機械推論技術等がある。

これらは機械学習技術と組み合わせる事で更にパワフルなツールとなる。人工知能技術概要について以下に記す。

情報理論&計算機工学

• シャノンの情報理論の概要と参考図書

シャノンの情報理論は、1948年にクロード・シャノンによって提唱された、情報の量や伝送の信頼性などを定量的に扱うための理論となる。シャノンの情報理論では、情報の量を「情報量」として定義する。情報量は、情報源が出力するメッセージの不確かさを表す指標であり、情報量が大きいほどメッセージが不確かであることを意味する。またシャノンの情報理論では、情報伝送の信頼性についても考慮されている。情報伝送には、誤りやノイズなどの影響があるため、送信された情報が正確に受信される保証がない。このような場合に対応するため、情報伝達の信頼性を高めるための手法が研究されている。

• チューリングの計算理論概要と参考図書とニューラルチューリングマシン

チューリングの計算理論は、アラン・チューリングによって提唱された、コンピュータの基本的な概念を理論化する理論となる。この理論は、コンピュータがどのように動作するか、そして計算が何であるかを理解するための基礎を提供するもので、次のような要素から構成されている。

ニューラルチューリングマシンとは、ニューラルネットワークとチューリングマシンを組み合わせた計算モデルのことを指す。

• 代数の文章題を解くプログラムに関する考察

chatGPTを用いると、以下に示す様に様々な代数の問題を解かせることができる。これらは、単純に答えを出すだけでなく、様々な公式を応用した解法を示してくれるため、万能のAIが出来ているかのような錯覚を受ける。

しかしながら、実際に計算を行ってみるとchatGPTが示してくれた答えが間違っている場合があることに気づく。これは、chatGPTが、あくまでも膨大な学習データを元に、次に何の文字が現れるかを推定しているだけで、本質的な計算を行っていないためである。

• オートグレーティング（自動採点）技術について

オートグレーディング（自動採点）は、コンピュータープログラムやアルゴリズムを使用して、学習活動や評価課題を自動的に評価し、得点を与えるプロセスを指す。この技術は主に教育や評価の分野で使用される。

• 現代思想2020年2月号　 特集＝量子コンピュータ ―情報科学技術の新しいパラダイム　読書メモ

Googleの研究チームによる「量子超越性の実証」が報じられて以来、改めて注目を集めつつある量子コンピュータ。それは私たちの世界をどのように変えうるのだろうか。本特集ではその歴史や理論的な基礎から最新の成果まで、量子情報科学の現在形を一望するとともに、政治経済や哲学、文学など多様な観点から量子時代の行く末を考える

• 情報理論 Math＆Science 読書メモ

クロード・シャノンが記念碑的論文「通信の数学的理論」を発表したのは1948年のことだった。それから60余年──今では情報理論は情報通信のみならず、生命科学や脳科学、社会科学など幅広い分野に応用されるようになっている。情報理論は高度な数学を用いているが、“大数の法則”をおさえることでその本質がすっきりと見えてくる。シャノンのアイディアから情報幾何学の基礎までを、初学者にもわかるよう明快に解説、情報理論の考え方と仕組みを直観的に理解するための、第一人者の手による入門書

• コンピューターを構成する計算要素と半導体チップについて

コンピューターの基本となるデジタル処理は、”0″,”1″の2つの数値(2進数)で表すものとなる。ここでこの”0″と”1″の2の状態を表現したものを1ビット(Binary Digitが語源)、また8ビットをひとつにまとめた情報単位をバイトと呼ぶ。1ビットが”0″と”1″の2通りの状態しか表せないのに対して、1バイトは256通りの状態を表現できる(1バイト=2⁸=256)。

• 情報としての生命 – 目的と意味

この本の作者であるポール・ナースはある早春の日、庭に舞い込んできた蝶の姿を見て、自分とはまったく違うけれど、蝶は自分と同じく紛れもなく生きていて、動くことも感じることも反応することもできて「目的」に向かっているように感じ、「生きているということはいったいどういうことなんだろう」という疑問を持っている。「WHAT IS LIFE」は、物理学者エルヴィン・シュレディンガー「命とはなにか」からのオマージュとなる。

• チューリングテストとサールの反論と人工知能

機械が知能を持っていると判断するためのテストとして、”会話とAI(チューリングテストから考える)“で述べているチューリングテストがある。このチューリングテストの基本的なアイデアは、人間との対話においてAIが人間と区別できないほどの知能を持っていれば、そのAIは人間と同等の知能を持っていると見なせるのではないかという仮説に基づいている。これに対してサールは「そもそもアルゴリズムに従って動く計算システムは知能をもてない。なぜなら、計算とは定義上形式的記号操作であり、そこに意味の理解はない」と結論づけている。

• ReAct(Reasoning and Acting)の概要とその実装例について

ReAct（Reasoning and Acting）は、AIシステムが知識を活用して推論し、その結果に基づいて適切な行動を取る能力を指し、人工知能（AI）の分野における重要な研究トピックの1つで、AIの進化と発展において重要な一歩であり、より複雑なタスクに対処するための新たな手法となる。ReActの主な目的は、AIシステムが推論と行動を統合することによって、より効果的に問題を解決し、環境に適応する能力を高めることであり、これにより、AIはより複雑な状況に対処し、より良い意思決定を行うことが可能となる。

• 感情認識と仏教哲学とAIについて

今回は感情認識の歴史と仏教哲学及び人工知能技術との関連性について述べたいと思う。

• 禅とメタ認知とAI

“瞑想と悟り(気づき)と問題解決“でも述べているようにマインドフルネス瞑想や禅のヴィパッサナー瞑想は「気づき」や「ありのままの注意」を重視する「洞察瞑想」であり、集中力を育て、物事をあるがままに観察することに注力したアプローチとなる。また、同様のアプローチは”認知科学への招待. 読書メモ“でも述べている認知科学では、「メタ認知」と呼ばれ、個々の思考や知識に対する認識の仕方を指し、自分が何を知っていて、何を理解しているかに対する理解と考えられている。

AI技術は、このようなメタ認知の様々な側面に対して、AI技術は実現可能なアプローチを提供している。

• 人工知能技術を用いて感情を検出する方法について

感情を抽出するために人工知能技術を使用する方法には主に(1)自然言語処理、(2)音声認識、(3)画像認識、(4)生体情報分析等のアプローチがある。これらの手法は、機械学習やディープラーニング等のアルゴリズムと組み合わされ、基本的には大量のトレーニングデータを用いて検出される。また、異なるモダリティ（テキスト、音声、画像、生体情報など）を組み合わせて感情を総合的に把握するアプローチもより精度の高い手法となる。

• 気づきと人工知能技術

「気づく」とは、何かを注意深く観察したり、認識したりすることを指し、また、人が状況や物事に対して気付くということは、その人がある情報や現象を認識し、それに関する気持ちや理解を持つことを意味する。気づくことは、外界の変化や出来事に注意を払うことによって、新たな情報を得たり、理解を深めたりする重要な過程となる。今回は、この気づきとそれらに対する人工知能技術の適用について述べてみたいと思う。

• 人の創造性とAIとの共生 – 無意識と記憶

“経済は「感情」で動いている“で述べている行動経済学は、現代の心理学における一つの潮流であり、従来の合理的な人間活動をベースとした経済学に対して、非合理的な思考や行動に焦点をあて、その非合理性に共通する法則を明らかにしようとするものとなる。我々の心には二つのシステムが想定され、一つは直感的判断のように、迅速かつ自動的で無意図的・無意識的なシステム、もう一つは論理的判断のように、時間はかかるがコントロール可能な意図的・意識的なシステムとなる。本ブログでも述べているAI技術は、このシステム2の合理的判断を人間の代わりに極限まで高めようとするものであり、”IA（Intelligence Augmentation）概要とその適用事例について“でも述べているIAは、システム1の有用な部分とシステム2をいかにしてつなげていくかというアプローチとなるとも言える。

• 人の創造性とAIとの共生 – 無意識とプライミング

プライミングは、AIの分野でも興味深い概念として取り上げられ、プライミングの概念を利用して、人間とAIのインタラクションを改善する研究も活発に行われている。例えば、AIを利用したエクスペリエンス（UX）デザインにおいて、ユーザーが特定のタスクを実行する際に、AIアシスタントがユーザーの意図をより正確に理解し、前もって関連する情報やコンテキストを提示することで、その後の操作がスムーズに進むようにするようなプライミングが考えられる。

• シミュレーション仮説と古典論理と非古典論理

『THE UNIVERSE IN A BOX 箱の中の宇宙』では、私たち自身の身体と心を含む、すべてのものがコンピュータの中にあるという可能性「シミュレーション仮説」について述べられている。我々が今いる場所は現実なのか、シミュレーションされているのかについて考えるアプローチにはいくつかある。一つは古典論理的なアプローチでもう一つは非古典論理的なアプローチとなる。

• システムデザインと意思決定システム

The Science of the Artificial(邦題:システムの科学（1969年）は、ハーバート・A・サイモンによる学習科学と人工知能の分野に関する本であり、特に設計理論に影響を与えたものとなる。この本は、人工現象をどのように分類すべきかをテーマにしており、そのような現象が「科学」の領域に属するかどうかについて議論している。

• エージェントシステムにおけるフレーム問題

エージェントシステムにおけるフレーム問題とは、エージェントが新しい情報を取得する際に、環境の状態や変化を適切に把握し、判断を下すことの難しさを指す。これは具体的には以下のようなケースにあたる。

• 万能コンピューター ライブニッツからチューリングへの道筋 読書メモ
• ノイマン・ゲーデル・チューリング 読書メモ
• 精霊の箱 チューリングマシンをめぐる冒険

人工知能技術の数学

• コンピューターの数学の基礎

コンピューターサイエンスの根底には数学がある。例えば深層学習や自然言語処理等に用いられるの機械学習には関数から始まり微分/積分を使った最適化の計算が使われ、人工知能で使われるシンボリックなアプローチでは集合論がベースに式の評価が行われたりしている。それらのデジタルトランスフォーメーション応用やITシステム応用を考える前にそれぞれの基礎的な要素について知識を整理することは重要な作業となる。

• 構造とアルゴリズムと関数 数学から見た要素間の関係

構造とはwikiによると「ひとつのものを作りあげている部分部分の組み合わせかた^[1]。ひとつの全体を構成する諸要素同士の、対立・矛盾・依存などの関係の総称^[2]。複雑なものごとの 部分部分や要素要素の 配置や関係」とある。数学の世界では、この「一つのものを作り上げている部分部分」をなるべく抽象化してそれらの関係を求めるということが基本のアプローチとなる。

数学とは数の学と書くが、古代からそれがすべてかというとそうではなく、例えば幾何学の世界は空間や図形の学問であって必ずしも数の学ではない。遠山はこれらを受けて、数学の起源として人類のもののパターンを認織する能力をあげている。本書によると、このパターンを認織する能力により複雑なこの世界を理解可能な形に切り出して、学問として昇華し数学として成り立たせていると述べられている。これは例えると、1,2,3,…というシンプルな数の概念も、単純に数だけではなく2個のりんご、2個のみかん、2人の人間、2匹の犬等の異なるものの間にある共通の形態、もしくはパターンの抽象化により導き出されたものが2という抽象的な概念であるとしている。

• 形式言語と数理論理学 文字列の組み合わせとしての言語

以前述べたプログラミング言語は、形式言語と呼ばれる言語の一種となる。形式言語とは、もとになる記号の集合（アルファベット等）と，生成規則（文法）から，生成することの出来る文字列（言葉）の集合をいい、数理論理学と呼ばれる数学が理論的基盤となる。

数理論理学は数学の基礎となるもので、集合論や証明論等を用いて数学のありとあらゆるものを定義したり証明したりする学問である。有名なものではZFC公理系を用いた古典数学体系の証明などがある。ここで行われていることは大雑把に言うと、基本パーツを定義して、それらを組み合わせて、大きな世界を構築していくことになる。

• その数式プログラミングできますか?

この本のテーマはプログラミングだが、ほとんどのプログラミング本と異なり、アルゴリズムやコードに加えて、数学証明や、古代から現代までの数学上の発見に関する歴史的経緯が含まれている。

もう少し具体的に言うと、テーマはジェネリックプログラミング(generic programming)となる。ジェネリックプログラミングは1980年台に登場したプログラミングの手法であり、1990年代にC++のTL(Standard Template Library)が開発された。ここで、ジェネリックプログラミングとは、アルゴリズムとデータ構造を設計することに焦点を合わせ、効率を低下させることなく、それらを最も一般的な環境で動作させるためのプログラミング手法となる。

• 集合とは何か 初めて学ぶ人のために 読書メモ

現代数学でどんな役割を果たしているのか？
「集合」抜きに現代数学は展開できない。集合とはなにかという問題は、新しい集合の公理の探究という問題をはらんで、現代数学の最も深い問題といってよい。集合概念がもたらす、深遠な謎、集合論の中に潜むロマンチックな創造の精神、これらを数学の訓練を経ていない人々に説明した名著にカントールの評伝を追加して復刊

人工知能技術の基本的なアルゴリズム

• アルゴリズム思考と問題の分割と問題解決

アルゴリズム思考（Algorithmic Thinking）は、問題解決やタスクの実行において、論理的な手順やアプローチを考える能力やプロセスを指す。アルゴリズム思考を持つことは、さまざまな複雑な課題に対処する際に役立つ重要なスキルとなっている。アルゴリズム思考における「問題の分割」は、大きな問題を複数の小さな部分問題に分けるプロセスであり、このアプローチにより、複雑な問題を扱いやすい単位に分割して、大きな課題がより理解しやすく、それぞれの部分問題を個別に効率的に解決できるようになるものとなる。「問題の分割」は、一般的な問題解決のステップにおける”最初の一歩”とも言える。

• 検索エンジンのマッチングアルゴリズム 検索エンジンでの文字列のマッチング

ジョン マコーミックによる「世界で最も強力な9のアルゴリズム」は現在のコンピューター技術のベースとなる概念をシンプルな表現で説明している中初心者向けの読み物だ。ここで述べられている「アルゴリズム」はソートとかデータ構造とかの一般的意味ではなく、検索エンジンの原理とか、機械学習の原理とソフトウェアがどう動いているかに対して、コンピューターサイエンスの理論に基づいて説明したものとなっている。それらの中からいくつかを紹介したい。

• 検索エンジンのページランクアルゴリズム

検索技術については以前にも概要を述べた。今回はその中でもグーグルを現在の位置に押し上げた検索の革新的なアルゴリズムであるページランク技術について述べる。これは、前回述べた検索エンジンの2つの要素のうちの後半部分の検索結果のランク付け技術になる。

このページランク技術の前提技術としてハイパーリンク技術を用いる。これはクリックすると別のWebページにジャンプできるような機能で、このブログの中にもあるアンダーラインがついた部分となる。このページランクのアイデアは1945年にアメリカのエンジニアのヴァネヴァー・ブッシュジによって書かれた「As We May Think」の中でも「文書を保存して自動的に索引を作ったり」、「連想的なインデクシング、つまり、任意の項目が、ただちに、そして自動的にほかの項目を意のままに選択する機構」等を持つmemexというマシンとしてすでに記述されている。

• データベースのアルゴリズム(1) データベースの一貫性

以前データベースについて利用する視点でまとめたが、今回はもう少しメカニズム寄りの視点で述べてみたい。wikiでのデータベースの定義では「検索や蓄積が容易にできるよう整理された情報の集まり。 通常はコンピュータによって実現されたものを指す。」とある。

本書ではこの蓄積すると言う概念をもう少し深掘りし、データベースが他の情報保存方法と違う最大のポイントとして、データベース内の情報が予め定義された構造を持っている事としている。またもう一つの特徴として「一貫性」をあげている。

• データベースのアルゴリズム(2) リレーショナルデータベース

今回は最後に残った重要なアルゴリズムであるリレーショナルデータベース」について。データベースは構造を持ったデータであり、最もシンプルなものは表の構造を持ったものになる。表の構造はは一つではなく複数に分割した方が効率的な場合がある。

• データ圧縮アルゴリズム(1) ロスなし圧縮

圧縮技術には大きく分けて「ロスなし圧縮」と「ロスあり圧縮」の二つの技術がある。「ロスなし圧縮」は圧縮されても元のデータを完全に再現できるため本来であればこれ一つあればよいが、圧縮率がそれほどよくできないと言う課題を持つ為、「ロスあり圧縮」が利用されている。

「ロスなし圧縮」の基本原理は、データが反復している部分を見つけてそれを省略することにある。

• データ圧縮アルゴリズム(2) ロスあり圧縮

画像情報(JPEG)等に用いられるデータ圧縮のアルゴリズムについての紹介。

• 決定不能性の証明 計算できない問題について

ここではコンピューター(のアルゴリズム)でできないものは何かについて述べられている。ここで言われているアルゴリズムは自動車を完璧に運転したり、学生の成績を見事に評価したりする難しい問題のことではなく、本質的に「計算できない問題」についてとなる。

説明の題材として、ソフトウェアのバグ、クラッシュを検出するチェックツールについて上げている。結論から言うと、どのプログラムツールでもすべてのクラッシュを起こしそうな場所を見つける事が不可能な事は証明できるというものになる。

• 誤り訂正符号アルゴリズム

コンピューターの行う3つの仕事について定義されている。一つが計算を実行すること、二つ目がデータを保存する事で、三つ目がデータを伝送することだ。ソフトウェア的な観点からはデータを保存する機能はデータベース技術に代表され、データを伝送する機能はインターネットを始めとするウェブ技術に代表される。

データの伝送と保存を考えた時に、最も重要なことはそのデータを「完全に正確に」保存/あるいは伝送することにある。それに対してメモリや通信等のハードウェアには必ずノイズや誤動作が付きまとい100%の動作は保証してくれない。その為ソフトウェア的な工夫で「完全に正確に」を担保してやる必要があり、それらを実現する技術の一つが「誤り訂正技術」になる。

「完全に正確に」なデータの保存/伝送手法は、データの冗長度をあげることになる。たとえば「5123」という数字を「five one two three」という形で伝送すると、前者の場合は1文字エラーが生じても元のデータが完全失われてしまうが、後者の場合は例えば「five」の一文字が代わり「fave」となったとしても、前後の情報で「five」に修正できる可能性が高い。

• デジタル署名アルゴリズム

デジタル署名の「署名」は読めるけれど誰にもコピーできないものと定義される。これは誰でもコピーできる「デジタル」とは全く逆の概念となる。このパラドックスに解を提供するものがデジタル署名となる。

デジタル署名はそもそも何のために使われるかと言うと、通常の手紙のように自分が誰かに送るものに署名するのではなく、誰れかから署名されたものが送られてきた時に、コンピューターがチェックするために存在している。

ここで署名に必要な要件として、(1)署名の原本を保管している所は信頼のおける場所であること、(2)署名は第三者には簡単に偽造されないことの2つが挙げられる。

• 公開鍵暗号法アルゴリズム

一番シンプルな暗号の手法は「共有する秘密を持つ」ことから始まる。あるデータを特定の人にだけ送る時、その人とだけ共有している秘密の数字があるとする。(例:322)その時データとして8を送る時、それを加えたものを相手に送り(322+8=400)相手が、送られた数字から共有する番号を引き算すれば良い。

これを更に実用的にするには、共有する数字が簡単に分からないもの、たとえばもっと長い数字を送れば良い。(例3桁の数字を秘密の数字にすると999通りあるが、この程度だとコンピューターは簡単にすべての組み合わせを試すことができる)一般的な暗号アルゴリズムでは送られたデータの30%を計算した桁数が鍵となるので、128ビットの暗号だと38桁で1兆の一兆倍の1兆倍より大きな数字となる。これを現在のコンピューターで計算すると10億年単位の時間がかかるので、安全な方式だと判断できる。

• データソートについて バブルソート、クイックソート、マージソート、選択ソート、ヒープソート

データのソート(並べ替え)はアルゴリズムの基本となる。ソートのアルゴリズムとしては以下に示すようなものがある。

隣接する値同士を比較し入れ替える作業を繰り返す「バブルソート」、ピポットと呼ばれる基準値を定めて、データ群を基準値以上と基準値未満の2つのグループに分ける作業を繰り返すことで要素の入れ替えを行う「クイックソート」、データを最小の単位(単一要素)まで分解し、最小の単位からソート、マージ(併合)を繰り返して要素を並び替える「マージソート」。

• ボードゲームとAI “アルファ碁はなぜ人間に勝てたのか” 読書メモ

AlphaGo（アルファ碁）は、Google DeepMindによって開発されたコンピュータ囲碁プログラムで、2015年10月に、人間のプロ囲碁棋士を互先（ハンディキャップなし）で破った初のコンピュータ囲碁プログラムとなる。コンピュータが人間に打ち勝つことが最も難しいと考えられてきた分野である囲碁において、人工知能が勝利を収めたことは世界に衝撃をもたらし、AlphaGoの登場は単なる一競技の勝敗を越え、人工知能の有用性を広く知らしめるものとなり、世界的AIブームを呼び起こすきっかけともなっていった。今回は、碁を含めたボードゲームとAIとの関連をテーマに述べ、図書「アルファ碁はなぜ人間に勝てたのか」の読書メモと「最強囲碁AI アルファ碁解体新書 深層学習、モンテカルロ木、強化学習から見たその仕組み」の読書メモも併記する。

• オセロゲームの解法アルゴリズムとGNN

オセロゲーム（Othello）は、2人で対戦するボードゲームで、白と黒のディスクを使ってプレイし、プレイヤーは自分の色のディスクを配置し、相手のディスクを挟んで裏返すことで自分の色に変えるのが基本ルールである競技となる。

論理学

• 論理学を作る-第1部論理学を始める 読書メモ

論理学って、こんなに面白かったのか！　出来あいの論理学を天下り式に解説するのでなく、論理学の目的をはっきりさせた上で、それを作り上げていくプロセスを読者と共有することによって、考え方の「なぜ」が納得できるようにした傑作テキスト。初歩の論理学が一人でマスターできる。論理学とは何か〜論理学の人工言語を作る〜人工言語に意味を与える(命題論理のセマンティクス)〜機械もすなる論理学(意味的タブロー)

• 論理学を作る-第2部論理学を広げる 読書メモ

論理学の対象言語を拡張する(述語論理)〜おおっと述語論理のセマンティクスがまだだった〜さらに論理言語を拡張する(PPL)〜さらにさらに論理言語を拡張する(IPL)

• 論理学を作る-第3部論理学をもう一つの目で見る 読書メモ

自然演繹法を使いこなそう(同一性記号を含む自然演繹)〜シンタクスの視点から論理学のゴールに迫る(公理系という発想)

• 論理学を作る-第4部論理学はここから先が面白い 読書メモ

めくるめく非古典論理の世界にようこそ(古典論理は神の論理である。2値原理と排中律のいかがわしさ、多値論理、直観主義論理、古典論理の拡張としての様相論理)〜古典論理にもまだ学ぶことがたくさん残っている(完全武装した述語論理の言語FOL、AFOLの完全性とそこから得られるいくつかの結果、第1階の理論、モデル同士の同型性、第2階の論理)

• 命題論理の充足可能性判定問題(SAT:Boolean SAtisfiability)の概要と実装

命題論理の充足可能性判定問題 (SAT: Boolean Satisfiability) とは、与えられた命題論理式が真となる変数の割り当てが存在するかどうかを判定する問題となる。例えば、「A かつ (B または C) かつ (D または E または F) が真であるような A, B, C, D, E, F の割り当てが存在するかどうか」という問題があった場合、これを命題論理式に変換し、その式が充足可能かどうかを判定するものとなる。

このような問題設定は、例えば、回路設計やプログラム解析、人工知能分野の問題、暗号理論など、多くの応用分野で重要な役割を果たしている。理論的な側面で見ると、SAT問題が解けるアルゴリズムは、「NP完全問題」であることが知られており、現在のコンピュータでは大規模な問題に対しては効率的な解法が見つかっていない。そのため、高速化や、ヒューリスティック探索アルゴリズムの開発などアルゴリズム効率化の為の研究が現在も行われている分野の技術となる。

• EMアルゴリズムを用いた制約充足問題の解法

EM(Expectation Maximization)アルゴリズムは、制約充足問題(Constraint Satisfaction Problem)の解法として使用することもできる手法となる。このアプローチは、欠損データや非完全データのような不完全な情報がある場合に特に有用となる。ここではこのEMアルゴリズムを用いた制約充足問題に関して、様々な適用事例とpythonによる実装について述べている。

• 機械学習とルールの融合としての制約充足による線画のラベル付け

画像情報のラベル付けは、後述する様に様々な機械学習のアプローチで実現できる。今回は、それら機械学習のアプローチとルールベースのアプローチである制約充足によるアプローチの融合について考えてみたいと思う。これらのアプローチは自然言語処理等を用いたテキストデータのラベル付け等にも拡張できるものとなる。

• 論理学で学ぶ数学
• 論理学の基礎
• その理屈証明できますか?
• 解集合プログラミング(Answer Set Programming)-論理プログラミングの歴史とASP概要

人工知能技術の中で複雑な知識情報を構築するための論理プログラミングの参考論文である人工知能学会誌(2010.5)論理に基づく推論研究の動向の中から「解集合プログラミング」より。

1970年代初頭に開発された論理型プログラミング言語Prologは、述語論理に基づく宣言的記述と定理証明に基づく計算手続きを併せ持つ新しい人工知能言語として注目され、1980年代にはエキスパートシステム、自然言語処理、演算データベースなどに幅広く有用されている。

Prologはチューリング完全で高い計算能力を持つ一方で、そのベースとなるホーン節論理プログラムは構文上の制約や推論能力の不足により、現実の知識表現や問題解決への適用は限定的であることも明らかになっている。

• 確率と論理の融合(1)ベイジアンネットとKBMCとPRMとSRL

以前述べたベイズ推定の応用としてベイジアンネットがある。ベイジアンネットは様々な事象間の因果関係（厳密には確率的な依存関係）をグラフ構造で表現するモデリング手法の一つで、故障診断や気象予測、医療的意思決定支援、マーケティング、レコメンドシステムなど様々な分野で利用や研究が行われている。

これを数学的に表現すると、有限個の確率変数X₁,..X_Nをノードとする有効グラフと各ノードに付随する条件付き確率表(conditional probability table:CPT)からなり、X₁,..,X_Nの同時分布 P(X₁=x₁,..X_N=x_n) を以下のようなグラフ構造で表す。

• 確率と論理の融合(2) PLL(確率論理的学習)

前回は北米で発達したSRL(stastical relational learning 統計的関係学習)について述べた。今回はヨーロッパの対抗馬であるPLL(probabilistic logic learning;確率論理学習)について述べる。

前述したPRM(probabilistic relational model 確率的関係モデル)やMLN(Markov logic network;マルコフ論理ネットワーク)等のSRLは関係式や論理式を使い確率モデルを豊かにしようという発想に基づいており、関係式や論理式を使うものの、術後論理を確率によって豊かにすることは直接の目的ではない。一方、人工知能の分野では術後論理による知識表現が古くから研究されており、そこに確率を取り入れて、常に成り立つ論理的知識だけでなく確率的な知識も表現しようとする試みが統計的機械学習がブームになる以前からあった。

• 可能世界と論理学と確率と人工知能と

可能世界(Possible Worlds)の考え方は、哲学や論理学の分野で主に使用される概念であり、現実世界とは異なる可能性のある世界のことを指している。これは、物理的な制約や法則によって制約されず、さまざまな要素や出来事が異なる方法で展開する可能性がある世界であるということを言っている。

これに対して、確率論(Probability Theory)は、不確実性やランダム性を扱う数学の分野であり、事象が起こる確率や結果の予測を行うための枠組みを提供するものとなる。このような観点で考えると、確率論は、現実世界での事象の確率を評価するだけでなく、可能世界での事象の確率を考慮するということもできる。。

人工知能技術(Artificial Intelligence, AI)は、コンピュータシステムが知的なタスクを実行するための技術の総称であり、機械学習、深層学習、自然言語処理、コンピュータビジョンなどのサブ領域に分けられるものとなる。AIは確率論や統計学の手法を活用し、現実世界での事象やデータを解析し、予測や意思決定を行うことが主な目的となる。

• A Probabilistic Model for Time-Aware Entity Recommendation

近年、キーワード検索によって関連する実体をランク付けし、推薦する技術の開発が進められている。また、情報検索（IR）の分野では、クエリの時間的な特徴を考慮して文書の関連性を評価することがトレンドとなっている。しかし、これは文書検索エンジンでは確立された機能となっているが、実体の推薦においては時間の重要性がまだ認識されていない。本論文では、時間を考慮した実体推薦のタスクを導入することで、このギャップを解決する。本論文では、Web上で公開されている様々なデータソースから抽出された実体の異種知識を利用し、実体の推薦に時間を考慮した初の確率的モデルを提案する。提案手法を広範囲に評価した結果、時間を考慮しない推薦手法と比較して、大幅な改善が見られた。

圏論

• 現代思想2020年7月号　 特集＝圏論の世界 ――現代数学の最前線 読書メモ

“矢印”が描きだす、豊穣なる現代数学の最前線。現代数学における最重要分野の一つともいえる圏論。その高度な抽象性と一般性は、物理学や計算機科学、生物学、言語学、美学などあらゆる領域で豊かな威力を発揮しつつある。本特集では圏論の基本からさまざまな応用の実際、さらには哲学的な射程についても紹介・検討することで、今ひときわ注目をあつめる数学的思考法の真髄に迫りたい。

• 数学における抽象性
• モナド
• 型推論

組み合わせ最適化問題と離散数学

• 組合せ最適化の概要と実装の為のライブラリと参考図書

組合せ最適化理論は、輸送計画、スケジューリング、配置、組合せ問題、そして最適化問題など実世界の多くの問題に応用されている理論となる。この問題は、ある個数の要素から構成される集合の中から、制約条件を満たす部分集合を見つけ、その中で最も優れた解を求めることを目的としたもので、ある制約条件の下で最適な解を求める離散的な最適化問題を扱う数学的な手法の一つとなる。

• 数学的決断の技術 意思決定の為の確率的アプローチ

強化学習のアルゴリズムにも用いられる意思決定の為の4つの基準「マックスミン基準」、「マックスマックス基準」、「期待値基準」、複数信念(multiple prior)」がある。

• ゲーム理論の概要とAI技術との融合と実装例

ゲーム理論とは、競争や協力など、相互に影響を与えあう複数の意思決定者（プレーヤー）が存在する場合に、彼らの戦略とその結果を数学的にモデル化することで、最適な戦略を決定するための理論となる。これは主に経済学や社会科学、政治学などの分野で用いられている。

ゲーム理論のアルゴリズムとしては、ミニマックス法、”モンテカルロ木探索の概要とアルゴリズム及び実装例について“でも述べているモンテカルロ木探索、深層学習、強化学習等様々な手法が用いられている。ここでは、R、Python、Clojureでの実装例について述べる。

• 劣モジュラ最適化の概要と適用事例および実装例

劣モジュラ最適化（Submodular Optimization）は、組合せ最適化の一種であり、特定の性質を持つ関数である劣モジュラ関数を最大化または最小化する問題を解決する手法となる。ここでは、この劣モジュラ最適化に関して、様々なアルゴリズム、適用事例、及びそれらの実装例について述べている。

• 動的計画法の概要と適用事例とpythonによる実装例

動的計画法(Dynamic Programming)は、最適化問題を解くための数学的手法の一つであり、特に重複する部分問題を持つような問題に適用される手法を指す。動的計画法は、一度計算した結果を保存して再利用することで、指数的な計算量を劇的に減らすことができるため、効率的な解法を提供する。ここでは、この動的計画法に対して、様々なアルゴリズムとpythonによる具体的な実装方法について述べている。

• 混合整数最適化の概要とアルゴリズム及びpythonによる実装

混合整数最適化は、数理最適化の一種であり、連続変数と整数変数を同時に扱う問題のことを指す。この分野は、さまざまな産業やビジネス領域で現実的な問題を解決する際によく用いられ、混合整数最適化の目標は、目的関数を最大化または最小化する際に、制約条件の下で最適な変数の値を見つけることとなる。ここでは、この混合整数最適化に関して、様々なアルゴリズムと実装について述べている。

グラフデータアルゴリズムと人工知能への活用

グラフはものや状態といった対象同士の結びつきを表すための表現方法となる。多くの問題をグラフの問題に帰着することができるため、グラフに関するアルゴリズムが多く提案されている。

本ブログでは 以下のページにてこのグラフデータの基本的なアルゴリズムである探索アルゴリズム、最短経路アルゴリズム、最小全域木アルゴリズム、データフローアルゴリズム、強連結成分分解をベースとしたDAG、SAT、LCA、決定木等のさまざまなアルゴリズムとグラフ構造をベースとした知識データ処理、ベイズ処理等の応用について述べている。

動的計画法

• 動的計画法の概要と適用事例とpythonによる実装例

動的計画法(Dynamic Programming)は、最適化問題を解くための数学的手法の一つであり、特に重複する部分問題を持つような問題に適用される手法を指す。動的計画法は、一度計算した結果を保存して再利用することで、指数的な計算量を劇的に減らすことができるため、効率的な解法を提供する。ここでは、この動的計画法に対して、様々なアルゴリズムとpythonによる具体的な実装方法について述べている。

• 動的計画法の音声認識への適用

音声認識には用途に応じて幾つかの種類があり、それに応じて方式が異なる。まず発生できる内容の違いでの分類は以下となる。また、使用者の観点からの分類として、特定話者認識と不特定話者認識がある。まず離散単語認識について。使用者が発生する「単語」を認識する認識方法を離散単語認識(isolated word recognition)と呼ぶ。語彙はあらかじめ定められており、使用者があらかじめ発生可能な語彙が何かを把握している必要がある。単語間の関係を考慮する必要がないのでアルゴリズムは簡易になる。

• 動的計画法のアルゴリズムとデータ構造

ある計算式に対して、一度計算した結果をメモに記録しておき、同じ計算を繰り返し行うという無駄を避けつつ、それを再利用することにより効率化を測ることは、プログラミングやアルゴリズムの設計を行う絵腕有効なアプローチとなる。その手法の一つが動的計画法となる。こここで数列からいくつかの数を選んで、それらの和でmが作れるかを全検索的に求める問題について考える。この問題は再帰・分割統治法で解くことが可能であるが、効率は良くない。これに対して動的計画法を適用することで高速化することができる。このアルゴリズムは以下のようになる。

• プランニング問題(1)-動的計画法を用いたアプローチと理論的裏付け

ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習である強化学習の参考図書である機械学習プロフェッショナルシリーズ「強化学習」より。今回は環境が既知の場合の逐次的意思決定問題であるプランニング問題について述べる。

• プランニング問題(2)動的計画法の実装(価値反復法と方策反復法)

ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習である強化学習の参考図書である機械学習プロフェッショナルシリーズ「強化学習」より。前回は環境が既知の場合の逐次的意思決定問題であるプランニング問題の理論的概要について述べた。今回はプランニング問題の実際のアルゴリズムについて述べる。

メタヒューリスティックアルゴリズム

• メタヒューリスティクスの数理　読書メモ

メタヒューリスティクスとは、難度の高い最適化問題を解くための経験的手法（ヒューリスティクス）を有機的に結合させたものであり、最近では、実務的な問題を楽に解くためのフレームワークとして、実務家の間でよく用いられる最適化アルゴリズムとなっている。実際問題を解くとき、ある程度のプログラミングの腕と、メタヒューリスティクスの選択眼と、設計のコツさえつかんでいれば、比較的短時間でロバスト（頑強）な解法を設計できる。

• 粒子群最適化(PSO)の概要と実装について

粒子群最適化（Particle Swarm Optimization、PSO）は、鳥や魚の群れの行動をモデル化し、自然界の群れの動きに着想を得たもので、進化計算アルゴリズムの一種であり、複数の個体が群れを形成し、最適解を探索する手法となる。PSOは、局所解に陥りやすい遺伝的アルゴリズムよりも、より広範な探索空間を探索できることが特徴となる。また、他の進化計算アルゴリズムよりも計算時間が短く、高速に最適解を見つけることができることがある。PSOは、機械学習や最適化問題の解決に広く用いられており、多数の研究や実用例が報告されている。

• オントロジーとPSO

前回は類似性を表す方程式のセットを用いた反復的な類似性計算アプローチについて述べた。今回はそれらを更に拡張した最適化アプローチについて述べる。今回はそれらの中からまず、期待値最大化と粒子群最適化の2つの手法について述べる。

• オントロジーと遺伝的アルゴリズム

前回はアライメントのソートのための機械学習について述べた。今回はマッチングのチューニングアプローチについて述べる。