点と超平面の最小 lp 距離 - 私の備忘録がないわね...私の...

解法 1 (そのまま)
- p = 1 のとき
- p = ∞ のとき
解法 2 (ラグランジュの未定乗数法)
解法 3 (Holder の不等式)

「点と直線の距離」やその多次元拡張である「点と超平面の距離」は高校数学的な解法, 例えば連立方程式やベクトルで解くことが出来るポピュラーな問題設定です. 本記事は更に拡張した「点と超平面の最小 $l_p$ 距離」について考えます. 通常良く使われる $l_2$ 距離では法線ベクトルを使った解法が有名ですが, これは全ての $p$ に対しては成り立ちません. なぜなら距離を最小にする方向が法線ベクトルとは限らないからです.

改めて, 問題設定を確認します. 点を $\boldsymbol{x}_0 \in \mathbb{R}^n$ , 超平面を $\boldsymbol{a}^\top\boldsymbol{x} + a_0 = 0$ とすると, 今回の問題は以下の最小化問題によって記述できます.

$\displaystyle \min_{\boldsymbol{x}} \| \boldsymbol{x} \|_p \quad \text{s.t.} \quad \boldsymbol{a}^\top (\boldsymbol{x}_0 + \boldsymbol{x}) + a_0 = 0.$

この問題は $a_0 \leftarrow \boldsymbol{a}^\top \boldsymbol{x}_0 + a_0$ とすれば, 以下の最小化問題と等価です. これは $\boldsymbol{x}_0$ が原点になるような平行移動です.

$\displaystyle \min_{\boldsymbol{x}} \| \boldsymbol{x} \|_p \quad \text{s.t.} \quad \boldsymbol{a}^\top \boldsymbol{x} + a_0 = 0.$

さらに $l_p$ 距離の定義からこの最小化問題は以下の最小化問題と解が同じです. 下の形の方がラグランジュの未定乗数法で解くとき簡単です. 特に微分後の形が簡単になります.

$\displaystyle \min_{\boldsymbol{x}} \sum_{i=1}^n | x_i |^p \quad \text{s.t.} \quad \boldsymbol{a}^\top\boldsymbol{x} + a_0 = 0.$

解法 1 (そのまま)

$p = 1, ~2,~\infty$ のときは, 特別な手法を使わなくても解くことが出来ます. $p = 2$ のときは有名なので, ここでは省略します.

p = 1 のとき

$m = \arg\max_{i=1,\ldots,n} |a_i|$ とします. 複数個ある場合はそのうちの一つを取ってくることにします. $x_m = -\frac{a_0}{a_m}, x_i = 0~(i\ne m)$ は制約条件を満たし, このとき $| \boldsymbol{x} |_1 = \left|\frac{a_0}{a_m}\right|$ . ここで制約条件を満たすように $x_m$ を $\Delta_m$ だけ変化させ, 他の $x_i~(i\ne m)$ も制約条件を満たすように $\Delta_i$ だけ変化させます. つまり今,

$\displaystyle \begin{align} x_m &= -\frac{a_0}{a_m} + \Delta_m, \\ x_i &= \Delta_i~(i\ne m), \\ a_m\Delta_m &= - \sum_{i\ne m}a_i \Delta_i. \end{align}$

3 番目の式を変形させていきます.

$\displaystyle \begin{align} a_m\Delta_m &= - \sum_{i\ne m}a_i \Delta_i \\ |a_m| |\Delta_m| &= \left|- \sum_{i\ne m}a_i \Delta_i \right| \\ &\leq \sum_{i\ne m} |a_i| |\Delta_i| \\ &\leq \left(\max_{i\ne m} |a_i| \right) \sum_{i\ne m} |\Delta_i|. \end{align}$

これより, 以下の不等式が成り立ちます.

$\displaystyle \begin{align} | \Delta_m | \leq \frac{| a_m |}{\max_{i\ne m} | a_i |}| \Delta_m | \leq \sum_{i\ne m} | \Delta_i |. \end{align}$

今, 超平面までの距離は以下のような不等式で表せます. 最後の右辺は地道な場合分けによって展開できます.

$\displaystyle \begin{align} \| \boldsymbol{x} \|_1 = \left| -\frac{a_0}{a_m} + \Delta_m \right| + \sum_{i\ne m}| \Delta_i | \geq \left| -\frac{a_0}{a_m} + \Delta_m \right| + | \Delta_m | \geq \left| \frac{a_0}{a_m} \right|. \end{align}$

よって $p=1$ のとき, $m = \arg\max_{i=1,\ldots,n} |a_i|$ とすると, 超平面上の点 $x_m = -\frac{a_0}{a_m}, x_i = 0~(i\ne m)$ が原点からの最小距離 $\left|\frac{a_0}{a_m}\right|$ を取ります.

p = ∞ のとき

今, $\| \boldsymbol{x} \|_\infty = \max_{i=1,\ldots,n}| x_i | = \epsilon (\geq 0)$ とすると $\left | \sum^n_{i=1} a_ix_i \right | \leq \sum^n_{i=1} |a_i| \epsilon$ . この不等式より制約条件 $\boldsymbol{a}^\top \boldsymbol{x} + a_0 = 0$ を満たすのは, $\epsilon \geq -\frac{a_0}{\sum^n_{i=1} | a_i |}$ のときとなります. すなわち $\| \boldsymbol{x} \|_\infty = -\frac{a_0}{\sum^n_{i=1} | a_i |}$ が最小の距離となります. またこのとき等号成立条件を考え, $\boldsymbol{x} = -\frac{a_0}{\sum^n_{i=1} | a_i |}\operatorname{sign} a_i$ です.

解法 2 (ラグランジュの未定乗数法)

ラグランジュの未定乗数法によって, $1\lt p\leq\infty$ に対して, 最小 $l_p$ 距離が計算できます. $p=1$ のときは $\sum_{i=1}^n |x_i|$ が $x_i = 0$ で微分不可能であり, ラグランジュの未定乗数法を使おうとすると面倒臭い場合分けが必要となります. 更に解法 1 から分かる通り, 最適解がその微分不可能な点にあるので, あまりラグランジュの未定乗数法の恩恵を受けられません. よって $1\lt p\leq\infty$ に対して考えます.

$p>1$ のとき, $|x|^p$ は全ての点で微分可能です. 一応, 原点での挙動を以下のように確認しておきます.

$\displaystyle \lim_{h\to +0}\frac{|h|^p}{h} = \lim_{h\to -0}\frac{|h|^p}{h} = 0.$

ラグランジュの未定乗数法を用いて, 上の最小化問題を解きます. 関数 $L(\boldsymbol{x},\lambda)$ を以下のように定義します.

$\displaystyle L(\boldsymbol{x},\lambda) = \sum_{i=1}^n | x_i |^p - \lambda (\boldsymbol{a}^\top\boldsymbol{x} + a_0)$

これを各変数で微分すると以下のようになります.

$\displaystyle \begin{align} \boldsymbol{\nabla}_\boldsymbol{x} L(\boldsymbol{x},\lambda) &= p |\boldsymbol{x}|^{p-1} \text{sign}~\boldsymbol{x} - \lambda \boldsymbol{a} \\ \nabla_\lambda L(\boldsymbol{x},\lambda) &= -(\boldsymbol{a}^\top\boldsymbol{x} + a_0) \end{align}$

関数 $L$ の極値を求めるために $\boldsymbol{\nabla}_\boldsymbol{x} L(\boldsymbol{x},\lambda) = 0, \nabla_\lambda L(\boldsymbol{x},\lambda) = 0$ を解きます. これは以下の連立方程式で表されます.

$\displaystyle \begin{align} p |\boldsymbol{x}|^{p-1} \text{sign}~\boldsymbol{x} - \lambda \boldsymbol{a} = 0 \\ \boldsymbol{a}^\top\boldsymbol{x} + a_0 = 0 \end{align}$

上の式は両辺に $\operatorname{sign}$ 関数を掛け合わせることで, $\operatorname{sign}\boldsymbol{x} = \operatorname{sign}\lambda\boldsymbol{a}$ が得られます. よって

$\displaystyle \begin{align} &p |\boldsymbol{x}|^{p-1} \text{sign}~\boldsymbol{x} - \lambda \boldsymbol{a} = 0\\ \Leftrightarrow &p |\boldsymbol{x}|^{p-1} \operatorname{sign}\lambda\boldsymbol{a} - \lambda \boldsymbol{a} = 0 \\ \Leftrightarrow &p |\boldsymbol{x}|^{p-1} = |\lambda \boldsymbol{a}| \\ \Leftrightarrow & |\boldsymbol{x}| = \left|\frac{\lambda \boldsymbol{a}}{p}\right|^{\frac{1}{p-1}} \\ \Leftrightarrow & \boldsymbol{x} = \left|\frac{\lambda \boldsymbol{a}}{p}\right|^{\frac{1}{p-1}}\operatorname{sign}\lambda\operatorname{sign}\boldsymbol{a} \\ \end{align}$

これを $\boldsymbol{a}^\top\boldsymbol{x} + a_0 = 0$ に代入して整理すると以下のようになります.

$\displaystyle \left| \frac{\lambda}{p} \right|^{\frac{1}{p-1}} \operatorname{sign}\lambda = - \frac{a_0}{\sum_{i=1}^n|a_i|^{\frac{p}{p-1}}}$

よって

$\displaystyle \boldsymbol{x} = - \frac{a_0}{\sum_{i=1}^n|a_i|^{\frac{p}{p-1}}} \cdot \left|\boldsymbol{a}\right|^\frac{1}{p-1}\operatorname{sign}\boldsymbol{a}$

のとき, 最小距離となります. またこの $\boldsymbol{x}$ に対して, $l_p$ ノルムを計算すると, $\| \boldsymbol{x} \|_p = \frac{|a_0|}{ \| \boldsymbol{a} \|_{\frac{p}{p-1}}}$ となります. $l_p$ に関しては解法 1 の結果と合いますが, それを満たす $\boldsymbol{x}$ は解法1と合いません. これは最初に述べた通り, ラグランジュの未定乗数法では微分可能でない点を考慮していないことが関係していると思われます.

解法 3 (Holder の不等式)

ラボの先輩から聞いた超シンプルかつ $1\leq p\leq \infty$ と広く成り立つ解法です.

アダマール積を $\odot$ とします. 制約条件から以下の不等式が導けます.

$\displaystyle \begin{align} a_0 &= -\boldsymbol{a}^\top \boldsymbol{x} \\ | a_0 | &= | \boldsymbol{a}^\top \boldsymbol{x} | \leq \sum^n_{i=1} | a_i x_i | \leq \| \boldsymbol{a}^\top \boldsymbol{x} \|_1. \end{align}$

ヘルダーの不等式より, $\frac{1}{p}+\frac{1}{q}=1$ とすると

$\displaystyle \| \boldsymbol{a}^\top \boldsymbol{x} \|_1 \leq \| \boldsymbol{a} \|_q \| \boldsymbol{x} \|_p.$

この二つの不等式から

$\displaystyle \begin{align} | a_0 | &\leq \| \boldsymbol{a} \|_q \| \boldsymbol{x} \|_p \\ \frac{| a_0 |}{\| \boldsymbol{a} \|_q} &\leq \| \boldsymbol{x} \|_p. \end{align}$