機械学習の数理②(パラメーター推定) （書きかけ）

機械学習の数理 機械学習 最適化問題 最尤推定 数学 教師なし学習 情報理論 勉強 統計学

はじめに

授業で勉強したことをまとめていきます。 前回はこちら
slimelimestech.hatenablog.com

次回はこちら

目次

2. パラメーター推定

\mathcal{X}：領域
X： \mathcal{X}上の確率変数
n：自然数
\theta：実数値パラメータ
\Theta：実パラメータ空間
\mathcal{P = \{ p(X^n;\theta)：\theta \in \Theta\}}：パラメトリックな確率分布のクラス
X^n = X_1,...,X_n：観測データ列
x^n = x_1,...,x_n：観測データ列

問題設定：
与えられたx^nから、\thetaを推定する。

2.1 最尤推定

尤度関数
\mathcal{L}(\theta)=p(x^n;\theta)=\prod_{i=1}^n p(x_i;\theta)を\thetaについて最大化する。

対数尤度関数 L(\theta) = log p(x^n;\theta)
\hat{\theta}=arg \max _{\theta \in \Theta} log p(x^n;\theta)を最尤推定量という。(Maximum Likelihood Estimator)

最尤推定量はなぜ良いか

以下の定理が成り立つため
定理 1.1 最尤推定量の一致性
定理 1.2 最尤推定量の漸近正規性及び有効性

2.2 ベイズ推定

p(\theta)：\thetaの事前確率
x^n = x_1,...,x_n：観測データ列
p(\theta|x^n)：\thetaの事前確率

定理1.3 ベイズの定理
p(\theta|x^n) = \frac{p(\theta|x^n)p(\theta)}{\int_\Theta p(\theta';x^n) d\theta'}

\hat{\theta} = \int_\Theta \theta p(\theta|x^n)d\thetaをベイズ推定量という。(Bayesian Estimator)

2.3 線型回帰

y \in \mathbb{R}：目的変数
x \in \mathbb{R}^d：説明変数
\theta \in \mathbb{R}^d：パラメータ
\epsilon 〜 \mathcal{N}(0, \sigma^2)：誤差\epsilonは、平均0、分散\sigmaの正規分布に従う
線型回帰モデルとは以下のような関係のモデルである。
y = \theta^T x + \epsilon

2.4 MAP推定

\hat{\theta} = arg \max_ \theta p(\theta|x^n)をMAP推定量という。(Maximum A Posterori Estimator)

2.5 スパース正則化

LASSOの最適化アルゴリズムについて説明する。

2.6 勾配降下法

解析的に解けない場合の最適化手法

2.7 ロジスティクス回帰

機械学習の数理①(機械学習の捉え方)

機械学習の数理 情報理論 最適化問題 機械学習 最尤推定 数学 教師なし学習 勉強 特徴量 統計学

はじめに

授業の復習用に勉強したことをまとめていきます。

1. 機械学習の捉え方

1.1 機械学習の捉え方

学習は以下の7つの要素の組み合わせと考えることができます。

  • データのタイプ
  • 教師あり or 教師なし
  • プロセスの型（Batch or Online）
  • 知識表現
  • 学習の目的
  • 学習アルゴリズム
  • 学習成功の評価基準

それぞれの要素についてどのようなものがあるのか見ていきます。

データのタイプ

  • 離散値、連続値
  • ベクトル型、マトリックス型、テンソル型、ネットワーク型
  • 一様的、非一様的 (定義は？)
  • 静的、ストリーム型、時系列型
  • 欠損値のあり、なし

教師ありかなしか

プロセスの型

  • バッチ学習 x^n = x_1, x_2,...,x_nが一括で与えられ、x^nを用いて、 P(x)を推定

  • オンライン学習 データが逐次的に与えられ、各時刻tに置いて、推定結果を逐次的に更新する。

知識表現

全ての知識表現(モデル)は確率分布として表現できる。
教師なし学習では、 P(x;\theta), P(x;\theta, M)
教師あり学習では、 P(y|x;\theta), P(y|x;\theta, M)

知識表現＝モデルクラス＝仮説空間(hypothesis class)

\Theta _M：モデルMに付随する実パラメーター空間

潜在表現モデル

P(X) = \sum_Z P(X, Z) = \sum_Z P(Z)P(X|Z) - 用語
X：顕在変数、 Z：潜在変数（状態変数）、P(X)：周辺化モデル、P(X, Z)：完全変数モデル

Ex. 混合分布、 トピックモデル、関係データモデル、状態空間モデル、NMF、RBM, ニューラルネットワーク etc.
★周辺化モデルには非正則性がある（パラメータが一意に決定しない）が、完全変数モデルは正則
機械学習で用いる重要知識表現は多くが潜在変数モデル

学習の目的関数

推定...未知の真の分布を当てる

\thetaの推定をパラメーター推定、 Mの推定をモデル推定という。

予測...将来のデータの出方（予測分布）を求める

P(X|x^{t-1})：時刻tにおける予測分布、ただしx^{t-1} = x_1, ...,x_{t-1} 必ずしもパラメーター推定やモデル選択は必要ではない。(Baysiam averaging)

経験損失関数

学習アルゴリズム

学習目的関数の最小化を効率的に解くための手続き、収束の速さ、計算効率、解の精度で良し悪しを評価

パラメーター推定

解析解を求めることが難しいことが多いので、連続最適化を行う。
連続最適化のアルゴリズムはモデル依存

モデル推定、状態推定

数え上げが難しい場合が多い - 離散最適化
動的計画法
変分ベイズ法
枚挙法
連続緩和
etc.

集団学習による精度強化

  • Boosting
  • Bagging
  • Aggregation
  • Random Forest
  • etc

学習成功の評価基準

学習目的関数を最適化することは一体何を学習しているのか？メタな視点から学習アルゴリズムを評価する必要がある。

  • 可読性が高い知識表現(決定木、トピックモデル、etc)が学習精度が高いとはかぎらない。
  • 学習精度の高い知識表現(CNN、RNN、etc)は一般に可読性が低い。
  • 可読性の高い or 学習精度の高い知識表現ほど一般に学習時間がかかる。

理論的評価フレームワーク

  • Batch学習
    • PAC(Probably Approximately Correct)学習
    • 汎化損失、統計的リスク
  • On-line学習
    • 累積予測損失 \sum_{t=1}^{n} L(x_t：学習結果_t) L:損失関数
    • リグレット
      \max_{x_1...x_n} \{ \sum_{t=1}^{n} L(x_t：学習結果_t) - \min_{P_1,...,P_n} \sum_{t=1}^n L(x_t：P_t) \} いかに小さく抑えられるか？、モデルクラスに依存。

実験的評価フレームワーク

学習結果の性能を、訓練データと同じ情報源から発生する異なるテストデータに対して経験的に評価する。

  • ROC(Receiver Operating Characteristic)曲線
  • Precision-Recall曲線

論文読み RecipeGPT: Generative Pre-training Based Cooking recipe Generation and Evaluation System (2019)

勉強 機械学習 AICooking 論文読み ファインチューニング GPT 自然言語処理 Multi-Field-Learning

1.論文の概要

新しいレシピの生成及び評価システムの研究。

  1. 与えられたタイトルと材料から手順の生成
  2. レシピのタイトルと手順から材料の抽出ができる。

pre-trained な GPT-2をファインチューニングして、レシピデータセットに適用したテキストベースな手法。

元論文：https://arxiv.org/abs/2003.02498

DEMO: https://recipegpt.org/

2. 問題設定と解決した点（先行研究と比べてどこが凄い？）

レシピのtext自動生成は、レシピ検索の制限を超えられる。レシピ生成はいままであまりなかった。この研究では、GPT-2を用いて、レシピの自動生成を行い、実際にサービスとして公開まで持っていった。

3. 技術や手法のキモ

手法：GPT-2のファインチューニング データセット：Recipe 1M data データの前処理：いくつかの材料を正規化(レシピでは材料が細かく書かれることが多いので、まとめる。)、料理に関係ない文章の削除。 Multi-Field Learning and Generation、材料のシャッフル、タイトル、bytepair encodeing + GPT-2

4. 主張の有効性検証

評価方法

Ingredient generation

F1 score between (正解ラベルと生成したラベル)

Instruction generation

BLUE, ROUGE(正解ラベルと生成したラベルで), NTED(normalized tree distance)

5. 議論すべき点

よくわからず、そもそもdiscussionがないんだけど。

6. 次に読むべき論文は？

ワトソン気になる

7. 関連研究

  • Generating Personalized Recipes from Historical User Preferences.
  • Inverse Cooking: Recipe generation from food images.
  • IBM Chef Watson: A big data approach to computational creativity: The curious case of Chef Watson.

8. 補足（Appendix）

GPT: SOTAの文章生成モデル
Byte Pair Encoding (BPE) :テキストの圧縮率を目的関数にして、貪欲的に分割を決定していくサブワード分割アルゴリズムです。
著者のブログ：https://medium.com/@audreyleduc/recipe-generation-with-gpt-2-37dd7c267ac6
NTED(normalized tree distance): INSERT, REMOVE, REPLACEを何回やったら一致するかの回数/全ノード数(リーベンシュタイン距離みたいなものか)
RecipeScape: An Interactive Tool for Analyzing Cooking Instructions at Scaleに詳細あり

Webデザインまとめ

勉強 webサービス webデザイン

はじめに

この記事では、ウェブデザインの思考法という本を参考にして、ウェブデザインについてのいろはをまとめます。この記事を読んで、ウェブデザインに興味を持った方、もっと詳しく勉強してみたいと思った人は、是非本を買ってください。 (ここにそのうちamazonのリンクを貼る)

目次

1. ウェブデザインの定義

デザインの定義

定義：

  • マテリアル・・・料理の材料（食材）やインテリアの材料（布や木）、webにおいては、写真や原稿などいわゆる素材と呼ばれるようなもののこと。
  • コンテンツ・・・レストランにおける料理や部屋のインテリアといった場の主役となるもの。
  • コンテナ・・・マテリアルをコンテンツにするために色や形、動きをあたえる加工や枠のこと。

    デザインするとは、マテリアルにコンテナをあたえて、コンテンツを生み出すという行為のことをさします。


デザインの例：スタバのコーヒーカップ

デザイン行為

  • 中の飲み物がこぼれにくくなるように蓋を配置。
  • 素材を持ちやすく、熱伝導性の低いものにする。
  • 表面にカフェのロゴを入れ、配色を施す。

デザインによってひこ起こされる変化・反応

  • 持ちやすい、飲みやすい
  • おしゃれ、かわいい



デザインによって、マテリアルは機能性（使いやすい、わかりやすいなど）と情緒性（おしゃれ、かわいい、かっこいいなど）が加わったコンテンツに生まれ変わると言えます。
したがって、ウェブデザインは、次のように定義することができます。

ウェブデザインとは、何らかの問題解決のために、材料であるマテリアルにコンテナを通じて機能性と情緒性を与えて、ユーザーインターフェース上にコンテンツを設計することである。
※ユーザーインターフェース：ユーザーがアプリケーションとやり取りをする部分のこと。

2. デザインの機能性

ウェブアプリケーションの機能性とは、平たく言うと、そのアプリケーションの見やすさ、使いやすさ、分かりやすさなどを言います。デザインすることの目的の一つは、デザインによってウェブアプリケーションの機能性を向上させることです。ここでは、機能性を6つの観点に分類してそれぞれについて見ていきます。機能性によっては、おしゃれさやかっこよさといった情緒性とトレードオフの関係にあるものもあるので、注意が必要です。

2.1 誘目性・視認性の向上

誘目性・視認性とは、サイトをパッと見たときの目的のコンテンツの見つけやすさのことです。
具体的な実践方法としては、以下の方法があります。

  • サイズの調整やアイコンの配置、点滅などの効果を入れることによる視線の誘導
  • 背景と文字色のコントラストの調整
  • 文章を枠線で囲う。

2.2 情報理解の促進

情報理解の促進とは、アプリケーション内の情報の表示を構造化し、サイトの分かりやすさを向上させることです。
具体的な実践方法としては、以下の方法があります。

  • 関係性の強い情報を近くに、逆に関係性の弱い情報は遠ざける。
  • まとまりのある情報を枠で囲って、グループ化する。
  • 適切な文字間隔、行間、パディングの使用による要素間距離の最適化
  • 文字情報を図や表で表現することによる情報の視覚化
  • 数字や漢字など、目立たせたい箇所だけ大きくするなどして、情報の強弱を視覚化

2.3 操作性の実現・向上

操作性の向上によって、ユーザーは望んでいる情報に容易にアクセスできるようになり、利用満足度が向上します。
具体的な実践方法としては、以下の方法があります。

  • 例えば、ボタンなら影をつけるなど、その要素が操作可能であるということをユーザーに気づいてもらえるように工夫します。
  • サイズや位置などを工夫して、操作するのにストレスがないようにします。
  • 画像を多用しない、容量に気を配る、動的な処理を検討するなどによって、軽量化に努め、レスポンス時間を早くし、ユーザーの待機時間を少なくします。
  • 適切なラベル、誤解のないフォルム、ミスタッチの生まれない配置などの工夫によって、ユーザーの誤動作を防止します。
  • 別の操作により現在の操作を中断したときに、後から復帰できるような設計を採用し、操作に対するハードルを下げます。
  • 処理中なのか処理が終わっているのか、後どれくらい操作が必要なのか、などのステータスをユーザーに伝達をすることで安心感を与えます。

2.4 習熟度の向上

習熟度の向上とは、ユーザーがサービスを利用するのに必要な学習コストを小さくすることです。覚えにくいものより覚えやすいもの、覚えやすいものより覚えなくていいものを目指します。
具体的な実践方法としては、以下の方法があります。

  • 同じ役割のパーツには、同じデザインを施し、サービスの中で一貫性を保ちます。
  • 画像の解像度や大きさの変更、トリミング、明暗の調整などで不自然にならない程度に画像を加工することによる画像表示の工夫
  • 黄金比や白銀比のシステムの導入などによる審美性の追求
  • 女性向けならピンクやベージュといった配色をベースにするなどの文化的背景への依拠
  • 一般的なサイトの構成に追従する、多数派への追従

2.5 アイデンティティの体現

アイデンティティの体現とは、端的に言うとデザインにそのサイトらしさを加えることです。これにより、識別性の向上、ブランディング化による満足度の向上というメリットがあります。
具体的な実践方法としては、以下の方法があります。

  • 画面の目立つところにロゴを配置し、帰属を明確にする。
  • キャラクターを配置することで、そのキャラクターのファンに対しての誘引性を高める。
  • サービスの理念やイメージなどのモチーフ化（例：背景を商品の写真にする、ボタンのデザインを料理教室っぽいものにさせるなど）
  • テーマカラーやレイアウトテンプレート、オリジナルフォントといったレギュレーションの適用

2.6 可変性の維持

ウェブアプリケーションでは、開発や運用において頻繁に更新・変更作業が発生します。また、インテリアやファッションと違い、ユーザー側の閲覧、利用環境が一定ではないという特徴があります。そこで、デザインにおいても可変的であることが求められます。 具体的な実践方法としては、以下の方法があります。

  • デバイスフォントの使用やcssの利用による画像の削減によるメンテナンス性の向上
  • レスポンシブデザイン
  • コンテンツが増えても対応できるような伸縮性の担保
  • 要素の入れ替え、組み換えの容易化

3. デザインの情緒性

ウェブデザインにおいて情緒性は、6つ軸に分類することができます。サービスの性質、ターゲットの属性に合わせて、この６つの軸の強弱をイゴライザーのように調整します。ここでは、6つの軸についてそれぞれ見ていきます。

3.1 装飾性

例:googleのサイトなど

シンプル(装飾性:少ない)

要素の数は少なく最小限で、影や立体処理といった意匠も少ない。

印象
  • クリーン
  • コンテンツを利用する上での手がかりが乏しくなる
  • 画面の余白が目立ち情報が乏しい印象を与えかねない

デコラティブ(装飾性:多い)

要素の数は多く、影や立体加工といった意匠も強く施されている。

印象
  • ユーザーの目を引きやすい。
  • 過度な装飾はユーザーに雑多な印象を与えかねない。

3.2 成熟度

爽やか、若々しい(成熟度:少ない)

寒色系で明度の高い配色、太いゴシック体や意匠の少ないデザイン

印象
  • 新鮮で清潔な印象
  • 明朗で希望に溢れている

円熟した、伝統的な (成熟度: 多い)

ゴールド系の配色、明朝体や縦書きの採用などが特徴

印象
  • ベテラン、大御所
  • 重厚で高級感がある
  • 時間の積み重ねを感じる

3.3 態度

真面目(態度: 硬い)

情報を正しく伝えられるようなベーシックなレイアウト。

印象
  • きっちりしている。
  • 画一的である。没個性的である。

ポップ、カジュアル(態度:柔らかい)

豊富なアイコンやイラストの使用、多様な配色、画一的でないレイアウト

印象
  • 親しみやすい。
  • 賑やかで楽しい。

3.4 愛嬌

スタイリッシュ、スマート(愛嬌:少ない)

大きく配置した写真、欧文を取り混ぜたタイポグラフィ設計、ソリッドさを強調した矩形

印象
  • シャープで洗練されている。
  • 自信や余裕が感じられる。

キュート、プリティ(愛嬌:多い)

暖色系の配色、丸みを帯びたシェイプやフォント

印象
  • 女性らしい
  • 子供っぽい

3.5 品性

アクティブ、ダイナミック(品性:少ない)

太いフォントや枠線、高い配色コントラスト、整列線を外したレイアウト。コンバージョンを求めらるようなランディングページやバナーと相性が良い。

印象
  • 大胆で積極的である
  • 立体的である

静か、落ち着いている(品性:多い)

使われている色相は少なく、要素はグリッドに沿ってしっかりと並べられる。線、ウェイトは細い。

印象
  • 上品
  • 平面的である。

3.6 温度感

冷たい、無機質(温度感:低い)

イメージ画像が少なく、情報密度が高い。平坦なテクスチャ。管理画面や業務用アプリケーションと相性が良い。

印象
  • 人工的である。
  • 実用的である。

暖かい、開放的(温度感:高い)

自然物を模した要素の配置、緑・茶色系の配色、手書きフォントなどの利用。不揃いな配置。ゆったりとしたレイアウト。飲食、美容業界と相性が良い。

印象
  • 有機的である。 -リラックスしている。

4. デザイン要素の分類

デザイン作業によって、機能性、情緒性が生み出される対象をデザイン要素といいます。デザイン要素には、以下の8つがあります。

  • 配色
  • タイポグラフィ
  • イメージ(写真、イラスト)
  • アイコン
  • シェイプ
  • デコレーション
  • インタラクション、アニメーション
  • レイアウト

5. 戦略・要件定義フェーズにおけるデザイン作業とデザインコンセプトの立案方法

戦略・要件定義フェーズにおけるデザインの進行方向は、主に以下の4つのプロセスからなります。

  1. 調査、分析
  2. デザイン基本方針立案
  3. デザイン詳細方針立案
  4. 可視化

ここでは、それぞれのプロセスについて簡単に説明します。

5.1 調査、分析

調査、分析では、デザイン作業の制限、前提となりうる情報を、調査分析し整理します。具体的には、以下の項目を確認します。

  • 対象クライアントとその特徴
  • 対象の業界
  • 種類
  • 対象のユーザー
  • デバイス
  • デザインの目的、背景、課題
  • その他

5.2 デザイン基本方針立案

デザインの前提条件をまとめたら、まずは大きな方針としてデザイン基本方針を策定します。具体的には、デザインの前提条件を考慮しながら、プロジェクトにおける7つの機能性、6つの情緒性について、あるべき方向性を検討、策定します。順番としては、以下のように行うと良いでしょう。

  1. 機能性についてあるべき方向性を記載、策定する。
  2. 情緒性についてあるべき方向性を記載、策定する。
  3. 上記二つをまとめて、デザイン基本方針をつくる。

5.3 デザイン詳細方針立案

デザイン詳細方針立案では、8つのデザイン要素のそれぞれの属性はどうあるべきなのか、どのようなことに気をつけるべきなのか、デザイン基本方針で定めた機能性と情緒性に紐付ける形で記載していきます。具体的なタスクもここで切り出すといいでしょう。

5.4 可視化

作成したデザイン詳細方針案をもとに、具体的にビジュアルサンプルを作成し、立案した方針を可視化します。可視化したデザインサンプルを元にスーテクホルダー内で確認をして、デザイン方針が正しいかどうかの確認をします。場合によっては、前のプロセスに立ち戻り、再検討をする必要も生じます。

箱玉系で使われるcrystal base論について

crystal base論 箱玉系 数学 離散数学 表現論 勉強 Ball-Box System crystal

crystal base論は量子群U_q のq = 0の表現論として、構築されたものです。この記事では、箱玉系(ball-box system)の基本的な要素であるcrystalという代数構造と組み合わせ数Rについて量子群U_q(sl_{n+1}) の場合について説明します。

1. Crystalの定義

U_q = U_q(sl_{n+1})のcrystalの定義をします。 Iを添え字集合とします。crystal Bとは、集合Bと写像

\begin{aligned} wt:B \rightarrow \bar{P} \\ \tilde{e_i}, \tilde{f_i}:B \rightarrow B \cup \{ 0 \} \\ \varepsilon _i, \varphi _i : B \rightarrow \mathbb{Z} _{\geq 0} (i \in \bar{I}) \end{aligned}


の集まりで以下の性質を満たすものです。

  1. b \in Bかつ\tilde{e_i}b \in B ならばwt(\tilde{e_i}b) = wt(b) + \alpha_i
  2. b \in Bかつ\tilde{f_i}b \in B ならばwt(\tilde{f_i}b) = wt(b) - \alpha_i
  3. \varphi _i(b) = max ｛ m \geq 0 | \tilde{f_i} ^m (b) \neq 0 ｝
  4. \varepsilon _i(b) = max ｛ m \geq 0 | \tilde{e_i} ^m (b) \neq 0 ｝
  5. \varphi _i(b) - \varepsilon_i(b) = ( h_i, wt(b))
  6. \tilde{e_i}(0) = \tilde{f_i}(0) = 0
  7. b, b' \in Bならばb'=\tilde{f_i}(b) とb=\tilde{e_i}(b')は同値

wt(b)をbのウェイトといいます。\tilde{e_i},\tilde{f_i} を柏原作用素といいます。その作用、すなわち、7.の状況をb \xrightarrow{i} b'と表し、これを頂点b からb'へ向かう「色」iの矢印と見立てれば、Bは色付き有向グラフとして図示されます。これをcrystalグラフといいます。crystalグラフの一つの頂点から色iの矢印は1つ出るか(\tilde{f_i} \neq 0)、出てないか(\tilde{f_i} = 0)のどちらかです。同様に、7.により、各頂点には色iの矢印は1つ入るか(\tilde{e_i} \neq 0)、入らないか(\tilde{e_i} = 0)のどちらかです。

例

U_q (sl_2)の例を挙げます。この時\alpha_1 = 2 \bar{\Lambda}です。

  • B(\bar{\Lambda_1})
    B(\bar{\Lambda_1})のcrystalグラフは次のように表されます。
    \fbox{1} \xrightarrow{1} \fbox{2}

  • B(2\bar{\Lambda_1})
    B(\bar{\Lambda_1})のcrystalグラフは次のように表されます。
    \fbox{1}\fbox{1} \xrightarrow{1} \fbox{1}\fbox{2} \xrightarrow{1} \fbox{2}\fbox{2}

    q=0の場合（箱玉系の場合に相当）

    q=0に絞ると上の定義は少し簡単にできます。 Iを添え字集合とします。この時crystal Bとは、集合Bと写像\tilde{e_i}, \tilde{f_i}:B \rightarrow B \cup { 0 }の集まりで、以下の性質を満たすものです。

  • 任意のb \in Bと任意のi \in Iに対して、\tilde{e_i}^n(b) = \tilde{f_i} ^n(b) = 0を満たすn > 0が存在する。
  • \tilde{e_i}(0) = \tilde{f_i}(0) = 0
  • b_1,b_2 \in Bに対して、\tilde{f_i}(b_1) = b_2が成り立つことと、\tilde{e_i} (b_2) = b_1が成立することは等しい。
    （ウェイト(wt)に関する部分の定義を省きました。）
    また、b \in Bに対して、
\begin{aligned} \varepsilon _i(b) = max ｛ m \geq 0 | \tilde{e_i} ^m (b) \neq 0 ｝\\ \varphi _i(b) = max ｛m \geq 0 | \tilde{f_i} ^m (b) \neq 0 ｝ \end{aligned}

を定めます。
箱玉系を構成するにあたって、\hat{sl} _ {n+1}と結びついている、crystalB _ lを使います。そしてn \in \mathbb{Z} _ {1 \leq n}のもとで、I=｛0,1,...,n｝をとります。
この時集合B_lは、次のようにして与えられます。

\begin{aligned} B_l = \left\{ (x _ 1,..., x _ {n+1} ) \in \mathbb{Z} ^ {n+1} | x _ i \geq 0, \sum ^ {n+1} _ {i=1} x _ i = l) \right\} \end{aligned}

B_lの各元は、ヤング盤によっても表現することができます。それぞれのx=(x _ 1,...,x _ {n+1}) \in B _ lについて、長さlの一列の半標準盤を対応させられます。例えば、n=2,l=2とすると、そのcrystalは、

\begin{aligned} B_2 = \left\{ (2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1) \right\} \end{aligned}

となります。これはヤング盤では、
B_2=｛[1][1], [2][2], [3][3], [1][2], [1][3], [2][3]　｝ と表せます。（各マスがボールを表していて、マスの中の数字が、対応するボールは今何マス目にいるのかということを表しています。） B_lは、l-foldの対象テンソル表現の基底のラベリングした 集合です。
x=(x _ 1,...,x _ {n+1}) \in B _ lで\tilde{e_i},\tilde{f_i}:B _ l \rightarrow B _ l \cup \{ 0 \} (0 \leq i \leq n)を

\begin{aligned} \tilde{e_i}(x) = (...,x _ i+1,x \ {i+1} -1,...), \tilde{f_i}(x) = (...,x _ i -1,x _ {i+1} +1) \end{aligned}

で定める写像とします。これらの写像はB_lからB_lに移るか、あるいはそれ以外のところに移ります。それ以外のところに移った時、\{ 0 \}に移ったと解釈します。
[tex:\varepsilon i(b),\varphi i(b) :B \rightarrow \mathbb{Z} (0 \leq i \leq n)]は、その定義により、 x=(x _ 1,...,x _ {n+1}) \in B _ lで\tilde{e_i},\tilde{f_i}:B _ l \rightarrow B _ l \cup \{ 0 \} (0 \leq i \leq n)を

\begin{aligned} \varepsilon _i(x) = x _ {i+1},\varphi _i(x) = x _ i \end{aligned}

のように表せます。（[tex:\varepsilon i(x)]は、[tex:\varepsilon i ^ m (x)]が0にならないように作用させ続けられる最大の回数をm表します。）
さて、任意の2つのcrystalB,B'に対して、テンソル積を定義することができます。集合としては、B \otimes B'は直積となります。しかし、これは crystal構造を保っています。任意の(x,y) \in B \times B'について、B \otimes B'の要素として、x \otimes yをとることができます。x \otimes 0 = 0 \otimes y = 0とします。
x \otimes y \in X \otimes X'に対して、写像[tex:\varepsilon i(x),\varphi i(x),\tilde{e_i}(x), \tilde{f_i}(x)]は次のようにして与えられます。

\begin{aligned} \varepsilon _i(x \otimes y) = \varepsilon _ i(x) + ( \varepsilon _i(y) - \varphi _i(y)) _ + \\ \varphi _i(x\otimes y) = \varphi _i(x) + (\varphi _i(y) - \varepsilon _i(y)) _ + \\ \\ \tilde{e_i}(x\otimes y) = \left\{ \begin{array} \tilde{e_i}(x) \otimes y 　\mbox{if}　 \varphi _i(x) \geq \varepsilon _i(y) \\ x \otimes \tilde{e_i}(y) 　\mbox{if} 　\varphi _i(x) < \varepsilon _i(y) \end{array} \right. \\ \\ \tilde{f_i}(x\otimes y) = \left\{ \begin{array} \tilde{f_i}(x) \otimes y 　\mbox{if}　 \varphi _i(x) > \varepsilon _i(y) \\ x \otimes \tilde{f_i}(y) 　\mbox{if} 　\varphi _i(x) \leq \varepsilon _i(y) \end{array} \right. \\ \end{aligned}

ただし、(x)_+ = max(x,0)とします。
このように定義してあげると、テンソル積は、crystalの定義を満たします。 (実際に1.~3.が成立します)
この構成方法を複数回用いることで、（テンソル積は結合法則が成り立つため）2つよりも多いcrystalのテンソル積も定義することができます。
crystalは、crystalグラフといわれる色付き有向グラフで表現することができます。
以下の図では、\tilde{f_i}を\xrightarrow{i}で表しています。公理3.より、\tilde{f_i}と\tilde{e_i}は等価であるので、\tilde{f_i}についてのみ表します。

例

  • B_1
    [1] \xrightarrow{1} [2] \xrightarrow{0} [1]

  • B_2
    [1][1] \xrightarrow{1} [1][2] \xrightarrow{1} [2][2] \xrightarrow{0} [1][2] \xrightarrow{0} [1][1]

  • B_1 \otimes B_2
    [1] \otimes [1] \xrightarrow{1} [2] \otimes [1] \xrightarrow{1} [2] \otimes [2] \xrightarrow{0} [1] \otimes [1] \xrightarrow{0} [1] \otimes [1]

2. 組み合わせR

一般にcrystalB \otimes B'とB' \otimes Bは同じ構造をしています。（同型です。） 組み合わせRとは、柏原演算子の作用で結びつけられたB \otimes B'とB' \otimes Bの間の全単射のことです。言い換えると、組み合わせRは次のような関係を満たす写像B \otimes B' \rightarrow B' \otimes Bのことを指します。

\begin{aligned} R(\tilde{e_i}(x \otimes y)) = \tilde{e_i}( R(x \otimes y)),　 R(\tilde{f_i}(x \otimes y)) = \tilde{f_i}( R(x \otimes y)) \\ (2.1) \end{aligned}

特殊な場合を除き、組み合わせRは上の条件を課すことで一意に決まることが知られています。
定義より、R _ {BB'} \circ R _ {B`B} = Id _ {B \otimes B'} が成立します。

\hat{sl} _ {n+1}crystal 組み合わせRに対して、区分線形な式が存在します。与えられたx = (x _ 1,...,x _ {n+1}),y=(y _ 1,...,y _ {n+1}) \in \mathbb{Z} ^ {n+1}に対して、\tilde{x} = (\tilde{x} _ 1,...,\tilde{x} _ {n+1}),\tilde{y}=(\tilde{y} _ 1,...,\tilde{y} _ {n+1}) \in \mathbb{Z} ^ {n+1}を次のように定めます。

\begin{aligned} \tilde{x} _ i = x _ i - P _ i(x,y) + P _ {i-1}(x,y), \\　 \tilde{y} _ i = y _ i + P _ i(x,y) - P _ {i-1}(x,y), \\ P _ i(x,y) = \max _ {1 \leq k \leq n+1} \left( \sum _ {j=k} ^ {n+1} x _ {i+j} + \sum _ {j=1} ^ {k} y _ {i+j} \right) \\ (2.2) \end{aligned}

命題2.1

与えられたx \in B _ l, y \in B _ {l'}に対して、\tilde{x},\tilde{y} \in \mathbb{Z} ^ {n+1}を上のように定めます。すると、次の1.,2.が成立します。
1. 全ての要素は非負です。ゆえに\tilde{x} \in B _ l,\tilde{y} \in B _ {l'}です。
2. R(x \otimes y) = \tilde{y} \otimes \tilde{x}によって、写像R:B _ l \otimes B _ {l'} \rightarrow B _ {l'} \otimes B _ lを定義します。すると、この写像は、\hat{sl} _ {n+1}crystalの組み合わせRとなります。（すなわち、R(\tilde{e_i}(x \otimes y)) = \tilde{e_i}( R(x \otimes y)),　 R(\tilde{f_i}(x \otimes y)) = \tilde{f_i}( R(x \otimes y))が満たされます。）

この命題は、後述する組み合わせRに関するアルゴリズムを上の式(2.1)と等価であることを示すことで証明できます。
組み合わせ数Rに関する式は、\sum _ {i=1} ^ {n+1} (x _ i - \tilde{x} _ i) =\sum _ {i=1} ^ {n+1} (y _ i - \tilde{y} _ i) = 0という条件の下で次の関係式によって特徴で付けられます。

\begin{aligned} x _ i + y _ i = \tilde{y} _ i + \tilde{x} _ i,　max(-y _ i,-x _ {i+1})　// (2.3) \end{aligned}

この関係は、(2.1)の式の結果として出てくるものです。

参考文献

ベーテ仮説と組み合わせ論　国場敦夫 Integrable structure of box-ball systems:crystal, Bethe ansatz, ultradiscretization and tropical geometry

教師なし学習(クラスタリング問題）の数理的な問題設定

教師なし学習 機械学習 最適化問題 勉強 クラスタリング ハードクラスタリング ソフトクラスタリング

教師なし学習の数学的な問題設定

教師なし学習の問題としては、２つの問題設定があります。

(\bf{x} _ i, z _ i) (ただしi = 1,...,n)という標本の集合が存在するとします。この集合の各要素について、\bf{x} _ iは観測可能だが、それに対応するz _ iは観測できません。このような状況下で、z _ iを推定するというのが教師なし学習の１つ目の問題です。また、母集団に存在する未知の\bf{x}についても、それに対応するzを予測するというのが２つ目の問題です。

1. クラスタリング問題

1.1 ハードクラスタリング

z _ i \in \{ 1,...,K \} のときクラスタリングまたはハードクラスタリングといいます。ハードクラスタリングは、教師変数のない他クラス分類問題と言いかえることもできます。また、ハードクラスタリングは、\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \{ 0, 1 \} ^ K, |\bf{z} _ i| = 1 \} と言いかえることもできます。(one-hot encoding, 1 of K 表記)

K-平均法

  • 予測
    各k \in [ K ] でクラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、
\DeclareMathOperator*{\argmin}{arg\,min} %argmin \begin{aligned} z _ k = \left\{ \begin{array}{11} 1 & k = \argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}

と定めます。要は一番近いクラスタ中心に属するという意味です。

  • 目的関数
    \mu = \mu _ k, Z = z _ {ik}とし、
\begin{aligned} J(\mu) = \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\ = \min _ {Z} \mathfrak{L}(Z, \mu) \\ ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\ Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。 \end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)のZについての最小化をします。

\begin{aligned} Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\ すなわち次のようにパラメータを更新をします。\\ z _ {ik} = \left\{ \begin{array}{11} 1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)の\muについての最小化をします。

\begin{aligned} \mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\ すなわち次のようにパラメータを更新をします。\\ \mu _ {k} = \frac{\Sigma _ i z _ {ik} \bf{x _ i}}{\Sigma _ i z _ {ik}} \end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。

1.2 ソフトクラスタリング

\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \bf{z} \in [ 0, 1 ] ^ K, | \bf{z} _ i| _ 1 = 1 \} のときソフトクラスタリングといいます。z _ {ik}はデータiがクラスkに属する割合と解釈されます。

ソフトK-平均法

  • 予測
    各k \in [ K ] でクラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、
\begin{aligned} z _ k = \frac{exp(-\beta ||\bf{x} - \mu _ k || ^ 2)}{\Sigma _ k' exp(-\beta ||\bf{x} - \mu _ k' || ^ 2)} \end{aligned}

と定めます。統計力学に出てくるカノニカル分布みたいな形をしていますね。

ちゃんとプリント読まないときついかも

  • 目的関数 K-平均法のminをsoftminで置き換えます。

\mu = \mu _ k, Z = z _ {ik}とし、

\begin{aligned} J(\mu) = \beta ^ {-1} \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\ = \min _ {Z} \mathfrak{L}(Z, \mu) \\ ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\ Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。 \end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)のZについての最小化をします。

\begin{aligned} Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\ すなわち次のようにパラメータを更新をします。\\ z _ {ik} = \left\{ \begin{array}{11} 1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)の\muについての最小化をします。

\begin{aligned} \mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\ すなわち次のようにパラメータを更新をします。\\ \mu _ {k} = \frac{\Sigma _ i z _ {ik} \vec{x _ i}}{\Sigma _ i z _ {ik}} \end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。

論理回路

コンピュータアーキテクチャ コンピュータ科学 勉強 論理回路 ブール代数 組み合わせ回路

はじめに

この記事では、論理回路について説明します。

論理回路を導入するモチベーション

まず、論理回路を導入するモチベーションをいいます。そもそも、コンピュータを利用する目的は何でしょうか。もちろんそれは人によってまちまちでしょうが、ざっくりと一言で言ってしまうと計算させるためであると言えると思います。では、どのようにしたら機械に計算させることができるでしょうか。また、そもそも”計算”とは何でしょうか。
まずは、人間が計算をするときの基本戦略を考えてみましょう。ここでは、掛け算の筆算を例にして考えます。掛け算の筆算は、まず最初に１の位を計算して、次に１０の位を計算して、・・・と言うようにひと桁同士の掛け算を覚えておき（例えば筆算では、下に記録しておく）、その結果を足し合わせることで、答えを導き出しています。

実は、実際のコンピュータの計算でもこのようなアプローチを利用しています。 つまり、プリミティブな計算表を準備しておき、それらを組みあわせることで複雑な演算を実現しているのです。 掛け算の例に戻ると、人間（日本人）の場合は九九の表覚えていて、その表に書いてある答えを組み合わせることで、複雑な掛け算を実現しています。そして、コンピュータは、記憶力がいいので、九九よりももっと多くの計算結果を覚えさせておくことができます。 実際の計算では、この表として、真理値表という形式を使っています。真理値表とは、次のようなm個の入力変数の列と、n個の出力変数の列からなる表で、それぞれの変数は、0または1の値を取ります。したがって全ての入力を網羅するために、真理値表は、2 ^ m個の行を持ちます。そして、この真理値表を現実世界で具体的に実現する手段として、デジタル回路を用います。真理値表の各変数が2進数で表現されているように、すべてのデータは2進数で表現します。また、2進数の一つ一つの桁のことをビットといいます。（なぜ2進数を採用するのかは、2進数で表現するのが一番実装しやすいからであると僕理解しています。）

数の表現方法

では、具体的にコンピュータでは、二進数でどのように数を表現しているのか見ていきましょう。

負の数の表現

負の数を二進数で表現するために、一般にコンピュータでは、負の補数表現という方法が採用されています。負の補数表現では、2進数で正負を表現するために、一番頭のビットを正負を表すのに使います。一番先頭のビットが0ならば、正、1ならば負とします。そして、正の数（及び0）は、通常通り定義します。なので、例えば、4bitの場合を例として考えると、次のように、正の数および０は表わせます。

数 二進数表現
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111

次に負の数を考えます。さてどのように負の数を定義してあげるのが、一番都合がいいでしょうか。ここで、次のような例として、2 - 6 = -4という計算を考えてみましょう。この右辺を二進数で表すと、0010 - 0110となります。そこで、-4を表す二進数表現を????と書くと、（?には0または1が入ります。）右辺の6を移行してきて2 = 6 + -4となります。すなわち、0010 = 0110 + ????が成立してほしいわけです。これを満たすように、????をさだめると、 ???? = 1010のとき、0110 + 1010 = 10010 となり、繰り上がりを切り捨てることで、2を表す、0010と一致します。このようにして負の数も定めてあげると、負の数は以下の表のように定義できます。

数 二進数表現
-1 1111
-2 1110
-3 1101
-4 1100
-5 1011
-6 1010
-7 1001
-8 1000

小数の表現

実数は指数関数を利用することで定義します。例えば単精度浮動点小数では、小数を表現するのに32ビット使いますが、次のようにその32ビットの中で、役割が分かれています。ちなみに、この浮動点というのは、誤差が生じるという意味です。

| 占有ビット | 名称 | 役割 | | ---- | ---- | ---- | |0~22ビット | fraction | 仮数部(符号なし整数) | 23~30ビット | exponent | 指数部（符号付き整数） | 31ビット | s | 符号部 |

そして、以下の式によって10進法の数字と対応付けます。


(-1) ^ s \times fraction \times 2 ^ exponent


データの精度は232ですが、指数部分があるおかげで大きな数も表せるようになっています。

ブール代数

2進数の演算を実装するにあたって、まずはその演算規則、つまり代数を知る必要があります。我々は、2進数の代数としてブール代数を採用しています。この代数系は電気回路で実現しやすいというメリットがあります。

ブール代数の構成

ブール代数では、全ての変数は、0か1のうちのどちらかとなります。そして、典型的な構成では、次の3つの演算子を定義します。

Logical Sum（論理和）

まず一つ目は、Logical Sum（論理和）です。論理和の標準的な表現法としては、次の3パターンがあります。

  • C = A OR B
  • C = A + B
  • C = A v B

上の表現から分かるように、論理和は、2つの元から1つの元への射影となっています。その射影規則は真理値表によって下のように表せます。

A B C
0 0 0
0 1 1
1 0 1
1 1 1

二つ目はLogical Product（論理積）です。論理積も論理和と同様に主に3パターンの表現方法があります。

  • C = A AND B
  • C = A ・　B
  • C = A ^ B
A B C
0 0 0
0 1 0
1 0 0
1 1 1
  • Logical Negation（論理否定）

C = NOT A

C = A- C = A`

A C
1 0
0 1

これらの結合で、あらゆる真理値表を実現できる。

想定されるすべての変数を含む論理積を最小項と呼ぶ。

最小項の論理和で表した論理関数のことを加法標準形または論理和標準形という。

例：Z = !ABC + A!BC + AB!C + ABCは加法標準形。
!ABC, A!BC, AB!C, ABCは最小項。ただし!XはXの否定を表す。

組み合わせ回路

組み合わせ回路とはブール代数を実現する回路のことです。

Gates

2入力1出力 AND,OR,NOTをどのようにして表すか。

簡単な論理演算回路（リレー回路） （電気回路） AND＞直列 OR＞並列 NOT＞電磁石で離れるようにすればいい。

＞＞リレー回路は動作が不安定（時間がかかったら、埃が入ると動かなくなったりする）

そこで、トランジスタの登場 AND Gate,OR Gate, NOT Gate（電子回路）

演算の実装

必要な計算の例 - 四則演算 - 論理演算 - シフト演算 - 比較演算

四則計算

足し算

半加算器 真理値表による表現

x y C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

論理回路への実装
いろいろな回路が組める。（ブール代数の式の恒等変換をする。） 全加算器の真理値表 z:繰り上がりしてきた入力

x y z C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

これを32個並べると、32bitのコンピュータが実現できる。

キャリー先読み論理回路 ＞桁上げだけ先に計算させてしまう。

引き算

半減算器、全減算器の真理値表を作って、同じように論理回路に実装する。

コンピュータ制御でよく使われる回路

  • Decoder, Encoder
  • Multiplexer(Selector), De-multiplexer

  • Parity Check

  • 多数決回路(Majority Circuit)

Decoder

命令を2進数で0~7で定義して、Inputを与えるとそれに応じたシグナルを出す。つまり[tex:｛0,1｝｛0,1｝｛0,1｝ \rightarrow ｛0,1,2,3,4,5,6,7｝]という写像。 機械語の命令を翻訳するのに使う。

Multiplexer

スイッチング。selectorの入力によって、input0とinput1のどちらを流すかを決める。電気信号の流れを制御する。

2-to-1

真理値表による表現

Input0 Input1 Selector Output
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

ブール代数による表現

[tex: C=(A!S) + (BS)]

電気回路

Parity Checker

エラーがあったときに誤り訂正するための符号化をチェックするやつ。 1bitだけ余分に付加して、必ず信号が偶数になるように符号化する。 1bitの誤りならば、奇数になっているので気付ける。

ALU (Arithmetic Logic Unit)

　1bit数を扱う、4bit後の計算機の命令

| op1 | op0 | a | b |
- op1,op0 ... 2bitの命令 00 ... a ^ b 01 ... a v b 10 ... a + b 11 ... NOP

and,or,加算器をくみあわせる。

  • 32個つなげれば、32bitの計算機ができる。
  • 入力を4bitより増やせばよりたくさんの命令を搭載できる。

PLA(Programmable Logic Array)

どんな演算でもいらないところをユーザーが焼き切ってしまえば、実現できる。

カルノーマップ

加法標準形から回路を作ると、回路の数が大きくなってしまう。 カルノーマップ...回路を簡略化するための表 カルノーマップは4入力が限界、、、。それ以上はコンピュータに計算させる必要がある。

論理回路の基本的な作り方

  1. 真理値表を作る。
  2. ブール代数の論理式に直す。
  3. カルノーマップを作成し、簡略化する。
  4. 論理回路ゲートを使って、実装する。