Колмогоровтың құрылымдық қызметі - Kolmogorov structure function

1973 жылы Колмогоров статистикаға және модельдерді таңдауға ықтимал емес көзқарасты ұсынды. Әрбір санақ ақырлы екілік жол, ал модель екілік жолдардың ақырлы жиынтығы болсын. Берілген максимум модельдерінен тұратын модельдік сыныптарды қарастырайық Колмогоровтың күрделілігі мәтіндері Колмогоровтың құрылымдық қызметі жеке деректер жолының моделдер класындағы күрделілік деңгейінің шектелуі мен мәліметтер құрамындағы сыныптағы модельдің ең төменгі лог-кардиенталдығы арасындағы байланысты білдіреді. Құрылым функциясы бәрін анықтайды стохастикалық жеке деректер жолының қасиеттері: әрбір шектеулі модель сыныбы үшін ол шынайы модель қарастырылған модель класында болғандығына қарамастан класс ішіндегі ең қолайлы модельді анықтайды. Классикалық жағдайда біз ықтималдық үлестірімі бар мәліметтер жиынтығы туралы айтамыз, ал қасиеттері күтуге болады. Керісінше, біз мұнда жеке деректер тізбегімен және жеке жолдың қасиеттерімен айналысамыз. Бұл параметрде қасиет классикалық жағдайдағыдай үлкен ықтималдықпен емес, сенімділікпен орындалады. Колмогоровтың құрылымы функциясы жеке деректерге қатысты жеке модельдің сәйкестігін дәл анықтайды.

Колмогоров құрылымының функциясы алгоритмдік ақпарат теориясы, а. құрылымын сипаттағаны үшін Колмогоров күрделілігі теориясы деп те аталады жіп пайдалану арқылы модельдер күрделене түсетін.

Колмогоровтың анықтамасы

Колмогоров (сол жақта) құрылым функциясы туралы айтады (тақтадағы суретті қараңыз) (Таллин, 1973).

Құрылым функциясы алғашында ұсынылған Колмогоров 1973 жылы Таллинде өткен кеңестік ақпарат теориясы симпозиумында, бірақ бұл нәтижелер жарияланған жоқ^[1] б. 182. Бірақ нәтижелер жарияланды^[2] 1974 жылы Колмогоровтың жалғыз жазбаша жазбасы. Оның соңғы ғылыми тұжырымдарының бірі (орыс тілінен аударған Л.А. Левин):

Әрбір конструктивті нысанға функция сәйкес келеді ${displaystyle Phi _ {x} (k)}$ натурал санның k - күрделіліктің максимумына анықтама беруге мүмкіндік беретін х құрамды жиынтықтардың минималды кардиналының журналы. Егер x элементінің өзі қарапайым анықтамаға мүмкіндік берсе, онда функция ${displaystyle Phi}$ тіпті кіші к үшін 0-ге дейін төмендейді. Мұндай анықтаманың жоқтығы, элемент теріс мағынада «кездейсоқ». Бірақ ол функциясы болған кезде ғана «ықтималдық кездейсоқ» болады ${displaystyle Phi}$ құнды қабылдаған ${displaystyle Phi _ {0}}$ салыстырмалы түрде аз ${displaystyle k = k_ {0}}$ , содан кейін шамамен өзгереді ${displaystyle Phi (k) = Phi _ {0} - (k-k_ {0})}$ .
— Колмогоров, жоғарыда келтірілген хабарландыру

Қазіргі заманғы анықтама

Бұл туралы мұқабада және Томаста талқыланады.^[1] Ол Верещагинде және Витания^[3] Мұндағы негізгі қасиеттер шешілген.Колмогоровтың құрылымының функциясын келесі түрде жазуға болады

{displaystyle h_ {x} (альфа) = min _ {S} {log | S |: xin S, K (S) leq alfa}}

қайда ${displaystyle x}$ - ұзындықтың екілік жолы ${displaystyle n}$ бірге ${displaystyle xin S}$ қайда ${displaystyle S}$ үшін ойластырылған модель (n ұзындықтағы жолдар жиынтығы) ${displaystyle x}$ , ${displaystyle K (S)}$ болып табылады Колмогоровтың күрделілігі туралы ${displaystyle S}$ және ${displaystyle альфа}$ - бұл қарастырылған күрделілікті шектейтін теріс емес бүтін мән ${displaystyle S}$ . Бұл функция өспейтіні және жететіні анық ${displaystyle журналы | {x} | = 0}$ үшін ${displaystyle альфа = K (x) + c}$ қайда ${displaystyle c}$ өзгерту үшін қажетті биттердің саны ${displaystyle x}$ ішіне ${displaystyle {x}}$ және ${displaystyle K (x)}$ болып табылады Колмогоровтың күрделілігі туралы ${displaystyle x}$ .

Алгоритмдік жеткілікті статистика

Біз жиынтықты анықтаймыз ${displaystyle S}$ құрамында ${displaystyle x}$ осындай

{displaystyle K (S) + K (x | S) = K (x) + O (1)}

.

Функция ${displaystyle h_ {x} (альфа)}$ сәйкес анықталған L жеткіліктілік сызығынан диагональдан төмен тұрақты тәуелсіз тұрақтыдан артық ешқашан кемімейді

{displaystyle L (альфа) + альфа = K (х)}

.

Оған график бойынша тұрақты қашықтыққа жақындайды ${displaystyle h_ {x}}$ белгілі бір дәлелдер үшін (мысалы, үшін ${displaystyle альфа = K (x) + c}$ ). Бұлар үшін ${displaystyle альфа}$ бізде бар ${displaystyle alfa + h_ {x} (альфа) = K (x) + O (1)}$ және онымен байланысты модель ${displaystyle S}$ (куә ${displaystyle h_ {x} (альфа)}$ ) үшін оңтайлы жиынтық деп аталады ${displaystyle x}$ , және оның сипаттамасы ${displaystyle K (S) leq альфа}$ биттер сондықтан алгоритмдік жеткілікті статистика. Біз шартты түрде «Колмогоров күрделілігіне» алгоритмдік деп жазамыз. Алгоритмнің негізгі қасиеттері жеткілікті статистикалық мыналар: егер ${displaystyle S}$ үшін алгоритмдік жеткілікті статистика болып табылады ${displaystyle x}$ , содан кейін

{displaystyle K (S) + log | S | = K (x) + O (1)}

.

Яғни, екі бөлімнен тұратын сипаттама ${displaystyle x}$ моделін қолдану ${displaystyle S}$ және индекс индексі-модельге код ретінде ${displaystyle x}$ тізбесінде ${displaystyle S}$ жылы ${displaystyle журналы | S |}$ бит, ең қысқа бір бөлік код сияқты қысқа ${displaystyle x}$ жылы ${displaystyle K (x)}$ биттер. Мұны оңай көруге болады:

{displaystyle K (x) leq K (x, S) + O (1) leq K (S) + K (x | S) + O (1) leq K (S) + log | S | + O (1) leq K (x) + O (1)}

,

тікелей теңсіздіктер мен жеткіліктілік қасиетін пайдаланып, біз мұны табамыз ${displaystyle K (x | S) = log | S | + O (1)}$ . (Мысалы, берілген ${displaystyle Si x}$ , біз сипаттай аламыз ${displaystyle x}$ өздігінен бөлінетін (оның соңын анықтауға болады) ${displaystyle журналы | S | + O (1)}$ бит.) Сондықтан кездейсоқтықтың жетіспеушілігі ${displaystyle журналы | S | -K (x | S)}$ туралы ${displaystyle x}$ жылы ${displaystyle S}$ тұрақты болып табылады, бұл дегеніміз ${displaystyle x}$ - бұл S-дің типтік (кездейсоқ) элементі ${displaystyle S}$ құрамында ${displaystyle x}$ бұл статистика жеткіліксіз. Алгоритмдік жеткілікті статистика ${displaystyle S}$ үшін ${displaystyle x}$ жақсы қасиеттерге ие модельден басқа қосымша қасиеттері бар ${displaystyle K (x, S) = K (x) + O (1)}$ сондықтан Колмогоровтың күрделілігі ақпараттың симметриясы (туралы ақпарат ${displaystyle x}$ жылы ${displaystyle S}$ туралы ақпаратпен бірдей ${displaystyle S}$ х) бізде бар ${displaystyle K (S | x ^ {*}) = O (1)}$ : жеткілікті алгоритмдік статистика ${displaystyle S}$ - бұл толығымен дерлік анықталатын ең жақсы модель ${displaystyle x}$ . ( ${displaystyle x ^ {*}}$ - бұл ең қысқа бағдарлама ${displaystyle x}$ .) Алгоритмдік жеткілікті статистика, ең азмен байланысты ${displaystyle альфа}$ алгоритмдік деп аталады минималды жеткілікті статистика.

Суретке қатысты: MDL құрылымының қызметі ${displaystyle lambda _ {x} (альфа)}$ төменде түсіндіріледі. Сәйкестік құрылымы функциясы ${displaystyle eta _ {x} (альфа)}$ кез-келген модельдің ең аз кездейсоқ жетіспеушілігі (жоғарыдан қараңыз) ${displaystyle Si x}$ үшін ${displaystyle x}$ осындай ${displaystyle K (S) leq альфа}$ . Бұл құрылым функциясы модельге жарамдылықты береді ${displaystyle S}$ (жол бар х) жол үшін x. Төмен болған кезде модель жақсы сәйкес келеді, ал жоғары болған кезде модель жақсы сәйкес келмейді. Егер ${displaystyle eta _ {x} (альфа) = 0}$ кейбіреулер үшін ${displaystyle альфа}$ онда типтік модель бар ${displaystyle Si x}$ үшін ${displaystyle x}$ осындай ${displaystyle K (S) leq альфа}$ және ${displaystyle x}$ S үшін типтік (кездейсоқ), яғни ${displaystyle S}$ х үшін ең қолайлы модель болып табылады. Толығырақ ақпаратты мына жерден қараңыз^[1] және әсіресе^[3] және.^[4]

Қасиеттерді таңдау

Шектеу шеңберінде график кем дегенде 45 градус бұрышпен төмендейді, ол n-ден басталып, шамамен аяқталады ${displaystyle K (x)}$ , әр график (а дейін ${displaystyle O (log n)}$ аргумент пен мәндегі аддитивті термин) кейбір мәліметтердің құрылымдық функциясы арқылы жүзеге асырылады х және керісінше. График бірінші диагональға түскен кезде аргумент (күрделілік) минималды жеткілікті статистиканың дәлелі болып табылады. Бұл орынды анықтау мүмкін емес. Қараңыз.^[3]

Негізгі мүлік

Әр деңгейде екендігі дәлелденді ${displaystyle альфа}$ құрылым функциясының күрделілігі бізге ең жақсы модельді таңдауға мүмкіндік береді ${displaystyle S}$ жолағындағы жеке жол үшін x ${displaystyle O (log n)}$ үлкен ықтималдықпен емес, сенімділікпен.^[3]

MDL нұсқасы

The Сипаттаманың минималды ұзындығы (MDL) функциясы: берілген максималды Колмогоров күрделілігінің жиынтықтарының модельдік класындағы K (S) моделінің құны мен S-дегі х индексінің ұзындығынан тұратын х үшін минималды екі бөлік кодының ұзындығы ${displaystyle альфа}$ , S жоғарғы күрделілігі ${displaystyle альфа}$ , MDL функциясы немесе шектеулі MDL бағалаушысы арқылы берілген:

{displaystyle lambda _ {x} (альфа) = min _ {S} {Lambda (S): Si x,; K (S) leq alfa},}

қайда ${displaystyle Lambda (S) = log | S | + K (S) geq K (x) -O (1)})$ - S моделінің көмегімен х-тің екі бөліктен тұратын кодының жалпы ұзындығы.

Негізгі мүлік

Әр деңгейде екендігі дәлелденді ${displaystyle альфа}$ күрделілігі құрылым функциясы жолақ ішіндегі x жолына арналған S моделін таңдауға мүмкіндік береді ${displaystyle O (log n)}$ үлкен ықтималдықпен емес, сенімділікпен.^[3]

Статистикада қолдану

Жоғарыда дамыған математика негізі ретінде алынды MDL оны ойлап тапқан адам Джорма Риссанен.^[5]

Ықтималдық модельдері

Ықтималдықтардың әр таралуы үшін ${displaystyle P}$ оны дәлелдеуге болады^[6] бұл

{displaystyle -log P (x) = log | S | + O (log n)}

.

Мысалы, егер ${displaystyle P}$ жиынтықта есептелетін үлестіру болып табылады ${displaystyle S}$ ұзын жіптер ${displaystyle n}$ , содан кейін әрқайсысы ${displaystyle xin S}$ ықтималдығы бар ${displaystyle P (x) = exp (O (log n)) / | S | = n ^ {O (1)} / | S |}$ . Колмогоровтың құрылымдық функциясы айналады

{displaystyle h '_ {x} (альфа) = min _ {P} {- журнал P (x): P (x)> 0, K (P) leq альфа}}

Мұндағы x - ұзындығы n болатын екілік жол ${displaystyle -log P (x)> 0}$ қайда ${displaystyle P}$ ойластырылған модель (ықтималдықтың есептелетін мүмкіндігі) ${displaystyle n}$ -ұзындық жолдары) үшін ${displaystyle x}$ , ${displaystyle K (P)}$ болып табылады Колмогоровтың күрделілігі туралы ${displaystyle P}$ және ${displaystyle альфа}$ - бұл қарастырылған күрделілікті шектейтін бүтін мән ${displaystyle P}$ . Бұл функция өспейтіні және жететіні анық ${displaystyle журналы | {x} | = 0}$ үшін ${displaystyle альфа = K (x) + c}$ мұндағы c - өзгерту үшін қажетті биттердің саны ${displaystyle x}$ ішіне ${displaystyle {x}}$ және ${displaystyle K (x)}$ болып табылады Колмогоровтың күрделілігі туралы ${displaystyle x}$ . Содан кейін ${displaystyle h '_ {x} (альфа) = h_ {x} (альфа) + O (log n)}$ . Әрбір күрделілік деңгейі үшін ${displaystyle альфа}$ функциясы ${displaystyle h '_ {x} (альфа)}$ Колмогоровтың күрделі нұсқасы максималды ықтималдығы (ML).

Негізгі мүлік

Әр деңгейде екендігі дәлелденді ${displaystyle альфа}$ құрылым функциясының күрделілігі бізге ең жақсы модельді таңдауға мүмкіндік береді ${displaystyle S}$ жеке жол үшін ${displaystyle x}$ жолағында ${displaystyle O (log n)}$ үлкен ықтималдықпен емес, сенімділікпен.^[3]

MDL нұсқасы және ықтималдық модельдері

MDL функциясы: моделдің құны K (P) және ұзындығынан тұратын x үшін минималды екі бөлік кодының ұзындығы ${displaystyle -log P (x)}$ Берілген максималды күрделіліктің массалық функцияларының есептелетін ықтималдықтарының модельдік класында ${displaystyle альфа}$ , P күрделілігі жоғарғы шектелген ${displaystyle альфа}$ , MDL функциясы немесе шектеулі MDL бағалаушысы арқылы берілген:

{displaystyle lambda '_ {x} (альфа) = min _ {P} {Lambda (P): P (x)> 0,; K (P) leq alfa},}

қайда ${displaystyle Lambda (P) = - log P (x) + K (P) geq K (x) -O (1)})$ - P моделінің көмегімен х-тің екі бөліктен тұратын кодының жалпы ұзындығы.

Негізгі мүлік

Әр деңгейде екендігі дәлелденді ${displaystyle альфа}$ күрделілігі MDL функциясы жолақ ішіндегі x жолына ең жақсы P моделін таңдауға мүмкіндік береді ${displaystyle O (log n)}$ үлкен ықтималдықпен емес, сенімділікпен.^[3]

Бұрмалау мен денонизациялау деңгейіне дейін кеңейту

Бұл теорияны кеңейтуге болады жылдамдықтың бұрмалануы жеке шекті тізбектердің және denoising жеке шекті тізбектер^[7] Колмогоровтың күрделілігін қолдана отырып. Нақты компрессорлық бағдарламаларды қолданатын эксперименттер сәтті өтті.^[8] Мұнда табиғи мәліметтер үшін Колмогоровтың күрделілігі жақсы компрессорды қолданатын сығылған нұсқа ұзындығынан алыс емес деген болжам бар.

Пайдаланылған әдебиеттер

^ ^а ^б ^c Мұқабасы, Томас М .; Томас, Джой А. (1991). Ақпарат теориясының элементтері. Нью-Йорк: Вили. бет.175–178. ISBN 978-0471062592.
^ Успехидегі Мәскеу математикалық қоғамына арналған баяндаманың тезисі. Наук 29-том, 4-шығарылым (178) Мәскеу математикалық қоғамының коммуникациясы 155-бетте (орыс тілінде, ағылшын тіліне аударылмаған)
^ ^а ^б ^c ^г. ^e ^f ^ж Верещагин, Н.К .; Витании, П.М.Б. (1 желтоқсан 2004). «Колмогоровтың құрылымдық функциялары және модельді таңдау». Ақпараттық теория бойынша IEEE транзакциялары. 50 (12): 3265–3290. arXiv:cs / 0204037. дои:10.1109 / TIT.2004.838346.
^ Гакс, П .; Тромп, Дж. Т .; Витании, П.М.Б. (2001). «Алгоритмдік статистика». Ақпараттық теория бойынша IEEE транзакциялары. 47 (6): 2443–2463. arXiv:математика / 0006233. дои:10.1109/18.945257.
^ Риссанен, Джорма (2007). Статистикалық модельдеудегі ақпарат және күрделілік (Онлайн-Аусг. Ред.). Нью-Йорк: Спрингер. ISBN 978-0-387-36610-4.
^ А.Х. Шен, Колмогоров мағынасындағы (α, β) -стохастика туралы түсінік және оның қасиеттері, кеңестік математика. Докл., 28: 1 (1983), 295-299
^ Верещагин, Николай К .; Витании, Пол М.Б. (1 шілде 2010). «Колмогоров күрделілігін пайдаланып жеке деректердің жылдамдығын бұрмалау және денонизациялау». Ақпараттық теория бойынша IEEE транзакциялары. 56 (7): 3438–3454. arXiv:cs / 0411014. дои:10.1109 / TIT.2010.2048491.
^ де Руй, Стивен; Витании, Павел (1 наурыз 2012). «Жеке деректердің жылдамдық-бұрмалану графиктерін жақындастыру: ысырапты сығымдау және денонизациялау тәжірибелері». Компьютерлердегі IEEE транзакциялары. 61 (3): 395–407. arXiv:cs / 0609121. дои:10.1109 / ТК.2011.25.

Әдебиет

Мұқабасы, Т.М .; П.Гакс; Р.М. Сұр (1989). «Колмогоровтың ақпараттық теорияға және алгоритмдік күрделілікке қосқан үлесі». Ықтималдық шежіресі. 17 (3): 840–865. дои:10.1214 / aop / 1176991250. JSTOR 2244387.
Колмогоров, А.Н .; Успенский, В.А. (1 қаңтар 1987 ж.). «Алгоритмдер және кездейсоқтық». Ықтималдықтар теориясы және оның қолданылуы. 32 (3): 389–412. дои:10.1137/1132060.
Ли, М., Витания, ПМБ. (2008). Колмогоровтың күрделілігі және оның қолданылуы туралы кіріспе (3-ші басылым). Нью-Йорк: Спрингер. ISBN 978-0387339986., Әсіресе Колмогоров құрылымының функциясы туралы 401-431 б., Ал жеке тізбектердің жылдамдығын бұрмалау және денотациялау туралы 613-629 бб.
Shen, A. (1 сәуір 1999). «Колмогоровтың күрделілігі және статистикалық талдау туралы талқылау». Компьютерлік журнал. 42 (4): 340–342. дои:10.1093 / comjnl / 42.4.340.
В'югин, В.В. (1987). «Шектелген объектінің күрделілігі берілген өлшемдерге қатысты кездейсоқтық ақаулары туралы». Ықтималдықтар теориясы және оның қолданылуы. 32 (3): 508–512. дои:10.1137/1132071.
V'yugin, V. V. (1 сәуір 1999). «Алгоритмдік күрделілік және шекті бинарлы тізбектің стохастикалық қасиеттері». Компьютерлік журнал. 42 (4): 294–317. дои:10.1093 / comjnl / 42.4.294.

[CT91-1] а ^б ^c Мұқабасы, Томас М .; Томас, Джой А. (1991). Ақпарат теориясының элементтері. Нью-Йорк: Вили. бет.175–178. ISBN 978-0471062592.

[2] Успехидегі Мәскеу математикалық қоғамына арналған баяндаманың тезисі. Наук 29-том, 4-шығарылым (178) Мәскеу математикалық қоғамының коммуникациясы 155-бетте (орыс тілінде, ағылшын тіліне аударылмаған)

[VV04-3] а ^б ^c ^г. ^e ^f ^ж Верещагин, Н.К .; Витании, П.М.Б. (1 желтоқсан 2004). «Колмогоровтың құрылымдық функциялары және модельді таңдау». Ақпараттық теория бойынша IEEE транзакциялары. 50 (12): 3265–3290. arXiv:cs / 0204037. дои:10.1109 / TIT.2004.838346.

[4] Гакс, П .; Тромп, Дж. Т .; Витании, П.М.Б. (2001). «Алгоритмдік статистика». Ақпараттық теория бойынша IEEE транзакциялары. 47 (6): 2443–2463. arXiv:математика / 0006233. дои:10.1109/18.945257.

[5] Риссанен, Джорма (2007). Статистикалық модельдеудегі ақпарат және күрделілік (Онлайн-Аусг. Ред.). Нью-Йорк: Спрингер. ISBN 978-0-387-36610-4.

[6] А.Х. Шен, Колмогоров мағынасындағы (α, β) -стохастика туралы түсінік және оның қасиеттері, кеңестік математика. Докл., 28: 1 (1983), 295-299

[7] Верещагин, Николай К .; Витании, Пол М.Б. (1 шілде 2010). «Колмогоров күрделілігін пайдаланып жеке деректердің жылдамдығын бұрмалау және денонизациялау». Ақпараттық теория бойынша IEEE транзакциялары. 56 (7): 3438–3454. arXiv:cs / 0411014. дои:10.1109 / TIT.2010.2048491.

[8] де Руй, Стивен; Витании, Павел (1 наурыз 2012). «Жеке деректердің жылдамдық-бұрмалану графиктерін жақындастыру: ысырапты сығымдау және денонизациялау тәжірибелері». Компьютерлердегі IEEE транзакциялары. 61 (3): 395–407. arXiv:cs / 0609121. дои:10.1109 / ТК.2011.25.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]