数理最適化と機械学習を比較してみる

数理最適化 Advent Calendar 2022 の記事です。

何の話かと言うと

Pythonではじめる数理最適化 ―ケーススタディでモデリングのスキルを身につけよう―

作者:岩永二郎,石原響太,西村直樹,田中一樹
オーム社

上記の書籍の第7章では、次のような問題を取り扱っています。

細かい点は書籍に譲りますが、まず、生データとして次のようなデータが与えられます。

これは、あるショッピングサイトの利用履歴を集計して得られたもので、あるユーザーが同じ商品を閲覧した回数（freq）と、その商品を最後に閲覧したのが何日前か（rcen）の2つの値から、そのユーザーが次にサイトにやってきた時に、再度、その商品を閲覧する確率（prob）を実績ベースで計算したものです。実績ベースのデータなので、ガタガタしたグラフになっていますが、理論的には、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件を満たした、なめらかな曲面になると期待することができます。

そこで何らかの方法で、このようななめらかな曲面のグラフを得ることができれば、これを予測に使うことができます。このサイトにユーザーがログインした際に、該当ユーザーの過去の閲覧履歴から、このユーザーが再度閲覧する確率が最も高い商品（つまり、このユーザーが、今、最も関心を持っている商品）を予測して、「おすすめ商品」として先回りして表示するなどの利用方法が考えられます。

原理的には、上記の実績ベースのグラフをそのまま使って予測することもできますが、実績ベースのデータは、理論的に妥当な予測値に対して、たまたまこのデータに含まれていたノイズ（理論には合わない例外的な行動や誤ったデータ）が加わってガタガタした結果になっていると考えれば、それよりも、理論的に妥当ななめらかな曲面のグラフで予測した方が、予測の精度は良いものと期待できます。

機械学習による予測

それでは、みなさんであれば、どのような方法で「理論的に妥当ななめらかな曲面のグラフ」を手に入れるでしょうか？　機械学習になじみのある方であれば、「上記のデータを学習データとして、最小二乗法で学習すればよいのでは？」と思いつくかもしれません。--- はい。私も最初、そう思いました。

で、やってみました。

データ数がそれほど多くないので、複雑なモデルにすると、簡単にオーバーフィッティングするのが目に見えているので、まずは、シンプルな線形モデルでやってみました。

　 $({\rm prob}) = w_1 ({\rm freq}) + w_2 ({\rm rcen}) + b$

というモデルを用意して、二乗誤差が最小になるように、 $w_1, w_2, b$ の値を学習します。

結果はこちらです。

確かに、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件は満たしていますが、元データと比較すると、ちょっと「ズレ」が大きい気がします。もうちょっと改善したいところです。

で、次の手として、二次の項まで含めたモデルにしてみました。

　 $({\rm prob}) = w_1({\rm freq}) + w_2 ({\rm rcen}) + w_3 ({\rm freq})^2 + w_4 ({\rm rcen})^2 + w_5 ({\rm freq}) ({\rm rcen}) + b$

結果はこちらです。

先ほどの結果と比べると、元データに近い、もっともらしい結果が得られました。これなら使ってみてもよさそうです。

・・・・なのですが、よーくみてみると、この結果は、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件が満たされなくなっています。

「予測精度が十分高ければ、このような条件を厳密に満たしてなくてもいいじゃん」という機械学習らしい考え方もできますが、仮に、どうしてもこの条件を満たす結果が必要であれば、みなさんならどうします？？？

まぁ、いろいろな方法がありそうな気はしますが、モデルそのものに作為的に手を加えすぎると、「データから学習する」という機械学習の本質からずれていきそうで、ちょっとアレな気分にならなくもないですね。

数理最適化モデルによる予測

一方、前述の書籍は、数理最適化の本なので、機械学習ではなく、数理最適化モデルを用いて予測を行います。詳細は、書籍に譲りますが、凸二次計画問題にモデリングして、

・recn に関する単調性
・freq に関する単調性
・recn に関する凸性（下に凸）
・freq に関する凹性（上に凸）

という制約条件を加えて最適化を行います。結果として、次のようなグラフが得られます。

最終的に、「予測値と実績値の二乗誤差を最小化する」という条件で最適化をおこなっていますので、この点については機械学習と同じことをやっていると言えますが、結果に対する単調性や凸性を明示的に制約条件として指定している点が、機械学習とは大きく異なるポイントになります。

数理最適化モデルと機械学習では、それぞれに得意・不得意がありますが、これまで機械学習を学んできた方で、「数理最適化はまだよく知らない」という方は、数理最適化モデルについても学んでみると、このような比較から、機械学習への理解がさらに深まるかもしれませんね。

追記

うーむ。確率をモデリングするならとりあえず、pをlog(p/(1-p))に変換した値をフィッティングすることを考えるかなぁ。いきなり多項式フィッティングは私はしないかなぁ。 https://t.co/icy3BOfMi6
— Takashi Miyamoto (@tmiya_) 2022年12月19日

この記事を公開した後、上記のコメントを Twitter でいただきました。ごもっともですね。確率値には $0\le p \le 1$ という本質的な制約がありますので、 $-\infty\le x\le\infty$ の値を取る線形モデルでフィッティングするというのは、筋のよいやり方ではありません。線形モデルの出力 $x$ をロジスティック関数