1. はじめに 『 賭博破戒録カイジ 』という作品の中で、地下チンチロリンという賭け事が登場します。その賭けの中で主人公であるカイジは、大槻班長という人心掌握術に長けたタヌキにイカサマをしかけられてしまいます。そのイカサマに使用された不正なサイコロが、かの有名な「四五六賽」、4・5・6の面しか出ないという代物です。 主人公カイジは、類い稀な洞察力を駆使して、それまでの出目の記録からイカサマサイコロの不正を暴きました。凡人の私には気づけそうもないので、数学の力をお借りして、大槻班長のイカサマを暴いていこうと思います。 2. 隠れマルコフモデル:Hidden Markov model まずは、この大槻班長のイカサマ行動を隠れマルコフモデル (Hidden Markov model: HMM) というモデルを使って、モデリングしていきます。 […]
1. 状態空間モデル 状態空間モデルは、2つの確率過程からなります。1つは潜在変数・状態変数・隠れ変数といわれるもので、これは直接観測できないがマルコフ連鎖に従う変数だとモデリングされます。例えば景気の良し・悪し等、概念として存在するけれど直接は観測できないものを想像してください。2つめは観測値で、これは直接観測できるもの、つまりデータです。ただし変数に依存して観測されるとします。今の例ですと、例えば株価などを想像してください。意味としては株価は景気の良し悪しに依存して決まるということです。この観測値にも「状態変数で条件づけると過去の自分自身とは独立となる」という仮定を置きます。 1.1. 状態空間モデルの定式化 \( t = 1,2,…,T \) を時刻とします。\( d_{ \boldsymbol{ x } } […]
※今回からは、なんの断りもなく確率統計の記号を使用しますが、数式が意味が分からなくても、なんとなく雰囲気を掴めるように心がけました。数学が分からない人はとりあえず数式部分は深く考えず読んでください。興味が湧いたら、数学勉強してみてね! 前回の記事 1. ARモデル ARモデルは、日本語では自己回帰モデルと呼ばれ、例えるなら、今日の我が身が明日の我が身を作り上げるという、因果律を表現したモデルです。数式にすると、 $$ y_t = c + \phi_1 y_{t-1} + \varepsilon_t,~~~\varepsilon_t \sim \textrm{W.N.}(\sigma^2) […]
1. 時系列解析とは何? いきなりですが、時系列解析 (時系列分析ともいう) とはなんでしょうか?weblio辞書では下記のように説明がされていました。 じけいれつ‐ぶんせき【時系列分析】 ある対象に関する数量の継続的な時間変動を分析し、将来の予測に役立てる手法。株価・為替レート・消費需要・気温や雨量などの自然現象について、その変動の傾向・周期・不規則なふるまいなどを、解析的・統計的・確率的な手法を用いて分析することを指す。 weblio辞書 さて、この無味乾燥とした辞書的説明に具体例を添えながら、時系列解析のイメージをざっくりと掴んでいきましょう。 weblio辞書の説明は 「ある対象に関する数量の継続的な時間変動」を 分析したり 予測したりする とざっくり分解できるので、この3項目のそれぞれ具体的なイメージが湧くように具体例を添えながら説明していきます。 1.1「ある対象に関する数量の継続的な時間変動」とは? まず、「ある対象に関する数量の継続的な時間変動」を時系列データといいます。時系列解析では、この時系列データと呼ばれるデータのみを扱います。 […]
Prophetの概要 ProphetはFacebook社が開発した時系列解析ライブラリです. Prophetでは, 時系列データ \(y(t)\) を3つの項の和としてモデリングします. $$ y(t) = g(t) + s(t) + h(t) + \varepsilon_t$$ […]
配送最適化(Vehicle routing problem)とは、1つまたは複数の拠点の荷物を、顧客がいる場所に運ぶ際、移動コストを最小にするような経路を求める問題です。 VRPにはいろいろな種類があります。CVRP:車両の積載量(数)に上限があるものVRPPD:集荷と配送があるものVRPTW:配送の希望時間(Time window)が指定されるものなどなど。(参考:wikipedia https://en.wikipedia.org/wiki/Vehicle_routing_problem) 問題 まずは簡単に、配送センターは1つ、1台の車両で5つの荷物まで一緒に運べる、という条件を考えてみます。・下図のように、弊社がある五反田駅あたりに(架空の)五反田集配センターがあります。・その周辺で、20人の顧客宅を緯度経度をランダムにピックアップしました。この20人に荷物を届けます。・実際は、移動時間をコストにすることが多いと思います。移動時間は地図APIなどを使って求めるのが良いかと思いますが、今回は簡単のため、緯度経度の差から概算しました。・20人の荷物を、上限5個ずつ車両に載せて運ぶとき、どれとどれをまとめてどのような経路で行けば一番短い時間で済むか、という問題です。     変数1:荷物が通るルートを表す変数 何を変数とするかを考えます。まずは、20人のそれぞれの荷物を集配センターから顧客宅へ届けなければならないので、それぞれの荷物が通るルートが変数になるようにします。\( p[i][j][k] \) : 顧客iの荷物がポイントj→ポイントkの間のパスを通る場合1、通らない場合0 とします。\( […]
はじめに 以前、敷き詰めパズルのペントミノを量子コンピュータで解いてみようとしたところ、なかなか解が出なくて大変だったので、同じ問題をPULPで組合せ問題として解いたらどうなるかやってみようと思います。 問題 ペントミノとは、5つの正方形を組み合わせた形状のことで、下図左の12個のピースがあります。ピースは、回転したり、裏返したりすることができます。これらのピースを、下図右のようなボートに敷き詰めていきます。 考え方 まずはピースp1のボードへの置き方を考えてみます。例えば、横向きにb1,b2,b3,b4,b5のところに置く、それを右に1つずらしてb2~b6のところに置く、などのような置き方が考えられます。また、縦向きにして、b1,b11,b21,b31,b41のところに置く、というような置き方も考えられます。横向きにしておく置き方が36パターン、縦向きにしておく置き方が20パターン、全部で56パターンあるようです。これらの置き方すべてを列挙し、それぞれprb[0][]=[1,2,3,4,5],prb2=[2,3,4,5,6]・・・のような配列に入れておきます。 prb[0][0]=[1,2,3,4,5] :ピース1(配列では0になっていますが)の置き方0は、ボードの「1,2,3,4,5」の部分をカバーする、というような意味です。 同様にしてすべての12ピースについて置き方を列挙します。ピースによっては、例えばp8のピースでは、回転と反転で8パターンあり、さらにボードへの置き方があるので、置き方の組合せもたくさんあります。 もちろん、すべて手作業で列挙するのは大変ですから、例えばp2のピースを のような配列で表して、プログラムで回転・反転・置き方を計算しました。ボードへの置き方では、例えばピースp11をボードの隅に置くような置き方は意味がありませんが、そのような置き方もすべて列挙しました。そのような置き方は、最適化計算で弾かれるはずだからです。 立式 PULPで数式化します。パズルなので、最小化・最大化する問題ではなく、すべて制約条件で書きます。 ■制約条件11つ目の制約条件は、各ピースの置き方の中から1のみが選ばれる、という制約条件です。例えばピース1は置き方が56パターンありますが、その中から1つの置き方のみが選ばれないといけません。それぞれの置き方が採用された場合1,採用されなかった場合0となるようなバイナリー変数で以下のように立式します。 これをすべてのピースについて制約します。12ピースそれぞれ、1つの置き方のみが選ばれる制約条件になります。 ■制約条件22つ目の制約条件は、ボード上でピースが重ならないようにする、というものです。例えば、ピース1の置き方として、[1,2,3,4,5]、ピース6の置き方として[2,11,12,21,22]という置き方が考えられますが、この2つが採用されるとボード上の2の部分が重なってしまいますのでダメです。そのため、「ボード上の同じ場所に置かれるような置き方から1つのみを選ぶ」というのを制約条件を設定します。例えばボードb1に関する式は以下のようになっています。 […]