分離超平面定理
(Hyperplane separation theorem から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/16 01:54 UTC 版)
ナビゲーションに移動 検索に移動
分離超平面定理（ぶんりちょうへいめんていり、英: separating hyperplane theorem, hyperplane separation theorem）は n 次元ユークリッド空間上の互いに素な凸集合に関する幾何学における 2 つの定理を指す。
一つ目の定理は、互いに素な凸集合の両方が閉集合であってかつ少なくともいずれか 1 つの凸集合がコンパクト集合である場合、2 つの閉凸集合の間に 1 つの超平面が存在でき、また閉凸集合の間に 2 つの平行な超平面を隙間を作って置くことができることを示す。
二つ目の定理は、互いに素な凸集合があり両者が開集合である場合、2 つの開凸集合の間に 1 つの超平面をはさむことができるが、2 つの開凸集合の間には必ずしも隙間が存在するわけではないことを示す（従って第一の定理と異なり、複数の超平面を重ねずに挟むことができない状況が存在する）。
分離超平面に対して直交する軸を分離軸 (separating axis) と呼ぶ。これは、2 つの凸体の分離軸への直交写像が互いに素であることによる。
分離超平面定理はヘルマン・ミンコフスキーの寄与によって発見された。ハーン＝バナッハの分離定理はミンコフスキーの結果を線型位相空間へ一般化したものである。
関連する結果として支持超平面定理がある。マージン最大化超平面 (maximum-margin hyperplane) は空間上にある点の集まりを 2 つのクラスタに分離する超平面の中で、両者のクラスタからの距離が等しいようなものである。このとき、それぞれのクラスタと分離超平面の間のマージンは最大化される。この事実はサポートベクターマシンなどに応用される。
ステートメントと証明
A または B の一方が凸集合でない場合、「分離定理」に対しては様々な反例が挙げられる。例えば A と B は同心円状にとることができる。
より微妙な反例として、A と B の両方が閉凸集合だがいずれもコンパクトでない場合が挙げられる。例として、A が閉半平面で B が双曲線の分枝の一方であるとすれば、この場合には分離超平面は厳密には存在しない（しかしながら、開凸集合に関する分離定理があるために A および B の内部を分離する超平面が 1 つ存在する）：
他のタイプの反例として A がコンパクトな閉凸集合であり B が開凸集合である場合がある。例えば、A を正方形の閉集合、B を正方形の開集合として A と B が接している状況がこれに当てはまる。
閉凸集合に関する分離定理では分離超平面を一意に決めることができないことは明らかである。開集合バージョンの分離定理では、超平面が一意に定まる場合もあるしそうでない場合もあり得る。技術的なことだがこれらのことは分離軸について言い換えられる。閉凸集合の分離定理では分離軸を一意に決められないが、開凸集合の分離定理では分離軸を一意に決定できる。
衝突判定への応用
関連項目
- 双対錐
- ファルカスの補題
脚注
- ^ Boyd & Vandenberghe 2004, Exercise 2.22..
参考文献
- Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3
- Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9
- Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1
外部リンク
- 分離超平面定理のページへのリンク
