SSブログ
最適化(数理計画法) ブログトップ

数理計画を実施した後のABテストの注意点 〜その1 コントロールグループ [最適化(数理計画法)]

よく施策が有効かどうかをABテストを実施して確認することが多いです。
単にMLや統計モデルのABテストだとそれほどややこしくはないですが、数理計画を実施すると少しややこしくなるので注意が必要。

例えば、クーポンやポイントを付与するかどうかをMLを使って判断する場合、コントロールグループをどう設計するかです。

まずは、コントロールグループの取扱い。

全データ
┗ CTLグループ(全員、一律)
┗ テストグループ(付与する人と付与しない人がいる)

MLの効果を判断する際に、うっかりやってしまう間違いとして

うっかりする間違い
・CTL(CTLグループ + テストグループのCTL)
・テストグループで付与する人

正しい計測方法
・CTL(CTLグループ)
・テストグループ(テストグループで付与する人 + テストグループのCT)


この様に書くと、当たり前のようにみえるのですが、テストが複雑になってくると、うっかりやってしまうので注意が必要。
・CTL
・テスト1
・テスト2
・テスト3

特に、数理計画などが絡んでくる場合、どう設計するかは複数の視点でレビューしたほうが良いかと思います。

nice!(0)  コメント(0) 
共通テーマ:学問

Pythonではじめる数理最適化: ケーススタディでモデリングのスキルを身につけよう [最適化(数理計画法)]

元同僚が書いた本。
数理計画の考え方を身につけると、ビジネス上の要件(制約条件)をシンプルに定式化し解くことができます。

知らないと、複雑なルールベースを設定したり、それっぽい結果を出して満足するということになってしまます。

そんな数理最適化とPythonという面白い組み合わせの本。
一読の価値ありだと思われます。


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

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

  • 出版社/メーカー: オーム社
  • 発売日: 2021/09/21
  • メディア: 単行本



nice!(2)  コメント(0) 
共通テーマ:学問

データサイエンティスト協会 セミナー2018 第2回 ~最適化~ [最適化(数理計画法)]

データサイエンティスト協会 セミナー2018 第2回
https://techplay.jp/event/682183

最適化(数理計画)のセミナーで講演してきました。
元々、統計モデル(マーケティングサイエンス)側の人なので、最適化にフォーカスした講演はあまりしたことがなく、少々不安でした。

どこまで伝えることが出来たかわかりませんが、これをきっかけに最適化にもチャレンジする人が出てくると嬉しいです。

nice!(4)  コメント(0) 
共通テーマ:学問

量子コンピューター [最適化(数理計画法)]

情報処理学会の講演で「量子コンピューター」についての講演会がありました。

以下、簡単なまとめ(備忘録)

量子コンピューターと呼ばれているものは、
・ゲート模式
・量子アニーリング
の二種類。

g

組み合わせ最適化を考えた場合、2nの組み合わせを計算すると膨大な計算量になる。
量子の揺らぎを利用することで、最適解を高速にみつけることができる。
ということで、量子コンピューターが着目されている。

量子アニーリングマシン(D-Wave本体)は数十億円、世界に数台しかない。
クラウド利用だと安価に利用できる。

ゲート方式は現状は小規模の問題しかとけないので、実用化には10年くらいかかる。
しかし、GoogleやAlibabaはそこに1兆円単位の投資(人+金)をかけてきている。

Googleは、ゲート模型と量子アニーリングの両方を持っており、Googleのサービス利用(有料)を視野に入れて開発をしている。
Amazonも同じ路線。

IBMでのカンファレンスでは、実事例はほとんど出てこなかったが、D-Waveのユーザカンファレンスでは、実用されている事例が出てき始めている。

いずれにしても、アメリカ、カナダ、中国、欧州は、量子コンピューティングに莫大な投資をしています。
すぐの実用化は難しいものの、10年くらいのスパンでみれば、何もやっていないリスクは大きい。
(日本は出遅れている・・・)

nice!(0)  コメント(0) 
共通テーマ:学問

応用に役立つ50の最適化問題 [最適化(数理計画法)]


応用に役立つ50の最適化問題 (応用最適化シリーズ)

応用に役立つ50の最適化問題 (応用最適化シリーズ)

  • 作者: 藤澤 克樹
  • 出版社/メーカー: 朝倉書店
  • 発売日: 2009/08
  • メディア: 単行本



買って読んでみました。

言葉の定義とか、実際の事例がまとまっている本です。

実際に自分が解きたい問題がどんぴしゃで載っているかといえば、そんな場合は滅多になく、重要なのは、自分が解きたい問題をこの本に書かれているような問題に帰着することができる能力だと思われます。

ちょっと見方や発想を変えるだけで、問題がシンプルになる場合が多く、そのあたりが分析者の力量なのかもしれません。

nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:学問

SEOの最適化 [最適化(数理計画法)]

4月になって新体制のスタート。
実際に動き出すのはGW後くらいからだろうけど。。。

ちょうど、この期が変わる時期が一番暇なので、日々の業務と離れて基礎研究っぽいにチャレンジする良い時期だ。

そこで考えたことが、
"リスティング広告の最適化みたく、ロジカルにSEOに関しても最適化できないか?"
制御できる変数が異なるのと、SEOの方が期間的に長くなるが、同じようなロジックで最適化できそうだ。

発展形として、アトリビューションっぽい方向に進むとか、SEOとリスティングの融合ってことも考えられるが、まずは、SEOでの最適化アルゴリズムを作ってみようと思う。

nice!(31)  コメント(0)  トラックバック(0) 
共通テーマ:学問

数理システム 事例紹介セミナー [最適化(数理計画法)]

数理システムにて、NUOPT 事例紹介セミナー で発表してきました。
http://www.msi.co.jp/nuopt/seminar/seminar_recruit.html

会場に着くと、思った以上に人が多く驚きですた!(・∀・)
モデルの話やら最適化の話をして、無事に終了。

2009年11月20日(金)のユーザーコンファレンスでも発表予定です。
http://www.msi.co.jp/userconf/09/

場所:アカデミーヒルズ(六本木ヒルズ 49F)
参加費:無料

5時くらいに終わったので、セミナーを聞きに来てくれた人を交え、みんなで飲みに行きました。
新宿マルイに入っている【いのこ家】という豚肉専門店。
一人4,000円~5,000円くらいで食べることができます。

nice!(1) 
共通テーマ:学問

数式を使わない最適化の簡単な原理 [最適化(数理計画法)]

数式を使わない最適化の簡単な原理

数式アレルギーの人向けに、数式を使わない最適化の簡単な原理を作ってみた。

いや、実際は数式を使わないのでかなり無理な気もするが、大きな流れや概念は外していないと思う。w

1. 施策ごとのコストとゲイン(収益)の関係を計算する。
(SPSS Clementine や数理システム VMS などを使いモデルを作る。)

この傾きが急なほど、効率が良い施策といえる。

施策にかけるコストにより三角形の大きさは異なってくるし、また、施策の種類により傾きは異なってくる。



2. 直角三角形の傾きが急なものからゆるいものまで順番に並べ替える。

簡単に理解するため、4つの施策を例に考える。
実際は、各施策の中を細分化することで、より効果の高い最適化を行うことができる。



3. 効率の悪い施策の予算を削減し、効率の良い施策に予算を配分する。



結果、最適化をすることで
・コストを削減することができる。
・収益(アクション数)を上げることができる。



実際には、ビジネス的な制約条件などのからみで、単に効率が悪いから削除しましょうってのはダメで、いくらくらい減らせるのかとか、いくらくらい増やせるのかを考えないといけない。

また、予算を割り当てる際に、線形で効果が増えるわけではないので、効率が良いからといって無制限に割り当てることはできない。
三角形の例で例えると、三角形は同じ形のまま大きくなったり小さくなったりはしないのである。

nice!(1) 
共通テーマ:学問

数理システム ユーザコンファレンス 2008 [最適化(数理計画法)]

『数理システム ユーザコンファレンス 2008』に行って来た。

今回は、データマイニングってよりNUOPTを中心とした数理計画の事例を聴くことにした。

面白いと思ったのは、
・西尾 明氏(棋士五段)、常盤 秀樹氏(日本将棋連盟)による『日本将棋連盟・関東奨励会における対戦表自動作成システムの導入事例』

・田辺 隆人氏による『数理計画法を用いた自動勤務表作成』

の2つだった。

両方とも、問題としては、ナーススケジューリング問題になるのだが、どちらも1-0整数計画問題で解くことができる。
どっちも、単にこうして解けますよという数学的な講演だけではなく、問題の背景や、実際にプロジェクトを進めていく中での苦労話などが盛りだくさんだった。

難しい堅い話の中に、ほっと和むようなちょっとした笑い話もあり、とても面白いものだった。


Excelで学ぶ実験計画法―シックスシグマと重回帰分析

Excelで学ぶ実験計画法―シックスシグマと重回帰分析

  • 作者: 菅 民郎
  • 出版社/メーカー: オーム社
  • 発売日: 2002/04
  • メディア: 単行本



nice!(0) 
共通テーマ:学問

数理システム ユーザーコンファレンス 2008 [最適化(数理計画法)]

数理システム ユーザーコンファレンス 2008

数理システムからダイレクトメールが来た。
今年も六本木ヒルズのアカデミーヒルズでユーザーコンファレンスがあるようだ。

先日参加した SPSS Directions は、マーケティング色が強いセミナーだったが、
数理の場合は、より数理色が強い気がする。

最近、NUOPTを使った案件も増えてきているので、データマイニングというよりは、数理計画を勉強しに参加してみようかと思う。

nice!(0) 
共通テーマ:学問

ナース・スケジューリング問題 [最適化(数理計画法)]

NUOPTの無料スキルアップセミナーに参加してきた。

数理計画法に関しては、丸投げすることが多く、実際に手を動かすことが少ないのだが、たまには実際に自分でプログラムすることって大切ですよね。

何ができるかとか、これとこれを組み合わせれば、○○ができる、な~んてことも発想するヒントにもなります。

個人的に面白かったのは、ナース・スケジューリング問題ってのがあるのだが、実は、日本将棋連盟も数理計画法を使っているとか。

順位戦の対戦表だったか、奨励会の対戦表だったか、まぁ、そのあたりの対戦表を作るのに、人が考えているとやたら時間がかかるので、この数理計画法を使っているらしい。


将棋世界 2008年 11月号 [雑誌]

将棋世界 2008年 11月号 [雑誌]

  • 作者:
  • 出版社/メーカー: 日本将棋連盟
  • 発売日: 2008/10/03
  • メディア: 雑誌



nice!(0) 
共通テーマ:学問

最適化の実装 [最適化(数理計画法)]

仕事が激忙しくて死亡すんぜんですた。(´д`)

大規模最適化、BTなど同時並行で進んでおり、その〆切りが今日。
最適化にかけるモデルは実験でもバッチリ効果がでているので、次は、このモデルを使っての最適化だ。

無事、配信できそうになったので、一安心。
後は、結果がどうなるか。

でも、働きすぎはよくないな。

nice!(0) 
共通テーマ:仕事

大規模最適化割り当て問題 [最適化(数理計画法)]

9月末〆切りのプロジェクトが多発している。
ちょっと、いや、かなり疲労気味。(´д`)

先日、大規模最適化割り当て問題のプログラムが納品された。

通常、リコメンドというのは、ユーザが望むものを出せば良いのだろうが、ユーザだけでなく、広告を出向してくれているクライアントの両方のCSを満たすためには、どうしても最適化問題を解く必要が出てくる。

規模としては、数千ユーザと比較的小規模のものから、数百万という超巨大な規模の問題を解かないといけない。

通常は、実時間内に実行させることは無理なのだが、クラスタ化するなどの処理をかませることで十分に実時間内に解くことができる。

どれくらいの効果があるのか、非常に楽しみだ。

nice!(0) 
共通テーマ:学問

BT(behavior targeting)からBT最適化へ [最適化(数理計画法)]

最近、社内でBT(behavior targeting)メールの案件が活発化している。

これだけ、案件が増えてくると、各事業ごとにモデルを作っているわけには行かないので、モデルのコアとなる部分は同じで作ることにした。
微妙なパラメータ部分に関しては、各事業ごとにパラメータで自己学習する様にしておいた。

グルメ領域と住宅領域に関して、BTとランダムのABテストを行ったところ、なんとBTの方が2倍~3倍の効果がでることが解った。
モデルは、アソシエーションでもなく、協調フィルタリングでもなく、自己作成のモデル。

実際に、社内の人や自分に対して、欲しい物がリコメンドされるのかをみたところ、確かに驚くほどピッタリとしたものが選ばれている。w
後は、その中で、ど真ん中のストライクをリコメンドするのか、ボールではないが、ギリギリストライクのものをリコメンドするのかといったさじ加減も必要になってくる。

次の展開としては、大規模割り当ての数理計画問題だ。
ユーザーが欲しいものをリコメンドするだけでなく、広告を出向しているクライアントなどのことも考えないといけない。
かといって、余剰在庫ばっかり送られたらユーザは、怒ってしまう。
このあたりのことは、データマイニングというよりも、最適化問題で解くのが良いだろう。

ここで問題となってくるのは、ユーザー数、商品数ともに巨大な場合、どのように解くのか?という大きな問題が残ってくる。
詳しくは書けないが、この問題も無事に解決できそうである。

nice!(0) 
共通テーマ:学問

大規模、最適化問題 [最適化(数理計画法)]

いつもお世話になっている方のご紹介で、慶応大学に行ってきました。

常々、大規模の最適化問題が解ければと思っているのですが、真正面から問題を解こうとしても、現状は、実時間内で解けない場合が多いです。

そこは、いかに問題をシンプルに置き換えるかとか、1-0整数計画問題から線形計画問題への置き換えなど、うまく問題を近似してあげることで解くことができそう。
このあたりの考え方やテクニックは、その道のプロに聞くのが一番ですね。

先生のオススメソフトとしては、
・CPLEX
http://www.ilog.com/

・NUOPT
http://www.msi.co.jp/nuopt/
らしい。

イメージとしては、大学の先生は自分でソフトを作っているのかと思っていたのですが、実際は、コアの部分は、上記の様なソフトを使って、その周りの部分を自作しているのが多いようです。

上手くクレメンタインに実装できないものか、、、とも考えていますが、
なかなか時間がありません。。。(´д`)


~備忘録~
高速化のための手法
・カラムジェネレーション
・分割統治法

単体法と内点法

ハードコンストレインとソフトコンストレイン

nice!(0) 
共通テーマ:学問

BT(behavior targeting)広告の最適化 完成♪ [最適化(数理計画法)]

リスティング広告(キーワード広告)を応用すれば、
 モデル → 最適化
 Clementine → NUOPT
ってのが、できそうだなぁってことを当初考えていた。

が、ちょっとした工夫をすると、Clementineだけで、最適化とシミュレーションまでできることを発見。
Clementine君だけで完結させると、NUOPT(最適化)のプログラミングが省けるし、ランタイムのライセンスもかからないので、何かとお得である。

当初の予定では、モデル作成が2週間、最適化が2週間くらいで1ヶ月くらいかかるんじゃないかって思っていたが、意外とサクッっと2週間くらいで完成した。

ただ、データ量が半端じゃないので、あらかじめ、raw data からデータマートを作成しておいたほうがよさそうだ。

クレメンタインの入門書としてあるのは、これ↓くらい。

SPSSクレメンタインによるデータマイニング

SPSSクレメンタインによるデータマイニング

  • 作者: 牛田 一雄
  • 出版社/メーカー: 東京図書
  • 発売日: 2003/10
  • メディア: 単行本


この本だけだと、Clementine でできることの1%くらいしか使えない気がする。(´д`)

nice!(0) 
共通テーマ:学問

行動ターゲティング広告(BT広告)と最適化 [最適化(数理計画法)]

行動ターゲティング広告(BT広告)と最適化

行動ターゲティング広告って、『Behavioral Targeting』書かれているものもあれば、『Behavior Targeting』って書かれているものもあって、どっちなんだろう。
GoogleやYahoo!で調べたら、数的には、『Behavior Targeting(行動ターゲティング)』ってのが多いが、『Behavioral Targeting(行動のターゲティング)』ってのもかなりの数が出てくる。
「行動」も「行動の」もそんなに差はないんだろうか。

さてさて、BTメールの方も第2回配信が終わって、その結果を検証した。
第3回から、データマイニング⇒最適化を使ってみようかと思っている。

そこで、数理システムのNUOPTを引っ張り出してきた。
最適化って奥が深い。


nice!(0) 
共通テーマ:仕事

MATLAB Optimization Toolbox User's Guide:解を探す [最適化(数理計画法)]

MATLAB Optimization Toolbox User's Guide:解を探す

マニュアルには、

解を探す
最適化問題を解くためには、
[x, fval] =lsqlin(C, d, [], [], Aeq, beq)
と入力します。lsqlin は、つぎのように出力します。
x = 0.3333
0.6667
1.3333
fval = 2.3333
最小は点 x で最小となり、 fval は x から原点への距離の二乗です。

と書かれています。

が、これだけでは、どこにどう入力すれば良いのか、さ~ぱり解りません。。。orz

あれこれ、いじってみたら

こんなところにTool Boxを発見しました。(・∀・)!

そして、
C: eye(3)
d: zeros(3,1)
Aeq: [1 2 4]
beq: [7]
と入力し、Startを実行すると、答えが出ました。

MATLABってなんか使いにくい。。。
慣れるまでに時間がかかりそうです。
モジ(((*´ε` *)(* ´З`*)))モジ


nice!(0) 
共通テーマ:学問

MATLAB:マニュアルR14Optimization Toolbox:サイバネットシステム [最適化(数理計画法)]

MATLAB:マニュアルR14Optimization Toolbox:サイバネットシステム
http://dl.cybernet.co.jp/matlab/support/manual/r14/toolbox/optim/

MATLABというオモチャをインストールしたのだが、ようやく遊ぶことができた。
最適化の例題が載っていたので、サクッっとやってみる。

例題の問題は、平面上の原点に最も近い点を探すこと。
この数式を変形すると

つまり、平面

上の点から原点への距離を最小にすることになります。

制約条件:


nice!(0) 
共通テーマ:学問

最適化 ~データマイニングから一歩先へ~ 第2回 [最適化(数理計画法)]

数理計画の中でも解くのが難しいといわれている整数計画問題についてです。
なぜ、解くのが難しいのか?
それは、組み合わせ爆発が起こり、【解くのにとんでもない時間がかかる!】からです。
コンピューターに計算させて、答えが出てくるのに何週間も何年もかかるようでしたら、それは解けたとは、言いがたいものがあります。

今回、ある商品(商品A, B, C)のDMとコールセンターによるアウトバンドキャンペーンを考えることにします。
まず、第一段階として、Clementineを用いてデータマイニングを行います。
デモグラフィック情報や過去の行動履歴からそれぞれの商品ごとにどういう顧客が反応してくれそうなのかというモデルを作成し、反応確率を計算します。

第二段階として、反応確率、DMの発送やコールセンターにかかるコスト、さらに、クロージングするコストを元にNPV(net present value)を計算したのが下記図になります。

ここで、NPVは、

と定義しています。

ここまでくれば、最適化するための準備は出来上がりです。
後は、いくつかの制約条件が考えられます。考えられる制約条件としては、
・同じ人に違うカードを勧めてはいけない
・コールセンターのアウトバンドでは、1家族1人まで
・1日にかけることのできるコールセンターの台数制限
・DMやコールセンターのアウトバンドコスト
と定義しています。

などが考えられます。上記の制約条件を満たしつつ

を最大にする組み合わせを求めることになるます。

インターネットモールで買い物をしたら、次の日から毎日のようにアウトバンドメールが届くようになった…経験のある方も多いかと思います。
メールなどはコストも安いため安易に送りがちですが、反応してくれそうだからといって、何通もメールを送ってしまったのでは、やがてそのメールは迷惑メールになってしまい、かえってマイナスになってしまいます。
「欲しい情報を、欲しい人に、欲しいタイミングで」を実現するためには、データマイニング+最適化が重要といえます。

統計学では、よく○×推定や□△検定といった話を展開します。
そこにはこのモデル精度は何%あるとか、検証方法はどうするといったことが議論の対象になります。
よく「その最適化の精度は?」とか「別のデータを持ってきて、この最適化を検証するには?」と質問されることがあります。
しかし、こういった発想は統計的な発想なわけで、最適化とは、

のように何億、何兆通りもある組み合わせの中から、目的を最大/最小にする組み合わせを見つけ出す作業なわけです。
この辺りが統計学の世界とは大きく異なる部分です。

小規模の最適化問題ですと、エクセルのソルバーを使って解くことができます。
しかし、大規模になるとエクセルでは解くことができません。
商用のソフトを用意する必要があります。
以前は、大規模な最適化を行えるソフトと言えば、非常に高価でした。
しかし、最近では、最適化ソフトの数も多く出回っており、かつ、お値段の方も安くなってきています。
中には線形の問題だけではなく、複雑な多次元の問題を解くことができる最適化ソフトも存在します。


nice!(0) 
共通テーマ:学問

最適化 ~データマイニングから一歩先へ~ 第1回 [最適化(数理計画法)]

今は昔、、、
データマイニングという言葉がなかった頃、データは何かアクションを行わないと集めることができませんでした。
その一つがアンケートです。
きちんとサンプリングを行い、精錬されたデータに対し、統計的アプローチ(推定・検定など)を行っていました。

しかし、現在では、POSデータなどのトランザクションデータをはじめ、テキストデータやWeb Logデータがどんどん集まってきます。
その中からデータとの長い戦いが始まったのでした。

特にアクセスログの場合、データ容量が半端ではありません。
メガの世界から、すぐにギガの世界へ、そして、テラデータの世界へと飛び込んでしまいます。
そこで、必要なデータを取捨選択し、加工する必要があります。
データを上手くハンドリングすることがマイニングの成功に繋がっているのではないでしょうか…

データ解析やデータマイニングの先にあるものは、、、
それは最適化です。

アメリカなどは、この最適化を使ったマーケティングが進んでいます。
しかし、日本では、最適化という存在を知らない人も少なくはないでしょう。

何回かに分け、最適化の話を展開したいと思います。


nice!(0) 
共通テーマ:学問
最適化(数理計画法) ブログトップ