xiangze's sparse blog

機械学習、ベイズ統計、コンピュータビジョンと関連する数学について

モデルとアルゴリズム、圏と関手と自然変換

お正月気分が抜けないのでほわっとした記事を書きます。

prompton.io

モデルとアルゴリズムの素朴な理解

機械学習や統計におけるモデルとアルゴリズムの違いを説明するときに学習、分析の対象をパラメータを使って数式で表現したものがモデルで最適なパラメーター値を探索する方法、プログラムが(最適化)アルゴリズムであるとしていました。

しかしネットを見ていると「データをアルゴリズムに投入して、できたロジックがモデル」といった説明も見かけます。これではアルゴリズムによる学習をする前にモデルは存在しないように聞こえます。stanによるベイジアンモデルの記述やpytorch,tensorflowによるネットワークの記述(プログラミング)は推定、学習に先立って行われるはずです。一方で決定木、ランダムフォレストなどは学習結果を反映して木の形が変わるのでこの説明の方が自然なようにも思えます。

またモデルは機械学習や統計的推論に従ってそのパラメーターが一回定まると通常は大量の異なるデータに対して同一の手順での識別処理を行う(データフロー)のに対し、通常のプログラミングにおけるアルゴリズムの意味はより広くデータがない状況での問題の最適化や探索も含み、実行中に動的に実行される命令が変化したり、再帰的な形になっている場合も多いです*1。
このようなモデルとアルゴリズムに対する素朴な考えをより精密に、プログラミングに近い言葉で表現する数学の分野として圏論(Category Theory)というのがあります(あるそうです)。

prompton.io

圏論による理解

圏論では対象(object)、とその間の射(morphism)という要素を持つ圏と呼ばれるものを考えます。大まかには対象は数(の集合)の一般化、射はそれを入出力とする関数の一般化と言えるかもしれません。対象と射の対応を保って他の圏に写す写像を一般化した概念が関手(functor)と呼ばれます。

例えばN次元のベクトル空間を圏とみなすとベクトルが対象、掛け合わすことでベクトルをベクトルに写す行列が射、別次元あるいは同じ次元にベクトルを変換する行列が関手と見なせます。あるいはN次元空間の点を対象とするとそれを移動させるベクトルが射、点はそのままにベクトルを変換する行列は関手と見なせます。

実数や複素数のベクトル空間、無限次元の関数や確率分布の空間、高次元空間の回転や平行移動の集合、さらに任意の係数の多項式の集まりや位相空間も圏とみなすことができます。

モデルは入力データと出力のラベル等及びパラメーターを対象(データ、数、集合などを抽象化したもの)とした射(関数や写像を抽象化したもの)で学習はモデルと対応するパラメータを変化させて射と対象を変えていく関手と見なせそうです。

射としてのモデル、関手としての学習アルゴリズム

SGDや自然勾配学習法などの手法を使った学習アルゴリズムは関手と言えるでしょう。
実際Backprop as Functorというそのままなタイトルの論文があります。ここでは学習プロセスを圏Learnとして定義し、ネットワーク、パラメーターとの関係を関手として表現しています。

様々な種類のニューラルネットは畳み込み層や活性化層などの連結や並列で構成されます、統計モデルも同様に確率変数とその演算で構成されます。モデルが複雑で解析対象ごとに違うためにpytorchやstanのようなライブラリのお世話になる訳です。このようなプログラミングで部品を組みあげるような構造も圏で表現するといいことがありそうです。

論文Reverse derivative categoriesではニューラルネットの学習則back propagationを逆微分という演算を定義し、モデルをその組み合わせで定義しています。そうすることで多層のニューラルネットを表現し、また微分可能という条件を持つプログラムを構成的に定義することができています。

これだけだと既存のディープラーニングフレームワークの実装をなぞっているだけのようですがこの論文では逆微分の圏から微分演算子を持つ圏を導出ことはできるものの逆は真ではないという興味深いことが示されています。逆微分があるような微分可能な圏を作るために†演算子というのを定義しています。

圏論から見た機械学習のレビュー論文Category Theory in Machine Learningでは2章でこのモデルの圏の構成を使ってlossの最小化のイテレーションである学習過程を図式で書いています。pytorchの学習部分のコードにあまり慣れてない人にもわかりやすいです。レジスタがあるデジタル回路図っぽくもあります*2。


学習イテレーションの詳しい図

関手で写される圏同士の対象間の関係が射となるような自然変換という概念があります*3。

圏CからDへの関手F，Gに対応した自然変換t

[1905.02072] Characterizing the invariances of learning algorithms using category theoryでは教師あり学習をデータの圏とモデルの圏の間の自然変換として捉えています。
この自然変換に対応する米田写像を考えると面白そうです。

prompton.io

米田写像yと自然変換

構造を保ったデータの学習

平行移動や回転に対しても画像
学習対象データの中にも隠れた規則性や構造がある場合がありそれを組み込むことで機械学習の精度が上がったり効率的に学習することができたりします。
その構造を保存したままモデルによる変換を行いたいです。そうすることでモデルは構造を保つ関手、学習は自然変換と言えるでしょう。
当てはめられそうな例としてgroup equivalent CNNがあります。

また単語をベクトル空間にマップするword2vec, テキストで書かれた特徴がベクトルとなり画像に畳み込まれるtext2img などはテキストの隠れた構造を保持したまま演算(NovelAIの{{}}はベクトルの定数倍のような動作をする )を可能とすることから関手と言えるかもしれません。

Category Theory in Machine Learningでは4章でこのような構造を保持した教師あり学習の手法が紹介されていますが圏論的な考察はそこまで進んではいないようです*4。この章では他にも教師なし学習の一種としての多様体学習やパーシステントホモロジー(ホモロジー代数で出てくる群やその間の完全列が圏論の発想の源泉のひとつなので当然と言えます)など幅広く機械学習の圏論的理解に繋がりそうな研究が紹介されています。

prompton.io

Haskell(とscala)プログラミング情報

Haskellと圏論の関わりの深さは様々なところで言われていますが、上記のモデルや学習(アルゴリズム)の圏を型として定義することができます。
Lensだけで作るニューラルネットワーク
このブログで書いたこと、特に圏としての学習はこちらのブログの内容に包含されるものでした。
Lensはsetter, getterを持つような一般的なオブジェクトのhaskellにおける型であり、Para(パラメーター)とLearnを圏として定義してそれらの間の関手としての学習を関数として記述しています。

qiita.com
Hasktorchはhaskellの依存型を用いたpytorchラッパーでテンソルのサイズを型に情報として持たせることができるそうです。
https://github.com/hasktorch/hasktorch/tree/master/examples
に多くの例が実装されていますが今回書いたような学習過程の抽象化はされていないようです。またインストールが結構難しいらしいです。GHCのFFI&ForeignPtrに関するパフォーマンスの調査（C++編） - Qiita

Haskellの機械学習ライブラリHLearn - Qiita 2013年の情報ですがその後は音沙汰なさそうです。

scalaですがプログラマー的には圏論初心者が自然変換について学んでみた！ - MicroAd Developers Blogの可換図式がわかりやすいです。生きてるかわからないURLやファイルパスのListを処理するときにOptionを使います。
圏論とかモナドなんて簡単だからscalaを使って説明してみた - だらだらしてたいなぁモナドは関手(map) + flattenと同じ。pandasで各列からdataframeを作ってconcatで縦に並べる処理はモナドかなと思いました。

def music_char_oneelection(df,i):
    s=str(i)
    ndf=pd.DataFrame()
    ndf['title']=df['title']
    ndf['titlenum']=df['title'].apply(lambda x:titlelist.index(x))
    ndf['title_integer']=df['title'].apply(lambda x:str(x).replace('東方','') in integerlist['作品'].values)
    ndf['title_noninteger']=df['title'].apply(lambda x:str(x).replace('東方','') in nonintegerlist['作品'].values)
    ndf['title_other']=~ndf['title_integer'] & ~ndf['title_noninteger']
    ndf["level"]=df["Number"]
    ndf["levelnum"]=df["Number"].replace('-','0').astype('int')
    
    ndf["曲名"]=df["Track Name"]
    ndf["回"]=i
    ndf["回n"]=i/18
    ndf['charname']=df['名前']
    ndf['音楽ポイント比率']=df[s+'_x']
    ndf['キャラポイント比率']=df[s+'_y']
#    ppd["名前n"]=[j/len(ppd.index) for  j in range(len(ppd.index))]

    return ndf

refdf=music_char_points_ratio
music_char_tate=pd.DataFrame()
#モナドっぽい処理
for i in range(1,19):
        music_char_tate=pd.concat([music_char_tate,music_char_oneelection(refdf,i)],axis=0)

toubou_vote_analysis/scrape_music_correlation.ipynb at main · xiangze/toubou_vote_analysis · GitHubより

圏論やHaskell得意な人から見た機械学習、統計モデリング

functor.tokyo -- How to get into Machine Learning for a Haskeller

prompton.io

微分可能な計算の一般化

Video: Derivative of a Regex?! (Brzozowski Derivative) : ProgrammingLanguages
正規表現にも形式的にライプニッツ則を満たす微分演算子を定義することができるらしいです。Brzozowski derivativeというらしいです。その全体は圏とみなし、逆微分を定義することができれば微分可能プログラミングを使って入力文字列から帰納的に正規表現を学習することができるかもしれません*5。
https://github.com/mattmight/project-regex-derivative

正規表現の微分

コンピュータ科学や組み合わせ論を“微分幾何”とみなす：CADGの夢 - 檜山正幸のキマイラ飼育記 (はてなBlog)
計算論における微分の一般化はこちらのブログでも詳しく紹介されています。基本的には環(和と積が定義された圏と言える)にライプニッツ則を満たす演算が入れられればなんでもいいはずです。今やディープラーニングそしてHMCがキラーアプリですが他にもあるかもしれません。

その他雑感と宣伝

metalearning, Neural Architecture Searchなどは圏論的にはどのように捉えられるでしょうか(安易なメタ思考)

Category Theory in Machine Learningの3章はベイズ統計モデリングの圏論的見方の話なので時間があったら読みたいです。

ベイズ統計モデリングを表現した図式Category Theory in Machine Learning より

www.iwanami.co.jp
薄くてわかりやすいです。方程式やベクトル空間、三角形など高校数学の範囲の概念を用いて圏論の使いどころを示していています。

表現可能関手 - bitterharvest’s diary
つかみのところで日本史の学説間の等価性を圏論の表現可能関手を用いて理解しようとしていて強い印象を受けたのがこの記事を書いた理由の一つです。

職業プログラマが圏論をスルーすべき理由
正直圏論は普通に暮らしていくには不必要に難しいです。しかし機械学習、統計のモデルは微分関数であることにこだわりpytorchなどのフレームワークでできることを追求したい、画像の回転や変形、あるいは言い換えや類義語に対して性能が変わらないニューラルネットを統一的に捉えて新たな発見をしたい、あるいはstan,pytorch,tensorflowのようなとても頭のいい人がpythonで素早くx86 CPUとNvidia GPUに特化して実装してしまったようなライブラリの根本部分に手を入れて独自のアルゴリズム、ハードウェアで動くようにしたいときに見通しよくしたい場合にはその恩恵が理解する労力を上回るかもしれません。

prompton.io

prompton.io
prompton.ioではAI生成画像でコミッションをしたい人、受けたい人、見たい人を募集しています。

課題

  • 学習を自然変換とみなせる場合の米田埋め込みは何か
  • lotzさんのLens実装のディープ化 convolution, full connection,resnet...他の学習法...
  • 正規表現の勾配法による学習
  • 文脈自由文法に微分演算子を導入できるか
  • prompton.ioの宣伝

*1:このためCNNなど機械学習の特定の処理用のアクセラレータは不得意とします。

*2:実際回路シミュレーターを実装する話もあった気がします

*3:一般には自然でない変換もあります

*4:Group Equivariant Convolution Networksを書いたTaco S. Cohenさんの論文が多く引用されています

*5:ChatGPTに聞けば良いという話もあります