
# 熱帯代数（トロピカル代数）とは


最小値をとる操作と足し算の２つの二項演算によって定義される代数系のことを熱帯代数、トロピカル代数、min-plus代数といいます。オペレーションズ・リサーチにおいて幅広い応用があるそうです。


先日[Tatsuya Hirose](https://qiita.com/lotz)さんが投稿された[動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜](https://qiita.com/lotz/items/094bffd77b24e37bf20e)を拝見してこの分野を知り、関心をもつようになりました。2020年8月8日段階で445LGTMsを集めるなど世間での関心が高いことが伺えます。今回記載されている内容を自分でもPythonで実装してみることにしました。熱帯代数の詳しい定義や問題設定など、僕の記事での実装の背景はここでは改めて説明しないのでもとの記事をご覧ください。


# なぜPythonで実装するのか


上では最小値をとる演算と加算をもつ代数系と熱帯代数を説明しましたが、実際にはもう少し踏み込んで「最小値をとる演算を通常の加算の代わりに」「加算を通常の乗算の代わりに」利用して内積や行列積を定義するところがカギになってきます。Pythonでは`__add__`を定義することで`+`の、`__mul__`を定義することで`*`の振る舞いを実装することができますが、この機能を利用することで数式の見た目とコードの見た目が一致して可読性があがります。


また元の記事ではHaskellを採用しており、実際に順序付け関数を別々に実装することでグラフの辺と重みという異なる対象を同じmin演算で呼び出すという関数型らしい実装をしています。この機能も`__le__`, `__ge__`を定義して`<=`, `>=`の振る舞いを定義できるPythonでうまく再現できそうです。


# 最短経路問題


実際に実装する前に、今回やろうとしていることを簡単に解説します。


元記事に掲載されている重み付きグラフの画像は以下のようになります。

<img style="width: 100%;" src="https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.ap-northeast-1.amazonaws.com%2F0%2F17134%2Fedfca915-97bf-7792-0a09-2c06fd7baf83.png?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&s=2e159b210bc0ab1e351c76235fb4010a" alt="画像が表示されない場合は元の記事を参照ください"/>

もし点同士の間に橋がかかっていなければ、そこは渡ることができません。便宜上コスト無限大の橋がかかっていると見做すこともできます。


このグラフ上で各点から各点へちょうど$n$回で橋を渡って行ける方法のなかで最短（重みの和が最も小さい）のものを探します。なぜこれが熱帯代数と関係するのかはベクトルの内積のしかたに秘密があります。

例えば、点aから２回で点dに行きたいとします。

点aからは直接には点aや点dに行くことはできず（コスト無限大）、点bへはコスト２、点cにはコスト４で行くことができます。各点への移動のコストをa,b,c,dの順に並べてベクトルで表すと$(\infty, 2, 4, \infty)$となります。


点dに点a,b,c,dそれぞれ**から**直接行くときのコストを同じように並べると$(\infty, 9, 5, \infty)$となります。


点aから点bを経由して点dに行く時、コストは２つの橋の合計になりますから$(\infty, 2, 4, \infty)$の第2要素と$(\infty, 9, 5, \infty)$の第2要素の和11がコストになります。同様に各点を経由した時のコストはベクトルの要素同士の和を見ればわかります。

$$(\infty, 11, 9, \infty)$$


そしてこの中の最小値をとれば最短経路のコストがわかります。

このように、最短経路は

<center>ベクトルの要素を足す -> 結果の最小をとる</center>

で求めることができます。一方で通常、ベクトルの内積は

<center>ベクトルの要素をかける -> 結果の和をとる</center>

となります。つまり掛け算の代わりに足し算を、足し算の代わりに最小を使う熱帯代数ではベクトルの内積によって（行列の積はそれを繰り返すので、最終的には行列の積によって）最短経路問題を解くことができます。


# ソースコード

今回実装した内容はこちらにまとめているので参考にしてください。

https://github.com/yaufai/python-notebook/tree/master/python_notebook/tropical_algebra_shortest_path

* 前半の最短経路のコストを求めるところまで: https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py
* 後半の最短経路の経路を求めるところまで: https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py


# 熱帯ベクトルを実装して最短経路のコストを求める


まずベクトルを定義します。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=5:8"></script>

なお、`float("inf")`で無限大を表す`float`型のオブジェクトを作成できるので、重みを表現するのに必要な条件は`float`だけで十分です。


そして加法と乗法を定義します。ベクトル空間には乗法は定義する必要はありませんが、今回はベクトルの乗法は`float`型の乗法が通常の足し算であるとみなした時の内積になっています。普段使ったり意識しているベクトルの積と異なる場合は混乱しないよう気をつけてください。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=15:32"></script>


このベクトルとその内積をもとに行列と行列の積を定義します。数学では縦ベクトルをつかって行列を表記することが多い気がしますが、横ベクトルを並べたものを行列としているので注意です。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=35:38"></script>
<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=48:68"></script>

冪乗は指数を減少させる再帰処理で実装しました。本当は基本行列を定義するともっとすっきりします。


上のグラフ上で２回、３回の橋を渡って行ける最短経路のコストを求めます。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=85:95"></script>


```
$ python tropical_algebra_1.py
['[inf, 2, 3, 9]', '[12, 0, 1, 6]', '[8, inf, inf, inf]', '[inf, 5, 7, inf]']
['[12, 2, 3, 8]', '[9, 0, 1, 6]', '[inf, 10, 12, inf]', '[inf, 5, 6, 12]']
```


# 橋にも代数系を定義して最短経路も求める

最短経路のコストはわかりましたが、最短経路自体がわからなければその解を実行することはできません。ここでは最短経路を求めるためにグラフの辺の集まり（経路）に対して最小と加算を定義していきます。そしてそのためにまずは抽象的な熱帯代数の枠組みを定義します。

まず熱帯代数の一つめの演算である「最小」についてですが、これは大小の比較さえ定まれば自明に決まります。一方、加法はそうではないので熱帯代数のクラスは大小比較(`__le__`, `__ge__`)と加法(ここでは乗法`__mul__`)を抽象メソッドにしたクラスとして定義します。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=9:36"></script>


前半までにやったような重みは

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=40:52"></script>

というように定義できます。
また経路に関しても同様に順序と乗法を定義すれば熱帯代数の元になれます。`None`は経路が存在しないことを示しています。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=53:70"></script>

まず大小比較ですが、経路のコストが小さいほどその経路が小さいと評価されることが重要です。つまりコストの最小化と経路の最小化が一致するので、あとで最小の演算が実行されるときに対応する最短経路が計算されることになります。乗法については通常のリストの結合と同じに定義してあります。コストの追加と対応する辺の経路への追加が一緒になるようになっています。


熱帯代数の元が定義できたのであとはそれを元にベクトルと行列を定義するだけです。これらは熱帯代数の元の加法（最小）と乗法（加法）を呼び出すだけで実際の熱帯代数の元の値などには依存しないので抽象クラスにする必要はありません。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=71:146"></script>


あとは重みを表現する隣接行列`A`と経路の行列`P`を以下のように定義すればグラフの描写は完了です。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=147:160"></script>



二乗を計算してみます。
<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=162:165"></script>


```
$ python tropical_algebra_2.py
['[inf, 2, 3, 9]', '[12, 0, 1, 6]', '[8, inf, inf, inf]', '[inf, 5, 7, inf]']
['[None, [(1, 2), (2, 2)], [(1, 2), (2, 3)], [(1, 3), (3, 4)]]', '[[(2, 4), (4, 1)], [(2, 2), (2, 2)], [(2, 2), (2, 3)], [(2, 3), (3, 4)]]', '[[(3, 4), (4, 1)], None, None, None]', '[None, [(4, 1), (1, 2)], [(4, 1), (1, 3)], None]']
```

最短経路が求められていることがわかります。


# 結び

他の方がすでに実装された内容を他の言語で再実装しただけの簡単なものでしたが、Pythonなりの抽象化のしかたや表現のしかたが見せれたと思います。


僕としては代数的な性質を意識しながらプログラムしたのがはじめてだったので面白かったです。特に、グラフの経路に対してよくいう「数」と遜色なく演算を定義して問題を解けることを確認できたのは、現代数学の抽象化の威力を再確認できました。


熱帯代数については応用は狭くなさそうなので、これを機に他の応用例についての文献を勉強したり、また他に代数をうまく活用した問題解決があればそちらも見ていきたいです。





# 目的

株取引をしている友人から移動平均線を使った取引手法が実際に通用しているのか検証したいという相談を受けました。彼はあまりプログラミング関連の知識はありませんが、問題をきちんと数式で記述できます。コードの勉強をしてからようやく彼の問題意識の検証、ではあまりに時間がもったいないです。

数式に近い形でクエリの条件をかけるような検索ツールがあれば、SQLやExcelを扱えなくても簡単なPythonが書ければすぐに分析に取り掛かれます。また、コードの可読性も大幅に向上します。

というわけで最低限の機能ですがデータ検索のためにQuerypyを公開しました。
[https://github.com/yaufai/querypy](https://github.com/yaufai/querypy)

# 簡単な使い方

おそらく例をみれば使い方はすぐ分かるかと思いますので、READMEの簡単な日本語訳を載っけます。
例えば下のようなデータから成績が条件を満たす（合格点に達しているか、など）学生を知りたいとしましょう。
```csv
名前, 解析入門, 経済学入門
山田,      80,      50
　劉,      50,      80
```

検索用のオブジェクトとクエリを作成すればすぐに結果を得ることができます。
```py
from querypy import Querypy

data    = Querypy.read_csv("scores.csv", "名前")
math101 = data.get_term("解析入門")
econ101 = data.get_term("経済学入門")

pass_math_exam  = math101 >=  60
better_in_econ  = math101 < econ101

print(data.find(pass_math_exam))
# -> ['劉']
print(data.find(better_in_econ))
# -> ['山田']
```

論理積や論理和を使った複雑な式にも対応できます。
```py
print(data.find(
    (econ101 == 100) & (math101 == 100)
))
# -> []　（全教科満点はいなかった）
print(data.find(
    (econ101 >= 60) | pass_math_exam
))
# -> ['山田', '劉']  （どれか1つに合格した人は2人でした）
```

# 実装にあたって

本来`==`はオブジェクトが同じものかを比較しますが、`math101 == 100`は`bool`値としては評価されていません。これを可能にしているのはPythonの演算子の振る舞いを上書きしているからです。

例えば`==`では
```py
    def __eq__(self, term: Term) -> Formula.Formula:
        return self.__abstract_operator__(term, Formula.Relations.Equal)
```
というメソッドで上書きしています。型アノテーションをみると分かるように、返り値は`bool`ではなく`Formula.Formula`となっています。このオブジェクトがCSVの項が条件を満たしているかの判断に責任を持っているわけです。

# 今後、やっていきたいこと

現在このツールはまだまだ最低限の機能（いや、それよりも少ない）しか持っていません。自分で使うにもまだまだ不自由なので追加していきたい機能として以下のものを考えています。

読者の方でもしこのソフトウェアに貢献されたい方が見えましたらぜひご協力ください。下にないものでも大歓迎です！

## ユニットテストを書く

手元である程度動くことを確認した程度で本来公開するのに必要な水準さえ確認できていません。

## 数値以外にも対応

現在は主キーを除いて全ての要素は数値しか取ることができません。例えば「経済学を専攻していてEcon101で80点以上」のようなクエリは（わざわざ専攻に数値をわり当てるなどの工夫をしなければ）対応できません。

## JSONなどに対応

基本的にはCSVファイルだけでも多くのことが表現できていますが、他にデータを記述する形式があるので、そちらの方も視野に入れていきたいです。

## 関数をつかった表現

現在は要素の比較までしか対応できてません。でもデータ分析には本来もっと複雑な条件が関わってくるはずです。

例えば上の例で「二教科の合計点が100点以上」というようなクエリで絞り込みたいときに合計を求める自作関数`compute_total_score`をみたいにかけるといいなと思っています：
```py
def compute_total_score(terms: List[Term]) -> Union[float, int]:
    return reduce(lambda acc, cur: acc + cur, terms, 0)

query = compute_total_score([math101, econ101]) >= 100
```

## 二項間の関係

現在は、各行ごとに条件をチェックしています。学生の成績のように個別に評価する場合はそれで十分ですが、時系列データで「昨日は条件Aをみたし、今日は条件Bをみたす日付の組すべて」みたいな検索はできません。

## 2つのCSVを利用

関係モデルのデータベースのような構造をもった複数のCSVが扱えればようやく多くの実務で使える検索ツールとしてはじめの一歩を踏み出せたといえるでしょう。


# バージョン0.0.1

先日公開した[Querypy](https://github.com/yaufai/querypy)で
1. テスト環境の整備
2. 関数記号の導入

までやったのでバージョンを0.0.1にしました。

## テスト環境

[momotaro98](https://github.com/momotaro98)さんがutilsのテストを書いてくださったついでに、READMEの開発指南にテスト関係の項目を追加しました。今後は重要な機能であったり複雑なロジックを実装した部分を意識しつつテスト済みコンポーネントを増やしていきたいです。

## 細かいREADMEの修正

READMEのスクリプトが間違っていたので修正しました。

## 項の間の演算

加減乗除とべき乗をつかって計算できるようになりました。

例によって以下の`scores.csv`を読み込んで条件に合う学生を探し出しましょう。
```csv
名前, 解析入門, 経済学入門
山田,      80,      50
　劉,      50,      80
```
```py
data    = Querypy.read_csv("scores.csv", "名前")
math101 = data.get_term("解析入門")
econ101 = data.get_term("経済学入門")
```

例えば二教科`math101`, `econ101`の合計点数は`math101 + econ101`と表現して実際に条件式に組み入れることができます。

```py
data.find(math101 + econ101 >= 100)
# -> ['山田', '劉']
```

他にも加減乗除、べき乗すべてが同様に条件式のなかで扱えることになります。

```py
# 解析入門のほうが点数が高い人
math101 - econ101 > 0

# 数学の点数を1.5倍の重みで評価する場合
math101 * 1.5 + econ101 >= 120

# 経済学入門のほうが１０％以上点数が高い人
econ101/math101 >= 1.1

# 両方共50点との距離を測る
(math101 - 50) ** 2 + (econ101 - 50) ** >= 100
```

## 関数記号の導入

関数記号を導入することでレコードに任意の演算を施した結果をつかって条件を記述できるようになりました。

例えばGPAを以下のようなルールでつけて、GPA３以上の学生を見つけたいとしましょう：

* 60点以上69点以下：２点
* 70点以上79点以下：３点
* 80点以上　　　　：４点

この条件分岐を含んだ式は上のような加減乗除べき乗だけでは表現できませんが、

```py
def get_grade_point(test_result):
    if test_result >= 80:
        return 4
    elif test_result >= 70:
        return 3
    elif test_result >= 60:
        return 2
    else:
        return 0

def get_gpa(math, econ):
    return (get_grade_point(math) + get_grade_point(econ)) / 2
```

という関数を用意すれば`get_gpa(math101, econ101)`みたいな感じで計算できそうです。これを条件式に組み込みたいときはまず

```py
from querypy.FunctionSymbol import FunctionSymbol

gpa_func_sym = FunctionSymbol(get_gpa)
```

という形で関数記号オブジェクト（`FunctionSymbol`）を作成します。
そしてそのあとは通常どおりに条件式を不等号をつかって作成できます。

```py
data.find(gpa_func_sym(math101, econ101) >= 3)
```

# 今後の方針

## ２つのレコードを利用

順序付きデータや時系列データでは
「前の項が条件Aをみたして次の項が条件Bをみたすもの」
「一時間での差分が５％以内」
など複数レコードにまたがる条件が使えると便利です。

まだこの機能の構想、設計ができていないのですぐにコードに落とし込むことはできませんが、逆になにかアイデアがあればIssueいただけると嬉しいです。

## テストの充実

せっかくテストのルールを作ることができたのでそれを活かして製品の質を上げていきたいです。

## 対象レコードの範囲

今はかなりかぎられた条件を満たすCSVしか使うことができません。
より一般的なCSVでも検索できるよう、またJSONなどほかの形式でも扱えるようにデザインを変更していきたいです。