2021-05-19

ぱらぱらめくる『トーリックイデアルの20年』

ぱらぱらめくるシリーズトーリックイデアル代数統計イデアル環多項式環グレブナー基底割り算倍数素数

http://www.math.sci.hokudai.ac.jp/sympo/100809/pdf/osugi.pdf

トーリックイデアルが興味深い対象として挙げられる理由３つ
- 凸多面体の三角形分割が、トーリックイデアルのイニシャルイデアルと対応する(三角形分割には団代数が付随し、そこにはローラン多項式な団変数があるが、トーリックイデアルの構成にもローラン多項式が登場する。コーラン多項式は「多項式環」の仲間ということで、「環」の「部分集合」で「代数的性質をもつもの」。この話にはルート系なども出てくるが、そもそも団代数はルート系の本体のような意味もあり、そういう意味でもつながっている
- トーリックイデアルにはグレブナー基底が取れて、これにより、整数計画問題の解法がもたらされた
- 同じくグレブナー基底をマルコフ基底(空間をうろうろするための一歩の集合)として分割表の取りうる空間をうろうろすることができて、それによって分割表検定のための情報が得られる
１　トーリックイデアル
- そもそも、イデアルって…
- 「数」の抽象的な概念なので、なじみの深い「数」における「イデアル」の位置づけを確認する
- 整数全体の集合として「部分集合に z=3の倍数の集合」というようなものが取れる。この部分集合はそれなりに演算に関して閉じている(３の倍数を足し合わせても、相変わらず３の倍数である、とか)。そういういい感じの性質を持った部分集合を考えたい
- z=3の倍数の集合を考えた時、zとして素数を取るのも悪くない発想。なので、イデアルには、「いい感じの取り方・取られ方」があって、それは素数的な意味合いもあるらしい
- 整数全体の部分集合を考えた。そのとき、いい感じの性質・演算で閉じているというものを考えた。その代数的性質が「環」なので、「倍数のようなものの一般化したもの」を作り出すことは、「環」に対して行うのがよい。…とそういうことらしい
- 大きな環としてローラン多項式環 $X[T,T^{-1}] = K[t_1^{\pm 1},t_2^{\pm 1},...,t_d^{\pm 1}]$ を取る
- その部分多項式集合を構成する種として、特定の単項式の集合 $\{T^{a1},T^{a2},...T^{an}\}$ , ( $T^{ai} = \prod_{p=1}^d t_p^{ai_p}$ を取る。ただし、 $a_i = (ai_1,ai_2,...,ai_d) \in Z^d$ のように $ai$ はd次元空間の格子点
- この種となる単項式を自由に決めると、「いい感じの取り方」になっていないので、「制約」が必要
- その制約として、n個のd次元格子点 $\{a1,...an\}$ は原点を通らないd次元空間超平面上にあるというものを定める。 $w \cdot ai=1;i=1,2,...,n$ となる $w$ (d次元実ベクトル)が存在する、とも言い換えられる制約である
- このような制約のことを、 $\{ai\}\subset Z^d$ が $R^d$ の配置であると呼ぶ
- このような制約を持った種になる単項式が構成する多項式集合は semigroup ringになると言う。これをトーリック環 $K[A]$ と呼ぶ(Aは配置の要素 $ai$ の集合
- このトーリック環に伴うイデアル、「トーリックイデアル」を定義するにあたり、もう一つ別の多項式環を準備する
- Tを使った多項式環はd変数だったが、トーリック環の構成に用いられた、もう一つの自然数、n(格子点の数n)

を用いて、n変数多項式環 $K[X]$ 考える( $x_1,...,x_n$ )

- このn変数多項式環の要素をトーリック環の要素に対応付ける。 $\pi (x_i) = T^{a_1}$ なる関係にする
- n変数多項式環はn変数の多項式の全体であるのに対して、トーリック環の要素は制約を持つ単項式が種となった多項式の集合なので、対応を取るにも１対１対応は取れない。うまく取ると、 $K[X]$ から $K[A]$ への全射になる。全射なので、 $K[A]$ の原点に対応する $K[X]$ は集合になる(カーネル)。この全射のカーネルのことをAのトーリックイデアルと言う
- 具体例を考える
- ... d = 5, n=6
  - 配置であることを確認。w = (0.5,0.5,...,0.5)を取ると、 $w A = (1,1,1,1,1,1)$ となっている
  - また、 $d=5$ 次元座標を $(t1,...,t5)$ とすれば、Aの６個の列ベクトルはすべて $t1 + t2 + ... + t5 = 2$ を満足するという意味で、d次元超平面上の点である
- このAに対して、トーリック環 $K [ A ] = K [ t_1t_3,t_1t_4,t_1t_5,t_2t_3,t_2t_4,t_2t_5 ]$ が定まる(Aの第１列ベクトルでは、第１、第３成分がそれぞれ１なので $t_1^1t_3^1$ となっている)
- このトーリック環のトーリックイデアルがだと言う
  - $x_1x_5-x_2x_4$ を例に取る。 $\pi(x_1) = T^{a1} = t_1t_3, \pi(x_5) = t_2t_4,\pi(x_2) = t_1t_4,\pi(x_4) = t_2t_3$ であるから、多項式環 $K[X]$ の要素 $x_1x_5 - x_2x_4$ に対応するトーリック環の要素は $t_1t_3 \times t_2t_4 - t_1t_4 \times t_2t_3 = 0$ となっており、確かに、 $x_1x_5- x_2x_4$ は全射 $\pi$ のカーネルに含まれている
  - トーリクイデアルの性質として、次のことも知られる
    - トーリックイデアルは素イデアルである。また、２項式で生成される。その生成ルールは $I_A = < p -q \in K[X] | \pi(p) - \pi(q) >$ ただし、 $p,q$ は単項式。これは $\pi(p) = \pi(x_1x_5) = t_1t_3t_2t_4$ であることに対応している
    - Aを行列とみなすと
      - $I_A = < X^u - X^v \in K[X] | u,v \in Z^n_{\ge 0}, Au = Av>$
      - $I_A = < X^{u^+} -X^{u^-} \in K[X] | u \in Z^n, Au = 0>$ ただし $u^+$ はuの正の部分、 $u^-$ はuの負の部分
      - これを実例でやってみる。 $u= (1,0,0,0,1,0),v = (0,1,0,1,0,0)$ とすると、 $A u = A v = (1,1,1,1,0)$ であり、これに対応する $X^u-X^v = x_1x_5 - x_2x_4$ である。また、 $u=(1,-1,0,-1,1,0)$ とすると、 $Au=(0,0,0,0,0)$ であり、 $X^{u^+} - X^{u^-} = X^{(1,0,0,0,1,0)} - X^{(0,1,0,1,0,0)} = x_1x_5- x_2x_4$ となる。このベクトルの成分の符号で分配する計算は団代数の変数変異ルールと通じるものになっている。ちなみに、トーリックイデアルは、 $x_i$ とその像 $T^{ai}$ とを考えた時に、像が $T^{ai}$ になる $K[X]$ の要素と $x_i$ との差で表される多項式の集合でもあるらしい
２　トーリックイデアルのグレブナー基底
- トーリックイデアルは多変数多項式。今、変数に順序を定めることで、単項式にも順序を定めることができる。それを「変数の順序の下での、単項式順序」と言う
- 単項式順序が定まると、多項式の各項にも順序ができる
- イデアルの多項式のそれぞれにも、「一番」の単項式を選ぶことができる。この「一番」単項式(イニシャルな単項式)を集めたものを、イデアルのイニシャルイデアルと言う
- イデアルの部分集合をとったときに、それぞれの要素のイニシャルな単項式を集めたものが、イデアルのイニシャルイデアルになっているとき、そのイデアルの部分集合をグレブナー基底と言う。そしてグレブナー基底はイデアルを生成するのだと言う(ちゃんとイデアルの要素を全部取れば、そのどれかには、このイデアルを構成するための、単項がイニシャル単項式として使われていないとイデアルとしての振る舞いができない、ということの裏返し(だろう))
３　凸多面体の三角形分割
- 配置Aが張る凸包を考え、その三角形分割(単体的複体とみなす)を取る。そういう意味での「三角形」への分割が、配置Aに変数順序を定めて取り出したトーリックイデアルのイニシャルイデアルと対応づくごとが証明されているという
- リンク先文書では細かいことが書いていないのだが…
４　整数計画問題への応用
- 整数最適化問題の条件を整数長方形行列として表現する
- 必ずしもこの長方形行列は「配置」でなくてもよい
- この長方形行列のトーリックイデアルは定義できる
- したがってグレブナー基底も定まる
- 多項式(変数の整数乗で表されたものになっている)なので、その割り算や余りを扱うことで、求めたい最適解が多項式の割り算・余りとして取り出せる
５　分割表の検定への応用
- 周辺度数を固定して分割表のセルの値(整数値)を色々と変えることは、モンテカルロな検定方法の１つ
- 分割表のあるセルの値を増やすことと別のセルの値を減らすことは、周辺度数制約のために相互依存している
- したがって、分割表のどのセルを増やしどのセルを減らすかのパターンが決まって来る
- このパターンがマルコフ基底によって張られる
- マルコフ基底はトーリックイデアルと関係しているという話
- トーリックイデアルを表す２項の差の形をした多項式の情報を使って、マルコフ基底(分割表と同じ形をした、整数値アレイ)が決まる

2021-05-15

ぱらぱらめくる『Algebraic Statistics, Graduate Studies in Mathematics 194』

代数統計パラパラめくるシリーズ

bookstore.ams.org

目次を眺めるとかなりのことがわかる

Chapter 1 Introduction (Discrete Markov Chain)

大事なのは、次の対応を理解すること

確率・統計	代数・幾何
確率分布	点
統計モデル	(Semi)Algebraic set
離散指数型分布族	トーリック多様体
Conditional Inference	Lattice points in polytopes
最尤推定	Polynomial optimization
モデル選択	Geometry of singularities
多変量ガウス分布モデル	Spectrahedral geometry
系統樹モデル	テンソルネットワーク
MAP estimates	トロピカル幾何

- 確率分布は点
  - 特定の確率質量分布・確率密度分布は情報幾何的に点である。それと同じこと
- 統計モデルは (Semi)-algebraic set
  - 例えばm変数の同時分布（全変数が{0,1}を取るような場合には、 $2^m$ の場合がある)。そこに、 $X_i$ の値が、 $X_{i-1}$ にのみ依存し、 $X_{j},j < i-1$ には依存しないというようなモデル（Markov chain model）を考えると、そのモデルには、 $2^m$ の場合の確率質量の間に等式(と不等式)が成立することが示せる。これが「モデル」を定めることで「式表現～algebraic」のセットを満足する点の集合が対象になる、という風に言い換えられる
- 離散指数型分布族はトーリック多様体
  - トーリック多様体は「強凸有理多面錐（cone）の集まりである扇（fan）(Wikipedia)

トーリック多様体 - Wikipedia」

- - まったくわからないが・・・、多分、離散の場合は、有限個の連立線形不等式になっており、それがトーリック多様体だ、、、ということなのではないか
- 最尤推定は Polynomial optimization
  - Markov chain modelでは、 $P(X_i=x_i | X_{i-1} = x_{i-1}$ が重要になるが、この（１つ前の変数に条件づいた、条件付確率を、代数式の変数とすれば、確率は多項式になる。したがって、「確率～尤度」の最大化は多項式の最適化と同じ
  - しかも、最適化は(偏)微分して0が最尤解。これが連立有理式になり、それが解けることもあるが、解けない場合もある
  - "Amazingly a complete, beautiful, yet still mysterious classification of models with rational formulas for maximum likelihood estimates exists and has ermarkable connections to other areas in algebraic geometry" ... Chapter 7
  - Real Algebraic Varietyというのは、連立実等式のセット。Semi-real... は連立実等式と連立実不等式のセット・・・多面体になる
- MAP estimates とトロピカル幾何・トロピカル代数
  - MAP 推定の中に、言語処理分野（音声を聞いて文字列に直す、とか）がある。その処理では、音素を辺にし、音素列をパスにしたようなグラフを構成し、ある音素列が与えられたときに、合致することを「適切なパス」の存在に対応付ける。そして、その「パスを選ぶ」ことが「対応する文字列」の出力に対応するように作ってある。例えば、"akada"という音素列（アルファベットが音素であるとする）に対して、a-k-a-d-aというパスが存在し、そのパスを通ったら「赤だ」という出力がなされるようなグラフのこと。実際には、同じ音素列を聞いても、どんな文字列が適切かは「選」ばないといけないが、その「選ぶ基準がMAP = Maximum a posteriori esimation」。これは、「最適パス」探索なのだが、この方法の良いところは、WFSTという仕組みがあって、音素列・文字列が長くなっても、グラフ自体を操作して簡約化できたりすることがある。また、このグラフ上で最適パスを見つけるアルゴリズム「Viterbi ビタビ」がある。ただし、ビタビアルゴリズムは優秀な動的計画法アルゴリズムだが、言語処理分野は巨大な探索空間を相手にするので、もっと効率化する必要がある。その効率化に現れるのが、ビタビの「尤度・確率」計算のトロピカル演算化である。トロピカル演算の軽さと、トロピカル演算の最適化問題が探索しやすいこととが、その「キモ」らしい
  - WFSTについてはこちら
  - ビタビとそのトロピカル演算についてはこちら
- ちなみに、トロピカル化は量子力学を古典力学的に引き戻す作用も持っている。量子力学では状態が複素関数であるところ、それを古典（実関数であり、理想気体のように要素間独立性が仮定できたり、絶対零度のような極限状態などへの近似を含む）にすることで、複素数に特有な「位相」を吹き飛ばすことができる。その位相を吹き飛ばす関数として、 $\log{複素数} = \log{|z|} + i \log{\theta}$ のような対数関数が活躍する。トロピカル化では、対数化関数が使われるが、それはそういう話。また、量子力学的な状態を「複素・代数的トーラス」がたくさん集まったもの（かけ合わせて作った、複素高次元トーラス）と見たときに、トロピカル化は、それを実高次元空間に移す関数として働く。また、機械学習の文脈では、（制限）ボルツマンマシンは学習を熱力学的に扱う仕組みだが、そこでもトロピカル化が使われるのは、熱力学～量子力学～そのトロピカル化による古典力学化と言う関係から理解することができる。また、トロピカル化によって、実格子とその上の凸包・整数問題化がなされることともつながる。その点でＲＢＭ（制限付きボルツマンマシン）とＭＡＰ推定との両方にトロピカル化が出てくることは、納得がいく・・・Geometry in the tropical limit（参考ペイパー（Restricted Boltzmann Machine)

Chapter 2 Probability Primer (確率とは、ランダム変数とは…)

Chapter 3 Algebra Primer (代数多様体、イデアル、グレブナー基底、Computational Algebra、射影空間・射影幾何)

Chapter 4 Conditional Independence (CI) (CI models、Primary Decomposition)

Chapter 5 Statistics Primer (統計モデル、データの型、パラメタ推定・仮説検定・ベイズ統計)

Chapter 6 指数型(分布)族 (Exponential families、実代数幾何、代数的指数型(分布)族)

いわゆる指数型分布族表現を離散確率変数に用いる
確率モデルは(r-1)-正単体内部に相当するとみることもできるが、指数型分布族にすると、(r-1)-次元実空間全体と見える
この空間が確率モデルの族であり、その点が特定の確率モデル
確率モデルにおける、観測データの尤度は、離散型確率変数の場合、有理多項式になる。分母は確率質量の総和が１であるとの制約を満足するための式に相当する
今、この分母の存在を射影幾何的に考えると、分子は斉次座標系のようなものになる
この分子の式は、変数の（非負）整数乗の掛け合わせになっており、「単項式」。すべての変数を等倍しても、同じモデルを表しているが、その特徴は、単項式イデアル。トーリックイデアルは、単項式の差によって構成されるイデアルのこと
- ここで「単項式のセット」→「トーリックイデアル」
- この取り出しにおいて、「十分統計量が等しくなるような、２つの単項式の引き算に相当する式（単項式の差の式）」がトーリックイデアルを生成するという意味で、「統計」が「トーリックイデアルの代数学」とつながる・・・ここに２ｘ２小行列式が登場したりもする
トーリックイデアルにグレブナー基底を与えると「よいこと」があり、代数アプリで実装されている
- ここで「トーリックイデアル」→「グレブナー基底」

Chapter 7 Likelihood inference (スコア等式の代数的解法、尤度の幾何、凸尤度関数、尤度比検定)

Chapter 8 The Cone of Sufficient Statistics (多面体)

Chapter 9 Fisher's exact test (条件付き推定、マルコフ基底、Graver基底、格子酔歩とPrimary decomposition、サンプリング)

Chapter 10 Bounds on Cell Entries (Integer Programming、グレブナー基底、Quotient Ring、Linear programming relaxation)

Chapter 11 Exponential Random Graph Models

Chapter 12 Design of Experiments (Computations with the Ideal of Points、グレブナー扇)

Chapter 13 Graphical Models (CI Description of Graphical Models)

Chapter 14 Hidden Variables (EMアルゴリズム)

Chapter 15 Phylogenetic Models (木と分岐)

Chapter 16 Identifiability

Chapter 17 Model Selection and Bayesian Integrals (Bayesian integrals and sngularitiyes、Information criteria)

Chapter 18 MAP Estimation and Parametric Inference (HMM、Normal Fans、Polytope algebra・Polytope propagation)

Chapter 19 Finite Metric Spaces (Metric Space、Cut polytope、トーリック多様体)

2021-05-14

ぱらぱらめくる『Algebraic Statistics in Practice: Applications to Networks』

ぱらぱらめくるシリーズ代数統計ネットワーク系統樹因果関係

arxiv.org

このペイパーでは
- Algebraic が：algebras, geometry, combinatorics　を指し、それらを使う統計手法を扱う
- Networksは：３つの例を扱う。Relational models, Causal structure discovery, Phylogenetics
- Applications として：Statistical achievements, Practical relevance の側面に焦点を当てる
1 Introduction
- 代数統計学の背景
  - 最小二乗法に基づく統計手法は、非常に広く用いられているが、それは連立線形方程式に基づく手法。これも「線形代数手法」と言えば、言える
  - 非線形な代数がそれに対比される形で現れた。対称性とか実験計画法とかを指す(？）。これらは「代数統計手法」とも言える
  - 指数型分布族に基づく手法もあり、これは凸性という幾何学的特徴に強く依存している。凸制約のある状況での関数・微分などに基づくものなので、そのような関数の代数を考えれば、代数統計ではあるが、『代数統計』と言うときには、解析的関数の代数以外を指して言うことが多いので、以下が対象となる
  - これらを経て、(計算能力の向上ともあいまって)登場しているのが、「(本ペイパーで扱う)代数統計手法」
- ３つのネットワークの特徴づけ
  - Relational models
    - 多要素の関係の有無・強さが観測される。その観測が、特定のネットワークモデルを設定し、それと合致するかどうかを検定する
  - Causal structure discovery
    - ネットワークは与えられるのではなく、データから見つけ出したい。「ネットワークとは要素と要素とのつながり～エッジである」とみなせば、このアプローチでは、頂点についての観測がなされ、それに基づきエッジのセット(とその重み)を見つけ出すことに相当する
  - Phylogenetics
    - これもグラフを見つけだす問題だが、見つけるべきグラフは木であって、その木のノードには、「観測対象である葉ノード」と「観測されない節・根ノード」とがあるという特徴がある
2 Relational models
- このモデルでは、ノード数が固定されたグラフのうち、特定の指標のセットが条件を満足するグラフをランダムに発生させる「ランダムグラフ」によって、「条件付きグラフ集合分布」を作成する。このためには「ランダムグラフ」の作り方を定める必要になる。その作り方も色々ある
- このペイパーでは、指数型分布族表現を持つランダムグラフモデルである"exponential family models of random graphs"に基づいて話を進めている
- exponential... とは、グラフを特徴づけるベクトル(十分統計量のセット)と、そのベクトルの要素ワイズの重みとの内積の指数関数に比例する確率を用いる。ここで要素ワイズの重みが分布の「θ座標」になる
- 検定には２種ある
  - Heuristic tests
    - 生成グラフ分布における観測グラフの外れの程度を定量する方法だが、外れの程度を測る指標の分布の素性が不明であるし、ネットワークの特徴ベクトルの選び方がarbitraryであるという問題がある
  - Asymptotic tests
    - ランダムであることにiidを仮定することが漸近近似では要求されるが、エッジのありなし・重みは、相互に独立にはできないので、そぐわない
    - 限定的なネットワーク形状・モデルでは漸近近似ができる統計量が知られていたりするが、一般化はできていない。特に疎グラフに合致しない(らしい)
- p個のノードにk変数のペアワイズ関連・遠近観測を行うと、 $p \times p \times i_1 \times ... \times i_k$ なる多元表になる。この多元表のセルは「ノードペア」の情報
- この多元表が求めるexponential random graph modelを表していると考えると、log-linear-ERGMになると言う
- 頂点次数を保存してグラフを改変する動きを、頂点ペア～辺の組(それを積にする)の加算・減算で表して、「代数化」する
3 Causal structure discovery
- DAG (Directed Acyclic Graph)。そのノードは観測される変数
- DAGの構造に応じて、変数の値の取り方に確率モデルを入れる。最も単純には変数間の関係に線形式を、乱雑項に正規乱数を取る
- 条件付き依存度 Conditional Independence (CI)に基づく変数(ノード)間の関係を導く。CI relationは、DAGの部品のようなものなので、それを組み合わせて、作りうるDAGはたくさんある。その際に用いられるのがMarkov property。そこからDAGを導く
- 完全グラフからスタートしてCIによりグラフを成型する。そのときにルールが必要で、そのルールがfaithfulであることを保証するのが実代数幾何の等式・不等式。その意味で「代数統計」
- Permutohedron とか Associohedronとかが出てくる
4 Phylogenetics
- 隠れたノードを含めて木のトポロジーの全体
- それらが、塩基の入れ替わりという「計算～代数」で繋がっている
- 尤度平面のglobal optimumや特異点についての情報を取り出すのにcomputational algebraが用いられる
- "Maximum likelihood estimation in statistics leads to the problem of maximizing a product of powers of polynomials.こちらのペイパーより" というような話と関係する
- データに基づいて、「よさそうな木トポロジー」を見つけたい

2021-05-12

ぱらぱらめくる『量子確率論への招待』

量子確率論パラパラめくるシリーズ正規分布半円分布酔歩格子木 C*-環

http://www.math.is.tohoku.ac.jp/~obata/research/file/1996-Nagoya-Forum.pdf

測度論的確率論は $(\Omega,F,P)$
量子論的確率論はC*-確率空間で $(A,\phi)$ 、Aが可換環なら古典論、Aが非可換環なら量子論
確率分布はモーメント列で(だいたい)決まる
量子確率論ではグラフを考える。グラフの頂点は群の集合の要素。グラフの「辺による移動」も群の集合の要素。ある頂点からある辺によって移動して別の頂点にたどり着くことは、群の二項演算によって表せるから、グラフ構造は群の幾何的構造と見える
各頂点に、「辺に相当する要素」を掛けて、(いくつかの)隣接頂点に移動することを考える。これをすべての頂点における「量子確率状態」の「確率推移」とみなすと、「辺に相当する要素」について、特定の１つの移動ではなくて、可能なあらゆる移動をすることを考えると、それは量子状態の言葉でいうと、ユニタリ作用
したがって、グラフ上の確率的な移動の全体(酔歩)の様相は量子確率ベクトルとユニタリ作用素で定義できる
今、ある頂点を原点とすると、「n次モーメント」は原点からn歩で原点に戻る道の数に比例することが示せる
その考えで行くと、格子グラフ(可換群 $Z^N$ )の場合のモーメント列の極限が、古典的な正規分布のモーメント列と一致する。また、k-分岐木(自由群 $F_N$ )のモーメント列の極限は、量子確率論でよく出てくる半円分布のモーメント列と一致する
この原点に戻って来る道の数え上げにあたって、自由群の場合にカタラン数が出てくるが、それを考えるときに、k本の一時独立なベクトルに関して、順方向と逆方向のそれが同じ回数ずつ現れること、その現れ方に非交叉対分割制約があることを使うことなどが登場する
気になったこと。閉じたグラフの辺ベクトルの制約にこの非交叉対分割があらわれるべきことと、戻って来る道の数とグラフのゼータ関数には関係があることの２つ。

2021-05-08

Boundary measurement mapの統計学的意味合い

Boundary measurement map Grassmannian グラフ Plabic graph Grassmannian graph 行列式 Determinant Total positivity Perfect orientation 団代数平面グラフ

arxiv.org

このペイパーでは、平面有向グラフ(ネットワーク)をPositive Grassmannian上の１点に対応付ける話をしている
平面有向グラフをPlabic graphと呼ばれる(無向で頂点が２タイプのグラフを円板内に配置したもの)に対応付けたり、さらに、Grassmannian graph(頂点タイプを２タイプではなく、もっと一般的にしたグラフ)に対応付けたりして、組合せ幾何的な取扱いをする話などがあったり、面白いのだが、その側面とは違う面～統計学的な意味合い(込み入った情報を持っていそうな対象を簡潔な表現にまとめ上げる)として、どう考えるかについて、メモしておきたい
平面有向グラフＧがある。頂点数|V|とする。周辺頂点数 Nb,内部頂点数 Ni とする。|V| = Nb + Ni である。
今、Ｇには、ある自然数 k ( $k \le Nb$ ) が取れて、 $k \times Nb$ 行列 M が与えられるという。
この行列Ｍについて、Nb個の列から、k列を取り出す場合の数は、 $d = \begin{pmatrix} Nb \\ k \end{pmatrix}$ 通りあるが、このd通りの $k \times k$ 行列の行列式を連ねたものをPlucker 座標と言い、Mを $d$ 次元空間の点(斉次座標になっているので自由度はd-1に減るが…)とみなすことができる、という。
この空間をGrassmannianと言う。Nb,kがGrassmannianの種類を定めるので $Gr(k,n)$ と書く。
これにより、Ｇを $Gr(k,Nb)$ 上の点とみなすことができる。
今、Ｍの要素の与え方に、あるルールを入れると、Plucker座標のすべての値が正になるので、Positive Grassmannian上の点とみなせる。逆にPositive Grassmannian上の点には、Nb,kを満足するグラフ表現も取れるのだと言う。
これにより、色々なGのGrassmannian上での相互位置関係がハンドリングできるようになるという、「嬉しさ」がある。これは統計学的に嬉しいことである。
もっと嬉しいことがある。
Gは $d = \begin{pmatrix} Nb \\ k \end{pmatrix}$ 個の座標で表せているし、 $Nb \times k$ 個の行列要素をその矩形の然るべきセルに置くというルールを付加すれば、d個の値で表せている。
さらに、Gの内部頂点(内部頂点は、その１頂点とそれに接続する辺とに着目することで、平面グラフとみなせる)ごとに、それに対応するGrassmannian上の座標(Plucker座標や、その情報を背負った行列表現)が付与できるが、Gのd個のPlucker座標は、この内部頂点のPlucker座標を用いて計算するルールがある。
そして、その計算ルールには、Ｇの有向グラフとしての構造が反映される。
これらのことは、Gの簡潔な表現として、Ｍやそれに定まるPlucker座標があるが、その完結表現が、Gの内部のピースの情報とGの構造とに関する情報を反映していること、また、それらをまとめ上げるルールが、Gに完結表現を可能にしている、ということを意味する。
「情報量の多い対象」に「モデルの族」という枠組みを与え、そのモデルの族の下で「特定のパラメタ値(のセット)」によって、特定のモデルによって説明する、ということに見える。
ちなみに、Gの内部の頂点に対応するGrassmannianもPositiveであるし、Gの内部の部分を取り出したサブグラフについてもPositive Grassmannianが対応するという意味で、「Total Positivity」がある
このTotal positivityを支えるのは、「引き算を含まない」関係式がGとそのサブグラフに付随するPlucker座標(という小行列式)に成り立つという背景関係である。
小行列式同士の関係に「引き算を含まない」関係式が成り立つことから、この情報集約は行列式を用いて構成されるが、「引き算を含まない」関係式で要素同士が繋がっている場合には、同様の「全体はたくさんだが、その部分を確定すると、全体が確定する」、しかも「total positive」という関係が得られる。
これが団代数と団変数で説明される(ことが多い？)。

2021-03-18

ニューラルネットワークでのトロピカル幾何

ニューラルネットワークトロピカル幾何トロピカル代数 ReLU

arxiv.org

この論文では、ニューラルネットワークでのactivation function をReLUに絞っても、まあ大丈夫、との判断の下、ReLUに絞った上で、ニューラルネットワークの入力から出力への変換がトロピカル幾何・トロピカル・有理関数で表現されることを説明している
ごく大雑把に言うと、ニューラルネットワークが作るモデルは非凸な多面体になるが、それは、凸多面体の差として関数表現されるが、この「関数の差」がトロピカル関数で言うと、関数の比になるので、トロピカル有理関数になる、と、そういう話
ReLUという活性化関数は、ニューラルネットワークで用いる活性化関数の１つだが、これに限定して話を進めても、ニューラルネットワークがどうしてうまく機能するのか、ということの本質的な議論にはある意味では大きな違いが生じないとみなす立場も取れる、ということで、ReLUに限局して話を進めている
ちなみに、ReLUという関数は、ある値より小さいときはゼロ、ある値から大きくなると、一次増加関数になるような関数だが、それは、 $max(ax+b, t)$ に相当し、これはトロピカル幾何では $(ax+b) \oplus t$ に相当するから、トロピカル関数と相性がよい：参照→

www.atmarkit.co.jp

ニューラルネットワークにより、d次元ベクトルが、p次元ベクトルに変換される
それを $y=(y_1,...,y_p) = max(A x + b,t)$ , $x = (x_1,...,x_d)$ と書くことにする。Aは $p \times d$ 行列であり、bは長さpのベクトルである
ここで、行列Aを、正の成分の部分と負の成分の部分とに分けて、 $A = A_{plus} - A_{minus}$ とする。このとき、 $A_{plus}$ も $A_{minus}$ も非負行列になっている
このとき出力 $y = max(Ax+b,t)$ は $max(A_{plus}x +b, A_{minus} x + t) - A_{minus}$ になるという
こういう分解は、いかにも、トロピカル関数的。なぜなら、max()関数を使っているし、行列はすべて非負成分だし、max() の項と $A_{minus}$ の項の引き算は、トロピカル有理関数に相当するから
とは言え、 $max(Ax+b,t) =max(A_{plus}x +b, A_{minus} x + t) - A_{minus}$ と言われても、え、ほんと、という感じがするので、手計算して正しいことを確認してみる

p <- 8
d <- 10

A <- matrix(rnorm(p*d),ncol=d)

x <- rnorm(d)

b <- rnorm(p)

t <- rnorm(1)

y <- A %*% x + b

y. <- apply(cbind(y,rep(t,p)),1,max)

Aplus <- A
Aplus[which(Aplus < 0)] <- 0

Aminus <- A
Aminus[which(Aminus > 0)] <- 0
Aminus <- - Aminus

#Aplus
#Aminus

range(A - (Aplus - Aminus))

y.. <- apply(cbind(Aplus %*% x + b, Aminus %*% x + t),1,max) - Aminus %*% x

#y.
#y..

range(y. - y..)

2021-02-14

Overleaf用にpubmedからcitation 情報を取り出す

Overleaf てふ pubmed 引用文献 citation

Overleaf

qiita.comは、オンライン上でLaTex文書を作るサイト

テンプレートもたくさんあるので便利
LaTexなので引用文献も

\cite{Yamada2020}

と文中に書き込んでおいて、引用文献を書きたい場所に

%This is where your bibliography is generated. Make sure that your .bib file is actually called library.bib
\bibliography{library}

%This defines the bibliographies style. Search online for a list of available styles.
\bibliographystyle{abbrv}

のようにしておき、library.bibなるファイルを置いておき、Yamada2020に対応する情報を、然るべき体裁で張り付けて置けばよい
そのしかるべき体裁をpubmedからひょいっと取って来るには、pubmedIDを確認し、このサイト

www.bioinformatics.orgのクエリにpubmedIDを入れて検索の上、 incl. abstract　オプションで exportすればよい

% 32275673
@Article{pmid32275673,
Author="Okada, D. and Yamada, R. ",
Title="{{D}ecomposition of a set of distributions in extended exponential family form for distinguishing multiple oligo-dimensional marker expression profiles of single-cell populations and visualizing their dynamics}",
Journal="PLoS One",
Year="2020",
Volume="15",
Number="4",
Pages="e0231250",
Abstract={Single-cell expression analysis is an effective tool for studying the dynamics of cell population profiles. However, the majority of statistical methods are applied to individual profiles and the methods for comparing multiple profiles simultaneously are limited. In this study, we propose a nonparametric statistical method, called Decomposition into Extended Exponential Family (DEEF), that embeds a set of single-cell expression profiles of several markers into a low-dimensional space and identifies the principal distributions that describe their heterogeneity. We demonstrate that DEEF can appropriately decompose and embed sets of theoretical probability distributions. We then apply DEEF to a cytometry dataset to examine the effects of epidermal growth factor stimulation on an adult human mammary gland. It is shown that DEEF can describe the complex dynamics of cell population profiles using two parameters and visualize them as a trajectory. The two parameters identified the principal patterns of the cell population profile without prior biological assumptions. As a further application, we perform a dimensionality reduction and a time series reconstruction. DEEF can reconstruct the distributions based on the top coordinates, which enables the creation of an artificial dataset based on an actual single-cell expression dataset. Using the coordinate system assigned by DEEF, it is possible to analyze the relationship between the attributes of the distribution sample and the features or shape of the distribution using conventional data mining methods.}
}

のように返って来るので、識別子の行 "% 32275673 "を削り、

@Article{pmid32375029,

の部分を、LaTex本文の記載に合わせて

@Article{Yamada2020,

と書き換えれば出来上がり
もちろん、書き換えずに、pubmedIDのまま、LaTex本文で引用しておけば、その書き換えの手間も不要