グラフカット最適化

グラフカット最適化は、離散変数の関数の族に適用できる組み合わせ最適化手法であり、フローネットワーク理論のカットの概念にちなんで名付けられています。最大フロー最小カット定理のおかげで、フローネットワークを表すグラフ上の最小カットを決定することは、ネットワーク上の最大フローを計算することと同等です。擬似ブール関数が与えられた場合、次のような正の重みを持つフローネットワークを構築できる場合、 ${\displaystyle f}$

• ネットワークの各カットは変数の割り当てにマッピングすることができ（逆も同様）、${\displaystyle C}$${\displaystyle \mathbf {x} }$${\displaystyle f}$
• コストは等しい（加算定数まで）${\displaystyle C}$${\displaystyle f(\mathbf {x} )}$

グラフの最小カットを計算することで、多項式時間でのグローバル最適値を見つけることが可能です。カットと変数割り当てのマッピングは、各変数をグラフ内の 1 つのノードで表すことによって行われ、カットが指定されると、対応するノードがソースに接続されたコンポーネントに属する場合は各変数の値は 0 になり、シンクに接続されたコンポーネントに属する場合は 1 になります。 ${\displaystyle f}$

すべての疑似ブール関数がフロー ネットワークで表現できるわけではなく、一般的なケースでは、グローバル最適化問題はNP 困難です。サブモジュラ 2 次関数など、グラフ カットを通じて最適化できる関数の族を特徴付けるための十分な条件が存在します。グラフ カットの最適化は、強い最適性特性を持つ反復アルゴリズムを使用してアプローチできる、有限個の値を持つ離散変数の関数に拡張でき、反復ごとに 1 つのグラフ カットを計算します。

グラフカット最適化は、マルコフ確率場や条件付き確率場などのグラフィカルモデルの推論に重要なツールであり、画像セグメンテーション、^{[1] [2]}ノイズ除去、^[3]レジストレーション^{[4] [5]}ステレオマッチングなどのコンピュータビジョンの問題に応用されています。^{[6] [7]}

擬似ブール関数は、 それぞれソースノードとシンクノードを持つ非負の重みとグラフが存在し、変数に割り当てられた値の組ごとに、かつの場合にグラフの最小カットによって決定されるフローの値に等しい（定数まで）ノードの集合が存在する場合に表現可能であると言われる。[ 8 ^]${\displaystyle f:\{0,1\}^{n}\to \mathbb {R} }$${\displaystyle G=(V,E)}$${\displaystyle s}$${\displaystyle t}$${\displaystyle V_{0}=\{v_{1},\dots ,v_{n}\}\subset V-\{s,t\}}$${\displaystyle (x_{1},\dots ,x_{n})\in \{0,1\}^{n}}$${\displaystyle f(x_{1},\dots,x_{n})}$ ${\displaystyle C=(S,T)}$${\displaystyle G}$${\displaystyle v_{i}\in S}$${\displaystyle x_{i}=0}$${\displaystyle v_{i}\in T}$${\displaystyle x_{i}=1}$

擬似ブール関数は、各項に寄与する変数の最大数によって決まる次数に従って分類することができます。各項が最大で 1 つの変数に依存するすべての 1 次関数は常に表現可能です。2 次関数

${\displaystyle f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i},x_{j}).}$

表現可能であるのは、それらが劣モジュラである場合のみである。つまり、各二次項に対して次の条件が満たされる。 ${\displaystyle w_{ij}}$

${\displaystyle w_{ij}(0,0)+w_{ij}(1,1)\leq w_{ij}(0,1)+w_{ij}(1,0)。}$

三次関数

${\displaystyle f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i },x_{j})+\sum _{i<j<k}w_{ijk}(x_{i},x_{j},x_{k})}$

は、正則である場合にのみ表現可能であり、つまり、残りの変数の値を固定することによって得られる2つの変数へのすべての可能な2値射影は、サブモジュラである。高階関数の場合、正則性は表現可能性の必要条件である。^[8]

表現可能な関数のグラフ構築は、2つの表現可能な関数との合計が表現可能であり、そのグラフが2つの関数を表すグラフとを結合したものであるという事実によって簡素化されます。このような定理により、各項を表す個別のグラフを構築し、それらを組み合わせて関数全体を表すグラフを取得できます。^[8]${\displaystyle f'}$${\displaystyle f''}$${\displaystyle G=(V'\カップ V'',E'\カップ E'')}$${\displaystyle G'=(V',E')}$${\displaystyle G''=(V'',E'')}$

変数の 2 次関数を表すグラフには頂点が含まれ、そのうち 2 つはソースとシンクを表し、残りは変数を表します。高次関数を表す場合、グラフには高次相互作用をモデル化できる補助ノードが含まれます。 ${\displaystyle n}$${\displaystyle n+2}$

単項項は1つの変数のみに依存し、1つの非終端ノードと1つのエッジを持つグラフで表すことができ、その重みは の場合、またはの場合に重みが である。^[8]${\displaystyle w_{i}}$${\displaystyle x_{i}}$${\displaystyle v_{i}}$${\displaystyle s\rightarrow v_{i}}$${\displaystyle w_{i}(1)-w_{i}(0)}$${\displaystyle w_{i}(1)\geq w_{i}(0)}$${\displaystyle v_{i}\rightarrow t}$${\displaystyle w_{i}(0)-w_{i}(1)}$${\displaystyle w_{i}(1)<w_{i}(0)}$

2次項（または2項）は、2つの非終端ノードとを含むグラフで表すことができます。この項は次のように書き直すことができます。 ${\displaystyle w_{ij}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$

${\displaystyle w_{ij}(x_{i},x_{j})=w_{ij}(0,0)+k_{i}x_{i}+k_{j}x_{j}+k_{ij }\left((1-x_{i})x_{j}+x_{i}(1-x_{j})\right)}$

と

${\displaystyle {\begin{aligned}k_{i}&={\frac {1}{2}}(w_{ij}(1,0)-w_{ij}(0,0))\\k_{ j}&={\frac {1}{2}}(w_{ij}(1,1)-w_{ij}(1,0))\\k_{ij}&={\frac {1}{2}}(w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)).\終了{整列}}}$

この式では、最初の項は定数であり、どの辺でも表されていません。次の2つの項は1つの変数に依存し、前のセクションで単項について示したように1つの辺で表されます。一方、3番目の項は重みを持つ辺で表されます（サブモジュラ性により、重みが非負であることが保証されます）。^[8]${\displaystyle v_{i}\rightarrow v_{j}}$${\displaystyle w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)}$

3次項（または3項）は、4つの非終端ノードを持つグラフで表すことができます。そのうち3つ（、 ）は3つの変数に関連付けられ、4つ目の補助ノードは1つです。^[注1]一般 的な3項は、定数、3つの単項、3つの2項、および簡略化された形式の3項の合計として書き直すことができます。 の符号に応じて、2つの異なるケースがあります。${\displaystyle w_{ijk}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle v_{k}}$${\displaystyle v_{ijk}}$${\displaystyle p=w_{ijk}(0,0,0)+w_{ijk}(0,1,1)+w_{ijk}(1,0,1)+w_{ijk}(1,1, 0)}$${\displaystyle p>0}$

${\displaystyle w_{ijk}(x_{i},x_{j},x_{k})=w_{ijk}(0,0,0)+p_{1}(x_{i}-1)+p_{2} (x_{j}-1)+p_{3}(x_{k} -1)+p_{23}(x_{j}-1)x_{k}+p_{31}x_{i}(x_{k}-1)+p_{12}(x_{i}-1) x_{j}-px_{i}x_{j}x_{k}}$

と

${\displaystyle {\begin{aligned}p_{1}&=w_{ijk}(1,0,1)-w_{ijk}(0,0,1)\\p_{2}&=w_{ijk}(1,1,0)-w_{ijk}(1,0,1)\\p_{3}&=w_{ijk}(0,1,1)-w_{ijk}(0,1,0)\\p_{23}&=w_{ijk}(0,0,1)+w_{ijk}(0,1,0)-w_{ijk}(0,0,0)-w_{ijk}(0,1,1)\\p_{31}&=w_{ijk}(0,0,1)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,0,1)\\p_{12}&=w_{ijk}(0,1,0)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,1,0).\end{aligned}}}$

構築は同様ですが、変数は反対の値を持ちます。関数が正則である場合、2 つの変数のすべての射影はサブモジュラになり、、およびが正であることを意味し、新しい表現のすべての項はサブモジュラになります。 ${\displaystyle p<0}$${\displaystyle p_{23}}$${\displaystyle p_{31}}$${\displaystyle p_{12}}$

この分解では、定数項、単項項、二項項は前の節で示したように表すことができます。三項項を4つの辺、、、、すべて重み を持つグラフで表すことができる場合、項を4つの辺、、、、、すべて重み を持つグラフで表すことができます。[ ^8]${\displaystyle p>0}$${\displaystyle v_{i}\rightarrow v_{ijk}}$${\displaystyle v_{j}\rightarrow v_{ijk}}$${\displaystyle v_{k}\rightarrow v_{ijk}}$${\displaystyle v_{ijk}\rightarrow t}$${\displaystyle p}$${\displaystyle p<0}$${\displaystyle v_{ijk}\rightarrow v_{i}}$${\displaystyle v_{ijk}\rightarrow v_{j}}$${\displaystyle v_{ijk}\rightarrow v_{k}}$${\displaystyle s\rightarrow v_{ijk}}$${\displaystyle -p}$

疑似ブール関数を表すグラフを構築した後、フロー ネットワーク用に開発されたさまざまなアルゴリズム ( Ford–Fulkerson アルゴリズム、Edmonds–Karp アルゴリズム、Boykov–Kolmogorov アルゴリズムなど) のいずれかを使用して、最小カットを計算できます。結果は、およびとなる2 つの連結コンポーネントとへのグラフの分割であり、対応するノード となる各に対して のとき、および対応するノード となる各 に対して のとき、関数はグローバル最小値を達成します。 ${\displaystyle S}$${\displaystyle T}$${\displaystyle s\in S}$${\displaystyle t\in T}$${\displaystyle x_{i}=0}$${\displaystyle i}$${\displaystyle v_{i}\in S}$${\displaystyle x_{i}=1}$${\displaystyle i}$${\displaystyle v_{i}\in T}$

ボイコフ・コルモゴロフのような最大フローアルゴリズムは、逐次計算には非常に効率的ですが、並列化が難しいため、分散コンピューティングアプリケーションには適しておらず、現代のCPUの潜在能力を活用することができません。プッシュ・リラベル^[9]やジャンプ・フラッド^[1]などの並列最大フローアルゴリズムが開発され、GPGPU実装のハードウェアアクセラレーションも活用できるようになりました。^{[10] [1] [11]}

前述の構成では擬似ブール関数の大域的最適化しかできなかったが、有限個の値を持つ離散変数の2次関数に拡張することができ、次のようになる。

${\displaystyle f(\mathbf {x} )=\sum _{i\in V}D(x_{i})+\sum _{(i,j)\in E}S(x_{i},x_{j})}$

ここで、およびである。関数は各変数の単項寄与（データ項と呼ばれることが多い）を表し、関数は変数間の二項相互作用（平滑化項）を表す。一般に、このような関数の最適化はNP困難問題であり、シミュレーテッドアニーリングなどの確率的最適化手法は局所的最小値の影響を受けやすく、実際には任意に最適でない結果を生成する可能性がある。^{[注 2]グラフカットを使用すると、実用的な関心のある幅広い二次関数の族（二項相互作用が}メトリックまたはセミメトリックである場合）に対して、強力な最適性特性を持つ局所的最小値に多項式時間で到達できる移動作成アルゴリズムを構築することができ、解における関数の値は、グローバル最適値から定数かつ既知の係数以内にある。^[12]${\displaystyle E\subseteq V\times V}$${\displaystyle x_{i}\in \Lambda =\{1,\dots ,k\}}$${\displaystyle D(x_{i})}$${\displaystyle S(x_{i},x_{j})}$${\displaystyle S(x_{i},x_{j})}$

を持つ関数と、変数への特定の値の割り当てが与えられた場合、各割り当てをとなるように変数の集合の分割に関連付けることができます。 と の 2 つの異なる割り当てと値 が与えられた場合、およびの場合には、を に変換する移動は-展開であるといわれます。 およびのいくつかの値が与えられた場合、の場合には、移動は -スワップであるといわれます。 直感的には、からの -展開移動は、で異なる値を持ついくつかの変数に の値を代入しますが、 -スワップ移動はに値を持ついくつかの変数に代入し、その逆も同様です。 ${\displaystyle f:\Lambda ^{n}\to \mathbb {R} }$${\displaystyle \Lambda =\{1,\dots ,k\}}$${\displaystyle \mathbf {x} =(x_{1},\dots ,x_{n})\in \Lambda ^{n}}$${\displaystyle \mathbf {x} }$${\displaystyle P=\{P_{l}|l\in \Lambda \}}$${\displaystyle P_{l}=\{x_{i}|x_{i}=l\in \Lambda \}}$${\displaystyle P}$${\displaystyle P'}$${\displaystyle \alpha \in \Lambda }$${\displaystyle P}$${\displaystyle P'}$${\displaystyle \alpha }$${\displaystyle P_{\alpha }\subset P'_{\alpha }}$${\displaystyle P'_{l}\subset P_{l}\;\forall l\in \Lambda -\{\alpha \}}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \alpha \beta }$${\displaystyle P_{l}=P'_{l}\;\forall l\in \Lambda -\{\alpha ,\beta \}}$${\displaystyle \alpha }$${\displaystyle \mathbf {x} }$${\displaystyle \alpha }$${\displaystyle \mathbf {x} }$${\displaystyle \alpha \beta }$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \mathbf {x} }$

各反復において、-展開アルゴリズムは、各可能な値 に対して、現在の一時解 から単一の -展開移動で到達できるすべての割り当ての中で関数 の最小値を計算し、それを新しい一時解として採用します。 ${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \mathrm {A} (\mathbf {x} )}$${\displaystyle \alpha }$${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {x} :={\text{arbitrary value in }}\Lambda ^{n}}$
${\displaystyle {\text{exit}}:=0}$
while  :
     foreach :
         if : の場合:
            ${\displaystyle {\text{exit}}\neq 1}$${\displaystyle {\text{exit}}=1}$
     ${\displaystyle \alpha \in \Lambda }$${\displaystyle \mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} (\mathbf {x} )}f(\mathbf {y} )}$
         ${\displaystyle f(\mathbf {\hat {x}} )<f(\mathbf {x} )}$${\displaystyle \mathbf {x} =\mathbf {\hat {x}} }$
            ${\displaystyle {\text{exit}}:=0}$

-swapアルゴリズムは似ていますが、からの単一の-swap 移動で到達可能なすべての割り当ての中で最小値を検索します。 ${\displaystyle \alpha \beta }$${\displaystyle \mathrm {A} \mathrm {B} (\mathbf {x} )}$${\displaystyle \alpha \beta }$${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {x} :={\text{arbitrary value in }}\Lambda ^{n}}$
${\displaystyle {\text{exit}}:=0}$
while  :
     foreach :
         if : の場合:
            ${\displaystyle {\text{exit}}\neq 1}$${\displaystyle {\text{exit}}=1}$
     ${\displaystyle (\alpha ,\beta )\in \Lambda ^{2}}$${\displaystyle \mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} \mathrm {B} (\mathbf {x} )}f(\mathbf {y} )}$
         ${\displaystyle f(\mathbf {\hat {x}} )<f(\mathbf {x} )}$${\displaystyle \mathbf {x} =\mathbf {\hat {x}} }$
            ${\displaystyle {\text{exit}}:=0}$

どちらの場合も、最も内側のループの最適化問題はグラフカットで正確かつ効率的に解決できます。どちらのアルゴリズムも外側のループの反復回数が有限になると確実に終了しますが、実際にはそのような回数は少なく、改善のほとんどは最初の反復で発生します。アルゴリズムは初期推定値に応じて異なるソリューションを生成する可能性がありますが、実際には初期化に関しては堅牢であり、すべての変数に同じランダム値が割り当てられる点から開始するだけで、通常は高品質の結果を生成するのに十分です。^[12]

このようなアルゴリズムによって生成される解は必ずしも大域的最適解ではないが、最適性は強く保証されている。 が計量でが-展開アルゴリズムによって生成される解である場合、または が半計量でが-スワップアルゴリズムによって生成される解である場合、 は大域的最小値から既知の定数倍の範囲内にある：^[12]${\displaystyle S(x_{i},x_{j})}$${\displaystyle \mathbf {x} }$${\displaystyle \alpha }$${\displaystyle S(x_{i},x_{j})}$${\displaystyle \mathbf {x} }$${\displaystyle \alpha \beta }$${\displaystyle f(\mathbf {x} )}$${\displaystyle f(\mathbf {x} ^{*})}$

${\displaystyle f(\mathbf {x} )\leq 2{\frac {\max _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}{\min _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}}f(\mathbf {x} ^{*}).}$

一般的に言えば、非サブモジュラ擬似ブール関数の最適化問題はNP困難であり、単純なグラフカットでは多項式時間で解くことができません。最も単純なアプローチは、類似しているがサブモジュラな関数で関数を近似することです。たとえば、すべての非サブモジュラ項を切り捨てるか、同様のサブモジュラ式に置き換えます。このようなアプローチは一般に最適ではなく、非サブモジュラ項の数が比較的少ない場合にのみ許容できる結果が得られます。^[13]

二次非劣モジュラ関数の場合、QPBOなどのアルゴリズムを使用して多項式時間で部分解を計算することが可能です。^[13]高次関数は、QPBOで最適化できる二次形式に多項式時間で簡約できます。^[14]

二次関数は広く研究され、詳細に特徴づけられているが、より一般的な結果は高次関数についても導かれている。二次関数は確かに多くの実用的な問題をモデル化できるが、変数間の二項相互作用しか表現できないという制限がある。高次相互作用を捉えることができれば、問題の性質をよりよく捉えることができ、二次モデルでは実現が難しいより高品質な結果をもたらすことができる。例えば、各変数が画像のピクセルまたはボクセルを表すコンピュータービジョンアプリケーションでは、高次相互作用を使用してテクスチャ情報をモデル化することができるが、これは二次関数だけでは捉えるのが難しい。^[15]

多項式時間で最適化できる高階擬似ブール関数を特徴付けるために、サブモジュラリティに類似した十分条件が開発され、^[16]高階関数のいくつかの族に対して、-展開や-スワップに類似したアルゴリズムが存在する。 ^[15]この問題は一般的なケースではNP困難であり、そのような条件を満たさない関数の高速最適化のための近似法が開発された。^{[16] [17]}${\displaystyle \alpha }$${\displaystyle \alpha \beta }$

• Boykov, Yuri; Veksler, Olga; Zabih, Ramin (2001). 「グラフカットによる高速近似エネルギー最小化」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 23 (11): 1222–1239. CiteSeerX  10.1.1.439.2071 . doi :10.1109/34.969114.
• Freedman, Daniel; Drineas, Petros (2005)。グラフカットによるエネルギー最小化: 可能な範囲の決定(PDF)。IEEE Computer Society Conference on Computer Vision and Pattern Recognition。第 2 巻。pp. 939–946。
• Goldberg, Andrew V; Tarjan, Robert E (1988). 「最大フロー問題への新しいアプローチ」(PDF) . Journal of the ACM . 35 (4): 921–940. doi :10.1145/48014.61051. S2CID  52152408.
• 石川 宏 (2014). 補助変数を使用しない高次クリーク削減(PDF) . IEEE コンピュータビジョンとパターン認識に関する会議。IEEE。pp. 1362–1369。
• Hong, Li; Chen, George (2004). グラフカットを使用したセグメントベースのステレオマッチング(PDF) . 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition の議事録。第 1 巻。pp. 74–81。
• Kohli, Pushmeet; Kumar, M. Pawan; Torr, Philip HS ( 2009)。「P3 とその先: 高階関数を解くための移動作成アルゴリズム」(PDF)  。IEEE Transactions on Pattern Analysis and Machine Intelligence。31 ( 9): 1645–1656。doi : 10.1109 /tpami.2008.217。PMID 19574624。S2CID 91470  。
• Kim, Junhwan; Kolmogorov, Vladimir; Zabih, Ramin (2003)。エネルギー最小化と相互情報量を使用した視覚的対応。第 9 回 IEEE 国際コンピュータビジョン会議の議事録。pp. 1033–1040。doi : 10.1109 /ICCV.2003.1238463。
• Kohli, Pushmeet; Ladicky, Lubor; Torr, PHS (2008). ロバストな高次ポテンシャルを最小化するグラフカット(PDF) (技術レポート). オックスフォードブルックス大学. pp. 1–9.
• Kolmogorov, Vladimir; Rother, Carsten (2007). 「非サブモジュラ関数の最小化: レビュー」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (7): 1274–1279. doi :10.1109/tpami.2007.1031. PMID  17496384. S2CID  15319364.
• Kolmogorov, Vladimir; Zabin, Ramin (2004). 「グラフカットによって最小化できるエネルギー関数は何か?」(PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 26 (2): 1645–1656. doi :10.1109/TPAMI.2004.1262177. hdl : 1813/5842 . PMID  15376891.
• Lombaert, Herve; Cheriet, Farida (2012)。グラフカットを使用した同時画像ノイズ除去とレジストレーション: 破損した医療画像への応用(PDF)。情報科学、信号処理とその応用に関する第 11 回国際会議。pp. 264–268。
• Peng, Yi; Chen, Li; Ou-Yang, Fang-Xin; Chen, Wei; Yong, Jun-Hai (2015). 「JF-Cut: 大規模画像およびビデオ向けの並列グラフカットアプローチ」. IEEE Transactions on Image Processing . 24 (2): 655–666. Bibcode :2015ITIP...24..655P. doi :10.1109/TIP.2014.2378060. PMID  25494510. S2CID  1665580.
• Rother, Carsten; Kolmogorov, Vladimir; Blake, Andrew (2004). Grabcut: 反復グラフカットを使用したインタラクティブな前景抽出(PDF) . ACM トランザクション オン グラフィックス。第 23 巻。pp. 309–314。
• So, Ronald WK; Tang, Tommy WH; Chung, Albert CS ( 2011)。「グラフカットを使用した脳磁気共鳴画像の非剛体画像登録」。パターン認識。44 (10–11): 2450–2467。doi :10.1016/j.patcog.2011.04.008 。
• Stich, Timo (2009). CUDA によるグラフカット(PDF) . GPU テクノロジー カンファレンス。
• Tang, Tommy WH; Chung, Albert CS (2007). グラフカットを使用した非剛体画像登録(PDF) . 国際医用画像コンピューティングおよびコンピュータ支援介入会議。pp. 916–924. doi : 10.1007/978-3-540-75757-3_111 .
• Vineet, Vibhav; Narayanan, PJ (2008). CUDA カット: GPU での高速グラフ カット(PDF) . IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. pp. 1–8.

• Vladimir Kolmogorov によるいくつかのグラフ カット アルゴリズムの実装 (C++)。
• GCO は、Olga Veksler と Andrew Delong によるグラフ カット最適化ライブラリです。