(57)【要約】  システムは、複数の変数のパラメータ推定を生成する。このシステムは、ユーザが受け入れることのできる基準およびユーザ目的を含む入力データを受ける。このシステムは、入力データを符号化して行列にし、双対線形プログラムを用いて入力データを変換する。このシステムは次に、双対シンプレックス法をボックス化された変数に対して用いて双対線形プログラムを解き、パラメータ推定のパラメータ値を回収する。このパラメータ推定を用いて小売予測を行なうことができる。
2014520340.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサによって実行されると前記プロセッサに複数の変数のパラメータ推定を実行させる命令が格納されたコンピュータ読取可能な媒体であって、前記命令は、
ユーザが受け入れることのできる基準およびユーザ目的を含む入力データを受けること、
前記入力データを符号化して行列にすること、
前記入力データを双対線形プログラムを用いて変換すること、
前記双対線形プログラムを、ボックス化された変数に対する双対シンプレックス法を用いて解くこと、および
前記パラメータ推定のパラメータ値を回収することを含む、コンピュータ読取可能な媒体。
【請求項２】
前記双対線形プログラムは、
【数１】
2014520340.tif 000014
を含む、請求項１に記載のコンピュータ読取可能な媒体。
【請求項３】
前記双対線形プログラムは、
【数２】
2014520340.tif 000015
を含む、請求項１に記載のコンピュータ読取可能な媒体。
【請求項４】
前記双対線形プログラムは、
【数３】
2014520340.tif 000016
を含む、請求項１に記載のコンピュータ読取可能な媒体。
【請求項５】
前記行列は密形式である、請求項１に記載のコンピュータ読取可能な媒体。
【請求項６】
下限から上限にまたは上限から下限にフリップできる各変数に対してトリプレット係数のアレイを生成すること、および
前記トリプレット係数を比率の昇順でソートすることをさらに含む、請求項１に記載のコンピュータ読取可能な媒体。
【請求項７】
前記双対線形プログラムを解くことによって主変数値および双対変数値を生成する、請求項１に記載のコンピュータ読取可能な媒体。
【請求項８】
前記パラメータ推定によって小売を予測する、請求項１に記載のコンピュータ読取可能な媒体。
【請求項９】
複数の変数のパラメータ推定のためのコンピュータによって実現される方法であって、前記方法は、
ユーザが受け入れることのできる要件およびユーザ目的を含む入力データを受けること、
前記入力データを符号化して行列にすること、
前記入力データを双対線形プログラムを用いて変換すること、
前記双対線形プログラムを、ボックス化された変数に対する双対シンプレックス法を用いて解くこと、および
前記パラメータ推定のパラメータ値を回収することを含む、コンピュータによって実現される方法。
【請求項１０】
前記双対線形プログラムは、
【数４】
2014520340.tif 000017
を含む、請求項９に記載のコンピュータによって実現される方法。
【請求項１１】
前記双対線形プログラムは、
【数５】
2014520340.tif 000018
を含む、請求項９に記載のコンピュータによって実現される方法。
【請求項１２】
前記双対線形プログラムは、
【数６】
2014520340.tif 000019
を含む、請求項９に記載のコンピュータによって実現される方法。
【請求項１３】
前記行列は密形式である、請求項９に記載のコンピュータによって実現される方法。
【請求項１４】
下限から上限にまたは上限から下限にフリップできる各変数に対してトリプレット係数のアレイを生成すること、および
前記トリプレット係数を比率の昇順でソートすることをさらに含む、請求項９に記載のコンピュータによって実現される方法。
【請求項１５】
前記双対線形プログラムを解くことによって主変数値および双対変数値を生成する、請求項９に記載のコンピュータによって実現される方法。
【請求項１６】
前記パラメータ推定によって小売を予測する、請求項９に記載のコンピュータによって実現される方法。
【請求項１７】
小売予測システムであって、
プロセッサと、
前記プロセッサに接続され命令を格納するコンピュータ読取可能な媒体とを備え、
前記命令は、前記プロセッサによって実行されるとき、
ユーザが受け入れることのできる基準およびユーザ目的を含む入力データを受けること、
前記入力データを符号化して行列にすること、
前記入力データを双対線形プログラムを用いて変換すること、
前記双対線形プログラムを、ボックス化された変数に対する双対シンプレックス法を用いて解くこと、および
前記パラメータ推定のパラメータ値を回収することを含み、前記パラメータ値は小売予測を含む、システム。
【請求項１８】
前記双対線形プログラムは、
【数７】
2014520340.tif 000020
を含む、請求項１７に記載のシステム。
【請求項１９】
前記双対線形プログラムは、
【数８】
2014520340.tif 000021
を含む、請求項１７に記載のシステム。
【請求項２０】
前記双対線形プログラムは、
【数９】
2014520340.tif 000022
を含む、請求項１７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
分野
ある実施の形態は、概してコンピュータシステムに関し、具体的にはパラメータ推定を用いた小売予測コンピュータシステムに関する。
【背景技術】
【０００２】
背景情報
パラメータ推定により、データを効率的に使用し解析して現象の数学的モデル化を支援し、得られたモデルに現れる定数を推定する。パラメータ推定のほとんどは、次に挙げる４つの最適化問題、（１）基準：最良の関数の選択による最適化（最小化または最大化）、（２）推定：選択された関数の最適化、（３）設計：最良のパラメータ推定を得るための最適設計、および（４）モデル化：データを測定する対象であるシステムを最適に説明する数学モデルの決定、に関連し得る。
【０００３】
パラメータ推定法は一般的に、「最小二乗法（ordinary least-squares）」（「ＯＬＳ」）としても知られている線形回帰技術を用いる。しかしながら、このような方法は、データ中の外れ値の影響を受ける可能性があるという点で「ロバスト」でないことが知られている。外れているデータポイントが１つ加わると、推定されるパラメータの値に大きな影響が生じ得る。
【発明の概要】
【課題を解決するための手段】
【０００４】
概要
ある実施の形態は、複数の変数のパラメータ推定を生成するシステムである。このシステムは、ユーザが受け入れることのできる基準およびユーザ目的を含む入力データを受ける。このシステムは、入力データを符号化して行列にし、双対線形プログラムを用いて入力データを変換する。このシステムは次に、双対シンプレックス法をボックス化された変数に対して用いて双対線形プログラムを解き、パラメータ推定のパラメータ値を回収する。このパラメータ推定を用いて小売予測を行なうことができる。
【図面の簡単な説明】
【０００５】
【図１】本発明の実施の形態を実現し得るコンピュータシステムのブロック図である。
【図２】ある実施の形態に従い小売パラメータ推定を生成するときの、図１の小売パラメータ推定モジュールの機能のフロー図である。
【発明を実施するための形態】
【０００６】
詳細な説明
ある実施の形態は、パラメータ推定を用いて小売をモデル化し予測するためのコンピュータシステムである。このシステムは、入力データを、浮動小数点アレイ等の密行列フォーマットで格納し、適切な双対定式を表わす追加の一時アレイを作成し、結果として得られた特殊構造の双対線形プログラムを、ボックス化された変数を所望の最適レベルにするために改訂双対シンプレックス法を用いて解く。その結果、小売のモデル化および予測に使用するパラメータ値が得られる。
【０００７】
パラメータ推定法は小売の予測に使用できる。たとえば、この方法を用いて、シャツの価格を２０％下げた場合売上高はどれだけ増加するかといったような、消費者製品に対する需要の価格弾力性を求めることができる。パラメータ推定法の中には、上記のように「最小二乗法」（「ＯＬＳ」）としても知られている線形回帰のように、データ中の外れ値の影響を受ける周知の方法がある。他の周知の方法には「最尤推定法（maximum likelihood estimation）」（「ＭＬＥ」）が含まれる。
【０００８】
さらに、ユーザが受け入れることのできる基準（たとえば、小売モデルを較正して販売促進による売上高を予測するときに、ユーザは、このモデルによる予測は、値引きが大きいほど売上高が伸びるまたは新聞の一面に広告を掲載すると新聞の内側の頁に広告を掲載した場合よりも売上高が増すという予測になるという、妥当な期待を抱くかもしれない）を取入れると、問題の解決が非常に困難になる。先行技術の解決策の中には、ユーザが受け入れることのできる基準を満たさないようなモデルを単に破棄するという解決策がある。しかしながら、そのようにすれば予測誤差が増す。
【０００９】
加えて、たとえユーザが複数の基準に注目する可能性があっても、市販のソルバー（solver）は一般的に「適合度」に関連する１つのメトリック（metric）しか最適化しない。たとえば、ユーザは、設定されたしきい値よりも大きい誤差が伴う予測が１つもないことを確実にしつつ一組の予測における予測誤差を最小にすることに、関心があるかもしれない。
【００１０】
線形計画法（linear programming）(「ＬＰ」）は、データ外れ値の影響が比較的小さいロバストな回答を生成することが証明されているので、パラメータ推定問題に使用されてきた。ＬＰは、ユーザが受け入れることのできる基準を指定することもできる。しかしながら、最も拡張性が高い周知のＬＰ実現化であっても、あまりに計算集約的であり、特に大量のデータを伴うこのようなパラメータ推定問題の直接符号化／ネイティブＬＰコーディングに適用されたときに十分実用的であるとはまだ立証されていない。
【００１１】
図１は、本発明の実施の形態を実現することができるコンピュータシステム１０のブロック図である。システム１０は、単一のシステムとして示されているが、その機能は分散システムとして実現することができる。システム１０は、情報通信のためのバス１２またはそれ以外の通信機構と、バス１２に接続され情報を処理するためのプロセッサ２２とを含む。プロセッサ２２の種類は汎用プロセッサでも専用プロセッサでもよい。システム１０はさらに、情報を格納するためかつプロセッサ２２が実行する命令を格納するためのメモリ１４を含む。メモリ１４は、ランダムアクセスメモリ（「ＲＡＭ」）、読取専用メモリ（「ＲＯＭ」）、磁気または光ディスク等の静的記憶装置、または他の種類のコンピュータ読取可能な媒体の、任意の組合せで構成されたものでもよい。システム１０はさらに、ネットワークインターフェイスカード等の、ネットワークに対するアクセスを提供する通信装置２０を含む。したがって、ユーザは、システム１０と、直接、またはネットワークもしくは他の任意の方法によって遠隔から、インターフェイスで接続してもよい。
【００１２】
コンピュータ読取可能な媒体は、プロセッサ２２がアクセスできる利用可能な任意の媒体であってもよく、揮発性媒体および不揮発性媒体双方、着脱可能媒体および着脱不能媒体双方、ならびに通信媒体を含む。通信媒体は、コンピュータ読取可能な命令、データ構造、プログラムモジュール、または、搬送波もしくはその他の移送機構等の変調されたデータ信号におけるその他のデータを含んでもよく、任意の情報伝達媒体を含む。
【００１３】
プロセッサ２２はさらに、バス１２を介して、情報をユーザに対して表示するための液晶表示装置（Liquid Crystal Display）（「ＬＣＤ」）等のディスプレイ２４に接続される。キーボード２６と、コンピュータのマウス等のカーソル制御装置２８とがさらにバス１２に接続されることによって、ユーザはシステム１０とインターフェイスで接続できる。
【００１４】
ある実施の形態において、メモリ１４は、プロセッサ２２によって実行されると機能を提供するソフトウェアモジュールを格納する。このモジュールは、システム１０に対してオペレーティングシステム機能を提供するオペレーティングシステム１５を含む。このモジュールはさらに、以下でより詳細に開示されるように、パラメータ推定を用いて、価格を設定し、小売売上高を予測しモデル化する小売パラメータ推定モジュール１６を含む。システム１０は、企業資源計画（enterprise resource planning）（「ＥＲＰ」）システム等のより大型のシステムの一部であってもよい。したがって、システム１０は一般的に、追加機能を含めるための１つ以上の追加機能モジュール１８を含む。データベース１７が、バス１２に接続されてモジュール１６および１８のための集中記憶装置を提供し、価格設定情報、在庫情報等を格納する。
【００１５】
入力データ
ある実施の形態で使用する入力データ／表記は、
ｍ＝予測モデルについて同時に推定されるパラメータの数（ｉ＝１，…，ｍ）（ｍは通常３０以下）、
ｎ＝これらｍ個のパラメータ各々についての係数の履歴観測数（ｊ＝１，…，ｎ）、ｎは通常非常に大きい（１，０００，０００以上の観測）、
ａ’ｉｊ＝観測ｊにおいてパラメータｉについて観測された係数、
ｓｉ＝パラメータｉについてのユーザが受け入れることのできる符号制約（これはパラメータｉが非負の値または非正の値いずれかであることを要求する）、
（ｌｉ，ｕｉ）＝パラメータｉの値の上限と下限、
ｗｊ＝観測ｊの相対的な重み（重要性）、
ｂｊ＝観測ｊにおける従属変数（ターゲット）の右辺の値、たとえば売上の伸び率、週間売上高など、
αｉ＝パラメータの値ｉに対するペナルティ（予測力がほとんどないであろうパラメータを確実にオフにするため）、
ｕａｃｋ＝２個以上のパラメータ値の加重和に対して結合（組合せ）制限を課すｋ番目のユーザが受け入れることのできる制約、である。この制約は次のように表わされる。
【００１６】
【数１】
2014520340.tif 000003
【００１７】
結果として得られる出力データは下記の通りである。
（出力データ）ｖａｌｉ＝すべてのユーザが受け入れることのできる制約を充足するとともに、従属変数の予測値と観測値の絶対誤差の総和を最小にするパラメータｉの値（その値を解析によって求める決定変数）。
【００１８】
これを解く従来の方策は、以下の式によって与えられる二乗誤差の総和を最小にする最小二乗法（「ＯＬＳ」）という方策である。
【００１９】
【数２】
2014520340.tif 000004
【００２０】
しかしながら、符号制約およびその他のユーザが受け入れることのできる制約があると、ＯＬＳは失敗に終わる。二次計画（quadratic programming）（「ＱＰ」）問題を解かねばならず、その場合、ｎが大きいときの事実上のパフォーマンスおよび応答要件を損なう傾向があり、誤差分布が正規分布曲線に似ていない多くの状況ではロバストな推定法にはならないかもしれず、従属変数（ターゲット）の重要であるが歪んだ観測が少数あると、結果として得られるモデルの実際の予測力が低下するかもしれない。
【００２１】
このような状況において上記問題を回避することになる選択肢として、線形計画法（「ＬＰ」）という方策がある。特に、絶対偏差の総和を最小にするＬＰという方策は、標本中央値のロバストな推定法となり得る。しかしながら、この方策には下記のようなさまざまな欠点がある。
・ＬＰにおける誤差最小化関数形式は、微分不可能で非平滑であるため、パフォーマンス要件に大きな影響を与える。
・大きなＬＰを解くためには一般的にいわゆる疎（sparse)である市販のＬＰソルバー（たとえばＩＢＭ社のIBM ILOG CPLEX Optimizer、または、Ｇｕｒｏｂｉ社のGurobi Optimization）に投資しなければならない。
・上記のような良質の市販ソルバーがあったとしても、入力として正しい数学モデルが与えられなければパフォーマンスは低いものとなり得る（選択肢はいくつかある）。
【００２２】
本発明の実施の形態は、変換の３段階（ステップ）シーケンスを通して得られる、パラメータ推定のための効率的なＬＰ定式を利用する。実施の形態はさらに、多様なユーザが受け入れることのできる制約および誤差最小化目的の形態の、新規のメトリックおよびユーザが受け入れることのできる要件を用いる。実施の形態は、結果として得られるＬＰ定式の特殊な構造を利用することによって、実際の収束性を大幅に改善する。さらに、実施の形態は、トリプレットデータ構造を、解法の経験的収束を高速化するクイックソートサブルーチンと組み合わせて用いる。
【００２３】
図２は、ある実施の形態に従い小売パラメータ推定を生成するときの図１の小売パラメータ推定モジュール１６の機能のフロー図である。ある実施の形態において、図２のフロー図の機能は、メモリまたはその他のコンピュータ読取可能なもしくは有形の媒体に格納されプロセッサによって実行されるソフトウェアにより実現される。その他の実施の形態では、この機能を、ハードウェアによって（たとえば特定用途向け集積回路（「ＡＳＩＣ」）、プログラマブルゲートアレイ（「ＰＧＡ」）、フィールドプログラマブルゲートアレイ（「ＦＰＧＡ」）などを使用して）、または、ハードウェアとソフトウェアの任意の組合せによって、果たしてもよい。
【００２４】
２０２で、ユーザが受け入れることのできる基準、ユーザ目的、観測、および対象としている変数を含む、入力データを受ける。ユーザが受け入れることのできる基準は、モデルの挙動の仕方に関するユーザの直感、ならびにハード制約（たとえば値引きによって売上が決して低下してはならない）およびソフト制約（たとえば一面の広告は裏面の広告よりも悪い傾向がある）を含んでもよい。
【００２５】
ある実施の形態において、２０２での入力データは以下の形態であってもよい。
・回帰係数行列（すなわち浮動小数点２次元アレイでありその要素は要素ａ’［］［］を表わす）。この入力は通常、疎形式である（すなわち非ゼロ要素およびそれらの位置が与えられる）。
・疎形式または密形式の従属変数の観測値（ｂ［］）。
・ブール値、整数および浮動小数点数値データ（符号制約、パラメータ間制約、アクティブパラメータ数を減じる所望のバイアス）の組合せ、ならびに数値許容差パラメータを用い、パラメータ化された形態で与えられる、ユーザが受け入れることのできる制約。
・所望の誤差最小化目的：絶対偏差の総和を最小化、最大偏差を最小化、またはこれら２つの目的の組合せの最小化。
【００２６】
２０４で、入力データを、密行列形式で（すなわち標準浮動小数点アレイを用いて）符号化する。
【００２７】
２０６で、追加の一時アレイを作成し要素を配置することによって、２０２で受けたユーザ目的に最も一致する適切な双対変数ＬＰ定式（以下で開示するＤＰ、ＤＰ２、またはＤＰ３）を表わす。
【００２８】
２０８で、結果として得られた特殊構造の双対線形プログラムを、所望レベルの最適性に達するように、以下で開示するボックス化された変数に対する改訂双対シンプレックス法を用いて解く。ある実施の形態では、この構造を迅速に収束させるソート法も導入する。
【００２９】
２１０で、解いたパラメータに基づき、ユーザが受け入れることのできる制約が実行可能か否か判断する。２１０においてユーザが受け入れることのできる制約が実行可能である場合、２１２で、パラメータ値を、２０６で求めた最適解における最適双対値から回収する。さもなければ、解は返されず、実行不能な状態が２１４で生じる。
【００３０】
数学的変換
ある実施の形態において、標準ＬＰ定式を３ステップの変換によって変換することにより、３つの新規の双対ＬＰ定式のうちの１つ（「ＤＰ」、「ＤＰ２」または「ＤＰ３」と呼ぶ）を生成する。図２の２０６との関連で先に開示したように、入力データをＬＰ定式に与えて出力を生成する。
【００３１】
変換ステップ１：元のＬＰ定式（最小絶対偏差（ＬＡＤ）の加重和の最小化）
【００３２】
【数３】
2014520340.tif 000005
【００３３】
変換１：線形プログラムに変換
【００３４】
【数４】
2014520340.tif 000006
【００３５】
問題「ＬＰ」は、市販のＬＰソルバーによって直接解くことができる。ｘについて得られた最適値を再度ｙにマッピングすることにより、必要な出力の組ｖａｌを生成することができる。しかしながら、ｎが大きい場合、ＬＰの行と列の数は約数百万である。結果として、ＣＰＬＥＸ等の市販のソフトウェアパッケージであってもこの問題を解くのに相対的に過剰に長い時間を要する。より効率的な定式を得るために、ある実施の形態は、以下で開示するように、この問題に対して双対の理論を利用して双対定式を生成する。
【００３６】
変換２：双対理論を用いて等価のＬＰを計算することにより「ＤＰ」を生成
【００３７】
【数５】
2014520340.tif 000007
【００３８】
ＤＰには下記の事項が該当する。
ａ）シンプレックス表（simplex-tableau）という方法に基づくＬＰ解法はその出力の一部として、
・主変数値
・双対変数値
という２組の答を生成する。
ｂ）ＤＰに対する最適シンプレックス表の一部として得られた最適双対変数値は、ｘについての最適値を返す。
ｃ）ＤＰには、決定変数πｉを通して少数（ｍ）の制約および多数（ｎ）の列がある。
ｄ）π変数の上限および下限（−ｗ，ｗ）は、「ボックス化された変数」としてこの解法により暗黙に処理される。
【００３９】
ＤＰの解法
ある実施の形態は、新規のユーザが受け入れることのできる制約および新規のユーザ指定事業目的によって特徴付けられる、パラメータ推定問題を解く。解は、パラメータ推定という点において新規の変換の数学的特性に隠された実際の意味を認識し、次に、利用できる最良の方策を見出し、所望の場合はこれを新規の向上によって修正して高速化することによって、得られる。
【００４０】
ある実施の形態は、ＤＰの行が少数であることを認識する。よって、改訂シンプレックス法を用いてこの問題を解くことができる。行の数が少ないので、ｍ×ｍの正方行列によって定められる小さな作業ベースを用いることができる。作業ベースが小さいので、単純で直接的な算術演算を行なうことによって、この行列の逆数ならびにシンプレックスの実現化に必要なその他の行および列演算を得ることができるが、これには複雑なライブラリは不要である。したがって、元の主問題に何百万もの行と列が含まれているとしても、実施の形態は、遥かに単純な密行列という方策を採用する。これは、購入するのに増大する高額費用を要するか、または、完成するのにかなりの工学技術作業を要する（たとえば２０倍以上の労力）、市販のパッケージで採用されているもっと複雑な疎行列法とは対照的である。
【００４１】
実施の形態は、双対シンプレックス法を用いる。双対シンプレックス法は、双対実行可能性が常に保たれる線形プログラムのための簡単な方法の一例である。したがって、実施の形態は、この方法の中間ステップすべてにおいてユーザが受け入れることのできる制約のほとんどを充足する。
【００４２】
また、実施の形態は、作業ベースの大きさを増すことなく、ボックス化された変数（π）を扱う必要があるので、これらの計算を暗黙に実施する。少なくとも（ｎ−ｍ）のボックス化された変数は、取り得る２つの値のうちの１つしか取ることができない、すなわち、この変数は最適解においてその上限（ｗ）かまたは下限（−ｗ）のいずれかにある。たとえば、観察（＝ボックス化された変数の数）が百万であり推定するパラメータが１０の場合、少なくとも９９９，９９０のボックス化された変数がその上限または下限にある。このため、この特徴を効率的に利用する解法は非常に速く収束するであろう。
【００４３】
実施の形態は、開示されているＤＰ線形計画法の定式化、改訂シンプレックスの実装、双対シンプレックス法、および効率的な暗黙のボックス化された変数処理の概念を、組み合わせる。こうして組合わされた方策は、迅速に収束する、ボックス変数（box-variables）に対する改訂双対シンプレックス法（revised dual-simplex method）（「ＲＤＳＭ−ＢＶ」）を単純にしたものを利用する。ある実施の形態では、周知の「ロングステップ」という方策（たとえば、Koberstein, A., "Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation", Journal of Computational Optimization and Applications 41 (2), 2008に開示されている）が修正される。
【００４４】
このロングステップという方策は、ボックス化された変数の大部分の効率的な計算を可能にする。ＲＤＳＭ−ＢＶに対するロングステップアルゴリズムにおける１つの重要なステップは、各ボックス化された変数についてスコアを計算することである。これにより、実施の形態は、あるボックス変数が、その現在値に保たれるか、その上限（ｗ）に移動させられるか、またはその下限（−ｗ）に移動させられるかを、判断できる。
【００４５】
実施の形態は、基本のロングステップアルゴリズムを高速化するために、中間ステップとして、特殊化されたトリプレットデータ構造を採用して効率を改善し、これらトリプレットのアレイに基づくクイックソートアルゴリズムを採用してパラメータ推定問題に対する有効性を改善する。このトリプレットとクイックソートを組み合わせて用いて、扱っている種類のパラメータ推定問題についての境界交換数を経験的に最大にするように、最も効果的な順序のボックス変数を効率的に計算する。
【００４６】
ボックス化された変数に対する改訂双対シンプレックス法のためのロングステップ技術
実施の形態は、その開示を本明細書に引用により援用する、Koberstein, A. "The Dual Simplex Method, Techniques for a fast and stable implementation", PhD Dissertation, Paderborn, Germany, 2005, Chapter 3, Algorithms 4-7に開示されているアルゴリズムの一般的なステップを新規に修正したものを使用する。Kobersteinに開示されている上記先行技術の方法／アルゴリズムとは異なり、実施の形態は、境界フリップ比率テストステップ（bound-flip ratio test）（「ＢＦＲＴ」）を実現することにより、小売予測／モデル化に関するこの種の問題を高速化する。結果として得られる数学的定式には異常に数が多いボックス化された変数が含まれているので、実施の形態は、目的関数値の最大の改善の達成ではなく、双対シンプレックス実装のすべてのステップでフリップできる境界の数を効率的に最大化することに、強く重点を置く。
【００４７】
実施の形態は、その境界をその下限から上限にまたはその逆にフリップできる各非基底変数についてトリプレット（すなわち３つの記録係数）のアレイ（「ＲＣｖａｒｓ」と呼ぶ）を生成し格納する。これら３つの係数は下記のように格納される。
係数１：＋ｋまたは−ｋ。ｋは非基底変数の指数。この非基底変数が現在その下限にある場合は−ｋが格納され、そうでなければ＋ｋが格納される。
係数２：比率［ｋ］＝変数の低下コストの、
【００４８】
【数６】
2014520340.tif 000008
【００４９】
によって与えられるその修正されたピボット値に対する比率。
係数３：傾き［ｋ］＝上限と下限の差によって与えられる非基底変数の潜在的改善値であり、これは、
【００５０】
【数７】
2014520340.tif 000009
【００５１】
によって与えられる修正されていないピボット値の絶対値によってさらにスケーリングされる。
【００５２】
許容差の値として１０−６が使用される。結果としての計算は疑似コードの形式で以下に示される。
【００５３】
パート１：境界フリップ候補を選択する方法
入力：現在の作業ベースＢ、および、改訂双対シンプレックス法に基づく対応するシンプレックス表
実行：すべての非基底変数を対象とする。
ステップ１：実行可能性テスト
（下限（ＬＢ）にある非基底変数およびその低下コスト（ｒｃ）値≦許容差）
ＯＲ
（上限（ＵＢ）にある非基底変数およびｒｃ＞許容差）
の場合、解は存在しないので、このルーチン全体を停止してこのルーチンから出る。
【００５４】
【数８】
2014520340.tif 000010
【００５５】
ステップ４：任意の標準ソートアルゴリズム（たとえばオラクル社の「Ｊａｖａ（登録商標）」において利用できるビルトインクイックソートアルゴリズム）を用いて、その割合（係数２）の昇順（値が増す順序）でＲＣｖａｒｓに格納されたトリプレットをソートする。こうすることによって、最も小さい割合が先に処理され、そのため、以下の説明からわかるように最大数の境界がフリップされる。さらに、この特定のトリプレット構造を使用することにより、実行時間−メモリから直接必要とされる関連情報をすべて効率的に取出すことができ、この場合さらに計算または再計算を行なう必要はない。
出力：ＲＣｖａｒｓアレイの再度順序付けがなされた（ソートされた）トリプレット
パート２：その境界が現在の双対シンプレックス反復においてフリップされる１組の変数を計算する方法
以下に示すように、値は、ソートされた順序でその下限からその上限に（またはその逆に）フリップされる。
入力：初期化に使用される、再度順序付けがなされたＲＣｖａｒｓアレイ、シンプレックス表、および、アルゴリズムパラメータΔｌｕの現在値
ステップ１：初期化
・設定  ｊ＝０
・割当  第１のトリプレット＝ＲＣｖａｒｓにおけるゼロ番目（第１）のエントリ
・初期化  現在の傾き＝｜Δｌｕ｜−第１のトリプレットの傾き
初期化  フリップの数＝０
ステップ２：境界フリップ
（ｊ＋１）＜ＲＣｖａｒｓのサイズ  ＡＮＤ  現在の傾きが、非負の値である間に、
ａ．現在の傾きの値をＲＣｖａｒｓの（ｊ＋１）番目のトリプレットの傾き分減じる
ｂ．ｊ＝ｊ＋１
ステップ２の反復終了
出力＝ｊ
これは、ソートされたＲＣｖａｒｓアレイにおける変数の最初のｊ個の要素の境界をその下限から上限にまたはその逆にフリップできることを示す（第１の係数はこれら２つの状況のうちいずれが適用されるかを示す）。
【００５６】
ステップ（２ａ）から観測できるように、現在の傾きの減少量が小さいほどそれが負になる（それによって反復を終了する）可能性は低い。実際、ボックス化された変数のうちの７５〜９０％がいずれか１つのロングステップ反復時にフリップされることが観測され、これにより、収束の速度が大幅に増し、最終的には、最適化に達するまでに必要な双対シンプレックス法の反復は１０〜１５以下である。実施の形態は、新規の特定のトリプレット構造を用いて候補データを記録し、その場合に候補を再度順序付ける技術を用い、次に結果を取出す。
【００５７】
他のユーザ指定目的（ＤＰ２、ＤＰ３）
ＤＰ２：すべての観察における従属変数（ターゲット）の予測値と観測値の最大誤差を最小にする（すなわちワーストケース予測における誤差を最小にする）。
【００５８】
【数９】
2014520340.tif 000011
【００５９】
実施の形態は以下の新規双対定式（ＤＰ２）を使用する。
【００６０】
【数１０】
2014520340.tif 000012
【００６１】
この等価の式ＤＰ２のシンプレックス表には、（２ｎ＋Ｋ）の列があるが、行は（ｍ＋１）しかない。この式には明らかなボックス化された変数が存在する訳ではないものの、（簡単な密行列技術に基づく）開示されている方策を使用できる。なお、この問題における少なくとも（２ｎ＋Ｋ−ｍ−１）の変数は、線形計画理論によってゼロになるであろう。したがって、ＤＰ２を用いる実施の形態は、実際比較的高速で収束する。さらに、双対変数（π）の十分に大きい（発見的（heuristic））上限を用いることにより、ボックス変数構造を回復することができ、それによって、実際の解決手続の高速化をさらに支援することができる。
【００６２】
決定変数ｚの最適値（双対変数の総和を単位元に限定する制約に対する最適双対変数として回収されたもの）がｚ＊であると仮定する。この値は、すべての観察の中で可能な最小の（最大偏差）誤差を表わす。１つの目的は、この最小の最大偏差の制限も行ないつつ絶対誤差の総和を最小にすることである。この追加のユーザが受け入れることのできる要件は、双対変数（π＋，π−）に対して上限（ｗ）を加え、以下に示す結果として得られる双対ＬＰ定式（すなわち「ＤＰ３」）を解くことによって、追加できる。
【００６３】
ＤＰ３：すべての観測における最大誤差の制限も行ないながら絶対偏差の総和を最小にする。
【００６４】
【数１１】
2014520340.tif 000013
【００６５】
実施の形態が取扱うことができるさらに他のユーザが受け入れることのできる制約は、パラメータ値に対してユーザが指定する下限および上限、ならびにユーザが好む（望む）入力パラメータ値からの絶対偏差に対するペナルティを含む。これらの制約は、制約を等価の上限および下限要件に変換するデータ変換技術によって処理される。
【００６６】
開示されているように、実施の形態は、パラメータ推定問題に対して一連の数学的変換によりＬＰ定式を生成することを含む。このＬＰ定式を用いることによって、販売促進の結果としての小売売上を予測する予測モデルのパラメータを推定することができるが、これは小売環境の外でも使用することができる。
【００６７】
実施の形態に従うＬＰ定式は、ユーザが受け入れることのできる制約／要件を充足しつつ、パラメータのロバストな推定のためのスケーラブルなアルゴリズムの実現を可能にする特殊構造を有し、この特殊構造にはさらに実際収束が高速であるという利点がある。ＬＰ定式の場合、パラメータを推定しながら、複数の「適合度（goodness of fit）」メトリックを同時に考慮することができる。具体的には、平均絶対偏差を、最大絶対偏差をユーザ指定値で制限する一方で、最小にすることができる。ある実施の形態において、ユーザが受け入れることのできる要件は、パラメータ推定数学定式にすべて統合され、ＬＰソルバーを一度コールすることによって最適化される。このため、先行技術の解法のいくつかでは必要な、パラメータの逐次推定、解がユーザが受け入れることのできる要件を充足するか否かの確認、パラメータの調整、再推定等は、不要である。
【００６８】
実施の形態は、変数の選択（潜在因子の集合の中から最高の変数のサブセットを選択する）および推定の階層的平滑化（ダイエットコーラの価格変更に対する売上の反応が、すべてのコーラ飲料が示す価格変更に対する売上の反応と、それほど違いがないようにする）といった、高度のモデル化タスクを可能にする。たとえデータ量が多くても、実施の形態が使用するメモリ量は限られており、経験的パフォーマンスは、双対シンプレックスの実行における重要なソートステップの使用を通じてある実施の形態で推定に使用されるデータ量の増加に伴ってわずかに増すだけである。
【００６９】
本明細書ではいくつかの実施の形態が具体的に示されおよび／または説明されているが、開示されている実施の形態は上記教示に含まれていることならびに本発明の精神および意図する本発明の範囲から外れることなく添付の特許請求の範囲に包含されていることが理解されるであろう。
【図１】
2014520340.tif 000023
【図２】
2014520340.tif 000024
【国際調査報告】
2014520340.tif 000025
2014520340.tif 000026