Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf), страница 6
Описание файла
PDF-файл из архива "Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
ê‡Ì„β·Ó„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡, „ËÔ·Ó΢ÂÒÍÓ„Ó ÔÓ ÉÓÏÓ‚Û, ‡‚ÂÌ 1.ê‡ÁÏÂÌÓÒÚ¸ ï‡ÛÒ‰ÓÙ‡ÑÎfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) Ë Î˛·˚ı ‰ÂÈÒÚ‚ËÚÂθÌ˚ı p, q > 0 ÔÛÒÚ¸M pq ( X ) =+∞p∑ (diam( Ai )) , „‰Â ËÌÙËÏÛÏ ·ÂÂÚÒfl ÔÓ ‚ÒÂÏ Ò˜ÂÚÌ˚Ï ÔÓÍ˚ÚËflÏ {Ai}ii =1ÏÌÓÊÂÒÚ‚‡ ï Ò ‰Ë‡ÏÂÚÓÏ Ai ÏÂ̸¯Â q. ê‡ÁÏÂÌÓÒÚ¸ ï‡ÛÒ‰ÓÙ‡ (ËÎË ‡ÁÏÂÌÓÒÚ¸ ï‡ÛÒ‰ÓÙ‡-ÅÂÒËÍӂ˘‡, ‡ÁÏÂÌÓÒÚ¸ ÂÏÍÓÒÚË, Ù‡Íڇθ̇fl ‡ÁÏÂÌÓÒÚ¸)dim Haus(X,d) ÏÌÓÊÂÒÚ‚‡ ï ÓÔ‰ÂÎflÂÚÒfl ͇Íinf p : lim M pq ( X ) = 0 . q→0ã˛·Ó ҘÂÚÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó ËÏÂÂÚ ‡ÁÏÂÌÓÒÚ¸ ï‡ÛÒ‰ÓÙ‡,‡‚ÌÛ˛ 0; ‡ÁÏÂÌÓÒÚ¸ ï‡ÛÒ‰ÓÙ‡ ‰Îfl ‚ÍÎˉӂ‡ ÔÓÒÚ‡ÌÒÚ‚‡ n ‡‚̇ n.ÑÎfl Í‡Ê‰Ó„Ó ‚ÔÓÎÌ ӄ‡Ì˘ÂÌÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ Â„Ó ‡ÁÏÂÌÓÒÚ¸ï‡ÛÒ‰ÓÙ‡ Ó„‡Ì˘Â̇ ÏÂÚ˘ÂÒÍÓÈ ‡ÁÏÂÌÓÒÚ¸˛ Ò‚ÂıÛ Ë ÚÓÔÓÎӄ˘ÂÒÍÓȇÁÏÂÌÓÒÚ¸˛ ÒÌËÁÛ.íÓÔÓÎӄ˘ÂÒ͇fl ‡ÁÏÂÌÓÒÚ¸ÑÎfl β·Ó„Ó ÍÓÏÔ‡ÍÚÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) Â„Ó ÚÓÔÓÎӄ˘ÂÒ͇fl‡ÁÏÂÌÓÒÚ¸ (ËÎË ‡ÁÏÂÌÓÒÚ¸ η„ӂ‡ ÔÓÍ˚ÚËfl) ÓÔ‰ÂÎflÂÚÒfl ͇Í{}inf dim ( X , d ′) ,d′Haus„‰Â d' – β·‡fl ÏÂÚË͇ ̇ ï, ÚÓÔÓÎӄ˘ÂÒÍË ˝Í‚Ë‚‡ÎÂÌÚ̇fl d, ‡ dim – ‡ÁÏÂÌÓÒÚ¸Hausï‡ÛÒ‰ÓÙ‡.Ç Ó·˘ÂÏ ÒÎÛ˜‡Â ÚÓÔÓÎӄ˘ÂÒÍÓÈï ̇Á˚‚‡ÂÚÒfl ̇ËÏÂ̸¯Â ˆÂÎÓÂÓÚÍ˚ÚÓ„Ó ÔÓÍ˚ÚËfl ÏÌÓÊÂÒÚ‚‡ ï(Ú.Â.
ÔÓ‰‡Á‰ÂÎÂÌËÂ), Ú‡ÍÓ ˜ÚÓ ÌË·ÓΠ˜ÂÏ n + 1 ˝ÎÂÏÂÌÚ‡Ï.‡ÁÏÂÌÓÒÚ¸˛ ÚÓÔÓÎӄ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡˜ËÒÎÓ n, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·Ó„Ó ÍÓ̘ÌÓ„ÓÒÛ˘ÂÒÚ‚ÛÂÚ ÍÓ̘ÌÓ ÓÚÍ˚ÚÓ ÔÓ‰ÔÓÍ˚ÚËÂӉ̇ ËÁ ÚÓ˜ÂÍ ÏÌÓÊÂÒÚ‚‡ ï Ì ÔË̇‰ÎÂÊËÚî‡ÍÚ‡ÎíÓÔÓÎӄ˘ÂÒ͇fl ‡ÁÏÂÌÓÒÚ¸ β·Ó„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ Ì Ô‚˚¯‡ÂÚÂ„Ó ‡ÁÏÂÌÓÒÚË ï‡ÛÒ‰ÓÙ‡. î‡ÍÚ‡ÎÓÏ Ì‡Á˚‚‡ÂÚÒfl ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó,‰Îfl ÍÓÚÓÓ„Ó ˝ÚÓ Ì‡‚ÂÌÒÚ‚Ó fl‚ÎflÂÚÒfl ÒÚÓ„ËÏ. (è‚Ó̇˜‡Î¸ÌÓ å‡Ì‰Âθ·ÓÈÚÓÔ‰ÂÎËÎ Ù‡ÍÚ‡Î Í‡Í ÚӘ˜ÌÓ ÏÌÓÊÂÒÚ‚Ó Ò ÌˆÂÎÓ˜ËÒÎÂÌÌÓÈ ‡ÁÏÂÌÓÒÚ¸˛ï‡ÛÒ‰ÓÙ‡). ç‡ÔËÏÂ, ÏÌÓÊÂÒÚ‚Ó ä‡ÌÚÓ‡, ‡ÒÒχÚË‚‡ÂÏÓÂ Í‡Í ÍÓÏÔ‡ÍÚÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚Ó ÔÓÒÚ‡ÌÒÚ‚‡ , d(x, y) = |x–y|), ӷ·‰‡ÂÚ ‡Áln 2ÏÂÌÓÒÚ¸˛ ï‡ÛÒ‰ÓÙ‡; (ÒÏ. ‰Û„Û˛ ä‡ÌÚÓÓ‚Û ÏÂÚËÍÛ Ì‡ ÌÂÏ ‚ „Î. 11, 18).ln 3ÑÛ„ÓÈ Í·ÒÒ˘ÂÒÍËÈ Ù‡ÍÚ‡Î, ÍÓ‚Â ëÂÔËÌÒÍÓ„Ó ÏÌÓÊÂÒÚ‚‡ [0,1] × [0,1], fl‚ÎflÂÚ-É·‚‡ 1.
鷢ˠÓÔ‰ÂÎÂÌËfl29Òfl ÔÓÎÌ˚Ï „ÂÓ‰ÂÁ˘ÂÒÍËÏ ÏÂÚ˘ÂÒÍËÏ ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚ÓÏ ÔÓÒÚ‡ÌÒÚ‚‡( 2 , d(x, y) = ||x–y||1 ).íÂÏËÌ Ù‡ÍڇΠËÒÔÓθÁÛÂÚÒfl Ú‡ÍÊ ‚ ·ÓΠӷ˘ÂÏ ÒÏ˚ÒΠ‰Îfl Ó·ÓÁ̇˜ÂÌËflÒ‡ÏÓÔÓ‰Ó·ÌÓÒÚË (Ú.Â., „Û·Ó „Ó‚Ófl, ÔÓ‰Ó·Ëfl ÔË Î˛·ÓÏ Ï‡Ò¯Ú‡·Â) Ó·˙ÂÍÚ‡(Ó·˚˜ÌÓ – ÔÓ‰ÏÌÓÊÂÒÚ‚‡ n).ê‡ÁÏÂÌÓÒÚ¸ ÄÒÒÛ‡‰–燄‡Ú‡ê‡ÁÏÂÌÓÒÚ¸˛ ÄÒÒÛ‡‰‡–燄‡Ú˚ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl̇ËÏÂ̸¯Â ‰ÂÈÒÚ‚ËÚÂθÌÓ ˜ËÒÎÓ n (ËÎË ∞, ÂÒÎË Ú‡ÍÓ„Ó ˜ËÒ· n Ì ÒÛ˘ÂÒÚ‚ÛÂÚ),‰Îfl ÍÓÚÓÓ„Ó ÒÛ˘ÂÒÚ‚ÛÂÚ ÍÓÌÒÚ‡ÌÚ‡ ë > 0, ڇ͇fl ˜ÚÓ ‰Îfl ‚ÒÂı s > 0 ËÏÂÂÚÒflÔÓÍ˚ÚË ï Â„Ó ÔÓ‰ÏÌÓÊÂÒÚ‚‡ÏË Ò ‰Ë‡ÏÂÚ‡ÏË ≤ë s, ‚ ÍÓÚÓÓÏ Í‡Ê‰ÓÂÔÓ‰ÏÌÓÊÂÒÚ‚Ó ï ‰Ë‡ÏÂÚ‡ ≤s ÔÂÂÒÂ͇ÂÚÒfl Ò ≤n + 1 ˝ÎÂÏÂÌÚ‡ÏË ÔÓÍ˚ÚËfl.ê‡ÁÏÂÌÓÒÚ¸ ÄÒÒÛ‡‰‡–燄‡Ú˚ ·Û‰ÂÚ ÍÓ̘ÌÓÈ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡d – ÏÂÚË͇ Û‰‚ÓÂÌËfl.íÓÔÓÎӄ˘ÂÒ͇fl ‡ÁÏÂÌÓÒÚ¸ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ Ì Ô‚˚¯‡ÂÚ Â„Ó‡ÁÏÂÌÓÒÚË ÄÒÒÛ‡‰‡–燄‡Ú˚.ê‡ÁÏÂÌÓÒÚ¸ Û‰‚ÓÂÌËflê‡ÁÏÂÌÓÒÚ¸˛ Û‰‚ÓÂÌËfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl ̇ËÏÂ̸¯Â ˆÂÎÓ ˜ËÒÎÓ N (ËÎË ∞, ÂÒÎË Ú‡ÍÓ„Ó ˜ËÒ· N Ì ÒÛ˘ÂÒÚ‚ÛÂÚ), Ú‡ÍÓ ˜ÚÓ͇ʉ˚È ÏÂÚ˘ÂÒÍËÈ ¯‡ (ËÎË, Ò͇ÊÂÏ, ÏÌÓÊÂÒÚ‚Ó ÍÓ̘ÌÓ„Ó ‰Ë‡ÏÂÚ‡) ÏÓÊÂÚ·˚Ú¸ ÔÓÍ˚Ú ÒÂÏÂÈÒÚ‚ÓÏ Ì ·ÓΠ2N ÏÂÚ˘ÂÒÍËı ¯‡Ó‚ (ËÎË ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓÏÌÓÊÂÒÚ‚) Ò ÔÓÎÓ‚ËÌÌ˚Ï ‰Ë‡ÏÂÚÓÏ.
ÖÒÎË (X,d) ËÏÂÂÚ ÍÓ̘ÌÛ˛ ‡ÁÏÂÌÓÒÚ¸Û‰‚ÓÂÌËfl, ÚÓ d ̇Á˚‚‡ÂÚÒfl ÏÂÚËÍÓÈ Û‰‚ÓÂÌËfl.ê‡ÁÏÂÌÓÒÚ¸ ÇÓθ·Â„‡–äÓÌfl„Ë̇ê‡ÁÏÂÌÓÒÚ¸˛ ÇÓθ·Â„‡–äÓÌfl„Ë̇ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl ̇ËÏÂ̸¯‡fl ÍÓÌÒÚ‡ÌÚ‡ C > 1 (ËÎË ∞, ÂÒÎË Ú‡ÍÓ„Ó ˜ËÒ· C Ì ÒÛ˘ÂÒÚ‚ÛÂÚ), ‰ÎflÍÓÚÓÓÈ ï ӷ·‰‡ÂÚ ÏÂÓÈ Û‰‚ÓÂÌËfl, Ú.Â.
·ÓÂ΂ÒÍÓÈ ÏÂÓÈ µ, Ú‡ÍÓÈ ˜ÚÓµ( B ( x, 2 r )) ≤ Cµ( B , r ))‰Îfl ‚ÒÂı x ∈ X Ë r > 0. åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ӷ·‰‡ÂÚ ÏÂÓÈ Û‰‚ÓÂÌËflÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ d fl‚ÎflÂÚÒfl ÏÂÚËÍÓÈ Û‰‚ÓÂÌËfl, Ë Î˛·‡fl ÔÓÎ̇fl ÏÂÚË͇ۉ‚ÓÂÌËfl ӷ·‰‡ÂÚ ÏÂÓÈ Û‰‚ÓÂÌËfl.äÓÌÒÚ‡ÌÚÓÈ ä‡„Â‡–êÛ· ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl ̇ËÏÂ̸¯‡fl ÍÓÌÒÚ‡ÌÚ‡ Ò > 1 (ËÎË ∞, ÂÒÎË Ú‡ÍÓ„Ó ˜ËÒ· Ò Ì ÒÛ˘ÂÒÚ‚ÛÂÚ), ‰Îfl ÍÓÚÓÓÈB ( x, 2 r ) ≤ c B ( x, r )‰Îfl ‚ÒÂı x ∈ X Ë r > 0. ÖÒÎË Ó̇ ÍÓ̘̇ (Ò͇ÊÂÏ, ‡‚̇ t), ÚÓ Ï‡ÍÒËχθÌÓÂÁ̇˜ÂÌË ‡ÁÏÂÌÓÒÚË Û‰‚ÓÂÌËfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ÒÓÒÚ‡‚ËÚ 4t.ÄÒËÏÔÚÓÚ˘ÂÒ͇fl ‡ÁÏÂÌÓÒÚ¸èÓÌflÚË ‡ÒËÏÔÚÓÚ˘ÂÒÍÓÈ ‡ÁÏÂÌÓÒÚË ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ·˚ÎÓ‚‚‰ÂÌÓ ÉÓÏÓ‚˚Ï.
ùÚÓ – ̇ËÏÂ̸¯Â ˜ËÒÎÓ n, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·Ó„Ó s > 0ÒÛ˘ÂÒÚ‚Û˛Ú ÍÓÌÒÚ‡ÌÚ‡ D = D(s) Ë ÔÓÍ˚ÚË ï Â„Ó ÔÓ‰ÏÌÓÊÂÒÚ‚‡ÏË Ò ‰Ë‡ÏÂÚ‡ÏË,Ì Ô‚ÓÒıÓ‰fl˘ËÏË D , ‚ ÍÓÚÓÓÏ Í‡Ê‰Ó ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ï ‰Ë‡ÏÂÚ‡ ≤s ÔÂÂÒÂ͇ÂÚÒfl Ò ≤n + 1 ˝ÎÂÏÂÌÚ‡ÏË ÔÓÍ˚ÚËfl.ê‡ÁÏÂÌÓÒÚ¸ ÉÓ‰ÒËΖå‡ÍÍÂflåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ËÏÂÂÚ ‡ÁÏÂÌÓÒÚ¸ ÉÓ‰ÒËΖå‡ÍÍÂfl n ≥ 0, ÂÒÎËÒÛ˘ÂÒÚ‚Û˛Ú ˝ÎÂÏÂÌÚ x0 ∈ X Ë ‰‚ ÔÓÎÓÊËÚÂθÌ˚ ÍÓÌÒÚ‡ÌÚ˚ Ò Ë ë , Ú‡ÍË ˜ÚÓ30ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈ̇‚ÂÌÒÚ‚Ó ckn ≤ |{x ∈ X : d(x, x0) ≤ k}| ≤ Ckn ËÏÂÂÚ ÏÂÒÚÓ ‰Îfl Í‡Ê‰Ó„Ó ˆÂÎÓ„Ó ˜ËÒ·k 0.
чÌÌÓ ÔÓÌflÚË ·˚ÎÓ ‚‚‰ÂÌÓ ‚ [GoMc80] ‰Îfl Ó·ÓÁ̇˜ÂÌËfl ÏÂÚËÍË ÔÛÚËÒ˜ÂÚÌÓ„Ó ÎÓ͇θÌÓ ÍÓ̘ÌÓ„Ó „‡Ù‡. Å˚ÎÓ ‰Ó͇Á‡ÌÓ, ˜ÚÓ ÂÒÎË „ÛÔÔ‡ n ‰ÂÈÒÚ‚ÛÂÚ̇ ‚¯Ë̇ı „‡Ù‡ ÚÓ˜ÌÓ Ë Ò ÍÓ̘Ì˚Ï ˜ËÒÎÓÏ Ó·ËÚ, ÚÓ ‰‡Ì̇fl ‡ÁÏÂÌÓÒÚ¸‡‚̇ n.ÑÎË̇ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ÑÎËÌÓÈ îÂÏÎË̇ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ ̇Á˚‚‡ÂÚÒfl Ó‰ÌÓÏÂ̇fl ‚̯Ìflflχ ï‡ÛÒ‰ÓÙ‡ ̇ X.ÑÎËÌÓÈ ïÂÈÍχ̇ lng(Y) ÔÓ‰ÏÌÓÊÂÒÚ‚‡ M ⊂ X ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d)̇Á˚‚‡ÂÚÒfl sup{lng( M ′) : M ′ ⊂ M , M ′ < ∞}. á‰ÂÒ¸ lng(∅ ) = 0 Ë, ‰Îfl ÍÓ̘ÌÓ„ÓnÔÓ‰ÏÌÓÊÂÒÚ‚‡ M' ⊂ X, lng(M') = min∑ d( xi −1, xi ),„‰Â ÏËÌËÏÛÏ ·ÂÂÚÒfl ÔÓ ‚ÒÂÏi =1ÔÓÒΉӂ‡ÚÂθÌÓÒÚflÏ x 0 , ..., xn, Ú‡ÍËÏ ˜ÚÓ {x i : i = 0, 1, ..., n} = M'.ÑÎËÌÓÈ òÂıÚχ̇ ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒflninf∑ ai2ÔÓ ‚ÒÂÏ Ú‡ÍËÏ ÔÓÒΉӂ‡ÚÂθÌÓÒÚflÏ a1, ..., an ÔÓÎÓÊËÚÂθÌ˚ı ˜ËÒÂÎ, ˜ÚÓi =1ÒÛ˘ÂÒÚ‚ÛÂÚ ÔÓÒΉӂ‡ÚÂθÌÓÒÚ¸ ï0, …, ïn ‡Á·ËÂÌËÈ ï ÒÓ ÒÎÂ‰Û˛˘ËÏË Ò‚ÓÈÒÚ‚‡ÏË:1. ï 0 = {X} Ë ïn = {{x} : x ∈ X};2. ï i ÔÓ‰‡Á·Ë‚‡ÂÚ ïi–1 ‰Îfl i = 1, …, n;3. ÑÎfl i = 1,…, n Ë B, C ⊂ A ∈ Xi– 1 Ò B, C ∈ X i ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡ÍÓ ӉÌÓÁ̇˜ÌÓÂÓÚÓ·‡ÊÂÌË f ËÁ Ç Ì‡ ë, ˜ÚÓ d(x, f)(x)) ≤ ai ‰Îfl ‚ÒÂı x ∈ B.íËÔ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡íËÔ ÔÓ ÖÌÙÎÓ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ‡‚ÂÌ , ÂÒÎË ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡Í‡flÍÓÌÒÚ‡ÌÚ‡ 1 ≤ ë < ∞, ˜ÚÓ ‰Îfl Í‡Ê‰Ó„Ó n ∈ Ë Í‡Ê‰ÓÈ ÙÛÌ͈ËË f : {–1,1}n → X ËÏÂÂÚÏÂÒÚÓ Ì‡‚ÂÌÒÚ‚Ó∑d p ( f (ε ), f ( − ε )) ≤ε ∈{−1,1}nn≤ Cp∑ ∑j =1 ε ∈{−1,1}d p ( f (ε1 ,..., ε j −1 , ε j +1 ,..., ε n ), f (ε1 ,..., ε j −1 , − ε j ,..., ε n )).nŇ̇ıÓ‚Ó ÔÓÒÚ‡ÌÒÚ‚Ó (V, || ⋅ ||) ÚËÔ‡ ÔÓ ÖÌÙÎÓ ËÏÂÂÚ ÚËÔ ÔÓ ê‡‰ÂχıÂÛ,Ú.Â.
‰Îfl ‚ÒÂı ı1 ,…,ın ∈ V ‚˚ÔÓÎÌflÂÚÒfl ̇‚ÂÌÒÚ‚Ópn∑ ∑ε ∈{−1,1}n j =1εjxjn≤ Cp∑pxj .j =1ÑÎfl ‰‡ÌÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ÒËÏÏÂÚ˘ÌÓÈ ˆÂÔ¸˛ å‡ÍÓ‚‡∞̇ ï fl‚ÎflÂÚÒfl ˆÂÔ¸ å‡ÍÓ‚‡ { l }l = 0 ̇ ÔÓÒÚ‡ÌÒÚ‚Â ÒÓÒÚÓflÌËÈ {ı1,…,ım} ⊂ Xc Ú‡ÍËÏ ÒËÏÏÂÚ˘Ì˚Ï ÔÂÂÌÓÒÓÏ m × m χÚˈ˚ ((aij)) ˜ÚÓ P(Zl+1 = xj : Zl = xj) = aij Ë1P(Z 0 = xi) =‰Îfl ‚ÒÂı ˆÂÎ˚ı 1 ≤ i, j ≤ m Ë l ≥ 0. åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d)m31É·‚‡ 1. 鷢ˠÓÔ‰ÂÎÂÌËflËÏÂÂÚ ÚËÔ ÔÓ å‡ÍÓ‚Û (ÅÓÎÎ, 1992), ÂÒÎË supT Mp (X, T) < ∞, „‰Â Mp (X, T) – ڇ͇fl∞̇ËÏÂ̸¯‡fl ÍÓÌÒÚ‡ÌÚ‡ C > 0, ˜ÚÓ ‰Îfl ͇ʉÓÈ ÒËÏÏÂÚ˘ÌÓÈ ˆÂÔË å‡ÍÓ‚‡ { l }l = 0Ì ‡ ï ‚˚ÔÓÎÌflÂÚÒfl, ‚ ÚÂÏË̇ı ÓÊˉ‡ÂÏÓÈ ‚Â΢ËÌ˚ (Ò‰ÌÂ„Ó Á̇˜ÂÌËfl)[ X ] =xp( x ) ‰ËÒÍÂÚÌÓÈ ÒÎÛ˜‡ÈÌÓÈ ‚Â΢ËÌ˚ ï, ̇‚ÂÌÒÚ‚Ó∑xd p ( ZT , Z0 ) ≤ TC pd p ( Z1 , Z0 ).åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó ÚËÔ‡ ÔÓ å‡ÍÓ‚Û ËÏÂÂÚ ÚËÔ ÔÓ ÖÌÙÎÓ.ëË· ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡èÛÒÚ¸ (X,d) – ÔÓËÁ‚ÓθÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ò s ‡Á΢Ì˚ÏË ÌÂÌÛ΂˚ÏË Á̇˜ÂÌËflÏË dx,y.
Ö„Ó ÒË· ÂÒÚ¸ ̇˷Óθ¯Â ˜ËÒÎÓ t, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·˚ıˆÂÎ˚ı p, q ≥ 0 c p + q ≤ t ÒÛ˘ÂÒÚ‚ÛÂÚ ÏÌÓ„Ó˜ÎÂÌ fpq(s) ÒÚÂÔÂÌË, Ì Ô‚ÓÒıÓ‰fl˘ÂÈ()() (( fmin{p, q}, Ú‡ÍÓÈ ˜ÚÓ ( dij2 p ) ( dij2 q ) =)).2pq ( dij )åÂÚ˘ÂÒÍËÈ ÙÛÌ͈ËÓ̇ÎÑÎfl ÒÎÛ˜‡fl ÍÓ̘ÌÓ„Ó ÔÓ‰ÏÌÓÊÂÒÚ‚‡ M ⊂ X ‚ ÏÂÚ˘ÂÒÍÓÏ ÔÓÒÚ‡ÌÒÚ‚Â (X,d)ÔËÏÂ˚ ÏÂÚ˘ÂÒÍÓ„Ó ÙÛÌ͈ËÓ̇· ̇ å Ô˂‰ÂÌ˚ ÌËÊÂ.1-˝Ì„Ëfl ÏÌÓÊÂÒÚ‚‡ å ÂÒÚ¸ ˜ËÒÎÓ; Ó·˚˜ÌÓ = 1,2.pd ( x, y)x , y ∈M , x ≠ y∑ë‰Ì ‡ÒÒÚÓflÌË ÏÌÓÊÂÒÚ‚‡ å ÂÒÚ¸ ˜ËÒÎÓ∑1d ( x, y).M ( M − 1) x , y ∈Mà̉ÂÍÒ ÇË̇ ÏÌÓÊÂÒÚ‚‡ å (ÔËÏÂÌflÂÏ˚È ‚ ıËÏËË) ÂÒÚ¸ ˜ËÒÎÓ∑1d ( x, y).2 x , y ∈MñÂÌÚ Ï‡ÒÒ˚ ÍÓ̘ÌÓ„Ó ÏÌÓÊÂÒÚ‚‡ å ÂÒÚ¸ ÚӘ͇ x ∈ M, ÏËÌËÏËÁËÛ˛˘‡flÙÛÌ͈ËÓ̇Îd 2 ( x, y).∑y ∈MóËÒÎÓ ‚ÒÚ˜ËóËÒÎÓÏ ‚ÒÚÂ˜Ë (ËÎË ˜ËÒÎÓÏ ÉÓÒÒ‡, χ„˘ÂÒÍËÏ ˜ËÒÎÓÏ) ÏÂÚ˘ÂÒÍÓ„ÓÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl ÔÓÎÓÊËÚÂθÌÓ ‰ÂÈÒÚ‚ËÚÂθÌÓ ˜ËÒÎÓ r(X,d) (ÂÒÎËÚ‡ÍÓ ÒÛ˘ÂÒÚ‚ÛÂÚ), Ú‡ÍÓ ˜ÚÓ ‰Îfl Í‡Ê‰Ó„Ó ˆÂÎÓ„Ó n Ë Î˛·˚ı (Ì ӷflÁ‡ÚÂθÌÓ‡Á΢Ì˚ı) x1,...,xn ∈ X ÒÛ˘ÂÒÚ‚ÛÂÚ x ∈ X, ‰Îfl ÍÓÚÓÓ„Ór( X, d ) =12n∑ d( xi , x ).i =1ÖÒÎË ‰Îfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ˜ËÒÎÓ ‚ÒÚÂ˜Ë r(X,d) ÒÛ˘ÂÒÚ‚ÛÂÚ, ÚÓ„Ó‚ÓflÚ, ˜ÚÓ (X,d) ËÏÂÂÚ Ò‚ÓÈÒÚ‚Ó Ò‰ÌÂ„Ó ‡ÒÒÚÓflÌËfl Ë Â„Ó Ï‡„˘ÂÒ͇fl ÍÓÌÒÚ‡ÌÚ‡r( X, d )ÓÔ‰ÂÎflÂÚÒfl ͇Í, „‰Â diam(X,d) = max d ( x, y) – ‰Ë‡ÏÂÚ (X,d).x , y ∈Xdiam( X , d )ä‡Ê‰Ó ÍÓÏÔ‡ÍÚÌÓ ҂flÁÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ó·Î‡‰‡ÂÚ Ò‚ÓÈÒÚ‚ÓÏÒ‰ÌÂ„Ó ‡ÒÒÚÓflÌËfl.
Ö‰ËÌ˘Ì˚È ¯‡ {x ∈ V : ||x|| ≤ 1} ·‡Ì‡ıÓ‚‡ ÔÓÒÚ‡ÌÒÚ‚‡(V, || ⋅ ||) ËÏÂÂÚ Ò‚ÓÈÒÚ‚Ó Ò‰ÌÂ„Ó ‡ÒÒÚÓflÌËfl Ò ˜ËÒÎÓÏ ‚ÒÚÂ˜Ë 1.32ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈèÓfl‰ÓÍ ÍÓÌ„Û˝ÌÚÌÓÒÚËåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ӷ·‰‡ÂÚ ÔÓfl‰ÍÓÏ ÍÓÌ„Û˝ÌÚÌÓÒÚË n, ÂÒÎË͇ʉÓ ÍÓ̘ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, Ì fl‚Îfl˛˘ÂÂÒfl ËÁÓÏÂÚ˘ÂÒÍË‚ÎÓÊËÏ˚Ï ‚ (X,d), ËÏÂÂÚ ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚Ó, ÒÓ‰Âʇ˘Â Ì ·ÓΠn ÚÓ˜ÂÍ, ÍÓÚÓÓÂÌ ÏÓÊÂÚ ·˚Ú¸ ËÁÓÏÂÚ˘ÂÒÍË ‚ÎÓÊÂÌÓ ‚ (X,d).ꇉËÛÒ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡èÛÒÚ¸ (X,d) – Ó„‡Ì˘ÂÌÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ë M ⊂ X. åÂÚ˘ÂÒÍËχ‰ËÛÒÓÏ (ËÎË ‡‰ËÛÒÓÏ) ÏÌÓÊÂÒÚ‚‡ å ̇Á˚‚‡ÂÚÒfl ËÌÙËÏÛÏ ‡‰ËÛÒÓ‚ ÏÂÚ˘ÂÒÍËı¯‡Ó‚, ÒÓ‰Âʇ˘Ëı å, Ú.Â. inf sup d ( x, y).
çÂÍÓÚÓ˚ ‡‚ÚÓ˚ ̇Á˚‚‡˛Ú ‡‰ËÛÒÓÏx ∈M y ∈MÔÓÎÓ‚ËÌÛ ‰Ë‡ÏÂÚ‡.ꇉËÛÒÓÏ ÔÓÍ˚ÚËfl ÏÌÓÊÂÒÚ‚‡ M ⊂ X ̇Á˚‚‡ÂÚÒfl max min d ( x, y), Ú.Â. ̇Ëx ∈X y ∈MÏÂ̸¯Â ˜ËÒÎÓ R, Ú‡ÍÓ ˜ÚÓ ÓÚÍ˚Ú˚ ÏÂÚ˘ÂÒÍË ¯‡˚ ‡‰ËÛÒ‡ R c ˆÂÌÚ‡ÏË ‚˝ÎÂÏÂÌÚ‡ı å ÔÓÍ˚‚‡˛Ú ï. Ö„Ó Ì‡Á˚‚‡˛Ú ¢ ÓËÂÌÚËÓ‚‡ÌÌ˚Ï ı‡ÛÒ‰ÓÙÓ‚˚χÒÒÚÓflÌËÂÏ ÓÚ ï Í å. åÌÓÊÂÒÚ‚Ó å ̇Á˚‚‡ÂÚÒfl ε-ÔÓÍ˚ÚËÂÏ, ÂÒÎË Â„Ó ‡‰ËÛÒÔÓÍ˚ÚËfl Ì Ô‚˚¯‡ÂÚ ε. ÑÎfl ‰‡ÌÌÓ„Ó ÔÓÎÓÊËÚÂθÌÓ„Ó ˜ËÒ· m ÏËÌËχÍÒËχθ̇fl ‡ÒÒÚÓflÌ̇fl ÍÓÌÙË„Û‡ˆËfl ‡Áχ m ÂÒÚ¸ m-ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ï Ò̇ËÏÂ̸¯ËÏ ‡‰ËÛÒÓÏ ÔÓÍ˚ÚËfl.ꇉËÛÒÓÏ ÛÔÎÓÚÌÂÌËfl ÏÌÓÊÂÒÚ‚‡ M ⊂ X ̇Á˚‚‡ÂÚÒfl Ú‡ÍÓ ̇˷Óθ¯Â r, ˜ÚÓÓÚÍ˚Ú˚ ÏÂÚ˘ÂÒÍË ¯‡˚ ‡‰ËÛÒ‡ r Ò ˆÂÌÚ‡ÏË ‚ ˝ÎÂÏÂÌÚ‡ı å fl‚Îfl˛ÚÒflÔÓÔ‡ÌÓ ÌÂÔÂÂÒÂ͇˛˘ËÏËÒfl, Ú.Â. min min d ( x, y) > 2 r. åÌÓÊÂÒÚ‚Ó å ̇Á˚‚‡ÂÚÒfly ∈X y ∈Mε-ÛÔÎÓÚÌÂÌËÂÏ, ÂÒÎË Â„Ó ‡‰ËÛÒ ÛÔÎÓÚÌÂÌËfl Ì ÏÂÌ ε. ÑÎfl ‰‡ÌÌÓ„Ó ÔÓÎÓÊËÚÂθÌÓ„Ó ˜ËÒ· m χÍÒËχθ̇fl ‡ÒÒÚÓflÌ̇fl ÍÓÌÙË„Û‡ˆËfl ‡Áχ m ÂÒÚ¸ m-ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ÏÌÓÊÂÒÚ‚‡ ï Ò Ì‡Ë·Óθ¯ËÏ ‡‰ËÛÒÓÏ ÛÔÎÓÚÌÂÌËfl.ê‡ÁÏ ̇ËÏÂ̸¯Â„Ó ε -ÔÓÍ˚ÚËfl Ì Ô‚ÓÒıÓ‰ËÚ ‡Áχ ̇˷Óθ¯Â„Óεε-ÛÔÎÓÚÌÂÌËfl.
-ÛÔÎÓÚÌÂÌË å fl‚ÎflÂÚÒfl ̇үËflÂÏ˚Ï, ÂÒÎË M ∪ {x} Ì fl‚ÎflÂÚ22εÒfl -ÛÔÎÓÚÌÂÌËÂÏ ‰Îfl Í‡Ê‰Ó„Ó x ∈ X\M, Ú.Â. å fl‚ÎflÂÚÒfl Ú‡ÍÊ ε-ÒÂÚ¸˛.2ùÍÒˆÂÌÚËÒËÚÂÚèÛÒÚ¸ (X,d) – Ó„‡Ì˘ÂÌÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó. ùÍÒˆÂÌÚËÒËÚÂÚÓÏ ÚÓ˜ÍËx ∈ X ̇Á˚‚‡ÂÚÒfl ˜ËÒÎÓ e( x ) = max d ( x, y). óËÒ· max e( x ) Ë min e( x ) ̇Á˚‚‡˛ÚÒfly ∈Xx ∈Xx ∈XÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ ‰Ë‡ÏÂÚÓÏ Ë ‡‰ËÛÒÓÏ (X,d).íÓ˜ÍË x ∈ X Ò Ï‡ÍÒËχθÌ˚Ï Â(ı) ̇Á˚‚‡˛ÚÒfl ÔÂËÙÂËÈÌ˚ÏË ÚӘ͇ÏË.åÌÓÊÂÒÚ‚‡ {x ∈ X : e(x) ≤ e(z) ‰Îfl β·Ó„Ó z ∈ X} Ë {x ∈ X :d ( x, y) ≤d ( z, y)∑y ∈X∑y ∈X‰Îfl β·Ó„Ó z ∈ X } ̇Á˚‚‡˛ÚÒfl ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ ÏÂÚ˘ÂÒÍËÏ ˆÂÌÚÓÏ (ËÎˈÂÌÚÓÏ ˝ÍÒˆÂÌÚËÒËÚÂÚ‡, ˆÂÌÚÓÏ) Ë ÏÂÚ˘ÂÒÍÓÈ Ï‰ˇÌÓÈ (ËÎË ˆÂÌÚÓχÒÒÚÓflÌËfl) ÔÓÒÚ‡ÌÒÚ‚‡ (X,d).k-ÔÓ‰ÏÌÓÊÂÒÚ‚Ó Ì‡Á˚‚‡ÂÚÒfl M ⊂ X k-ωˇÌÓÈ, ÂÒÎË Ó̇ ÏËÌËÏËÁËÛÂÚ ÒÛÏÏÛd ( x, M ), „‰Â d(x,M) – ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ.∑x ∈X33É·‚‡ 1.