古典的機械学習手法を高階関数パイプラインとして再定式化する
著者: Asher Bond (asher.bond@distillative.ai)
要旨
本稿では、よく知られた三つの機械学習手法——決定木、k-means クラスタリング、勾配ブースティング——を高階関数のパイプラインとして述べ直す。各手法を原子的な手順へ分解し、その手順を標準的な関数コンビネータ map・reduce・filter へ対応づける。これらのコンビネータは関数型プログラミングにおける日常的な語彙であり [1, 2, 3]、アルゴリズムをこの語彙で表現すれば、計算内容を一切変えることなく、その構造と再利用可能な部品が明示される。得られるのは合成的な明快さである。古典的手法は大規模ニューラルモデルより解釈しやすく、計算資源の消費も小さい [4, 5]。そして手法を合成の観点から簡潔に記述すれば、その再利用可能な部品は再結合可能になる。
1. はじめに
現在の実践では大規模 Transformer モデルが主流を占めるが [4, 5]、古典的機械学習手法は解釈性の高さと計算要求の慎ましさゆえに、依然として価値をもつ。こうした手法を統一された合成的語彙で記述すれば、再利用可能な部品が明示され、再結合が可能になる。本稿はまさにこれを三つの手法について、高階関数を共通語彙として用いて行う。決定木の分割手順を map として書き直しても、木が計算する内容は変わらない——変わるのは構造が明示される点であり、それこそが本稿の寄与である。すなわち、各アルゴリズムの合成的な形を浮かび上がらせる再記述である。
2. 関連研究
関数コンビネータ。 map・reduce/fold・filter は関数型プログラミングにおける正統的な高階関数である。これらを通じて計算を表現することがモジュール性と推論に資するという主張は古典的であり [1, 2]、その基盤となる言語概念も同様に確立されている [3]。以下の変換は、新たなコンビネータを発明するのではなく、これらを再利用する。
手法そのもの。 決定木、k-means、勾配ブースティングは、本稿に何十年も先立つ教科書的アルゴリズムであり、本稿はそれらが計算する内容を何一つ変えない。より軽量で解釈しやすい手法が重量級のニューラルモデルを補完するという位置づけ [4, 5] こそが、これらを合成的に記述する動機である。
3. 三つの再記述
各手法をまず原子的な手順へ分解し、次にその手順を高階関数の言葉で名づける。付随するコードは骨格的であり——分解の内容を伝えるためのものである。
3.1 決定木
- 分解: 分割基準の評価、再帰的構築、枝刈り。
- HOF への対応づけ: 候補分割の全体に分割基準を
mapし、最良のものを選ぶためにreduceし、枝刈りのためにfilterする。
[ILLUSTRATIVE] 骨格:
# Schematic — communicates the decomposition.
def split_scores(data, criterion): # map: score each candidate split
return map(criterion, candidate_splits(data))
def build(data, depth=0):
if stop(data, depth):
return leaf(data)
best = max(split_scores(data, criterion)) # reduce: pick best split
left = filter(lambda x: x < best.threshold, data) # filter: partition
right = filter(lambda x: x >= best.threshold, data)
return node(best, build(left, depth+1), build(right, depth+1))
3.2 k-means クラスタリング
- 分解: セントロイドの初期化、距離計算、割り当て、セントロイドの更新。
- HOF への対応づけ: 各点にわたって距離と割り当てを
mapし、セントロイドを更新するためにreduce(グループ平均)する。
[ILLUSTRATIVE] 骨格:
# Schematic.
def assign(points, centroids): # map: nearest centroid per point
return map(lambda p: argmin_dist(p, centroids), points)
def update(points, labels, k): # reduce: mean of each cluster
return [mean(points_where(points, labels, i)) for i in range(k)]
3.3 勾配ブースティング
- 分解: 弱学習器の当てはめ、残差の計算、ブースティングの反復。
- HOF への対応づけ: 弱学習器を反復し、推論時にはその予測を
reduce(総和)する。
[ILLUSTRATIVE] 骨格:
# Schematic.
def fit(X, y, n):
residual, learners = y, []
for _ in range(n):
h = fit_weak_learner(X, residual) # one boosting step
learners.append(h)
residual = residual - h(X) # update residuals
return learners
def predict(X, learners): # reduce: sum learner outputs
return sum(h(X) for h in learners)
これらの素描は、各アルゴリズムの「形」を HOF の言葉で示す。フレームワーク固有の詳細を省くのは意図的である。主題は合成そのものであり、同じ map/reduce/filter の構造は、それを実現するフレームワークが何であれ成り立つ。
根拠と適用範囲
これは統一された語彙による再記述である。決定木、k-means、勾配ブースティングを map/reduce/filter を通じて表現すれば、計算する内容を変えることなく、その構造と再利用が明快になる——精度、計算量、スケーラビリティは、いずれも基礎となるアルゴリズムそのものの性質である [1, 2, 3]。コードブロックは各分解を伝える [ILLUSTRATIVE] な骨格である。ここで論じた利点——大規模 Transformer モデルに比しての解釈性と計算コストの慎ましさ [4, 5]——は古典的手法に属するものであり、合成的な記述はそれを可読にする。
References
- John Backus (1978). Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of the ACM. [1977 ACM Turing Award Lecture]
- John Hughes (1989). Why Functional Programming Matters. The Computer Journal.
- Christopher Strachey (2000). Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation. [Reprint of 1967 lecture notes]
- Ashish Vaswani et al. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS). arXiv:1706.03762.
- Tom B. Brown et al. (2020). Language Models are Few-Shot Learners. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2005.14165. [GPT-3]