Рандомизированный метод решения дискретных некорректных задач
Запропоновано підхід до сталого рішення дискретних некоректних задач на основі комбінації випадкового проектування погано обумовленої початкової матриці з невизначеним чисельним рангом і псевдообернення результуючої матриці. Для вибору розмірності проекційної матриці пропонується використовувати кри...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84136 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Рандомизированный метод решения дискретных некорректных задач / Д.А. Рачковский, Е.Г. Ревунова // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 163-181. — Бібліогр.: 32 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860113068640436224 |
|---|---|
| author | Рачковский, Д.А. Ревунова, Е.Г. |
| author_facet | Рачковский, Д.А. Ревунова, Е.Г. |
| citation_txt | Рандомизированный метод решения дискретных некорректных задач / Д.А. Рачковский, Е.Г. Ревунова // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 163-181. — Бібліогр.: 32 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано підхід до сталого рішення дискретних некоректних задач на основі комбінації випадкового проектування погано обумовленої початкової матриці з невизначеним чисельним рангом і псевдообернення результуючої матриці. Для вибору розмірності проекційної матриці пропонується використовувати критерії вибору моделі і параметра регуляризації. Наведено результати експериментального дослідження на відомих прикладах дискретних некоректних задач. Помилка рішення близька до помилки регуляризації Тихонова, однак скорочення розмірності матриць (завдяки проекції) сприяє зменшенню обчислювальних витрат, особливо при високому рівні шуму.
An approach is proposed to the stable solution of discrete ill-posed problems, based on a combination of random projection of the initial ill-conditioned matrix with ill-defined numerical rank and pseudo-inversion of the resultant matrix. To select the dimension of the projection matrix, we propose to use selection criteria for the model and regularization parameter. The results of experimental studies on the well-known examples of discrete ill-posed problems are given. The solution error is close to the Tikhonov regularization error however, reducing the matrix dimension due to the projection reduces the computational costs, especially at high noise levels.
|
| first_indexed | 2025-12-07T17:34:58Z |
| format | Article |
| fulltext |
Ä.À. ÐÀ×ÊÎÂÑÊÈÉ, Å.Ã. ÐÅÂÓÍÎÂÀ
ÓÄÊ 004.942 + 623.454.862 ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÉ ÌÅÒÎÄ ÐÅØÅÍÈß
ÄÈÑÊÐÅÒÍÛÕ ÍÅÊÎÐÐÅÊÒÍÛÕ ÇÀÄÀ×
Êëþ÷åâûå ñëîâà: äèñêðåòíàÿ íåêîððåêòíàÿ çàäà÷à, ñëó÷àéíûå ïðîåêöèè,
ðåãóëÿðèçàöèÿ.
ÂÂÅÄÅÍÈÅ
Äëÿ ìíîãèõ ïðàêòè÷åñêèõ ïðèëîæåíèé íåîáõîäèìî ðåøåíèå äèñêðåòíîé çàäà-
÷è Ax b� , ãäå ìàòðèöà A è âåêòîð b èçâåñòíû, âåêòîð x òðåáóåòñÿ îöåíèòü.
Åñëè ñèíãóëÿðíûå çíà÷åíèÿ A ïëàâíî óáûâàþò äî íóëÿ è îòíîøåíèå ìåæäó
íàèáîëüøèì è íàèìåíüøèì íåíóëåâûì ñèíãóëÿðíûìè çíà÷åíèÿìè âåëèêî, çà-
äà÷ó íàçûâàþò äèñêðåòíîé íåêîððåêòíîé çàäà÷åé [1].
Ïðèáëèæåííûå ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷ êàê çàäà÷ íàèìåíü-
øèõ êâàäðàòîâ ñ èñïîëüçîâàíèåì ÷èñëåííûõ ìåòîäîâ ëèíåéíîé àëãåáðû, òàêèõ êàê
ðàçëîæåíèÿ LU, Õîëåöêîãî, QR, ÿâëÿþòñÿ íåóñòîé÷èâûìè. Ýòî îçíà÷àåò, ÷òî ìàëûå
âîçìóùåíèÿ âî âõîäíûõ äàííûõ ïðèâîäÿò ê áîëüøèì âîçìóùåíèÿì â ðåøåíèè.
Ðåøåíèå íåêîððåêòíûõ çàäà÷ âîñòðåáîâàíî âî ìíîãèõ îáëàñòÿõ íàóêè è òåõ-
íèêè. Äèñêðåòíûå íåêîððåêòíûå çàäà÷è âîçíèêàþò, íàïðèìåð, ïðè äèñêðåòèçà-
öèè èíòåãðàëüíûõ óðàâíåíèé Ôðåäãîëüìà è Âîëüòåððû ïåðâîãî ðîäà. Âàæíûå
ïðîáëåìû ñïåêòðîìåòðèè [2], ãðàâèìåòðèè, ìàãíèòîìåòðèè, ýëåêòðîðàçâåäêè è
äðóãèå îáëàäàþò ñâîéñòâàìè äèñêðåòíûõ íåêîððåêòíûõ çàäà÷.
Äëÿ ïðåîäîëåíèÿ íåñòàáèëüíîñòè è ïîâûøåíèÿ òî÷íîñòè ðåøåíèÿ äèñêðåò-
íûõ íåêîððåêòíûõ çàäà÷ ïðåäëîæåíû ìåòîäû ðåãóëÿðèçàöèè [1–5]. Ðåãóëÿðèçà-
öèÿ íàêëàäûâàåò íà èñêîìîå ðåøåíèå îãðàíè÷åíèÿ, îáåñïå÷èâàþùèå åãî óñòîé-
÷èâîñòü. Íàïðèìåð, ðåãóëÿðèçàöèÿ Òèõîíîâà [3, 1] íàêëàäûâàåò øòðàô íà
ðåøåíèÿ ñ áîëüøèìè l2-íîðìàìè.
Íåäîñòàòêè, ïðèñóùèå ìåòîäàì ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷ íà
îñíîâå ðåãóëÿðèçàöèè Òèõîíîâà, ñâÿçàíû ñ âûñîêîé âû÷èñëèòåëüíîé ñëîæíîñ-
òüþ è òðóäíîñòüþ âûáîðà íàäëåæàùåãî ïàðàìåòðà ðåãóëÿðèçàöèè (âåñà øòðàôà),
âëèÿþùåãî íà óñòîé÷èâîñòü ðåøåíèÿ. Ýòî îïðåäåëÿåò ïðàêòè÷åñêóþ ïîòðåá-
íîñòü â ðàçâèòèè àëüòåðíàòèâíûõ ïîäõîäîâ ê ðåøåíèþ äèñêðåòíûõ íåêîððåêò-
íûõ çàäà÷, èìåþùèõ òî÷íîñòü, ñðàâíèìóþ ñ ðåãóëÿðèçàöèåé Òèõîíîâà, íî ïðè
ìåíüøèõ âû÷èñëèòåëüíûõ çàòðàòàõ.
 íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ ïîäõîä, èñïîëüçóþùèé èäåè íåéðîñåòåâî-
ãî ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ èíôîðìàöèè è ñëó÷àéíûõ ïðîåêöèé [6–9].
 ïîñëåäíåå âðåìÿ èññëåäîâàòåëè, ðàáîòàþùèå â îáëàñòè ÷èñëåííûõ ìåòîäîâ ëè-
íåéíîé àëãåáðû, ïðèìåíÿþò ïîäîáíûå èäåè äëÿ ïîëó÷åíèÿ áûñòðûõ ðàíäîìèçè-
ðîâàííûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ íàèìåíüøèõ êâàäðàòîâ, ôàêòîðèçàöèè ìàò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 163
© Ä.À. Ðà÷êîâñêèé, Å.Ã. Ðåâóíîâà, 2012
ðèö, àíàëèçà ãëàâíûõ êîìïîíåíò è äð. Â äàííîé ñòàòüå îáîáùåíû ðåçóëüòàòû
ïðåäûäóùèõ èññëåäîâàíèé àâòîðîâ ïî ðàçðàáîòêå ðàíäîìèçèðîâàííûõ ìåòîäîâ
íà îñíîâå ñëó÷àéíûõ ïðîåêöèé, êîòîðûå ïîçâîëÿþò óñêîðèòü è îáåñïå÷èòü
óñòîé÷èâîñòü ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ îáðàòíûõ çàäà÷. Ïðèâåäåíû òàê-
æå íîâûå ðåçóëüòàòû ïî âûáîðó ïàðàìåòðîâ ðàíäîìèçèðîâàííîãî ïðåîáðàçîâàíèÿ
äëÿ ïîëó÷åíèÿ áëèçêîé ê îïòèìàëüíîé (ìèíèìàëüíîé) îøèáêè ðåøåíèÿ.
1. ËÈÍÅÉÍÛÅ ÇÀÄÀ×È ÍÀÈÌÅÍÜØÈÕ ÊÂÀÄÐÀÒÎÂ È ÄÈÑÊÐÅÒÍÛÅ
ÍÅÊÎÐÐÅÊÒÍÛÅ ÇÀÄÀ×È
Âî ìíîãèõ ïðèëîæåíèÿõ ìàòåìàòèêè, ôèçèêè, àíàëèçà äàííûõ òðåáóåòñÿ ïðè-
áëèæåííîå ðåøåíèå ñèñòåìû ëèíåéíûõ óðàâíåíèé, êîòîðàÿ íå èìååò òî÷íîãî
ðåøåíèÿ. Íàïðèìåð, â çàäà÷å
Ax b� , (1)
ãäå ìàòðèöà A �� �m n è âåêòîð b èçâåñòíû, âåêòîð x íóæíî îöåíèòü, äëÿ
m n� , èëè m n� , èëè min( , ) ( )m n � rank A â îáùåì ñëó÷àå íå ñóùåñòâóåò òàêîãî x,
÷òî Ax b . Ìåòîä íàèìåíüøèõ êâàäðàòîâ âûáèðàåò x
, ìèíèìèçèðóþùèé
ñóììó êâàäðàòîâ êîìïîíåíòîâ âåêòîðà íåâÿçêè, ïóòåì ðåøåíèÿ îïòèìèçàöèîí-
íîé çàäà÷è
x Ax b
x
�arg min| | | |2 . (2)
Ðåøåíèå (2) ìîæíî ïîëó÷èòü, âçÿâ ïðîèçâîäíóþ îò | | | |Ax b� 2 ( )Ax b� �T
� �( )Ax b ïî x è ïîëîæèâ åå ðàâíîé íóëþ. Ýòî äàåò ñèñòåìó òàê íàçûâàåìûõ
íîðìàëüíûõ óðàâíåíèé [10]
A Ax A bT T , (3)
êîòîðóþ íàäî ðåøèòü äëÿ ïîëó÷åíèÿ ìèíèìèçèðóþùåãî âåêòîðà x
. Ïðè òàêîì
ðåøåíèè âåêòîð îñòàòêà (íåâÿçêè) ( )Ax b
� îðòîãîíàëåí ïðîñòðàíñòâó ñòîëáöîâ A,
ò.å. ( )Ax b A
� T 0. Åñëè ìàòðèöà A AT èìååò ïîëíûé ðàíã è õîðîøî îáóñëîâëå-
íà, ñèñòåìó (3) ìîæíî ðåøèòü ñ ïîìîùüþ ðàçëîæåíèÿ Õîëåöêîãî A A R RT T ,
÷òî äàåò R Rx A bT T , ãäå R ÿâëÿåòñÿ âåðõíåé òðåóãîëüíîé ìàòðèöåé.
 ñëó÷àå, êîãäà A èìååò íåïîëíûé ðàíã èëè ïëîõî îáóñëîâëåíà, ìîæåò èñ-
ïîëüçîâàòüñÿ ðåøåíèå QR-ðàçëîæåíèåì: A QR , ãäå Q — îðòîãîíàëüíàÿ ìàòðè-
öà, R — âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. Òîãäà èç (3) ïîëó÷àåì ñèñòåìó Rx Q b T ,
êîòîðàÿ áëàãîäàðÿ òðåóãîëüíîñòè R ðåøàåòñÿ ïîñëåäîâàòåëüíî, ïóòåì îáðàòíîé
ïîäñòàíîâêè.
Ïðè î÷åíü ïëîõî îáóñëîâëåííîé ìàòðèöå A äëÿ ðåøåíèÿ èñïîëüçóþò ðàçëî-
æåíèå ïî ñèíãóëÿðíûì çíà÷åíèÿì — SVD (Singular Value Decomposition). Ìåòîä
SVD ïðåäñòàâëÿåò A êàê
A USV T , (4)
ãäå U — ìàòðèöà ëåâûõ ñèíãóëÿðíûõ âåêòîðîâ ñ îðòîíîðìèðîâàííûìè ñòîëá-
öàìè, V — ìàòðèöà ïðàâûõ ñèíãóëÿðíûõ âåêòîðîâ ñ îðòîíîðìèðîâàííûìè
ñòîëáöàìè, S — äèàãîíàëüíàÿ ìàòðèöà ñèíãóëÿðíûõ çíà÷åíèé. Ñ ïîìîùüþ
SVD ðåøåíèå ïîëó÷àþò â âèäå
x VS U b A b
� �1 T , (5)
ãäå A � — îáîáùåííîå îáðàùåíèå Ìóðà–Ïåíðîóçà (ïñåâäîîáðàùåíèå) ìàòðè-
öû A. Ýòî ðåøåíèå äàåò âåêòîð ìèíèìàëüíîé äëèíû ñðåäè âåêòîðîâ, óäîâëåò-
âîðÿþùèõ (2).
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ìåòîäû, îñíîâàííûå íà (5), íàõîäÿò ðåøåíèå çà âðåìÿ O mn( )2 . Ìåòîä SVD
íàèáîëåå âû÷èñëèòåëüíî íàãðóçî÷íûé ñðåäè óïîìÿíóòûõ âûøå (ñ òî÷íîñòüþ äî
ïîñòîÿííûõ ìíîæèòåëåé), íî åãî èñïîëüçîâàíèå ïðåäïî÷òèòåëüíî, åñëè A î÷åíü
ïëîõî îáóñëîâëåíà. Îáîçíà÷èì i-å ñèíãóëÿðíîå çíà÷åíèå A êàê � i ( )A , �1 ( )A
� 2 0( )A � , à ìàêñèìàëüíîå è ìèíèìàëüíîå ñèíãóëÿðíûå çíà÷åíèÿ A — êàê
� �max ( ) ( )A A 1 è � min ( )A . ×èñëî îáóñëîâëåííîñòè A åñòü cond( )A
� �max min( ) / ( )A A . Åñëè cond( )A âåëèêî, ìàòðèöà ïëîõî îáóñëîâëåíà, ÷òî ïîä-
ðàçóìåâàåò ïîòåíöèàëüíî íåóñòîé÷èâîå è íåòî÷íîå ðåøåíèå. Ïðîÿâëåíèåì íå-
óñòîé÷èâîñòè ÿâëÿåòñÿ òîò ôàêò, ÷òî íåçíà÷èòåëüíûå èçìåíåíèÿ â âåêòîðå b (íà-
ïðèìåð, èç-çà øóìà) âûçûâàþò áîëüøèå èçìåíåíèÿ â ðåøåíèè x
è îøèáêà
ðåøåíèÿ, êàê ïðàâèëî, âåëèêà, îñîáåííî ïðè ïîâûøåíèè óðîâíÿ øóìà. Äåéñò-
âèòåëüíî, äëÿ áîëüøèõ cond( )A âåëè÷èíû, îáðàòíûå ñèíãóëÿðíûì çíà÷åíèÿì
â S�1, ñòàíîâÿòñÿ î÷åíü áîëüøèìè, ïîýòîìó çíà÷åíèÿ êîìïîíåíòîâ x
òàêæå áó-
äóò î÷åíü áîëüøèìè, êàê ñëåäóåò èç (3) è (5).
Åñëè â ñïåêòðå ñèíãóëÿðíûõ çíà÷åíèé èìååòñÿ ðåçêèé ïåðåïàä, à ñèíãóëÿð-
íûå çíà÷åíèÿ ïîñëå ïåðåïàäà î÷åíü ìàëû, îíè ìîãóò ðàññìàòðèâàòüñÿ êàê øóìî-
âûå è â íåêîòîðûõ ìåòîäàõ óñòðàíÿþòñÿ ïðèìåíåíèåì ïîðîãà, ÷òî îáåñïå÷èâàåò
ïîâûøåíèå óñòîé÷èâîñòè. Îäíàêî ýòîò ïðèåì íå ðàáîòàåò â äèñêðåòíûõ íåêîð-
ðåêòíûõ çàäà÷àõ, ïîñêîëüêó, êàê îòìå÷àëîñü âî ââåäåíèè, â ðÿäó ñèíãóëÿðíûõ
çíà÷åíèé íåò ðàçðûâîâ è ÷èñëåííûé ðàíã íå îïðåäåëåí.
Êëàññè÷åñêèì ìåòîäîì ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷ ÿâëÿåòñÿ
ðåãóëÿðèçàöèÿ Òèõîíîâà [3, 1]. Çàäà÷à ðåãóëÿðèçàöèè Òèõîíîâà ñòàíäàðòíîãî
âèäà ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì:
x Ax b x
x
reg arg min � �(| | | | | | | | ),2 2 2� (6)
ãäå � — ïàðàìåòð ðåãóëÿðèçàöèè.
Ðåøåíèå (6) ìîæíî ïîëó÷èòü ìåòîäîì ôèëüòðîâàííîãî SVD [1]:
x V U yreg
Tdiag ( / )f i i� , (7)
ãäå f i i i �� � �2 2 2/ ( ) — òàê íàçûâàåìûå ôèëüòðóþùèå ìíîæèòåëè [1].
Îäíîé èç ïðîáëåì ÿâëÿåòñÿ èñïîëüçîâàíèå SVD-ðàçëîæåíèÿ äëÿ A, òàê êàê îíî
èìååò áîëüøóþ âû÷èñëèòåëüíóþ ñëîæíîñòü O mn m n( min , ){ } . Åùå îäíà âàæíàÿ
ïðîáëåìà — âûáîð íàäëåæàùåãî ïàðàìåòðà ðåãóëÿðèçàöèè �. Ýòî òðåáóåò äîïîëíè-
òåëüíûõ âû÷èñëåíèé è íå âñåãäà ïîçâîëÿåò äîñòè÷ü íåîáõîäèìîãî ðåçóëüòàòà,
ò.å. îáåñïå÷èòü óñòîé÷èâîå è òî÷íîå ðåøåíèå x
.
Ïðåäëîæåí ðÿä ìåòîäîâ äëÿ âûáîðà ïàðàìåòðà ðåãóëÿðèçàöèè [1]. Â ìåòîäå
L-êðèâîé [11] ñòðîèòñÿ ãðàôèê | | | |x reg 2 îò | | | |Ax breg �
2
äëÿ äîïóñòèìûõ çíà÷å-
íèé ïàðàìåòðà ðåãóëÿðèçàöèè. Ïðè òàêîì ïðåäñòàâëåíèè L-êðèâàÿ îòðàæàåò êîì-
ïðîìèññ ìåæäó | | | |x reg 2 è | | | |Ax breg �
2
, ÷òî è ÿâëÿåòñÿ ñóùíîñòüþ ðåãóëÿðèçà-
öèè. Äëÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷ L-êðèâàÿ, ïîñòðîåííàÿ â ëîãàðèôìè-
÷åñêîì ìàñøòàáå, ÷àñòî èìååò õàðàêòåðíóþ L-îáðàçíóþ ôîðìó. Âåðòèêàëüíóþ è
ãîðèçîíòàëüíóþ ÷àñòè êðèâîé ðàçäåëÿåò âûðàæåííûé óãîë.  êà÷åñòâå îïòèìàëü-
íîãî âûáèðàåòñÿ ïàðàìåòð ðåãóëÿðèçàöèè, ñîîòâåòñòâóþùèé òî÷êå âáëèçè îò
óãëà L-êðèâîé. Äëÿ äèñêðåòíîãî ïàðàìåòðà ðåãóëÿðèçàöèè óãîë íàõîäèòñÿ êàê
òî÷êà ñ ìàêñèìàëüíîé êðèâèçíîé íà ñïëàéí-àïïðîêñèìàöèè.
Ñîãëàñíî ïðèíöèïó íåâÿçêè [4] ïàðàìåòðû ðåãóëÿðèçàöèè âûáèðàþòñÿ òàê,
÷òîáû íîðìà îñòàòêà äëÿ ðåãóëÿðèçîâàííîãî ðåøåíèÿ óäîâëåòâîðÿëà
| | | | | | | |Ax b dreg � 2 2
, ãäå d — âîçìóùåíèå ïðàâîé ÷àñòè è, ñëåäîâàòåëüíî, òðåáó-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 165
åò îöåíêè | | | |d
2
. Ïðèíöèï íåâÿçêè ðåàëèçóåòñÿ êàê ìèíèìèçàöèÿ â ñìûñëå íàè-
ìåíüøèõ êâàäðàòîâ ñ êâàäðàòè÷íûì îãðàíè÷åíèåì: min| | | |x x� 1 ïðè óñëîâèè
| | | |Ax b� � �, ãäå x1 — íà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿ (ðàâíî íóëþ, åñëè íå çà-
äàíî), � — ïîëîæèòåëüíàÿ êîíñòàíòà. Ïðè íåïðåðûâíîì ïàðàìåòðå ðåãóëÿðèçà-
öèè äëÿ ìèíèìèçàöèè èñïîëüçóåòñÿ ìåòîä Íüþòîíà.
Âûáîð ïàðàìåòðà ðåãóëÿðèçàöèè â ìåòîäå îáîáùåííîé ïåðåêðåñòíîé ïðî-
âåðêè (êðîññ-âàëèäàöèè) [12] îñíîâàí íà òîì, ÷òî çíà÷åíèå ïðîèçâîëüíîãî êîì-
ïîíåíòà bi ïðàâîé ÷àñòè b ìîæíî ñïðîãíîçèðîâàòü ñ ïîìîùüþ ñîîòâåòñòâóþùå-
ãî ðåãóëÿðèçîâàííîãî ðåøåíèÿ. Ïàðàìåòð âûáèðàåòñÿ òàê, ÷òîáû ìèíèìèçèðî-
âàòü | | | | /Ax breg � 2 2D , ãäå D — ýôôåêòèâíîå ÷èñëî ñòåïåíåé ñâîáîäû, êîòîðîå
âû÷èñëÿåòñÿ êàê D m f i
i
� � èëè êàê trace I( )I AA� , ãäå A I — ìàòðèöà, ñ ïî-
ìîùüþ êîòîðîé ïîëó÷àþò ðåãóëÿðèçîâàííîå ðåøåíèå x A breg
I . Çäåñü îøèáêè
â b (âåêòîð àääèòèâíîãî øóìà) ñ÷èòàþòñÿ íåêîððåëèðîâàííûìè ñëó÷àéíûìè
âåëè÷èíàìè ñ íóëåâûì ñðåäíèì è îäèíàêîâîé äèñïåðñèåé.
Óêàçàííûå ìåòîäû íå âñåãäà äàþò óñòîé÷èâûå ðåçóëüòàòû, ïîýòîìó ïðè íåâåð-
íûõ çíà÷åíèÿõ ïàðàìåòðà ðåãóëÿðèçàöèè îøèáêà ðåøåíèÿ ìîæåò áûòü çíà÷èòåëü-
íîé. Â ïîñëåäíåå âðåìÿ ïîÿâèëèñü ðàíäîìèçèðîâàííûå ïîäõîäû, èäåè êîòîðûõ ìî-
ãóò áûòü ïîëåçíû äëÿ ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷. Õîòÿ â ýòèõ ïîäõî-
äàõ ðàíäîìèçàöèÿ íàïðàâëåíà íà óñêîðåíèå âû÷èñëåíèé, åå ìîæíî òàêæå
èñïîëüçîâàòü äëÿ ñòàáèëèçàöèè ðåøåíèÿ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷.
2. ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÀß ÀÏÏÐÎÊÑÈÌÀÖÈß ÍÀÈÌÅÍÜØÈÕ ÊÂÀÄÐÀÒÎÂ
Ïðè áîëüøîé ðàçìåðíîñòè ìàòðè÷íûõ äàííûõ êëàññè÷åñêèå àëãîðèòìû íå âî
âñåõ ñëó÷àÿõ ìîãóò îáåñïå÷èòü ýôôåêòèâíóþ îáðàáîòêó. Òðàäèöèîííûå àëãî-
ðèòìû ïðåäíàçíà÷åíû äëÿ îáðàáîòêè ìàòðèö, ýëåìåíòû êîòîðûõ çàäàíû ñ âû-
ñîêîé òî÷íîñòüþ, ÷òî íå âñåãäà îïðàâäàíî, òàê êàê äàííûå â áîëüøèõ ìàòðè-
öàõ ÷àñòî èçíà÷àëüíî íåòî÷íûå. Êðîìå òîãî, â íåêîòîðûõ ïðèëîæåíèÿõ ïåðå-
äà÷à äàííûõ ìîæåò ñîñòàâëÿòü çíà÷èòåëüíóþ äîëþ îáùèõ âû÷èñëèòåëüíûõ
çàòðàò, ïîýòîìó òðåáóþòñÿ àëãîðèòìû ñ ìåíüøèì êîëè÷åñòâîì ïðîõîäîâ ïî
äàííûì, ïîçâîëÿþùèå èñïîëüçîâàòü ìîùíîñòè íîâûõ ïðîöåññîðíûõ àðõèòåê-
òóð, îïòèìèçèðîâàííûõ ïîä ñïåöèôè÷åñêèå âåêòîðíûå îïåðàöèè. Äëÿ ïðå-
îäîëåíèÿ ýòèõ ïðîáëåì íåäàâíî ïðåäëîæåíû è àêòèâíî ðàçâèâàþòñÿ ïîäõîäû
ê ìàòðè÷íîé îáðàáîòêå ñ èñïîëüçîâàíèåì ðàíäîìèçèðîâàííûõ àëãîðèòìîâ [13].
Ñëåäóåò îòìåòèòü, ÷òî ðàíäîìèçèðîâàííûå àëãîðèòìû, êàê ïîêàçûâàþò îöåíêè
èõ òî÷íîñòè, ÷àñòî ÿâëÿþòñÿ áîëåå òî÷íûìè è íàäåæíûìè, ÷åì äåòåðìèíèðîâàííûå.
Õîòÿ èõ ðåçóëüòàòû íîñÿò âåðîÿòíîñòíûé õàðàêòåð, âåðîÿòíîñòü îøèáêè ìîæåò ðå-
ãóëèðîâàòüñÿ ïóòåì âûáîðà ïàðàìåòðîâ è äîñòèãàòü ìàëûõ çíà÷åíèé (íàïðèìåð, ìå-
íåå 10–15), ñîõðàíÿÿ ïðè ýòîì ïðåèìóùåñòâà ïî âû÷èñëèòåëüíûì çàòðàòàì.
Ðàíäîìèçàöèÿ ðåàëèçóåòñÿ ïóòåì ñëó÷àéíîãî ñýìïëèðîâàíèÿ (âûáîðêè),
ñëó÷àéíîé ïðîåêöèè èëè èõ êîìáèíàöèè [14, 15]. Ïîä ñýìïëèðîâàíèåì çäåñü ïî-
íèìàåòñÿ ïîëó÷åíèå íåêîòîðîãî ñëó÷àéíîãî ïîäìíîæåñòâà ìàòðèöû — îòäåëü-
íûõ ýëåìåíòîâ (êîìïîíåíòîâ, ÿ÷ååê) ëèáî ñòîëáöîâ è ñòðîê â ñîîòâåòñòâèè ñ íå-
êîòîðûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé. Ïðîåöèðîâàíèå — ñëó÷àéíîå ëèíåéíîå
îòîáðàæåíèå (âëîæåíèå), ðåàëèçóåìîå, êàê ïðàâèëî, ñ ïîìîùüþ óìíîæåíèÿ íà
ñëó÷àéíóþ ìàòðèöó, ýëåìåíòû êîòîðîé ãåíåðèðóþòñÿ â ñîîòâåòñòâèè ñ íåêîòî-
ðûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé. Êàê ñýìïëèðîâàíèå, òàê è ïðîåöèðîâàíèå
óìåíüøàþò ðàçìåðíîñòü èñõîäíîé çàäà÷è è ñîîòâåòñòâåííî âû÷èñëèòåëüíóþ
ñëîæíîñòü ïîñëåäóþùåé îáðàáîòêè.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Íà ðàáîòû ïî ðàíäîìèçèðîâàííûì ìàòðè÷íûì àëãîðèòìàì ñóùåñòâåííî ïî-
âëèÿëî íàïðàâëåíèå ñëó÷àéíûõ âëîæåíèé.  [16] ïîêàçàíî, ÷òî ïîïàðíûå åâêëè-
äîâû ðàññòîÿíèÿ ìåæäó òî÷êàìè âî âõîäíîì ïðîñòðàíñòâå ïðèáëèæåííî ñîõðà-
íÿþòñÿ ïðè îòîáðàæåíèè òî÷åê â åâêëèäîâî ïðîñòðàíñòâî ãîðàçäî ìåíüøåé ðàç-
ìåðíîñòè ñ èñïîëüçîâàíèåì ñëó÷àéíîãî ãàóññîâà ïðîåêòîðà. Óêàçàííàÿ è
ïîñëåäóþùèå ðàáîòû çàðîäèëè èäåþ, ÷òî íåêîòîðûå âû÷èñëèòåëüíûå çàäà÷è ìî-
ãóò áûòü ðåøåíû ñ áîëüøåé âû÷èñëèòåëüíîé ýôôåêòèâíîñòüþ, åñëè èõ ïðåäâàðè-
òåëüíî ïåðåâåñòè â ïðîñòðàíñòâî ìåíüøåé ðàçìåðíîñòè. Ýòî áûëî èñïîëüçîâàíî
â ïðèëîæåíèÿõ, òðåáóþùèõ áûñòðîé îöåíêè ñõîäñòâà âåêòîðîâ. Â [17] òàêîé
ïîäõîä âïåðâûå ïðèìåíåí ê ëèíåéíîé àëãåáðå â êîíòåêñòå «ëàòåíòíîãî
ñåìàíòè÷åñêîãî èíäåêñèðîâàíèÿ» íà îñíîâå SVD.
 ðÿäå ðàáîò èçó÷àëñÿ âîïðîñ óìåíüøåíèÿ âû÷èñëèòåëüíûõ çàòðàò íà ðåàëè-
çàöèþ ñàìîãî îòîáðàæåíèÿ.  [18] ïîêàçàíî, ÷òî äèñêðåòíûå ñëó÷àéíûå ìàòðèöû
ñ ýëåìåíòàìè {–1,0,1} äàþò ïî÷òè òàêèå æå õîðîøèå ðåçóëüòàòû, êàê è ãàóññîâû
ìàòðèöû. Â [19, 7] ðàññìîòðåíû ñèëüíî ðàçðåæåííûå (è ïîýòîìó ïîòåíöèàëüíî
«áûñòðûå») äèñêðåòíûå ñëó÷àéíûå ìàòðèöû, îäíàêî ðåçóëüòàòû ýòèõ èññëåäîâà-
íèé íå áûëè ïðèìåíåíû ê ÷èñëåííûì ìåòîäàì ëèíåéíîé àëãåáðû. Áûñòðîå ïðå-
îáðàçîâàíèå Äæîíñîíà–Ëèíäåíøòðàóññà, êîòîðîå ñî÷åòàåò ñêîðîñòü áûñòðîãî
ïðåîáðàçîâàíèÿ Ôóðüå ñî ñâîéñòâàìè âëîæåíèé, èìåþùèìèñÿ ó ãàóññîâîé ìàò-
ðèöû, âûçâàëî ñóùåñòâåííûé èíòåðåñ â äàííîé îáëàñòè.  ÷àñòíîñòè, ïðèìåíå-
íèå ýòîãî ìåòîäà ê àïïðîêñèìàöèè ìàòðèö [20] ïðèâåëî ê ñîçäàíèþ ñàìûõ áûñ-
òðûõ àëãîðèòìîâ, èçâåñòíûõ â íàñòîÿùåå âðåìÿ.
 ðàíäîìèçèðîâàííûõ àëãîðèòìàõ áûñòðîãî ðåøåíèÿ çàäà÷è àïïðîêñèìàöèè ìå-
òîäîì íàèìåíüøèõ êâàäðàòîâ ðàíäîìèçàöèÿ ðàññìàòðèâàåòñÿ êàê óìíîæåíèå âõîäíîé
ìàòðèöû A è âåêòîðà b íà ñïåöèàëüíî ñêîíñòðóèðîâàííóþ, íå çàâèñÿùóþ îò äàííûõ,
ñëó÷àéíóþ ìàòðèöó S (÷àñòî ïîñòðîåííóþ èç íåñêîëüêèõ äðóãèõ ìàòðèö). Òàêèì îá-
ðàçîì, èñõîäíàÿ çàäà÷à íàèìåíüøèõ êâàäðàòîâ (2) çàìåíÿåòñÿ ñëåäóþùåé:
x Sb SAx
x
�arg min| | | |2 . (8)
Ðåøåíèå (8) ìîæåò áûòü ïîëó÷åíî òðàäèöèîííûì äåòåðìèíèðîâàííûì àëãîðèò-
ìîì, íàïðèìåð ñ èñïîëüçîâàíèåì SVD äëÿ âû÷èñëåíèÿ îáîáùåííîé îáðàòíîé ìàòðèöû:
x SA Sb
�( ) . (9)
Ìîãóò ïðèìåíÿòüñÿ òàêæå ñòàíäàðòíûå èòåðàöèîííûå ìåòîäû, íàïðèìåð ìåòîä
ñîïðÿæåííûõ ãðàäèåíòîâ íàä íîðìàëüíûì îñòàòêîì (Conjugate Gradient
Normal Residual).
Äëÿ ðàíäîìèçàöèè çàäà÷è íàèìåíüøèõ êâàäðàòîâ èñïîëüçóþò êàê ñýìïëèðî-
âàíèå [15], òàê è ïðîåöèðîâàíèå [20]. Ãðàíèöû îøèáêè è ñêîðîñòè äëÿ îáîèõ ïîä-
õîäîâ óëó÷øåíû â [10] äëÿ çàäà÷ àïïðîêñèìàöèè íàèìåíüøèõ êâàäðàòîâ â ñëó÷àå
èçáûòî÷íûõ îãðàíè÷åíèé m n�� .  ðàáîòå [21] ïîäîáíûå ïðèåìû ïðèìåíÿëèñü äëÿ
òåîðåòè÷åñêîãî è ýêñïåðèìåíòàëüíîãî àíàëèçà àëãîðèòìîâ ñëó÷àéíîãî ïðîåöèðîâà-
íèÿ ïðè ðåøåíèè ïåðåîïðåäåëåííûõ (m n� ) çàäà÷ íàèìåíüøèõ êâàäðàòîâ. Êðîìå
òîãî, ìåòîä ñýìïëèðîâàíèÿ ðàñïðîñòðàíÿåòñÿ íà ñëó÷àé íåäîîïðåäåëåííîé (m n� )
çàäà÷è íàèìåíüøèõ êâàäðàòîâ [22].
3. ÐÅØÅÍÈÅ ÄÈÑÊÐÅÒÍÛÕ ÍÅÊÎÐÐÅÊÒÍÛÕ ÇÀÄÀ×
ÍÀ ÎÑÍÎÂÅ ÑËÓ×ÀÉÍÛÕ ÏÐÎÅÊÖÈÉ
Ðàññìîòðèì äèñêðåòíóþ íåêîððåêòíóþ çàäà÷ó âèäà
Fx y . (10)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 167
Çäåñü F �� �n n — ìàòðèöà ñ ñèíãóëÿðíûìè çíà÷åíèÿìè � i , ïëàâíî óáûâàþ-
ùèìè äî íóëÿ, è áîëüøèì ÷èñëîì îáóñëîâëåííîñòè (ò.å. ìàòðèöà F ïëîõî
îáóñëîâëåíà è èìååò íåîïðåäåëåííûé ÷èñëåííûé ðàíã). Âåêòîð y ��n èñêà-
æåí àääèòèâíûì øóìîì � ��n : y y �0 �.
Èññëåäîâàíèÿ ðàíäîìèçèðîâàííûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷è íàèìåíüøèõ
êâàäðàòîâ ïðîâåäåíû èõ àâòîðàìè äëÿ ñëó÷àÿ, êîãäà âåêòîð b íå èñêàæåí øóìîì,
ìàòðèöà A õîðîøî îáóñëîâëåíà è èìååò ïîëíûé ðàíã. Èìåííî äëÿ ýòîãî âàðèàí-
òà äîêàçûâàþò (íàïðèìåð, â [10]), ÷òî ðåøåíèå ñ èñïîëüçîâàíèåì ñëó÷àéíîãî
ïðîåöèðîâàíèÿ (9) ñ ðîñòîì k ïðèáëèæàåòñÿ ê ðåøåíèþ ñ ïîìîùüþ îáû÷íîãî
ïñåâäîîáðàùåíèÿ (5). Îäíàêî äëÿ ðàññìàòðèâàåìîãî ñëó÷àÿ äèñêðåòíîé íåêîð-
ðåêòíîé çàäà÷è ðåøåíèå (5) íåóñòîé÷èâî è èìååò íåäîïóñòèìî íèçêóþ òî÷íîñòü.
Ïîýòîìó äëÿ äàííîé çàäà÷è íå òðåáóåòñÿ áëèçîñòè ðåøåíèÿ, ïîëó÷åííîãî
ñ èñïîëüçîâàíèåì ñëó÷àéíîé ïðîåêöèè, ê ðåøåíèþ íà îñíîâå ïñåâäîèíâåðñèè.
Ðàññìîòðèì ïîäõîä ê óñòîé÷èâîìó ðåøåíèþ äèñêðåòíîé íåêîððåêòíîé çàäà-
÷è íà îñíîâå ðàíäîìèçàöèè. Êàê è ïðè ðàíäîìèçèðîâàííîì ðåøåíèè îáû÷íîé çà-
äà÷è íàèìåíüøèõ êâàäðàòîâ (9), óìíîæèì îáå ÷àñòè (10) íà ìàòðèöó G �� �k n ,
k n� , ýëåìåíòû êîòîðîé ÿâëÿþòñÿ ðåàëèçàöèÿìè ñëó÷àéíîé âåëè÷èíû ñ íîðìàëü-
íûì (ãàóññîâûì) ðàñïðåäåëåíèåì ñ íóëåâûì ñðåäíèì è åäèíè÷íîé äèñïåðñèåé.
×èñëî ñòîëáöîâ n ìàòðèöû G îïðåäåëÿåòñÿ ðàçìåðíîñòüþ ìàòðèöû F, ÷èñëî
ñòðîê k àïðèîðíî íåèçâåñòíî. Ïîëó÷àåì
GFx Gy , GF �� �k n , Gy ��k . (11)
Òîãäà çàäà÷à íàèìåíüøèõ êâàäðàòîâ ñ ó÷åòîì ïðîåêöèè çàïèñûâàåòñÿ êàê
x GFx Gy
x
Pr arg min �| | | | 2 , (12)
à åå ðåøåíèå ñ ïðèìåíåíèåì îáû÷íîé ïñåâäîîáðàòíîé ìàòðèöû — â âèäå
x GF GypinPr �( ) . (13)
Òî÷íîñòü ðåøåíèÿ îáðàòíîé çàäà÷è îöåíèì ñ èñïîëüçîâàíèåì îøèáêè e âîñ-
ñòàíîâëåíèÿ èñòèííîãî âåêòîðà x 0 :
e �
| | | | | | | |x x e0 2 2 , (14)
ãäå x
— ïîëó÷åííîå ðåøåíèå, e — âåêòîð îøèáêè ðåøåíèÿ.
Âåêòîð îøèáêè e ìîæíî ïðåäñòàâèòü êàê ñóììó ñìåùåíèÿ è äèñïåð-
ñèè [23]. Âû÷èñëèì èõ ñëåäóþùèì îáðàçîì. Îáîçíà÷èì P îïåðàòîð, ïðåîáðàçó-
þùèé y â x Py
. Òîãäà, ïðèíèìàÿ âî âíèìàíèå, ÷òî y y �0 � è y Fx0 0 , âûðà-
æåíèå äëÿ x
çàïèøåì â âèäå
x P y Py P PFx P
� � �( )0 0 0� � �. (15)
Èñïîëüçóÿ (15), ïîëó÷àåì âûðàæåíèå äëÿ e:
e x x PFx x P PF I x P
� � � � �0 0 0 0� �( ) . (16)
Èòàê,
e e e �1 2 , e1, e 2 ��n , e PF I x1 0 �( ) , e P2 �. (17)
Ñîñòàâëÿþùóþ e1 íàçûâàþò ñìåùåíèåì, e 2 — äèñïåðñèåé.
Ïîñëå ïðîåöèðîâàíèÿ ðàçëîæåíèå ñìåùåíèå-äèñïåðñèÿ âåêòîðà îøèáêè ðå-
øåíèÿ ïðèíèìàåò ñëåäóþùèå ôîðìû. Äëÿ îøèáêè ðåøåíèÿ ìåòîäîì ïðîåöèðî-
âàíèÿ ìîæíî çàïèñàòü
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
e x x P Gy x P G Fx x P GF I x PPr Pr Pr Pr Pr Pr � � � � � �0 0 0 0 0( ) ( )� G� , (18)
ãäå x Pr — ðåøåíèå ïîñëå ïðîåêöèè, PPr — îïåðàòîð, ïðåîáðàçóþùèé Gy
â x Pr : x P GyPr Pr .
Äëÿ ïñåâäîîáðàòíîãî ðåøåíèÿ ïîñëå ïðîåöèðîâàíèÿ èìååì
P C BpinPr
Tdiag ( / )� i is . (19)
Çäåñü B, C, � — ðåçóëüòàò SVD ìàòðèöû GF B C �
T , si diag � — ñèíãóëÿð-
íûå çíà÷åíèÿ (ýëåìåíòû äèàãîíàëüíîé ìàòðèöû �), si ïîäâåðãàþòñÿ ïîðîãîâî-
ìó ïðåîáðàçîâàíèþ:
åñëè � �i i� tresh , 1 , èíà÷å � i 0 ; tresh eps max( , ) (max( ))K N i� , (20)
ãäå îòíîñèòåëüíàÿ òî÷íîñòü ïðåäñòàâëåíèÿ ÷èñëà ñ ïëàâàþùåé òî÷êîé eps( )z —
ïîëîæèòåëüíîå ðàññòîÿíèå îò abs( )z äî ñëåäóþùåãî áîëüøåãî ïî âåëè÷èíå
÷èñëà ñ ïëàâàþùåé òî÷êîé òîé æå òî÷íîñòè, ÷òî è z. Çäåñü ñìåùåíèå è äèñ-
ïåðñèÿ îøèáêè èìåþò âèä
e P GF I x1 0pinPr pinPr �( ) , e P G2pinPr pinPr �; e e e1 2pinPr pinPr pinPr� , (21)
ãäå e pinPr — âåêòîð îøèáêè ðåøåíèÿ äëÿ ïñåâäîîáðàùåíèÿ ñ èñïîëüçîâàíèåì
ñëó÷àéíîé ïðîåêöèè.
Ïñåâäîîáðàòíîå ðåøåíèå, îñíîâàííîå íà QR-ðàçëîæåíèè, ðåàëèçîâàíî ñëå-
äóþùèì îáðàçîì:
x Q F Q yQR
T T �( ) , P Q F QQR
T T �( ) , (22)
ãäå Q ïîëó÷àåòñÿ QR-ðàçëîæåíèåì ìàòðèöû ( )GF QRT ;
e P F I x1 0QR QR �( ) , e P2QR QR �. (23)
Äëÿ ðåøåíèé, ïîëó÷åííûõ ñ ïîìîùüþ ñëó÷àéíîé ïðîåêöèîííîé ìàòðèöû,
ìîæíî ïîñòðîèòü ãðàôèê çàâèñèìîñòè îò ðàçìåðíîñòè k íîðìû ñìåùåíèÿ
e1 1 2 | | | |e è äèñïåðñèè e2 2 2 | | | |e , à òàêæå ñóììàðíîé îøèáêè e �| | | |e e1 2 2
.
Ïðèìåð çàâèñèìîñòåé äëÿ äèñêðåòíîé íåêîððåêòíîé çàäà÷è Phillips [24] è ìåòîäà
ïðîåöèðîâàíèÿ ñëó÷àéíîé ìàòðèöåé G( )k n� ïðè óðîâíÿõ øóìà 1å–3, 1å–5, 1å–7
ïðèâåäåí íà ðèñ.1.
Ïðè âîçðàñòàíèè k | | | |e1 óìåíü-
øàåòñÿ, à | | | |e 2 âîçðàñòàåò, òàê ÷òî
| | | |e e1 2� èìååò ìèíèìóì. Òàêîå ïîâå-
äåíèå ýòèõ çàâèñèìîñòåé õàðàêòåðíî
äëÿ çàäà÷ âûáîðà ìîäåëåé, â êîòîðûõ
ìîäåëü îïòèìàëüíîé ñëîæíîñòè îáåñ-
ïå÷èâàåò ìèíèìóì îøèáêè. Ïîäîáíûé
õàðàêòåð ïîâåäåíèÿ îøèáêè èìåë ìåñ-
òî äëÿ âñåõ èññëåäîâàííûõ íåêîððåê-
òíûõ îáðàòíûõ çàäà÷ ïðè óðîâíå øóìà
âûøå íåêîòîðîãî ìèíèìàëüíîãî.
Òàêèì îáðàçîì, äëÿ ïîëó÷åíèÿ ðå-
øåíèÿ ñ ìèíèìàëüíîé îøèáêîé íåîá-
õîäèìî èñïîëüçîâàòü ñëó÷àéíóþ ïðî-
åêöèîííóþ ìàòðèöó ñ ðàçìåðíîñòüþ k,
áëèçêîé ê îïòèìàëüíîé. Îäíàêî îïðåäåëåíèå îïòèìàëüíîãî çíà÷åíèÿ k ïî ãðàôè-
êàì çàâèñèìîñòè îøèáêè âîññòàíîâëåíèÿ èñòèííîãî ñèãíàëà îò k ïðåäñòàâëÿåò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 169
Ðèñ. 1. Ãðàôèêè çàâèñèìîñòåé îøèáêè ðåøåíèÿ e,
åå ñìåùåíèÿ e1 è äèñïåðñèè e2 îò ðàçìåðíîñòè k
ñëó÷àéíîé ïðîåêöèîííîé ìàòðèöû
e
k
òîëüêî òåîðåòè÷åñêèé èíòåðåñ, òàê êàê âûðàæåíèå (14) âêëþ÷àåò âåêòîð
èñòèííîãî ðåøåíèÿ, íåèçâåñòíûé ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷.
Äëÿ òîãî ÷òîáû âûáðàòü ðàçìåðíîñòü k ïðîåêöèîííîé ìàòðèöû, ïðè êîòîðîé
îøèáêà ðåøåíèÿ áëèçêà ê ìèíèìàëüíîé â ðåàëüíûõ óñëîâèÿõ, ò.å. êîãäà òî÷íîå
ðåøåíèå íåèçâåñòíî, èñïîëüçóåì ðàçëè÷íûå òèïû êðèòåðèåâ âûáîðà. Ïðè ýòîì
ðàçìåðíîñòü k âûáèðàåòñÿ òàêîé, ïðè êîòîðîé êðèòåðèé ïðèíèìàåò íåêîòîðîå
õàðàêòåðíîå çíà÷åíèå (îáû÷íî ìèíèìóì èëè ìàêñèìóì).
Èñïîëüçóåì äâà òèïà êðèòåðèåâ:
— êðèòåðèè, ïðåäëîæåííûå äëÿ âûáîðà ïàðàìåòðîâ ðåãóëÿðèçàöèè Òèõîíî-
âà (ÊÂÏÐ);
— êðèòåðèè âûáîðà ìîäåëè (ÊÂÌ), ïðèìåíÿåìûå äëÿ âûáîðà îïòèìàëüíûõ
ìîäåëåé â îáëàñòè ìàøèííîãî îáó÷åíèÿ (machine learning), èíäóêòèâíîãî îáó÷å-
íèÿ (inductive learning) è àíàëèçà äàííûõ (data mining).
ÊÂÏÐ ñ èñïîëüçîâàíèåì L-êðèâîé, îáîáùåííîé êðîññ-âàëèäàöèè è ïðèíöè-
ïà íåâÿçêè [1, 4, 12] ðàññìîòðåíû â ðàçä. 1; îñîáåííîñòè ïðèìåíåíèÿ ÊÂÌ îïèñà-
íû äàëåå.
3.1. Âûáîð ðàçìåðíîñòè ïðîåêöèîííîé ìàòðèöû ïî ÊÂÌ.  çàäà÷àõ ïî-
ñòðîåíèÿ ìîäåëåé èñïîëüçóåòñÿ ðÿä ïîäõîäîâ, â òîì ÷èñëå ëèíåéíûå ìîäåëè,
íåéðîííûå ñåòè, êëàññèôèêàöèÿ è ðåãðåññèÿ íà îñíîâå äåðåâüåâ, ÿäåðíûå ìåòîäû
è äð. Ïî çàäàííûì äàííûì, îáû÷íî ñîñòîÿùèì èç ïàð âõîä–âûõîä, ñòðîèòñÿ ìî-
äåëü, ñâÿçûâàþùàÿ âõîä è âûõîä. Íåîáõîäèìî âûáðàòü ìîäåëü, áëèçêóþ ê îïòè-
ìàëüíîé äëÿ îïðåäåëåííîãî ïðèëîæåíèÿ.
Ìåòîäû âûáîðà ìîäåëè èñïîëüçóþò ðàçëè÷íûå êðèòåðèè âûáîðà [25–27].
ÊÂÌ ôîðìóëèðóþòñÿ òàê, ÷òîáû àâòîìàòè÷åñêè óìåíüøàòü ñëîæíîñòü ìîäåëè
ñ óâåëè÷åíèåì óðîâíÿ øóìà ïóòåì áàëàíñà ìåæäó ñëîæíîñòüþ ìîäåëè è îøèá-
êîé àïïðîêñèìàöèè. Íà îïòèìàëüíûõ ìîäåëÿõ êðèòåðèè äîñòèãàþò ìèíèìóìà.
ÊÂÌ ðàçðàáîòàíû íà îñíîâå ðàçëè÷íûõ ïðåäïîëîæåíèé, íàïðèìåð ñ èñïîëüçîâà-
íèåì îøèáêè ïðîãíîçèðîâàíèÿ (predictive training error) [26], îøèáêè îáîáùåíèÿ
(generalization error ) [23, 28], èíôîðìàöèîííûõ ñòàòèñòèê (information statistics)
[25], äëèíû îïèñàíèÿ (description length) [29] è äp.  îòëè÷èå îò ÊÂÏÐ, êîòîðûå
ðàçðàáàòûâàëèñü äëÿ ãðàäóàëüíîãî (íå äèñêðåòíîãî) ïàðàìåòðà � ðåãóëÿðèçàöèè
Òèõîíîâà, ÊÂÌ ñîçäàâàëèñü äëÿ ìîäåëåé ñ äèñêðåòíîé ñëîæíîñòüþ (íàïðèìåð,
÷èñëîì áàçèñíûõ ôóíêöèé s).
 íàñòîÿùåé ðàáîòå èññëåäîâàí âûáîð ðàçìåðíîñòè ñëó÷àéíîé ïðîåêöèîí-
íîé ìàòðèöû ñ èñïîëüçîâàíèåì íàèáîëåå èçâåñòíûõ êðèòåðèåâ âûáîðà ìîäåëè:
Cð (Cð Statistic) Ìàëëîóçà [26], AIC (Akaike Information Criterion) Àêàèêå [25],
gMDL (Minimum Description Length) Áèí Þ [27].
Ïóñòü íàáîð äàííûõ DL ïðåäñòàâëåí L ïàðàìè D yL i i i L { }( , ) ,... ,x 1 ,
X �� �L N , y yi i i �0 � , � — ãàóññîâ àääèòèâíûé øóì. Ìîäåëü èìååò âèä
y f w x xT ( ) .
Îøèáêà ïðîãíîçèðîâàíèÿ — ýòî ìåðà îøèáêè ìåæäó îöåíåííûìè è ðåàëü-
íûìè çíà÷åíèÿìè â òî÷êàõ, ñîîòâåòñòâóþùèõ îáðàçöàì îáó÷àþùåé âûáîðêè:
I EPTE
Ttrace � � �� | | | | | | | | ( )By y By y BQB0
2
0 0
2 , (24)
ãäå B X X X X �
s s s s( )T T1 — îòîáðàæåíèå y â îöåíêó ìîäåëüþ (íåçàøóìëåí-
íûõ) y 0 , Q — êîâàðèàöèîííàÿ ìàòðèöà øóìà, X s — äàííûå, ñîîòâåòñòâóþ-
ùèå s N� íåíóëåâûì êîìïîíåíòàì âåêòîðà âåñîâ (ïàðàìåòðîâ) w ìîäåëè
ñëîæíîñòè s, E� — àíñàìáëåâîå óñðåäíåíèå ïî øóìó.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Êðèòåðèé Cp [26] äàåò íåñìåùåííóþ îöåíêó îøèáêè ïðîãíîçèðîâàíèÿ
Cð = RSS �2 2� s, (25)
ãäå RSS — êâàäðàò íîðìû íåâÿçêè y, � 2 — äèñïåðñèÿ øóìà.
Îøèáêà îáîáùåíèÿ åñòü ðàçíîñòü ìåæäó çíà÷åíèåì ôóíêöèîíàëà ñðåäíåãî
ðèñêà äëÿ ïîëó÷åííîãî ðåøåíèÿ f
H L,
è çíà÷åíèåì ôóíêöèîíàëà ñðåäíåãî ðèñêà
äëÿ èñòèííîãî ðåøåíèÿ f 0 [23]:
I I f I fG H L �( ) ( ), 0 , f I fH L
f H
, ( )
�
arg min emp ,
I f V y f x Li i
i
L
emp ( ) ( , ( )) /
�
1
, (26)
ãäå f H L, — ðåøåíèå, ïîëó÷åííîå ñ èñïîëüçîâàíèåì îãðàíè÷åííîé îáó÷àþùåé
âûáîðêè äëèíîé L äëÿ ìîäåëè H (îãðàíè÷åííîé ñëîæíîñòè), I emp — ýìïèðè-
÷åñêèé ðèñê, V ( )� — ôóíêöèÿ ïîòåðü.
Èíôîðìàöèîííûé êðèòåðèé AIC [25] îöåíèâàåò îøèáêó îáîáùåíèÿ ñ òî÷êè
çðåíèÿ èíôîðìàöèîííîé ñòàòèñòèêè. Îí âû÷èñëÿåòñÿ êàê
AIC �2s L ln (RSS), (27)
ãäå L — ÷èñëî íàáëþäåíèé (îáðàçöîâ), s — ÷èñëî ïàðàìåòðîâ.
Êðèòåðèè ìèíèìàëüíîé äëèíû îïèñàíèÿ äëÿ ðåãðåññèè ìîæíî çàïèñàòü
â âèäå
I ssMDL DL DL �( | ) ( )y X , (28)
ãäå DL( | )y X s — äëèíà îïèñàíèÿ y ìîäåëüþ ñëîæíîñòè s, DL( )s — äëèíà îïè-
ñàíèÿ ìîäåëè.
 [27] ïðåäëîæåíû âûðàæåíèÿ äëÿ êðèòåðèÿ gMDL, ìèíèìóì êîòîðîãî ñî-
îòâåòñòâóåò ìèíèìóìó äëèíû îïèñàíèÿ (28):
gMDL log RSS log log � � �0 5 0 5, ( / ( )) , ( ) ( )L L s s F L ïðè R s L2
/ ,
gMDL log logT �0 5 0 5, ( ) , ( )L L Ly y / èíà÷å. (29)
Çäåñü F
s
L s
�
�
y yT RSS
RSS
( ), R — ìíîæåñòâåííûé êîýôôèöèåíò êîððåëÿöèè,
R 2 1 �
RSS
Ty y
, RSS ��| | | |AA y y 2 .
Ïðè ïðîåöèðîâàíèè ñëó÷àéíîé ìàòðèöåé ïðèâåäåííûå âûðàæåíèÿ äëÿ ÊÂÌ
ñîîòâåòñòâóþùèì îáðàçîì ìîäèôèöèðóþòñÿ: â (24)–(29) âìåñòî y, A èñïîëüçó-
þòñÿ Sy, SF.
4. ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÎÅ ÈÑÑËÅÄÎÂÀÍÈÅ
Ýêñïåðèìåíòàëüíîå èññëåäîâàíèå ïðîâåäåíî íà ïðèìåðå èçâåñòíûõ äèñêðåò-
íûõ íåêîððåêòíûõ çàäà÷ Carasso, Phillips, Delves, Baart [24], à òàêæå çàäà÷è
Spectr, âîçíèêàþùåé â àýðî-ãàììà ñúåìêå [2].
4.1. Çàäà÷è. Çàäà÷à Carasso — ðåêîíñòðóêöèÿ âðåìåííîãî ïðîôèëÿ èñòî÷-
íèêà òåïëà íà îñíîâå èçìåðåíèÿ òåìïåðàòóðû ñ ôèêñèðîâàííîãî ðàññòîÿíèÿ.
Îáðàòíîå óðàâíåíèå òåïëîâîãî ïîòîêà ÿâëÿåòñÿ èíòåãðàëüíûì óðàâíåíèåì Âîëü-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 171
òåððû ïåðâîãî ðîäà K x t f t dt g x
a
x
( , ) ( ) ( )� ñ èíòåðâàëîì èíòåãðèðîâàíèÿ [0,1].
ßäðî èìååò âèä
K s t f s t( , ) ( ) � , t t3 2 1 22 1 4/ // ( exp ( / ))� � . (30)
Èíòåãðàëüíîå óðàâíåíèå äèñêðåòèçèðóåòñÿ ìåòîäîì êâàäðàòóð ñ èñïîëüçîâàíè-
åì ïðîñòîé êîëëîêàöèè è ïðàâèëà ñðåäíåé òî÷êè ñ N òî÷êàìè. Êîíñòðóèðóåò-
ñÿ òî÷íîå ðåøåíèå x 0 , è çàòåì y 0 âû÷èñëÿåòñÿ êàê y Fx0 0 , ò.å. â ýòîé çàäà-
÷å Fx 0 òî÷íî ðàâíî y 0 .
Äèñêðåòíîå ïðåäñòàâëåíèå ÿäåð è ïðàâûõ ÷àñòåé äëÿ çàäà÷ Carasso, Phillips,
Delves, Baart ïîëó÷åíî ñ èñïîëüçîâàíèåì ïðîãðàìì Regularization Tools [24].
Çàäà÷à Phillips — ðåøåíèå óðàâíåíèÿ Ôðåäãîëüìà ïåðâîãî ðîäà
K s t f t dt g s
a
b
( , ) ( ) ( )� . Ðåøåíèå f , ÿäðî K, ïðàâàÿ ÷àñòü g èìåþò ñîîòâåòñòâåííî âèä
f t t( ) cos ( / ) �1 3� ïðè | |t � 3, f t( ) 0 ïðè | |t
0 ,
K s t f s t( , ) ( ) � ,
g s s s s( ) ( | | )( , cos ( / )) ( / ) ( | | / ) � � �6 1 0 5 3 9 2 3� � �sin . (31)
Èíòåðâàë èíòåãðèðîâàíèÿ ñîñòàâëÿåò [–6, 6]. Äèñêðåòèçàöèÿ îñóùåñòâëÿåòñÿ
ìåòîäîì Ãàëåðêèíà. Äëÿ ìàòðèöû F âåëè÷èíû m n m n, ( ) äîëæíû áûòü êðàòíû
÷åòûðåì.  ýòîé çàäà÷å Fx 0 íå òî÷íî ðàâíî y 0 .
Çàäà÷à Delves — âû÷èñëåíèå âòîðîé ïðîèçâîäíîé. Îñóùåñòâëÿåòñÿ äèñêðå-
òèçàöèÿ àíàëèòè÷åñêè çàäàííîãî óðàâíåíèÿ Ôðåäãîëüìà ïåðâîãî ðîäà ñ ÿäðîì K,
êîòîðîå ÿâëÿåòñÿ ôóíêöèåé Ãðèíà âòîðîé ïðîèçâîäíîé, ñ ïðàâîé ÷àñòüþ g è ðå-
øåíèåì f :
K s t s t( , ) ( ) �1 ïðè s t� , K s t t s( , ) ( ) �1 ïðè s t
,
g s s s( ) ( ) / �3 6, f t t( ) . (32)
 äàííîé çàäà÷å Fx 0 òî÷íî ðàâíî y 0 .
Çàäà÷à Baart — äèñêðåòèçàöèÿ èñêóññòâåííîãî èíòåãðàëüíîãî óðàâíåíèÿ
Ôðåäãîëüìà ïåðâîãî ðîäà ñ ÿäðîì K è ïðàâîé ÷àñòüþ g, êîòîðûå çàäàíû êàê
K s t s t( , ) exp( cos( )) , g s s s( ) ( ) / 2sin , s�[ , / ]0 2� , t �[ , ]0 � . (33)
Ðåøåíèåì ÿâëÿåòñÿ f t t( ) ( ) sin . Äèñêðåòèçàöèÿ îñóùåñòâëÿåòñÿ ìåòîäîì Ãà-
ëåðêèíà ñ îðòîíîðìàëüíûìè áàçèñíûìè ôóíêöèÿìè. Äëÿ ìàòðèöû F âåëè÷èíû
m n m n, ( ) äîëæíû áûòü ÷åòíûìè.  ýòîé çàäà÷å Fx 0 íå òî÷íî ðàâíî y 0 .
 çàäà÷å Spectr [30, 31] òðåáóåòñÿ, èñïîëüçóÿ ìîäåëüíûå äàííûå ðàäèîàê-
òèâíîãî ìîíèòîðèíãà ïîñðåäñòâîì àýðî-ãàììà ñúåìêè, âîññòàíîâèòü ïîâåðõíîñ-
òíóþ ïëîòíîñòü èñòî÷íèêîâ ðàäèîàêòèâíîñòè. Çíà÷åíèÿ èçìåðåíèé y ïîëó÷åíû
óìíîæåíèåì ñèãíàëà x, ïîäëåæàùåãî âîññòàíîâëåíèþ, íà ìàòðèöó F, êîòîðàÿ ñî-
îòâåòñòâóåò îòêëèêó äåòåêòîðà, íàõîäÿùåãîñÿ íà âûñîòå h m 100 (íà áîðòó àâèà-
íîñèòåëÿ) [2].  ýòîé çàäà÷å Fx 0 òî÷íî ðàâíî y 0 .
Âî âñåõ çàäà÷àõ ìàòðèöà F èìåëà ðàçìåð 200�200, áîëüøîå ÷èñëî îáóñëîâ-
ëåííîñòè ( ( ) / )max mincond F ��� � 1 è ñèíãóëÿðíûå çíà÷åíèÿ, ïëàâíî óáûâàþ-
ùèå äî íóëÿ. Ïðàâàÿ ÷àñòü y 0 èñêàæàëàñü àääèòèâíûì øóìîì ñ ãàóññîâûì ðàñ-
ïðåäåëåíèåì è ðàçëè÷íûìè àìïëèòóäàìè. Ìàòðèöà ñëó÷àéíûõ ïðîåêöèé
G �� �k n , n 200, k n� , — ãàóññîâà ñëó÷àéíàÿ ìàòðèöà ñ ýëåìåíòàìè ñ íóëåâûì
ñðåäíèì è åäèíè÷íîé äèñïåðñèåé.
4.2. Ðåçóëüòàòû. Ïðîâåäåíî ýêñïåðèìåíòàëüíîå ñðàâíåíèå ñëåäóþùèõ ìå-
òîäîâ ðåøåíèÿ óêàçàííûõ äèñêðåòíûõ íåêîððåêòíûõ îáðàòíûõ çàäà÷.
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
1. Ðåøåíèå íà îñíîâå ïñåâäîîáðàùåíèÿ (5),
2. Ðåãóëÿðèçàöèÿ Òèõîíîâà (7) ñ âûáîðîì ïàðàìåòðà ðåãóëÿðèçàöèè � íà
îñíîâå: îáîáùåííîé ïåðåêðåñòíîé ïðîâåðêè (êðîññ-âàëèäàöèè) — GCV
(Genåralized Cross Validation); ïðèíöèïà íåâÿçêè — DSC (Discrepancy); ñ èñïîëü-
çîâàíèåì L-êðèâîé — LC (L Curve).
Ðåøåíèå äëÿ ðåãóëÿðèçàöèè Òèõîíîâà ïîëó÷åíî ñ ïðèìåíåíèåì ïðîãðàìì
Regularization Tools [24].
3. Ïñåâäîîáðàùåíèå (PseudoInverse) ñ ïðîåöèðîâàíèåì ñëó÷àéíîé ìàòðèöåé G (13)
è îðòîãîíàëèçèðîâàííîé ìàòðèöåé Q (22) è âûáîðîì èõ ðàçìåðíîñòåé ñ ïîìîùüþ:
— ÊÂÏÐ íà îñíîâå GCV; DSC; ñ ïðèìåíåíèåì LC;
— ÊÂÌ ñ èñïîëüçîâàíèåì gMDL; Cp; AIC.
Êàê è íà ðèñ. 1, äëÿ âñåõ èññëåäîâàííûõ çàäà÷ è ðåøåíèÿ ïñåâäîîáðàùåíèåì
ñ ïðîåöèðîâàíèåì ñëó÷àéíîé ìàòðèöåé ñóùåñòâóåò äèàïàçîí óðîâíåé øóìà,
â êîòîðîì ïðè íåêîòîðîì çíà÷åíèè k íàáëþäàåòñÿ ìèíèìóì îøèáêè ðåøåíèÿ.
Ñ ïîâûøåíèåì óðîâíÿ øóìà ïîëîæåíèå ìèíèìóìà ñìåùàåòñÿ ê ìåíüøèì çíà÷å-
íèÿì k è ìèíèìàëüíîå çíà÷åíèå îøèáêè óâåëè÷èâàåòñÿ.
Íàïîìíèì, ÷òî â ðåàëüíûõ óñëîâèÿõ êðèâûå çàâèñèìîñòè îøèáêè îò ðàçìåð-
íîñòè k ïðîåêöèîííîé ìàòðèöû íåäîñòóïíû, òàê êàê íåèçâåñòíî èñòèííîå ðåøå-
íèå, ïîýòîìó äëÿ âûáîðà k, ïðè êîòîðîì îøèáêà ðåøåíèÿ áëèçêà ê ìèíèìàëüíîé,
èñïîëüçóåì ÊÂÏÐ (ðàçä. 1) è ÊÂÌ (ðàçä. 3.1). Íà ðèñ. 2 ïðèâåäåíû ïðèìåðû çà-
âèñèìîñòåé îò k çíà÷åíèé íåêîòîðûõ èç ýòèõ êðèòåðèåâ â çàäà÷å Phillips. Äëÿ
âñåõ ýêñïåðèìåíòîâ óðîâåíü øóìà 1å–5; ïðîåöèðîâàíèå îñóùåñòâëÿëîñü ñëó÷àé-
íûìè ìàòðèöàìè G (13) è Q (22). Ìîæíî âèäåòü, ÷òî çíà÷åíèÿ k, ïðè êîòîðûõ
äîñòèãàþòñÿ ìèíèìóìû ðåàëüíîé îøèáêè è êðèòåðèåâ, áëèçêè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 173
Ðèñ. 2. Ãðàôèêè çàâèñèìîñòåé çíà÷åíèé êðèòåðèåâ âûáîðà ìîäåëè (ëåâàÿ îñü Y) è îøèáêè
ðåøåíèÿ e (ïðàâàÿ îñü Y) îò k: AIC (à); gMDL (á); Cp (â); GCV (ã)
k
e
k
e
k
e
k
e
a á
â ã
 òàáë. 1–3 îòðàæåíû ðåçóëüòàòû íåêîòîðûõ ýêñïåðèìåíòîâ â òåðìèíàõ
îøèáêè ðåøåíèÿ. Â òàáë. 1 ïðèâåäåíî ðåøåíèå äèñêðåòíûõ íåêîððåêòíûõ çàäà÷
Carasso, Phillips, Delves, Baart, Spectr äëÿ òðåõ óðîâíåé øóìà nl â y òðàäèöèîííû-
ìè ìåòîäàìè áåç ïðîåöèðîâàíèÿ — ïñåâäîîáðàùåíèåì (PseudoInverse) è ðåãóëÿ-
ðèçàöèåé Òèõîíîâà (Tikhonov) ñ âûáîðîì ïàðàìåòðà ðåãóëÿðèçàöèè ÊÂÏÐ; äàíû
ñðåäíèå çíà÷åíèÿ M (err) è ñðåäíåêâàäðàòè÷íûå îòêëîíåíèÿ (ñ.ê.î.) äëÿ äåñÿòè
ðåàëèçàöèé øóìà â y.
Îáû÷íîå ïñåâäîîáðàùåíèå îáåñïå÷èâàåò ïðèåìëåìóþ îøèáêó ðåøåíèÿ òîëü-
êî ïðè ñàìîì íèçêîì óðîâíå øóìà â íåêîòîðûõ çàäà÷àõ, íî íå ìîæåò èñïîëüçî-
âàòüñÿ âî âñåõ çàäà÷àõ ïðè áîëüøèõ óðîâíÿõ øóìà èç-çà î÷åíü áîëüøîé îøèáêè.
Ïðèìåíåíèå ðåãóëÿðèçàöèè Òèõîíîâà çíà÷èòåëüíî ñíèæàåò îøèáêó ðåøåíèÿ.
Äëÿ çàäà÷ Carasso, Phillips, Delves ñðåäè äåòåðìèíèðîâàííûõ ìåòîäîâ íàè-
ìåíüøóþ îøèáêó ðåøåíèÿ îáåñïå÷èâàåò ðåãóëÿðèçàöèÿ Òèõîíîâà ñ ÊÂÏÐ DSC.
Áëèçêèå ðåçóëüòàòû ó ÊÂÏÐ GCV. Äëÿ çàäà÷è Baart õîðîøèå ðåçóëüòàòû äàåò ðå-
ãóëÿðèçàöèÿ Òèõîíîâà ñ ÊÂÏÐ LC è DSC, à êðèòåðèé GCV ðàáîòàåò ïëîõî. Äëÿ
çàäà÷è Spectr âñå äåòåðìèíèðîâàííûå ìåòîäû ïðè ôèêñèðîâàííîì óðîâíå øóìà
ïîêàçûâàþò ñðàâíèìóþ îøèáêó.
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Çàäà÷à/ìåòîä M(err) ñ.ê.î. M(err) ñ.ê.î. M(err) ñ.ê.î.
Carasso nl=1e–3 nl =1e–5 nl =1e–7
PseudoInverse 1.08E+05 1.11E+04 1190.35 166.09 11.79 2.67
Tikhonov GCV 0.736 0.399 0.098 0.016 0.024 0.002
Tikhonov DSC 0.530 0.046 0.069 0.007 0.023 0.001
Tikhonov LC 9852 31153 125.96 396.33 11.79 2.67
Individual LC H: 98515 L: 0.498 H: 1254 L: 0.529 H: 18.30 L: 8.91
Phillips nl =1e–3 nl =1e–5 nl =1e–7
PseudoInverse 8419 2745 78.22 32.51 0.80 0.17
Tikhonov GCV 0.204 0.452 0.009 0.003 0.0013 0.0002
Tikhonov DSC 0.032 0.004 0.005 0.001 0.0009 0.0001
Tikhonov LC 0.350 0.063 0.881 0.143 0.293 0.088
Individual LC H: 0.448 L: 0.275 H: 1.169 L: 0.703 H: 0.414 L: 0.120
Delves nl =1e–5 nl =1e–6 nl =1e–7
PseudoInverse 32.30 2.00 3.36 0.23 0.34 0.04
Tikhonov GCV 0.149 0.084 0.084 0.006 0.057 0.005
Tikhonov DSC 0.120 0.007 0.082 0.002 0.053 0.002
Tikhonov LC 0.128 0.013 0.145 0.010 0.072 0.005
Individual LC H: 0.152 L: 0.110 H: 0.154 L: 0.120 H: 0.077 L: 0.065
Baart nl =1e–5 nl =1e–7 nl =1e–9
PseudoInverse 1.14E+08 7.04E+07 9.40E+05 5.92E+05 11649 3558
Tikhonov GSV 2.92E+07 9.24E+07 40920 116648 2313 7314
Tikhonov DSC 0.107 0.027 0.064 0.002 0.038 0.001
Tikhonov LC 0.075 0.015 0.063 0.007 0.046 0.013
Individual GCV H: 2.92E+08 L: 0.06 H: 371238 L: 0.061 H: 23131 L: 0.036
Spectrum nl =1e–1 nl =1e–2 nl =1e–6
PseudoInverse 4.68E+12 3.76E+12 5.5E+09 2.82E+09 490117 374641
Tikhonov GCV 107.5 49.02 65.8 20.7 2287 6841
Tikhonov DSC 93.6 6.74 62.86 1.146 22.62 0.2
Tikhonov LC 91.87 4.75 57.9 2.2 23.4 2.25
Individual GCV H: 241 L: 77.1 H: 124 L: 52.9 H: 21741 L: 21.6
Ò à á ë è ö à 1
Äëÿ íåêîòîðûõ ÊÂÏÐ íàáëþäàþòñÿ íåñòàáèëüíûå ðåçóëüòàòû. Ýòî ïðîÿâëÿ-
åòñÿ â òîì, ÷òî ïðè îïðåäåëåííûõ ðåàëèçàöèÿõ øóìà îøèáêà ðåøåíèÿ î÷åíü âå-
ëèêà è ìîæåò ïðèáëèæàòüñÿ ê îøèáêå PseudoInverse. Äëÿ èëëþñòðàöèè â ñòðîêàõ
Individual òàáë. 1 ïðèâåäåíà ìèíèìàëüíàÿ (L) è ìàêñèìàëüíàÿ (H) îøèáêè ðåøå-
íèÿ ñðåäè ðåøåíèé, ïîëó÷åííûõ äëÿ ðàçíûõ ðåàëèçàöèé øóìà.  ÷àñòíîñòè, íå-
ñòàáèëüíûå ðåçóëüòàòû äëÿ ÊÂÏÐ ñ èñïîëüçîâàíèåì L-êðèâîé ñâÿçàíû ñ òåì, ÷òî
ïðîöåäóðà íàõîæäåíèÿ óãëà L-êðèâîé íåòðèâèàëüíà äëÿ òåõ èçìåíåíèé çíà÷åíèé
íåâÿçêè è íîðìû âåêòîðà ðåøåíèÿ, êîòîðûå ðåàëüíî âñòðå÷àþòñÿ âî ìíîãèõ çàäà-
÷àõ. Êëàññè÷åñêèé àëãîðèòì â ðåàëèçàöèè Õàíñåíà [24] ÷àñòî äàåò îøèáêó. Åãî
óëó÷øåíèå îòêðûâàåò ïåðñïåêòèâû ïîâûøåíèÿ ñòàáèëüíîñòè ìåòîäà L-êðèâîé,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 175
Çàäà÷à/
ìåòîä
M(e) ñ.ê.î. M(k) ñ.ê.î. M(e) ñ.ê.î. M(k) ñ.ê.î. M(e) ñ.ê.î. M(k) ñ.ê.î.
Carasso nl =1e–3 nl =1e–5 nl =1e–7
e G 1.43 0.24 12.1 2.23 0.21 0.05 29.5 2.59 0.03 0.063 61.6 4.14
GCV G 3.59 2.86 17.9 5.47 1.35 1.41 49.4 14.2 0.08 0.016 76.5 10.5
DSC G 1.80 0.84 12.4 2.27 0.28 0.13 33.8 5.03 0.04 0.007 65.4 4.97
MDL G 2.14 1.72 14.4 3.34 0.21 0.05 29.9 3.45 0.04 0.007 53.8 3.22
Cp G 1.48 0.27 12.5 1.84 0.21 0.05 29.9 3.45 0.04 0.028 63.3 4.69
AIC G 2.75 2.27 16.3 4.16 0.92 0.97 45.8 12.6 0.05 0.001 70.5 7.01
e Q 0.48 0.07 16.7 1.70 0.08 0.01 34.1 3.14 0.02 0.001 70.7 3.92
GCV Q 0.55 0.14 17.1 1.10 0.09 0.01 36.2 1.62 0.02 0.006 72.4 1.78
DSC Q 1.91 0.28 8.6 0.84 0.34 0.10 24.4 1.71 0.05 0.007 50.4 2.22
MDL Q 0.65 0.15 12.8 2.10 0.10 0.02 28.8 1.23 0.04 0.005 45.0 7.26
Cp Q 0.92 0.16 10.2 1.23 0.10 0.02 28.2 1.14 0.04 0.001 52.7 3.53
AIC Q 0.56 0.11 16.1 1.10 0.08 0.01 35.0 1.63 0.02 0.063 70.2 2.30
Phillips nl =1e–3 nl =1e–5 nl =1e–7
e G 0.13 0.04 9.6 1.17 0.02 0.01 19.7 3.13 0.002 0.000 44.5 3.57
GCV G 0.72 1.34 14.3 6.31 0.25 0.39 44.5 23.1 0.003 0.001 57.2 5.49
DSC G 0.15 0.07 9.5 1.84 0.03 0.02 23.4 5.64 0.002 0.000 45.7 4.30
MDL G 0.17 0.09 11.0 1.94 0.02 0.01 21.3 3.56 0.002 0.000 39.1 3.78
Cp G 0.16 0.08 10.5 1.65 0.03 0.02 23.1 5.95 0.002 0.000 43.9 3.48
AIC G 0.64 1.34 13.3 6.31 0.08 0.10 33.5 11.2 0.003 0.001 54.9 6.24
e Q 0.03 0.00 12.1 1.60 0.005 0.001 24.5 2.37 0.001 0.000 45.6 3.50
GCV Q 0.03 0.01 12.1 0.88 0.006 0.001 24.3 1.89 0.001 0.000 54.7 5.89
DSC Q 0.25 0.11 7.3 0.48 0.030 0.008 14.7 1.25 0.004 0.001 32.1 2.23
MDL Q 0.04 0.02 9.6 1.26 0.007 0.002 18.7 2.21 0.001 0.000 35.8 1.81
Cp Q 0.07 0.02 7.9 0.74 0.009 0.002 17.0 1.76 0.001 0.000 35.4 1.71
AIC Q 0.03 0.00 11.1 0.88 0.005 0.001 23.1 1.91 0.001 0.000 47.9 2.18
Delves nl =1e–5 nl =1e–6 nl =1e–7
e G 0.18 0.03 9.4 2.07 0.12 0.01 23.5 3.47 0.07 0.003 58.3 8.18
GCV G 0.26 0.09 13.6 1.65 0.27 0.11 48.5 11.0 0.09 0.037 80.2 23.4
DSC G 0.19 0.03 7.4 2.32 0.12 0.01 22.5 3.89 0.07 0.002 49.1 4.36
MDL G 0.22 0.06 10.3 3.06 0.13 0.01 23.7 5.12 0.08 0.005 39.4 5.97
Cp G 0.21 0.06 9.5 3.21 0.13 0.01 21.1 5.13 0.07 0.004 44.6 5.91
AIC G 0.23 0.06 12.5 1.65 0.25 0.09 46.0 8.74 0.07 0.005 63.1 7.53
e Q 0.12 0.01 17.5 3.57 0.08 0.005 32.7 4.16 0.05 0.002 77.6 8.13
GCV Q 0.13 0.01 14.9 2.02 0.13 0.04 46.6 4.93 0.06 0.003 67.2 6.32
DSC Q 0.22 0.04 5.1 0.74 0.14 0.01 13.4 1.90 0.08 0.004 34.9 1.79
MDL Q 0.13 0.01 10.6 1.90 0.10 0.01 20.8 3.91 0.08 0.006 34.2 5.98
Cp Q 0.16 0.01 7.0 1.25 0.11 0.01 16.1 2.64 0.07 0.004 35.4 4.35
AIC Q 0.13 0.01 13.9 2.02 0.11 0.01 43.2 3.19 0.06 0.002 62.0 6.20
Ò à á ë è ö à 2
÷òî ìîæåò ïîâûñèòü òî÷íîñòü ðåøåíèÿ, òàê êàê ïðè ïðàâèëüíîì ñðàáàòûâàíèè
ýòîò êðèòåðèé ïîêàçûâàåò ëó÷øèå ðåçóëüòàòû [8, 9]. Íåêîòîðûå øàãè â äàííîì íà-
ïðàâëåíèè ïðåäïðèíÿòû â ðàáîòå [32].
 òàáë. 2 è 3 îòðàæåíû ðåçóëüòàòû äëÿ ðåøåíèÿ ñ ïðîåöèðîâàíèåì íåïîñðåä-
ñòâåííî ñëó÷àéíîé ìàòðèöåé G (13) è ìàòðèöåé Q ïîñëå îðòîãîíàëèçàöèè QR
ðàçëîæåíèåì (22). Ïðèâåäåíû ðåçóëüòàòû (ñðåäíèå è ñ.ê.î.), ïîëó÷åííûå ïðè äå-
ñÿòè ñëó÷àéíûõ ðåàëèçàöèÿõ ïðîåêöèîííûõ ìàòðèö è îäíîé ðåàëèçàöèè øóìà
(òðè óðîâíÿ øóìà â y) äëÿ çàäà÷ Carasso, Phillips, Delves (òàáë. 2) è çàäà÷ Baart,
Spectr (òàáë. 3).
4.3. Àíàëèç ðåçóëüòàòîâ äëÿ ìåòîäîâ ñ ïðîåöèðîâàíèåì. Àíàëèç ðåçóëüòà-
òîâ ïîêàçàë, ÷òî â èññëåäîâàííûõ çàäà÷àõ êà÷åñòâî ðåøåíèÿ ñ ïîìîùüþ ïñåâäîîá-
ðàòíîé ìàòðèöû ïîñëå ïðîåöèðîâàíèÿ è âûáîðà çíà÷åíèÿ k ïî ìèíèìàëüíîìó çíà-
÷åíèþ ñîîòâåòñòâóþùèõ êðèòåðèåâ äîñòèãàåò êà÷åñòâà ðåøåíèÿ ðåãóëÿðèçàöèè
Òèõîíîâà. Ðàññìîòðèì äåòàëüíåå ïîâåäåíèå ðåøåíèÿ äëÿ êîíêðåòíûõ çàäà÷.
Çàäà÷è Carasso, Phillips, Delves. Äëÿ ïðåäëîæåííûõ ïðîåêöèîííûõ ìåòîäîâ
ìèíèìàëüíàÿ îøèáêà, äîñòèãàåìàÿ ïðè ïîëó÷åíèè ðåøåíèÿ ñ ïîìîùüþ Q-ïðîåê-
öèè, íàõîäèòñÿ íà óðîâíå ëó÷øèõ ðåçóëüòàòîâ äåòåðìèíèðîâàííîãî ìåòîäà (îò-
ëè÷èå 5%). Îøèáêà ìåòîäîâ ñ G-ïðîåêöèåé â ñðåäíåì â 1,5–3 ðàçà âûøå, ÷åì ñ Q-ïðî-
åêöèåé, îäíàêî ýòè îøèáêè íà íåñêîëüêî ïîðÿäêîâ ìåíüøå, ÷åì îøèáêà ðåøå-
íèÿ, ïîëó÷åííàÿ ñ ïîìîùüþ ïñåâäîîáðàòíîé ìàòðèöû áåç ïðîåöèðîâàíèÿ.
Äëÿ G-ïðîåêöèè ñðåäè ÊÂÏÐ ëó÷øå ðàáîòàåò êðèòåðèé DSC, êîòîðûé èñ-
ïîëüçóåò àïðèîðíóþ èíôîðìàöèþ îá óðîâíå øóìà â y. Íåïëîõèå ðåçóëüòàòû
äàåò ÊÂÏÐ LC ïðè «ðó÷íîì» îïðåäåëåíèè âåðøèíû óãëà L-êðèâîé. Îäíàêî èç-çà
çíà÷èòåëüíîãî ÷èñëà ñáîåâ ïðè àâòîìàòè÷åñêîì îïðåäåëåíèè óãëà ðåçóëüòàòû ïî
L-êðèâîé íå âêëþ÷åíû â òàáëèöû. Ñðåäè ÊÂÌ ëó÷øèå ðåçóëüòàòû äåìîíñòðèðó-
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Çàäà÷à/
ìåòîä
M(e) ñ.ê.î. M(k) ñ.ê.î. M(e) ñ.ê.î. M(k) ñ.ê.î. M(e) ñ.ê.î. M(k) ñ.ê.î.
Baart nl =1e–5 nl =1e–7 nl =1e–9
e G 0.16 0.04 4.0 0.67 0.07 0.01 5.10 0.32 0.05 0.01 6.60 0.52
MDL G 76.8 170 5.8 1.03 0.11 0.06 5.60 0.52 0.06 0.01 6.40 0.52
Cp G 76.8 170 5.8 1.03 0.11 0.06 5.60 0.52 0.06 0.01 6.40 0.52
AIC G 104 183 5.9 1.10 0.11 0.06 5.70 0.48 0.06 0.01 6.50 0.53
e Q 0.07 0.00 5.0 0.00 0.06 0.00 6.00 0.00 0.04 0.00 7.00 0.00
GCV Q 0.43 0.03 6.0 0.00 0.06 0.00 6.00 0.00 0.04 0.00 7.00 0.00
DSC Q 0.20 0.11 4.0 0.00 0.07 0.02 5.00 0.00 – – – –
MDL Q 0.14 0.02 4.1 0.32 0.07 0.00 5.00 0.00 0.04 0.00 7.00 0.00
Cp Q 0.14 0.00 4.0 0.00 0.07 0.00 5.00 0.00 0.04 0.00 7.00 0.00
AIC Q 0.07 0.00 5.0 0.00 0.06 0.00 6.00 0.00 0.04 0.00 7.00 0.00
Spectr nl =1e–1 nl =1e–2 nl =1e–6
e G 122 12.2 12.3 2.71 64.7 1.27 22.4 1.43 25.1 2.24 33.8 1.14
MDL G 237 238 14.3 2.16 74.2 14.1 24.0 1.89 35.7 24.9 34.2 1.23
Cp G 135 21.3 11.5 2.92 72.4 13.7 23.9 1.96 205 324 35.9 1.97
AIC G 237 238 14.4 2.07 130 115 25.6 2.51 205 324 36.0 1.89
e Q 86.9 5.92 16.3 1.06 57.2 1.34 27.9 0.88 22.2 0.62 35.7 0.67
GCV Q 116 18.2 18.2 0.42 59.7 1.41 26.2 0.63 24.4 3.40 36.6 0.70
DSC Q 133 8.40 7.70 2.06 67.6 2.64 20.1 0.74 27.7 2.08 32.5 0.71
MDL Q 93.1 7.53 14.7 1.49 64.2 1.58 21.7 1.16 23.0 0.87 34.4 0.70
Cp Q 108 11.5 12.1 1.73 64.9 0.07 20.9 0.74 23.2 0.92 34.3 0.67
AIC Q 108 17.1 17.2 0.42 61.0 1.11 25.2 0.63 22.9 2.66 35.4 0.84
Ò à á ë è ö à 3
åò Cp — îíè áëèçêè ê ìèíèìàëüíîé äîñòèæèìîé îøèáêå e äëÿ G-ïðîåêöèè (íà
10–50% õóæå).
Äëÿ Q-ïðîåêöèè è ÊÂÏÐ ýôôåêòèâíåå ðàáîòàåò GCV Q. Ñðåäè ÊÂÌ ëó÷øèå
ðåçóëüòàòû äåìîíñòðèðóåò AIC Q — îíè áëèçêè ê ìèíèìàëüíîé äîñòèæèìîé
îøèáêå äëÿ Q-ïðîåêöèè (îøèáêà AIC — îò 0 äî 20% õóæå e Q) è íåìíîãî ëó÷øå
ðåçóëüòàòîâ GCV.
Çàäà÷è Baart, Spectr. Ñïåöèôèêîé çàäà÷è Baart ÿâëÿþòñÿ ìàëûå îïòèìàëü-
íûå çíà÷åíèÿ k äàæå ïðè ìàëîì óðîâíå øóìà. Äëÿ çàäà÷è Spectr èñïîëüçîâàí
î÷åíü âûñîêèé óðîâåíü øóìà, è àáñîëþòíàÿ îøèáêà ðåøåíèÿ âåëèêà. Ïðè òàêèõ
îñîáåííîñòÿõ ÊÂÏÐ äëÿ G-ïðîåêöèè íóæäàþòñÿ â äîïîëíèòåëüíîé íàñòðîéêå,
ïîýòîìó îíè íå âêëþ÷åíû â òàáë. 3.
 çàäà÷å Baart ïðè nl =1å–5 êðèâûå çàâèñèìîñòè ÊÂÌ îò k î÷åíü «êðóòûå»,
è îøèáêà â îïðåäåëåíèè îïòèìàëüíîãî k äàæå íà 1–2 åäèíèöû ïðèâîäèò ê áîëü-
øîé îøèáêå ðåøåíèÿ äëÿ G-ïðîåêöèè. Ïðè óðîâíÿõ øóìà nl =1å–7, nl =1å–9 âñå
òðè êðèòåðèÿ ðàáîòàþò õîðîøî è ïîêàçûâàþò áëèçêèå çíà÷åíèÿ. Q-ïðîåêöèÿ
óëó÷øàåò ðåçóëüòàòû äëÿ âñåõ êðèòåðèåâ. Äëÿ ÊÂÏÐ ëó÷øèé ðåçóëüòàò äàåò
DSC; äëÿ ÊÂÌ AIC — ðåçóëüòàòû íà óðîâíå äåòåðìèíèðîâàííûõ ìåòîäîâ.
 çàäà÷å Spectr äëÿ G-ïðîåêöèè è ÊÂÌ ýôôåêòèâíûå ðåçóëüòàòû ïîëó÷åíû äëÿ
êðèòåðèÿ Cp. Äëÿ Q-ïðîåêöèè è ÊÂÏÐ ëó÷øèå ðåçóëüòàòû — äëÿ GCV (îò 5 äî
30% õóæå ìèíèìàëüíîé îøèáêè), à äëÿ ÊÂÌ — ïðèìåðíî îäèíàêîâûå ðåçóëüòà-
òû äëÿ âñåõ êðèòåðèåâ, ïðè ìåíüøèõ óðîâíÿõ øóìà — ïîðÿäêà ìèíèìàëüíîé
îøèáêè, ïðè áîëüøèõ — îøèáêà äî 10–20% õóæå ìèíèìàëüíîé.
 öåëîì, äëÿ G-ïðîåêöèè çíà÷åíèÿ k è îøèáêè ðåøåíèÿ, áëèçêèå ê îïòèìàëü-
íûì, äàåò êðèâàÿ äëÿ Cp, à äëÿ Q-ïðîåêöèè — AIC. Ðåçóëüòàòû äëÿ Q-ïðîåêöèé
ëó÷øå, ÷åì äëÿ G-ïðîåêöèé. Ðåçóëüòàòû äëÿ ìåòîäà ðåøåíèÿ ñ ïðîåöèðîâàíèåì
çíà÷èòåëüíî ýôôåêòèâíåå, ÷åì äëÿ òðàäèöèîííîãî ìåòîäà ïñåâäîîáðàùåíèÿ.
 ñëó÷àå, êîãäà âåëèêà îøèáêà ðåøåíèÿ ñ ïðîåöèðîâàíèåì, äîñòèãàåìàÿ ïðè
ìèíèìóìå êðèòåðèÿ, àíàëèç ïîêàçûâàåò, ÷òî ýòî ÷àñòî ïðîèñõîäèò èç-çà íåâåðíîãî
«ñðàáàòûâàíèÿ» êðèòåðèÿ ïðè íåêîòîðîé ðåàëèçàöèè ñëó÷àéíîé ìàòðèöû, êîãäà
âûáðàííîå çíà÷åíèå k çíà÷èòåëüíî îòëè÷àåòñÿ îò îïòèìàëüíîãî (âûáðîñû). Îáû÷-
íî ýòî íàáëþäàåòñÿ äëÿ êðèòåðèåâ, çàâèñèìîñòü êîòîðûõ îò k ïîëîãàÿ, è G-ïðîåê-
öèè, ïðè êîòîðîé ãðàôèê èìååò «èçðåçàííûé» âèä. Íà ðèñ. 3 ýòî ïðîèëëþñòðèðî-
âàíî ïðèìåðàìè çàâèñèìîñòåé ÊÂÌ è ÊÂÏÐ îò k äëÿ G-ïðîåêöèè, ïðè êîòîðûõ
ïîëó÷åíà íàèáîëüøàÿ îøèáêà ðåøåíèÿ äëÿ ðàçíûõ çàäà÷ è óðîâíåé øóìà.
Ïîâûøåíèÿ òî÷íîñòè îïðåäåëåíèÿ îïòèìàëüíîãî k ìîæíî îæèäàòü ïðè ñãëà-
æèâàíèè ãðàôèêîâ è âûáîðå â êà÷åñòâå îïòèìàëüíîãî k çíà÷åíèÿ â ïåðâîì ëî-
êàëüíîì ìèíèìóìå âìåñòî ãëîáàëüíîãî. Òàêèå ìîäèôèêàöèè íåîáõîäèìû òàêæå
äëÿ èíêðåìåíòíûõ ìåòîäîâ îïðåäåëåíèÿ ïñåâäîîïòèìàëüíîãî k. Ïðè Q-ïðîåêöèè
ïðàâàÿ âåòâü ãðàôèêà ñòàíîâèòñÿ áîëåå êðóòîé, à ãðàôèê — áîëåå ïëàâíûì, ÷òî
ïðèâîäèò ê áîëåå òî÷íîìó îïðåäåëåíèþ k è äîñòèæåíèþ ìèíèìàëüíîé îøèáêè.
Íà ðèñ. 3 ïðèâåäåíû çàâèñèìîñòè äëÿ Q-ïðîåêöèé, èëëþñòðèðóþùèå óëó÷-
øåíèå ðåçóëüòàòîâ. Òàê, äëÿ çàäà÷è Phillips è óðîâíÿ øóìà 1å–5 äëÿ ÊÂÏÐ GCV
ïðè G-ïðîåêöèè k =61 è e =0,28 ïðîòèâ èñòèííîãî çíà÷åíèÿ k =21 è e =0,017,
à ïðè Q-ïðîåêöèè k =23 è e =0,0058 â îòëè÷èå îò èñòèííîãî çíà÷åíèÿ k =24 è
e =0,0053 (ðèñ. 3, à); äëÿ øóìà 1å–2 â çàäà÷å Spectr è ÊÂÌ AIC äëÿ G-ïðîåêöèè
k= 68 è e =3,27Å+09 ïðè èñòèííîì çíà÷åíèè k =23 è e =63,4, à äëÿ Q-ïðîåêöèè
k =26 è e =61,17 ïðîòèâ èñòèííîãî k =29 è e =55,45 (ðèñ. 3, á); äëÿ øóìà 1å–3
â çàäà÷å Carasso è ÊÂÌ MDL äëÿ G-ïðîåêöèè k=21 è e =6,87 ïðè èñòèííîì k = 9
è e =1,69, à äëÿ Q-ïðîåêöèè k = 14 è e = 0,55 ïðè èñòèííîì k=16 è e = 0,53
(ðèñ. 3, â); äëÿ øóìà 1å–5 â çàäà÷å Baart è ÊÂÌ Cp ïðè G-ïðîåêöèè k =7 è
e = 60,31 â îòëè÷èå îò èñòèííîãî k =5 è e = 0,086, à ïðè Q-ïðîåêöèè k = 4 è e =
0,14 ïðîòèâ èñòèííîãî çíà÷åíèÿ k= 5 è e = 0,0665 (ðèñ. 3, ã).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 177
4.4. Áûñòðîäåéñòâèå. Íà ðèñ. 4 ïðèâåäåíî âðåìÿ âû÷èñëåíèé äëÿ ðàçëè÷-
íûõ ìåòîäîâ â çàâèñèìîñòè îò k. Êàê è îæèäàëîñü, ðåøåíèå íà îñíîâå ïñåâäîîá-
ðàùåíèÿ áåç ñëó÷àéíîé ïðîåêöèè çàíèìàåò ïîñòîÿííîå è äîâîëüíî áîëüøîå âðå-
ìÿ ïî ñðàâíåíèþ ñ ðåøåíèÿìè ñ èñïîëüçîâàíèåì ñëó÷àéíîé ïðîåêöèè ïðè ìàëûõ
çíà÷åíèÿõ k. Íàïðèìåð, ïðè k =30
âðåìÿ âû÷èñëåíèÿ ñî ñëó÷àéíûì
ïðîåöèðîâàíèåì (~0,003 s äëÿ G-
è Q-ïðîåêöèé) â 20 ðàç ìåíüøå,
÷åì äëÿ ïñåâäîîáðàùåíèÿ áåç ñëó-
÷àéíîãî ïðîåöèðîâàíèÿ (0,06 s).
Óìåíüøåíèå âðåìåíè âû÷èñëåíèÿ
îáúÿñíÿåòñÿ òåì, ÷òî ïîñëå ïðîå-
öèðîâàíèÿ ðàçëîæåíèå ïî ñèíãó-
ëÿðíûì çíà÷åíèÿì îñóùåñòâëÿåò-
ñÿ äëÿ ðåçóëüòèðóþùåé ìàòðèöû
( )n k� , ãäå k ñîñòàâëÿåò ìàëóþ
äîëþ n èñõîäíîé ìàòðèöû F
( )n n� . Ñ óâåëè÷åíèåì óðîâíÿ
øóìà ïîëîæåíèå ìèíèìóìà
îøèáêè ñìåùàåòñÿ â îáëàñòü
ìåíüøèõ çíà÷åíèé k. Ýòî îòðàæà-
åò òîò ôàêò, ÷òî çàâèñèìîñòü ñî-
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ðèñ. 3. Ãðàôèêè çàâèñèìîñòåé çíà÷åíèé îøèáêè e (ïðàâàÿ îñü Y) è êðèòåðèåâ âûáîðà ìîäåëè (ëåâàÿ
îñü Y) îò k äëÿ G-ïðîåêöèè è Q-ïðîåêöèè: Phillips, GCV, øóì 1e–5 (à); Spectr, AIC, 1å–2 (á);
Carasso, gMDL, 1e–3 (â); Baart, Cp, 1å–5 (ã)
k
e
k
e
k
e
k
e
a á
â ã
Ðèñ. 4. Ãðàôèê çàâèñèìîñòè âðåìåíè âû÷èñëåíèé îò
ðàçìåðíîñòè k ñëó÷àéíîé ïðîåêöèîííîé ìàòðèöû: áåç
ïðîåöèðîâàíèÿ (pinv), ñ G-ïðîåöèðîâàíèåì è Q-ïðîå-
öèðîâàíèåì
t
k
ñòàâëÿþùåé ñìåùåíèÿ îøèáêè | | | |e1 îò k ïðàêòè÷åñêè îäèíàêîâà äëÿ âñåõ óðîâ-
íåé øóìà, â òî âðåìÿ êàê ñîñòàâëÿþùàÿ äèñïåðñèè îøèáêè | | | |e
2
âîçðàñòàåò ñ ïî-
âûøåíèåì óðîâíÿ øóìà. Âîçìîæíîñòü âûèãðûøà ïî âðåìåíè óâåëè÷èâàåòñÿ ïðè
áîëåå âûñîêèõ óðîâíÿõ øóìà, êîãäà îïòèìàëüíîå k ìàëî.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåí ïîäõîä ê ðåøåíèþ äèñêðåòíûõ íåêîððåêòíûõ çàäà÷ ñ èñïîëüçîâà-
íèåì ñëó÷àéíûõ ïðîåêöèé.  îòëè÷èå îò ñîâðåìåííûõ ïðîåêöèîííûõ ïîäõî-
äîâ ê ïîâûøåíèþ âû÷èñëèòåëüíîé ýôôåêòèâíîñòè ðåøåíèÿ çàäà÷è íàèìåíü-
øèõ êâàäðàòîâ ñ õîðîøî îáóñëîâëåííîé ìàòðèöåé A è íåçàøóìëåííûì âåêòî-
ðîì ïðàâîé ÷àñòè, â êîòîðûõ òî÷íîñòü ðåøåíèÿ âîçðàñòàåò ïðè óâåëè÷åíèè
ðàçìåðíîñòè ñëó÷àéíîé ïðîåêöèîííîé ìàòðèöû, â ïðåäëàãàåìîì ïîäõîäå èìå-
åòñÿ îïòèìàëüíàÿ ïðîìåæóòî÷íàÿ ðàçìåðíîñòü, ïðè êîòîðîé äîñòèãàåòñÿ ìèíè-
ìóì îøèáêè ðåøåíèÿ.
Ïðè îïòèìàëüíîì k (ìåíüøåé ðàçìåðíîñòè ïðîåêöèîííîé ìàòðèöû) îøèáêà
ðåøåíèÿ ìåòîäîì ïñåâäîîáðàùåíèÿ íà íåñêîëüêî ïîðÿäêîâ ìåíüøå, ÷åì îøèáêà
ðåøåíèÿ ìåòîäîì ïñåâäîîáðàùåíèÿ áåç ïðîåöèðîâàíèÿ, è íàõîäèòñÿ íà óðîâíå
îøèáêè ðåøåíèÿ ìåòîäàìè ðåãóëÿðèçàöèè Òèõîíîâà.
Äëÿ âûáîðà k, áëèçêîãî ê îïòèìàëüíîìó, íà îñíîâå àíàëèçà ïîâåäåíèÿ ñî-
ñòàâëÿþùèõ îøèáêè ðåøåíèÿ — ñìåùåíèÿ è äèñïåðñèè — ïðåäëîæåíî èñïîëü-
çîâàòü äâà òèïà êðèòåðèåâ: êðèòåðèè âûáîðà ïàðàìåòðà ðåãóëÿðèçàöèè Òèõîíîâà
è êðèòåðèè âûáîðà ìîäåëåé.
Ñ óâåëè÷åíèåì óðîâíÿ øóìà âåëè÷èíà îøèáêè ðåøåíèÿ óâåëè÷èâàåòñÿ äëÿ
âñåõ ìåòîäîâ. Îäíàêî äëÿ ïðåäëîæåííîãî ìåòîäà çíà÷åíèå ðàçìåðíîñòè k, ïðè
êîòîðîì äîñòèãàåòñÿ ìèíèìóì îøèáêè, óìåíüøàåòñÿ. Ýòî ñîçäàåò âîçìîæíîñòü
ñîêðàùåíèÿ âû÷èñëèòåëüíûõ çàòðàò íà ïîëó÷åíèå ðåøåíèÿ. Ðàçëîæåíèå ïî ñèí-
ãóëÿðíûì çíà÷åíèÿì SVD äëÿ ïîëó÷åíèÿ ïñåâäîîáðàòíîé ìàòðèöû, ñ ïîìîùüþ
êîòîðîé âû÷èñëÿåòñÿ ðåøåíèå, âûïîëíÿåòñÿ äëÿ ðåçóëüòèðóþùåé ( )n k� -ìàòðè-
öû ïîñëå ïðîåöèðîâàíèÿ. Ïîýòîìó, êîãäà k ñîñòàâëÿåò ìàëóþ äîëþ n, âû÷èñëè-
òåëüíûå çàòðàòû íà SVD óìåíüøàþòñÿ ïî ñðàâíåíèþ ñ çàòðàòàìè äëÿ èñõîäíîé
ìàòðèöû ( )n n� . Âûèãðûø óâåëè÷èâàåòñÿ ïðè áîëüøîì óðîâíå øóìà, êîãäà
îïòèìàëüíîå k ìàëî.
Òàêèì îáðàçîì, èçó÷åíèå è ïðèìåíåíèå ìåòîäîâ ðåøåíèÿ äèñêðåòíûõ íå-
êîððåêòíûõ çàäà÷, èñïîëüçóþùèõ ðåãóëÿðèçàöèþ íà îñíîâå ïñåâäîîáðàùåíèÿ ñî
ñëó÷àéíûì ïðîåöèðîâàíèåì, ÿâëÿåòñÿ ïåðñïåêòèâíûì ïîäõîäîì áëàãîäàðÿ
óìåíüøåíèþ âû÷èñëèòåëüíûõ çàòðàò, à òàêæå óñòîé÷èâîñòè è òî÷íîñòè ðåøåíèÿ.
Íàïðàâëåíèÿ äàëüíåéøèõ èññëåäîâàíèé â ýòîé îáëàñòè:
— ïîäáîð ïàðàìåòðà ðåãóëÿðèçàöèè äëÿ ðåãóëÿðèçàöèè Òèõîíîâà ïî êðèòå-
ðèÿì âûáîðà ìîäåëè;
— ñîçäàíèå ìåòîäîâ âû÷èñëèòåëüíî ýôôåêòèâíîãî âûáîðà îïòèìàëüíîé ðàç-
ìåðíîñòè ïðîåêöèîííîé ìàòðèöû íà îñíîâå àïðèîðíîé èíôîðìàöèè î ðåøåíèè,
íàïðèìåð ãëàäêîñòè ëèáî íåîòðèöàòåëüíîñòè ðåøåíèÿ;
— ðàçðàáîòêà âûñîêîïðîèçâîäèòåëüíîé àïïàðàòíîé ðåàëèçàöèè äëÿ ïðèëî-
æåíèé, òðåáóþùèõ ðåàëüíîãî âðåìåíè îáðàáîòêè, ñ èñïîëüçîâàíèåì ýôôåêòèâ-
íûõ ñèñòîëè÷åñêèõ àðõèòåêòóð.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. H a n s e n P . C . Rank-deficient and discrete ill-posed problems. Numerical aspects of linear
inversion. — Philadelphia: SIAM, 1998. — 247 p.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 179
2. Ç à á ó ë î í î â Þ . Ë . , Ê î ð î ñ ò è ë ü Þ . Ì . , Ð å â ó í î â à Å . Ã . Îïòèìèçàöèÿ ðåøåíèÿ
îáðàòíîé çàäà÷è ïî âîññòàíîâëåíèþ ôóíêöèè ïëîòíîñòè ðàñïðåäåëåíèÿ ïîâåðõíîñòíûõ
çàãðÿçíåíèé // Ñá. íàó÷. òð. ÈÏÌÝ ÍÀÍ Óêðàèíû «Ìîäåëèðîâàíèå è èíôîðìàöèîííûå
òåõíîëîãèè». — 2006. — C. 77–83.
3. Ò è õ î í î â À . Í . , À ð ñ å í è í Â . ß . Ìåòîäû ðåøåíèÿ íåêîððåêòíûõ çàäà÷. — Ì.: Íàóêà,
1979. — 285 ñ.
4. Ì î ð î ç î â Â . À . Ðåãóëÿðíûå ìåòîäû ðåøåíèÿ íåêîððåêòíî ïîñòàâëåííûõ çàäà÷. —
Ì.: Íàóêà, 1987. — 239 ñ.
5. E n g l H . W . , H a n k e M . , N e u b a e r A . Regularization of inverse problems. — Dordrecht:
Kluwer Acad. Publ., 2000. — 321 p.
6. Ì è ñ ó í î È . Ñ . , Ð à ÷ ê î â ñ ê è é Ä . À . , Ñ ë è ï ÷ å í ê î Ñ . Â . Âåêòîðíûå è
ðàñïðåäåëåííûå ïðåäñòàâëåíèÿ, îòðàæàþùèå ìåðó ñåìàíòè÷åñêîé ñâÿçè ñëîâ // Ìàò. ìàøèíû
è ñèñòåìû. — 2005. — ¹ 3. — Ñ. 50–67.
7. Ð à ÷ ê î â ñ ê è é Ä . À . , Ì è ñ ó í î È . Ñ . , Ñ ë è ï ÷ å í ê î Ñ . Â . Ðàíäîìèçèðîâàííûå
ïðîåêöèîííûå ìåòîäû ôîðìèðîâàíèÿ áèíàðíûõ ðàçðåæåííûõ âåêòîðíûõ ïðåäñòàâëåíèé //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 1. — Ñ. 176–188.
8. Ð å â ó í î â à Å . à . , Ð à ÷ ê î â ñ ê è é Ä . À . Ïîâûøåíèå òî÷íîñòè ðåøåíèÿ îáðàòíîé çàäà÷è
ñ èñïîëüçîâàíèåì ñëó÷àéíûõ ïðîåêöèé // 16-th Intern. Conf. Knowledge-Dialogue-Solution. —
2009. — 10. — P. 95–102.
9. Ð å â ó í î â à Å . à . Èññëåäîâàíèå ñîñòàâëÿþùèõ îøèáêè äëÿ ðåøåíèÿ îáðàòíîé çàäà÷è
ñ èñïîëüçîâàíèåì ñëó÷àéíûõ ïðîåêöèé // Ìàò. ìàøèíû è ñèñòåìû. — 2010. — ¹ 4. —
Ñ. 33–42.
10. D r i n e a s P . , M a h o n e y M . W . , M u t h u k r i s h n a n S . , S a r l o s T . Faster least squares
approximation: Tech. Rep. // arXiv: 0710.1435. — 2007. — 21 p.
11. H a n s e n P . C . , O ’ L e a r y D . P . The use of L-curve in the regularization of discrete ill-posed
problems // SIAM J. Sci. Comput. — 1993. — 14. — P. 1487–1503.
12. G o l u b G . H . , H e a t h M . , W a h b a G . Generalised cross-validation as a method for choosing
a good ridge parameter. Technometrics. — 1979. — 21(2). — P. 215–223.
13. H a l k o N . , M a r t i n s s o n P . G . , T r o p p J . A . Finding structure with randomness:
Stochastic algorithms for constructing approximate matrix decompositions // ACM Rep. Caltech. —
2009. — N 5. — P. 1–82.
14. B o u t s i d i s C . , D r i n e a s P . , M a h o n e y M . W . An improved approximation algorithm for
the column subset selection problem // STOC’09: Proc. 41st Ann. ACM Symp. Theory of
Computing. — 2009. — P. 968–977.
15. D r i n e a s P . , M a h o n e y M . W . , M u t h u k r i s h n a n S . Sampling algorithms for l2
regression and applications // Proc. of the 17th ACM-SIAM Symp. on Discrete Algorithms (SODA).
— 2006. — P. 1127–1136.
16. J o h n s o n W . B . , L i n d e n s t r a u s s J . Extensions of Lipschitz mappings into a Hilbert space
// Contemporary Mathematics. — 1984. — 26. — P. 189–206.
17. P a p a d i m i t r i o u C . H . , R a g h a v a n P . , T a m a k i H . , V e m p a l a S . Latent semantic
indexing: A probabilistic analysis // J. Comput. System Sci. — 2000. — 61. — P. 217–235.
18. A c h l i o p t a s D . Database-friendly random projections: Johnson–Lindenstrauss with binary coins
// Ibid. — 2003. — 66(4). — Ð. 671–687.
19. L i P . , H a s t i e T . J . , C h u r c h K . W . Very sparse random projections // 12th ACM SIGKDD
Intern. Conf. on Knowledge discovery and data mining. — Philadelphia: ACM Press, 2006. —
P. 287–296.
20. S a r l o s T . Improved approximation algorithms for large matrices via random projections // Proc.
of the 47th Annual IEEE Symp. on Foundations of Computer Sci. — 2006. — P. 143–152.
21. R o k h l i n V . , T y g e r t M . A fast randomized algorithm for overdetermined linear least-squares
regression // PNAS. — 2008. — 105(36). — P. 13212–13217.
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
22. T y g e r t M . A fast algorithm for computing minimal-norm solutions to underdetermined systems
of linear equations: Tech. rep. N09-48 // arXiv:0905.4745. — May 2009. — 13 p.
23. N i y o g i P . , G i r o s i F . On the relationship between generalization error, hypothesis complexity
and sample complexity for radial basis functions // Neural Comput. — 1996. — 8. — P. 819–842.
24. H a n s e n P . C . Regularization tools: A Matlab package for analysis and solution of discrete
ill-posed problems // Numer. Algorithms. — 1994. — 6. — P. 1–35.
25. A k a i k e H . A new look at the statistical model identification // IEEE Trans. Automatic Control.
— 1974. — 19, N 6. — P. 716–723.
26. M a l l o w s C . L . Some comments on Cp // Technometrics. — 1973. — 15, N 4. — P. 661–675.
27. H a n s e n M . , Y u B . Model selection and minimum description length principle // J. Amer.
Statist. Assoc. — 2001. — 96. — P. 746–774.
28. S u g i y a m a M . , O g a w a H . Subspace information criterion for model selection // Neural
Comput. — 2001. — 13, N 8. — P. 1863–1889.
29. R i s s a n e n J . Lectures on statistical modeling theory. — Tampere: Univ. of Technology, 2002.
— P. 1–65. (http://www.cs.tut.fi/~rissanen/)
30. R a c h k o v s k i j D . A . , R e v u n o v a E . G . Intelligent gamma-ray data processing for
environmental monitoring // Intelligent Data Processing in Global Monitoring for Environment and
Security. — Kiev–Sofia: ITHEA, 2011. — P. 136–157.
31. Ç à á ó ë î í î â Þ . Ë . , Ë è ñ è ÷ å í ê î à .  . , Ð å â ó í î â à Å . à . Ñòîõàñòè÷åñêàÿ
ðåãóëÿðèçàöèÿ îáðàòíîé çàäà÷è âîññòàíîâëåíèÿ ïàðàìåòðîâ ïîëÿ ðàäèîàêòèâíîñòè ïî äàííûì
àýðî-ãàììà ñúåìêè // Ñá. íàó÷. òð. ÈÏÌÝ ÍÀÍ Óêðàèíû «Ïðîáëåìû ìîäåëèðîâàíèÿ â
ýíåðãåòèêå». — 2009. — Âûï. 52. — Ñ. 89–96.
32. B e l g e M . , K i l m e r M . E . , M i l l e r E . L . Efficient determination of multiple regularization
parameters in a generalized L-curve framework // Inverse Problems. — 2002. — 18. —
P. 1161–1183.
Ïîñòóïèëà 14.07.2010
|
| id | nasplib_isofts_kiev_ua-123456789-84136 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:34:58Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рачковский, Д.А. Ревунова, Е.Г. 2015-07-03T09:30:15Z 2015-07-03T09:30:15Z 2012 Рандомизированный метод решения дискретных некорректных задач / Д.А. Рачковский, Е.Г. Ревунова // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 163-181. — Бібліогр.: 32 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84136 004.942 + 623.454.862 Запропоновано підхід до сталого рішення дискретних некоректних задач на основі комбінації випадкового проектування погано обумовленої початкової матриці з невизначеним чисельним рангом і псевдообернення результуючої матриці. Для вибору розмірності проекційної матриці пропонується використовувати критерії вибору моделі і параметра регуляризації. Наведено результати експериментального дослідження на відомих прикладах дискретних некоректних задач. Помилка рішення близька до помилки регуляризації Тихонова, однак скорочення розмірності матриць (завдяки проекції) сприяє зменшенню обчислювальних витрат, особливо при високому рівні шуму. An approach is proposed to the stable solution of discrete ill-posed problems, based on a combination of random projection of the initial ill-conditioned matrix with ill-defined numerical rank and pseudo-inversion of the resultant matrix. To select the dimension of the projection matrix, we propose to use selection criteria for the model and regularization parameter. The results of experimental studies on the well-known examples of discrete ill-posed problems are given. The solution error is close to the Tikhonov regularization error however, reducing the matrix dimension due to the projection reduces the computational costs, especially at high noise levels. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Рандомизированный метод решения дискретных некорректных задач Рандомізований метод розв’язання дискретних некоректних задач Randomized method for solving discrete ill-posed problems Article published earlier |
| spellingShingle | Рандомизированный метод решения дискретных некорректных задач Рачковский, Д.А. Ревунова, Е.Г. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title | Рандомизированный метод решения дискретных некорректных задач |
| title_alt | Рандомізований метод розв’язання дискретних некоректних задач Randomized method for solving discrete ill-posed problems |
| title_full | Рандомизированный метод решения дискретных некорректных задач |
| title_fullStr | Рандомизированный метод решения дискретных некорректных задач |
| title_full_unstemmed | Рандомизированный метод решения дискретных некорректных задач |
| title_short | Рандомизированный метод решения дискретных некорректных задач |
| title_sort | рандомизированный метод решения дискретных некорректных задач |
| topic | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84136 |
| work_keys_str_mv | AT račkovskiida randomizirovannyimetodrešeniâdiskretnyhnekorrektnyhzadač AT revunovaeg randomizirovannyimetodrešeniâdiskretnyhnekorrektnyhzadač AT račkovskiida randomízovaniimetodrozvâzannâdiskretnihnekorektnihzadač AT revunovaeg randomízovaniimetodrozvâzannâdiskretnihnekorektnihzadač AT račkovskiida randomizedmethodforsolvingdiscreteillposedproblems AT revunovaeg randomizedmethodforsolvingdiscreteillposedproblems |