こんにちは、 @kz_morita です。 圏論に入門する記事の 7 回目です。 圏論への入門 圏論とは 圏論への入門 圏の例としての順序集合 圏論への入門 集合圏 Set 圏論への入門 モノイドとモノイドの圏 圏論への入門 関手とは 圏論への入門 Hom 関手について 圏論への入門 自然変換 (本記事) 自然変換 自然変換は、関手の間同士の関係性で以下のような定義になっています。 $圏 \ C$ から $圏 \ D$ への関手 $F, G$ に対して $t$ が以下の条件をみたすときに、$F$ から $G$ への自然変換という $t$ は $圏C$ の各対象 $X$ に対して、射 $F(X) \xrightarrow{t_X} G(X)$ を対応させる。 $圏C$ の任意の対象 X, Y 及び、任意の射 $X \xrightarrow{f} Y$ に対して、$G(f) \circ t_X = t_Y \circ F(f)$ が成り立つ $t_X$ は $t$ の $X成分$、$t_Y$ は $t$ の $Y成分$ と呼ぶ 自然変換は以下のように記述する

こんにちは、 @kz_morita です。 圏論に入門する記事の6 回目です。 これまでの記事はこちら 圏論への入門 圏論とは 圏論への入門 圏の例としての順序集合 圏論への入門 集合圏 Set 圏論への入門 モノイドとモノイドの圏 圏論への入門 関手とは Hom 集合 とある圏 C の２つの対象 $X, Y$ について、２つの対象の間の射は複数存在するが、その射の集合を Hom 集合 とよび、$Hom_C(X, Y)$ と表現します。 Hom 関手 とある圏Cに対してある特定の点A を固定してそこから各対象への Hom集合を取る操作はもとの圏C から 集合圏 Set への関手となり、Hom 関手 と呼ばれます。 最初 Hom 関手について聞いたときに、なんのことかよくわからなかったのですが図解して見るうちに理解できてきたので図をつかって説明します。 関手の定義のおさらい 関手の定義は以下の様なものでした。 圏C と 圏D において、以下の条件を満たす $F$ を関手 (functor) と呼ぶ。 $C\ の射 \ f: X \to Y \ を \ D \ の射 \ F(f): F(X) \to F(Y)$ に対応させる $F (f \circ g) = F(f) \circ F(g)$ $F(1_X) = 1_{F(x)}$ この定義にそって、特定の点A から各対象への Hom集合を取る操作が関手になるかを確認していきます。

こんにちは、 @kz_morita です。 圏論について入門する記事の5回目です。 これまでの記事はこちら 圏論への入門 圏論とは 圏論への入門 圏の例としての順序集合 圏論への入門 集合圏 Set 圏論への入門 モノイドとモノイドの圏 関手とは 前回の記事 でモノイドの圏について考えましたが、今回はより抽象化した関手について考えます。 関手は圏と圏の間の対応をあわらす、いわば圏を対象としたときの射のようなものです。 定義は以下の通り 圏C と 圏D において、以下の条件を満たす $F$ を関手 (functor) と呼ぶ。 $C\ の射 \ f: X \to Y \ を \ D \ の射 \ F(f): F(X) \to F(Y)$ に対応させる $F (f \circ g) = F(f) \circ F(g)$ $F(1_X) = 1_{F(x)}$ 具体例で考える 前回のモノイド準同型の例で、具体例を考えると以下のようなことです。 ↓の２つの圏 (モノイド) を考えます。 $圏\ C = (\mathbb{R}, +, 0)$ 実数の集合を対象とし、+ (加算)を射とするモノイド。単位元は 0 $圏\ D = (\mathbb{R}_{>0}, *, 1)$ 正の実数を対象とし、* (乗算) を者とするモノイド。単位元は 1 $F(x) = 2^x$ が関手になるのですが、定義を具体例で再確認します。

こんにちは、 @kz_morita です。 圏論について入門する記事の４回目です。 これまでの記事はこちら 圏論への入門 圏論とは 圏論への入門 圏の例としての順序集合 圏論への入門 集合圏 Set モノイドとは モノイドとは、圏において対象がただ１つの圏のことを指します。 例としてあげると、実数 $\mathbb{R}$ (の集合) を対象とし加算を射とするような圏があげられます。 どんな加算をしても $\mathbb{R}$ の要素となるため対象は１つで、射が複数あります。 また、モノイドは対象が１つのため実質的に射の集合として捉えることができます。 前述の例だと、以下のような射の集合と考えられます。 $$ X = \lbrace +0, +1, +2, +3, … \rbrace $$ また、対象が１つであるためどの２つの射でも合成ができ、合成結果もモノイドの射の集合の要素となります。これを、モノイドの射の集合 $M$ をもちいて以下のように表します。 $$ \circ : M \times M \to M $$ $M \times M$ は集合の直積 ($M$ の要素すべての組み合わせ)を表し、それが $M$ への写像であるということです。 また、恒等射も考えることができます。 上記の射の集合の場合、$+0$ は恒等射ということができそうです。 モノイドの定義を圏論的に考えると以下のようになります。 モノイドは次の３つの組み合わせの事を言います。 $(M, \circ, 1_M)$ M は 集合 $\circ$ は、$\circ: X \times X \to X$ となる M上の演算 $1_M \in M$ となる M の元 となり、下記の満たすものです。

こんにちは、 @kz_morita です。 圏論について入門する記事の三回目です． 前回の記事はこちら． 圏論への入門 圏論とは 圏論への入門 圏の例としての順序集合 集合圏 Set とは 一つの集合を対象とし，集合間の写像を射とする圏のことです． 集合 A を 集合 B に移すような写像を $f: A \to B$ と書き，写像 $f$ は，$f(a) = b$ と表せるように，集合 A の要素 a を ただひとつの集合 B の要素 b に移すような関数を指します． 具体例でいうと，整数全体 $\mathbb{Z}$ を自然数全体 $\mathbb{N}$ に移すような写像 $f(x) = x^2$ などを考えることができます． 写像についておさらい 写像に大きく分けて以下の 3 つがある 単射 全射 全単射 単射 単射の定義は，以下の通りです． $$ a \neq a' \ ならば \ f(a) \neq f(a') $$

こんにちは、 @kz_morita です。 前回は、圏とはなにかについてまとめたので今回は、圏論について入門する第二弾の記事で圏の例を見ていきます。 前回はこちら 圏論への入門 圏論とは 順序集合 順序の概念がありときに、「$\leq$」で表される大小関係 ( 二項関係 という ) がある集合を順序集合という。 単純な例だと、数値は数値同士比較できる ( 二項関係がある ) ため、数値の集合は順序関係と言える。 順序集合には以下の3通りあるので説明していく 前順序集合 半順序集合 全順序集合 前順序集合 (preorder set) 以下の条件を満たすものが前順序集合である。 集合内の任意の要素 $a, b$ について $a \leq a$ (反射律) $a \leq b \ かつ \ b \leq c \ ならば、a \leq c$ (推移律) 半順序集合 (partialOrder set) 半順序集合は、前順序集合に加えて以下の条件を満たすものである。 $a \leq b \ かつ \ b \leq a \ ならば、\ a = b$ (反対称律) 全順序集合 (totalOrder set) 全順序集合は、半順序集合の条件に加えて以下の条件を満たすものである。

こんにちは、 @kz_morita です。 前から気になっていた圏論について、 『圏論の道案内』 という本を読み始めました。 普段 Scala を書くエンジニアとしてモナドなどよく耳にしますが、それがどういう概念に基づく言葉なのか理解したいと思ったのがきっかけです。 学んだことなどをメモがてら書いていきます。 圏論について 圏論は、圏とよばれる矢印からなるシステムについての学問という理解です。 圏 (Category) は、対象 (object) と 射 (arrow) からなります。 定義としては、次の通りの理解です。 対象と射からなるシステムで射が合成でき、 結合律と単位律を満たすのであれば圏と呼ぶことができる 以下で説明していきます。 圏の構成要素 対象 A, B と A から B への射 を f とすると以下のように表記することができます。 $$ B \xleftarrow f A $$ A のことを、射f の 域 (domain) といい、B のことを、射f の 余域 (codomain) といい以下のように表記できます。 $$ A = dom(f), B = cod(f) $$ 射の合成 圏の定義として、射 $f, g$ で $cod(f) = dom(g)$ であれば、$dom(f)$ から $cod(g)$ の射が一意に存在します。

こんにちは、 @kz_morita です。 今回は，検索エンジンなどの，クエリと文書のマッチ度に使われる BM25 の式を読み解いていきます． BM25 とは BM25 は，検索システムにおいて，クエリが文書とどれだけマッチしているかについてを計算するための手法になります． 式で表すと以下になります． $$ score(D, Q) = \sum^{n}_{i=1} IDF (q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)} {f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{avgdl})} $$ これらの式の意味を一つずつ見ていきます． 各種変数の意味 上記の式の score 関数に登場する各種変数について見ていきます． D 検索対象の特定の文書の文字列集合 |D| 検索対象の特定の文書の文字列集合の大きさ (どれくらいの単語量 ≒ 文書量) なのか avgdl 全文書の文字列集合の大きさの平均 Q 検索クエリの文字列集合 q 検索クエリの１つの単語 IDF関数 Inverse Document Frequency の略．いろんな文書に登場する一般的な単語だと値が小さく，レアな単語だと値が大きい f 関数 検索クエリの単語が対象の文書の中でどのくらい現れるかの指標．tf (Term Frequency) であったり，純粋な数のカウントだったりする．tf の場合は，以下のような式になる $$ tf = \frac{ある単語の出現回数}{全単語の合計数} $$

こんにちは、 @kz_morita です。 今回は類似度を測る指標について、Cos 類似度と、Jaccard係数 そしてそれを高速に処理するための MinHash について調べたことをまとめていきます。 類似度の計算の必要性 ベクトルの類似度を計算することは、例えばベクトル化された文書間の類似検索であったり、重複するドキュメントを検出したりする際に有効とされています。 今回は、類似度の指標である Cos 類似度 Jaccard 係数 と高速化のための MinHash というアルゴリズムついて見ていきます。 Cos 類似度の定義 Cos 類似度は、ベクトル同士の類似度 (≒ ちかさ) を表すことができる式です。 ベクトル $\vec{a}$ と $\vec{b}$ の Cos 類似度はを表す式は以下のような形になります。 $$ cos \theta = \frac{\vec{a}\cdot\vec{b}}{|\vec{a}||\vec{b}|} = \frac{\sum_{i=1}^{N} a_{i}b_{i}}{\sqrt{\sum_{i=1}^{N} a^2_{i}} \sqrt{\sum_{i=1}^{N} b^2_i}} $$ これは、ベクトルの内積の式である $$ \vec{a}\cdot\vec{b} = |\vec{a}||\vec{b}| cos \theta $$ から変形したものになります。 つまり二つのベクトルが成す角 $\theta$ の $cos$ の値を類似度として使うということで、その値の範囲は $$ -1 \leq Cos 類似度\leq 1 $$ になり、1に近づくほど角度が近い = 類似度が近いとなり、0 に近づくほど直交していて、-1 ほど反対になるというものになります。