オフセット濾過
異なるサイズの 2 つの円からサンプリングされたポイント クラウド上の 6 つのスケール パラメータでのオフセット フィルタリング。

オフセット濾過（「ユニオン・オブ・ボールズ」[1]または「ユニオン・オブ・ディスクズ」[2] 濾過とも呼ばれる）は、データセットの位相的特徴のサイズとスケールを検出するために使用される、メトリックボールの増加列である。オフセット濾過は、パーシステントホモロジーや位相データ解析の分野でよく用いられる。ボールの和集合を用いて幾何学的物体の形状を近似するという手法は、1992年にユークリッド空間の部分多様体の文脈において、フロシニによって初めて提案された。[3]この構成は1998年にロビンズによって独立に検討され、アトラクターに関する位相的特徴の安定性を観察するために、一連の増加するスケールパラメータでインデックス付けされたオフセットの集合（すなわち、ボールの増加列）を考慮するように拡張された。[4]フロシニとロビンズのこれらの論文で導入されたホモロジー的持続性は、その後、エデルスブルンナーらによって形式化された。 2002年の画期的な論文「位相的持続性と単純化」の中で、オフセットフィルタリングは次のように説明されました。[5]それ以来、オフセットフィルタリングは計算トポロジーとデータ分析の研究における主要な例となっています。

意味

を計量空間 の有限集合とし、任意の に対してを を中心とする半径 の閉球とします。このとき、和集合はのパラメータ に関するオフセット（または単に の-オフセット）と呼ばれます。 X {\displaystyle X} ( M , d ) {\displaystyle (M,d)} x ∈ X {\displaystyle x\in X} B ( x , ε ) = { y ∈ X ∣ d ( x , y ) ≤ ε } {\displaystyle B(x,\varepsilon )=\{y\in X\mid d(x,y)\leq \varepsilon \}} ε {\displaystyle \varepsilon } x {\displaystyle x} X ( ε ) := ⋃ x ∈ X B ( x , ε ) {\textstyle X^{(\varepsilon )}:=\bigcup _{x\in X}B(x,\varepsilon )} X {\displaystyle X} ε {\displaystyle \varepsilon } ε {\displaystyle \varepsilon } X {\displaystyle X}

全体にわたってオフセットの集合を考えると、となる空間の族が得られる。したがって、を添字とする入れ子になった位相空間の族も得られ、これは上のオフセット濾過として知られる濾過を定義する。[6] ε ∈ [ 0 , ∞ ) {\displaystyle \varepsilon \in [0,\infty )} O ( X ) := { X ( ε ) ∣ ε ∈ [ 0 , ∞ ) } {\displaystyle {\mathcal {O}}(X):=\{X^{(\varepsilon )}\mid \varepsilon \in [0,\infty )\}} X ( ε ) ⊆ X ( ε ′ ) {\displaystyle X^{(\varepsilon )}\subseteq X^{(\varepsilon ^{\prime })}} ε ≤ ε ′ {\displaystyle \varepsilon \leq \varepsilon ^{\prime }} O ( X ) {\displaystyle {\mathcal {O}}(X)} ε {\displaystyle \varepsilon } X {\displaystyle X}

なお、オフセットフィルタリングを非負実数のポセットカテゴリから位相空間と連続写像のカテゴリへの関手として見ることも可能である。 [7] [8] Bubenikらによって検討されているように、カテゴリカルな観点にはいくつかの利点がある。[9] O ( X ) : [ 0 , ∞ ) → T o p {\displaystyle {\mathcal {O}}(X):[0,\infty )\to \mathbf {Top} }

プロパティ

神経定理の標準的な応用は、閉じた球が凸であり、凸集合の交差が凸であるため、球の和集合はその神経と同じホモトピー型を持つことを示しています。 [10]球の和集合の神経はチェフ複合体としても知られており、[11]これはヴィエトリス-リップス複合体のサブ複合体です。 [12]したがって、オフセット濾過はチェフ濾過（すべてのスケールパラメータにわたる各オフセットの神経として定義される）と弱同値であるため、それらのホモロジー群は同型です。[13]

ヴィエトリス-リップス濾過は一般にチェフ濾過と同一ではないが、ある意味では近似である。特に、集合 に対して、 のときはいつでも、リップス複体とチェフ複体の間に包含連鎖が存在する。[14]一般的な計量空間では、すべての に対してが成り立ち、これは2009年にチャザルらによって導入されたインターリービング距離に関して、リップス濾過とチェフ濾過が2-インターリーブされていることを意味する。[15] [16] X ⊂ R d {\displaystyle X\subset \mathbb {R} ^{d}} Rips ε ⁡ ( X ) ⊂ Cech ε ′ ⁡ ( X ) ⊂ Rips ε ′ ⁡ ( X ) {\displaystyle \operatorname {Rips} _{\varepsilon }(X)\subset \operatorname {Cech} _{\varepsilon ^{\prime }}(X)\subset \operatorname {Rips} _{\varepsilon ^{\prime }}(X)} X {\displaystyle X} ε ′ / ε ≥ 2 d / d + 1 {\displaystyle \varepsilon ^{\prime }/\varepsilon \geq {\sqrt {2d/d+1}}} Cech ε ⁡ ( X ) ⊂ Rips 2 ε ⁡ ( X ) ⊂ Cech 2 ε ⁡ ( X ) {\displaystyle \operatorname {Cech} _{\varepsilon }(X)\subset \operatorname {Rips} _{2\varepsilon }(X)\subset \operatorname {Cech} _{2\varepsilon }(X)} ε > 0 {\displaystyle \varepsilon >0}

ユークリッド空間内の滑らかな部分多様体の十分に密なランダム点群サンプルが与えられた場合、ある半径の球体の和集合はチェフ複体の変形収縮を介して物体のホモロジーを回復するという結果は、ニヨギ、スメール、ワインバーガーのよく知られた結果である。[17]

オフセット・フィルトレーションは、基となるデータセットの摂動に対しても安定であることが知られています。これは、オフセット・フィルトレーションが計量空間の距離関数に関するサブレベルセット・フィルトレーションと見なせるという事実から導かれます。サブレベルセット・フィルトレーションの安定性は、次のように述べられます。位相空間上の任意の2つの実数値関数が与えられ、すべての に対して、に関するサブレベルセット・フィルトレーション上の -次元ホモロジー・モジュールが点ごとに有限次元である場合、次式が成り立ちます。ここで、 とはそれぞれボトルネック距離と超ノルム距離を表し、 は-次元パーシステント・ホモロジー・バーコードを表します。[18]このサブレベル安定性の結果は、2005年に初めて提唱されましたが、時には「等長定理」として知られる代数的安定性特性からも直接導かれます。[9]この定理は、2009年に一方向が証明され、[16]、2011年に他の方向が証明されました。 [19] [20] γ , κ {\displaystyle \gamma ,\kappa } T {\displaystyle T} i ≥ 0 {\displaystyle i\geq 0} i th {\displaystyle i{\text{th}}} γ , κ {\displaystyle \gamma ,\kappa } d B ( B i ( γ ) , B i ( κ ) ) ≤ d ∞ ( γ , κ ) {\displaystyle d_{B}({\mathcal {B}}_{i}(\gamma ),{\mathcal {B}}_{i}(\kappa ))\leq d_{\infty }(\gamma ,\kappa )} d B ( − ) {\displaystyle d_{B}(-)} d ∞ ( − ) {\displaystyle d_{\infty }(-)} B i ( − ) {\displaystyle {\mathcal {B}}_{i}(-)} i th {\displaystyle i{\text{th}}}

複数のボールで覆われた点を考慮して定義されるオフセット濾過の多パラメータ拡張は、マルチカバー二重濾過によって与えられ、パーシステントホモロジーや計算幾何学においても注目されている。[21] [22]

参考文献

  1. ^ アダムス, ヘンリー; モイ, マイケル (2021). 「機械学習へのトポロジーの応用：グローバルからローカルへ」.人工知能のフロンティア. 4 668302: 2. doi : 10.3389/frai.2021.668302 . ISSN  2624-8212. PMC  8160457. PMID  34056580 .
  2. ^ エデルスブルンナー、ハーバート (2014).計算幾何学と位相幾何学の短期コース. Cham. p. 35. ISBN 978-3-319-05957-0. OCLC  879343648。{{cite book}}: CS1 maint: location missing publisher (link)
  3. ^ Frosini, Patrizio (1992-02-01). Casasent, David P. (編). 「サイズ関数による形状測定」 .知能ロボットとコンピュータビジョンX：アルゴリズムとテクニック. 1607.ボストン, MA: 122– 133. Bibcode :1992SPIE.1607..122F. doi :10.1117/12.57059. S2CID  121295508.
  4. ^ Robins, Vanessa (1999-01-01). 「近似値からホモロジーを計算する方法」(PDF) . Topology Proceedings . 24 : 503– 532.
  5. ^ Edelsbrunner; Letscher; Zomorodian (2002). 「位相的持続性と単純化」.離散幾何学と計算幾何学. 28 (4): 511– 533. doi : 10.1007/s00454-002-2885-2 . ISSN  0179-5376.
  6. ^ Halperin, Dan; Kerber, Michael; Shaharabani, Doron (2015), Bansal, Nikhil; Finocchi, Irene (編)、「凸包オブジェクトのオフセットフィルタリング」、Algorithms - ESA 2015、Lecture Notes in Computer Science、vol. 9294、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp.  705– 716、arXiv : 1407.6132、doi :10.1007/978-3-662-48350-3_59、ISBN 978-3-662-48349-7, S2CID  660889 , 2023年2月25日取得
  7. ^ Bauer, Ulrich; Kerber, Michael; Roll, Fabian; Rolle, Alexander (2023-02-16). 「関数神経定理とその変種に関する統一的見解」. Expositiones Mathematicae . 41 (4): 8. arXiv : 2203.03571 . doi :10.1016/j.exmath.2023.04.005. S2CID  247291819.
  8. ^ Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). 「2パラメータパーシステントホモロジーの安定性」.計算数学の基礎. 24 (2): 385– 427. arXiv : 2010.09628 . doi :10.1007/s10208-022-09576-6. ISSN  1615-3375. S2CID  224705357.
  9. ^ ab Bubenik, Peter; Scott, Jonathan A. (2014). 「パーシステントホモロジーの分類」.離散幾何学と計算幾何学. 51 (3): 600– 627. arXiv : 1205.3669 . doi :10.1007/s00454-014-9573-x. ISSN  0179-5376. S2CID  254027425.
  10. ^ エデルスブルンナー、ハーバート (1993). 「球体の和集合とその双対形状」.第9回計算幾何学シンポジウム - SCG '93 の議事録. サンディエゴ、カリフォルニア州、アメリカ合衆国: ACM Press. pp.  218– 231. doi :10.1145/160985.161139. ISBN 978-0-89791-582-3. S2CID  9599628。
  11. ^ キム、ジス;シン・ジェヒョク。シャザル、フレデリック。リナルド、アレッサンドロ。ワッサーマン、ラリー (2020-05-12)。 「チェフ錯体とヴィエトリス・リップス錯体によるホモトピー再構成」。arXiv : 1903.06955 [math.AT]。
  12. ^ エデルスブルンナー、ハーバート (2010).計算トポロジー入門. J. ハラー. プロビデンス、ロードアイランド州: アメリカ数学会. p. 61. ISBN 978-0-8218-4925-5. OCLC  427757156。
  13. ^ Chazal, Frédéric; Michel, Bertrand (2021). 「位相的データ分析入門：データサイエンティストのための基礎的および実践的側面」. Frontiers in Artificial Intelligence . 4 667963. doi : 10.3389/frai.2021.667963 . ISSN  2624-8212. PMC 8511823. PMID 34661095  . 
  14. ^ de Silva, Vin; Ghrist, Robert (2007-04-25). 「永続ホモロジーによるセンサーネットワークの被覆」. Algebraic & Geometric Topology . 7 (1): 339– 358. doi : 10.2140/agt.2007.7.339 . ISSN  1472-2739.
  15. ^ 穴井宏一;シャザル、フレデリック。マルク・グリッセ。池裕一。稲越寛也；ティナラージ、ラファエル。梅田、雄平（2020-05-26）。トポロジカル データ分析。アベルシンポジウム。 Vol. 15. arXiv : 1811.04757。土井：10.1007/978-3-030-43408-3。ISBN 978-3-030-43407-6. S2CID  242491854。
  16. ^ ab Chazal, Frédéric; Cohen-Steiner, David; Glisse, Marc; Guibas, Leonidas J.; Oudot, Steve Y. (2009-06-08). 「持続モジュールの近接性とそれらのダイアグラム」 第25回計算幾何学シンポジウム議事録(PDF) . デンマーク、オーフス: ACM. pp.  237– 246. doi :10.1145/1542362.1542407. ISBN 978-1-60558-501-7. S2CID  840484。
  17. ^ Niyogi, Partha; Smale, Stephen; Weinberger, Shmuel (2008). 「ランダムサンプルから高信頼度で部分多様体のホモロジーを見つける」.離散幾何学と計算幾何学. 39 ( 1–3 ): 419–441 . doi : 10.1007/s00454-008-9053-2 . ISSN  0179-5376. S2CID  1788129.
  18. ^ Cohen-Steiner, David; Edelsbrunner, Herbert; Harer, John (2007). 「持続図の安定性​​」.離散幾何学と計算幾何学. 37 (1): 103– 120. doi : 10.1007/s00454-006-1276-5 . ISSN  0179-5376.
  19. ^ Lesnick, Michael (2015). 「多次元パーシスタンスモジュールにおけるインターリービング距離の理論」.計算数学の基礎. 15 (3): 613– 650. arXiv : 1106.5305 . doi :10.1007/s10208-015-9255-y. ISSN  1615-3375. S2CID  254158297.
  20. ^ Lesnick, Michael (2023). 「AMAT 840：マルチパラメータ持続性に関する講義ノート」(PDF) .ニューヨーク州立大学アルバニー校.
  21. ^ Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). 「多重被覆二濾過の計算」.離散幾何学と計算幾何学. 70 (2): 376– 405. arXiv : 2103.07823 . doi :10.1007/s00454-022-00476-8. ISSN  0179-5376. PMC 10423148. PMID 37581017  . 
  22. ^ Edelsbrunner, Herbert; Osang, Georg (2021). 「ユークリッド球体の多重被覆持続性」.離散幾何学と計算幾何学. 65 (4): 1296– 1313. doi :10.1007/s00454-021-00281-9. ISSN  0179-5376. PMC 8550220. PMID 34720303  . 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Offset_filtration&oldid=1309877249"