Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений
Досліджуються властивості рандомізованих бінарних векторних представлень з регульованою часткою ненульових компонентів, які формуються з вхідних векторів проекцією випадкової матриці з тернарними елементами {–1, 0, +1}. Проаналізовано точність оцінювання мір схожості–відмінності вихідних векторів, щ...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84026 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 175-187. — Бібліогр.: 25 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84026 |
|---|---|
| record_format |
dspace |
| spelling |
Рачковский, Д.А. Мисуно, И.С. Слипченко, С.В. 2015-07-02T08:34:29Z 2015-07-02T08:34:29Z 2012 Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 175-187. — Бібліогр.: 25 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84026 004.22 + 004.93’11 Досліджуються властивості рандомізованих бінарних векторних представлень з регульованою часткою ненульових компонентів, які формуються з вхідних векторів проекцією випадкової матриці з тернарними елементами {–1, 0, +1}. Проаналізовано точність оцінювання мір схожості–відмінності вихідних векторів, що мають формат із плаваючою комою, за вихідними бінарними векторами. Отримані векторні представлення можуть використовуватися для обчислювальної ефективної обробки замість великих масивів вхідних багатовимірних векторів у застосуваннях, пов’язаних з пошуком, класифікацією, асоціативною пам’яттю та ін. We investigate the properties of randomized binary vector representations with adjustable sparseness formed from the input vectors by projecting them using a random matrix with ternary elements {–1, 0, +1}. We analyze the accuracy of estimating the measures of similarity-difference of the source vectors having a floating-point format by the output binary vectors. Those vector representations can be used for an efficient processing of large volumes of input multidimensional vectors in applications related to search, classification, associative memory, etc. Д.А. Рачковский выражает благодарность А.А. Фролову и И.П. Муравьеву за плодотворные обсуждения. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений Рандомізовані проекційні методи формування бінарних розріджених векторних представлень Randomized projective methods for construction of binary sparse vector representations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| spellingShingle |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений Рачковский, Д.А. Мисуно, И.С. Слипченко, С.В. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title_short |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| title_full |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| title_fullStr |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| title_full_unstemmed |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| title_sort |
рандомизированные проекционные методы формирования бинарных разреженных векторных представлений |
| author |
Рачковский, Д.А. Мисуно, И.С. Слипченко, С.В. |
| author_facet |
Рачковский, Д.А. Мисуно, И.С. Слипченко, С.В. |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Рандомізовані проекційні методи формування бінарних розріджених векторних представлень Randomized projective methods for construction of binary sparse vector representations |
| description |
Досліджуються властивості рандомізованих бінарних векторних представлень з регульованою часткою ненульових компонентів, які формуються з вхідних векторів проекцією випадкової матриці з тернарними елементами {–1, 0, +1}. Проаналізовано точність оцінювання мір схожості–відмінності вихідних векторів, що мають формат із плаваючою комою, за вихідними бінарними векторами. Отримані векторні представлення можуть використовуватися для обчислювальної ефективної обробки замість великих масивів вхідних багатовимірних векторів у застосуваннях, пов’язаних з пошуком, класифікацією, асоціативною пам’яттю та ін.
We investigate the properties of randomized binary vector representations with adjustable sparseness formed from the input vectors by projecting them using a random matrix with ternary elements {–1, 0, +1}. We analyze the accuracy of estimating the measures of similarity-difference of the source vectors having a floating-point format by the output binary vectors. Those vector representations can be used for an efficient processing of large volumes of input multidimensional vectors in applications related to search, classification, associative memory, etc.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84026 |
| citation_txt |
Рандомизированные проекционные методы формирования бинарных разреженных векторных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 175-187. — Бібліогр.: 25 назв. — рос. |
| work_keys_str_mv |
AT račkovskiida randomizirovannyeproekcionnyemetodyformirovaniâbinarnyhrazrežennyhvektornyhpredstavlenii AT misunois randomizirovannyeproekcionnyemetodyformirovaniâbinarnyhrazrežennyhvektornyhpredstavlenii AT slipčenkosv randomizirovannyeproekcionnyemetodyformirovaniâbinarnyhrazrežennyhvektornyhpredstavlenii AT račkovskiida randomízovaníproekcíinímetodiformuvannâbínarnihrozrídženihvektornihpredstavlenʹ AT misunois randomízovaníproekcíinímetodiformuvannâbínarnihrozrídženihvektornihpredstavlenʹ AT slipčenkosv randomízovaníproekcíinímetodiformuvannâbínarnihrozrídženihvektornihpredstavlenʹ AT račkovskiida randomizedprojectivemethodsforconstructionofbinarysparsevectorrepresentations AT misunois randomizedprojectivemethodsforconstructionofbinarysparsevectorrepresentations AT slipčenkosv randomizedprojectivemethodsforconstructionofbinarysparsevectorrepresentations |
| first_indexed |
2025-11-26T00:17:42Z |
| last_indexed |
2025-11-26T00:17:42Z |
| _version_ |
1850599255977230336 |
| fulltext |
Ä.À. ÐÀ×ÊÎÂÑÊÈÉ, È.Ñ. ÌÈÑÓÍÎ, Ñ.Â. ÑËÈÏ×ÅÍÊÎ
ÓÄÊ 004.22 + 004.93’11 ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÏÐÎÅÊÖÈÎÍÍÛÅ
ÌÅÒÎÄÛ ÔÎÐÌÈÐÎÂÀÍÈß ÁÈÍÀÐÍÛÕ
ÐÀÇÐÅÆÅÍÍÛÕ ÂÅÊÒÎÐÍÛÕ ÏÐÅÄÑÒÀÂËÅÍÈÉ
Êëþ÷åâûå ñëîâà: cëó÷àéíûå ïðîåêöèè, âåêòîðíûå ïðåäñòàâëåíèÿ, ðàçðåæåí-
íûå áèíàðíûå ïðåäñòàâëåíèÿ, ðàñïðåäåëåííûå ïðåäñòàâëåíèÿ, ýôôåêòèâíàÿ
îöåíêà ñõîäñòâà.
ÂÂÅÄÅÍÈÅ. ÑËÓ×ÀÉÍÛÅ ÏÐÎÅÊÖÈÈ ÂÅÊÒÎÐÍÎÉ ÈÍÔÎÐÌÀÖÈÈ
Ìíîãèå òèïû èíôîðìàöèè ìîãóò áûòü ïðåäñòàâëåíû â âèäå ìàòðèö èëè òàá-
ëèö. Íàïðèìåð, äëÿ ïîèñêà èëè êëàññèôèêàöèè ìàññèâû äîêóìåíòîâ ÷àñòî
ðàññìàòðèâàþò êàê ìàòðèöû äîêóìåíòû-ñëîâà [1, 2] (ñòðîêè — äîêóìåíòû,
ñòîëáöû — ñëîâà, ýëåìåíòû ìàòðèöû — çíà÷åíèÿ íåêîòîðîé ôóíêöèè ÷àñòîòû
âñòðå÷àåìîñòè ñëîâ â äîêóìåíòàõ). Ýòó æå èíôîðìàöèþ ìîæíî ðàññìàòðèâàòü
êàê íàáîð âåêòîðîâ èëè òî÷åê â ìíîãîìåðíîì ïðîñòðàíñòâå. Ðàçìåðíîñòü ïðî-
ñòðàíñòâà — ÷èñëî êîîðäèíàò (äëÿ äàííîãî ïðèìåðà ÷èñëî ñëîâ), à êàæäàÿ
òî÷êà ñîîòâåòñòâóåò îáúåêòó (äîêóìåíòó). Êîîðäèíàòû ïðîñòðàíñòâà — êîìïî-
íåíòû âåêòîðà èëè ïðèçíàêè.
Ðàçìåðíîñòü ïðîñòðàíñòâà ìîæåò ñîñòàâëÿòü ñîòíè òûñÿ÷ è ìèëëèîíû (íà-
ïðèìåð, ÷èñëî ñëîâ â ñëîâàðå), à ÷èñëî òî÷åê — ìèëëèîíû è ìèëëèàðäû (÷èñëî
äîêóìåíòîâ, íàïðèìåð, âåá-ñòðàíèö Èíòåðíåò). Ýòî îáóñëîâëèâàåò öåëåñîîáðàç-
íîñòü ïðåîáðàçîâàíèÿ èíôîðìàöèîííûõ ìàññèâîâ áîëüøîé ðàçìåðíîñòè òàêèì
îáðàçîì, ÷òîáû îáúåêòû ñîõðàíèëèñü, íî ïîâûñèëàñü ýôôåêòèâíîñòü èõ îáðàáîò-
êè è/èëè õðàíåíèÿ. Ïðåîáðàçîâàíèå ìîæåò áûòü ðåàëèçîâàíî ïåðåõîäîì â ïðî-
ñòðàíñòâî ñ ñîîòâåòñòâóþùèìè ñâîéñòâàìè — ìåíüøåé ðàçìåðíîñòè, ÷åì èñõîä-
íîå, ñ âû÷èñëèòåëüíî áîëåå ýôôåêòèâíûìè îïåðàöèÿìè îáðàáîòêè, ëèáî
â ïðîñòðàíñòâî, äëÿ êîòîðîãî ñóùåñòâóþò ýôôåêòèâíûå ìåòîäû îáðàáîòêè.
Ìíîãèå ìåòîäû è àëãîðèòìû èíôîðìàöèîííîãî ïîèñêà, êëàññèôèêàöèè, êëàñ-
òåðèçàöèè, àïïðîêñèìàöèè, îáó÷åíèÿ è ðàññóæäåíèé íà îñíîâå ïðèìåðîâ, àññîöèà-
òèâíîé ïàìÿòè è äð. èñïîëüçóþò ìåðû ðàçëè÷èÿ è ñõîäñòâà âåêòîðîâ, òàêèå êàê
ðàññòîÿíèå, ñêàëÿðíîå ïðîèçâåäåíèå, êîñèíóñ óãëà, îòíîøåíèå ðàññòîÿíèé è óãëîâ
è äð. Òàê, øèðîêî èñïîëüçóåìûå ëèíåéíûå ìîäåëè îñíîâàíû íà ñêàëÿðíîì ïðîèç-
âåäåíèè, ìåòîä áëèæàéøåãî ñîñåäà èñïîëüçóåò ðàññòîÿíèÿ è ò.ä. Òàêèì ìåòîäàì è
àëãîðèòìàì äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ïîëåçíî îïåðèðîâàòü ñ ïðåîáðàçîâàí-
íûìè âåêòîðíûìè ïðåäñòàâëåíèÿìè è ïîëó÷àòü ðåçóëüòàòû, ñîãëàñóþùèåñÿ ñ ðå-
çóëüòàòàìè â èñõîäíîì ìíîãîìåðíîì âåêòîðíîì ïðîñòðàíñòâå.
Êîíñòðóèðîâàíèå è ðåàëèçàöèÿ òàêîãî ïðåîáðàçîâàíèÿ ñâÿçàíû ñ îïðåäåëåí-
íûìè òðóäíîñòÿìè. Íàïðèìåð, ðàñïðîñòðàíåííûå ìåòîäû ïðåîáðàçîâàíèÿ íà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 175
© Ä.À. Ðà÷êîâñêèé, È.Ñ. Ìèñóíî, Ñ.Â. Ñëèï÷åíêî, 2012
îñíîâå àíàëèçà ãëàâíûõ êîìïîíåíòîâ PCA (Principal Component Analysis) èëè
ðàçëîæåíèÿ ïî ñèíãóëÿðíûì çíà÷åíèÿì SVD (Singular Value Decomposition) íå
ïðåäíàçíà÷åíû äëÿ îöåíèâàíèÿ ìåð ñõîäñòâà è ðàçëè÷èÿ èñõîäíûõ âåêòîðîâ.
Âîïðîñû ñîêðàùåíèÿ ðàçìåðíîñòè âåêòîðíûõ ïðåäñòàâëåíèé, ïðîäóöèðóþùåãî
âåêòîðû ñ íóæíûìè ñâîéñòâàìè, èññëåäóþòñÿ â ðàìêàõ íåéðîñåòåâîãî ïîäõîäà
ðàñïðåäåëåííûõ ïðåäñòàâëåíèé [2–8], à òàêæå â îáëàñòè ñëó÷àéíûõ ïðîåêöèé
[9–12]. Çäåñü ïîäõîä ê ïðåîáðàçîâàíèþ, êîòîðûé ñîõðàíÿåò èëè ïîçâîëÿåò îöåíè-
âàòü ðàññòîÿíèÿ è óãëû, çàêëþ÷àåòñÿ â ïðèìåíåíèè ñïåöèàëüíî ñêîíñòðóèðîâàí-
íîé ïðîåêöèîííîé ìàòðèöû R( )A N� . Èñõîäíûé ìàññèâ äàííûõ ïðåäñòàâëåí
â âèäå âõîäíîé ìàòðèöû X( )L A� , ãäå A — ÷èñëî àòðèáóòîâ â âåêòîðå, L — ÷èñëî
âåêòîðîâ. Ðåçóëüòàò ïðåîáðàçîâàíèÿ — ñïðîåöèðîâàííàÿ ìàòðèöà Y XR� —
èìååò ðàçìåðíîñòü L N� . Âûõîäíàÿ ìàòðèöà Z , êîòîðàÿ èñïîëüçóåòñÿ
ïîñëåäóþùèìè ìåòîäàìè îáðàáîòêè, ïîëó÷àåòñÿ ïðåîáðàçîâàíèåì Y: Z Y� f ( ) ,
â ÷àñòíîì ñëó÷àå Z Y� .
 ðàáîòå [9] â êà÷åñòâå ïðîåêöèîííîé ìàòðèöû áûëî ïðåäëîæåíî èñïîëüçî-
âàòü ñëó÷àéíóþ ãàóññîâó ìàòðèöó R (ýëåìåíòû ìàòðèöû — ðåàëèçàöèè ñëó÷àé-
íîé ãàóññîâîé âåëè÷èíû ñ íóëåâûì ñðåäíèì è åäèíè÷íîé äèñïåðñèåé �( , )01 ). Ïî
ðåçóëüòàòàì ïðîåöèðîâàíèÿ âõîäíîãî ìàññèâà ñ ïîìîùüþ òàêîé ìàòðèöû ìîæíî
îöåíèòü ðàññòîÿíèÿ ìåæäó èñõîäíûìè âåêòîðàìè: âûõîäíûå âåêòîðû
y R x� T N/ õîðîøî ñîõðàíÿþò ïîïàðíûå åâêëèäîâû ðàññòîÿíèÿ ìåæäó âåêòî-
ðàìè x âî âõîäíîì ïðîñòðàíñòâå ïðè N A�� : E d{ }| | | |y y1 2
2� � ,
D d N{ }| | | | /y y1 2
2 22� � , ãäå E{} — ìàòåìàòè÷åñêîå îæèäàíèå, D{} — äèñïåð-
ñèÿ, d � �| | | |y y1 2
2 . Äëÿ ñêàëÿðíûõ ïðîèçâåäåíèé â [13] ïîêàçàíî, ÷òî
D m m N{ }( , ) /v v1 2 1 22� , à â [14] — ÷òî äëÿ ñêàëÿðíîãî ïðîèçâåäåíèÿ
( , )x x1 2 � a: E a{ }( , )y y1 2 � , D m m a N{ }( , ) ( ) /y y1 2 1 2
2� � , ãäå m m1 2, —
êâàäðàòû l2-íîðì x x1 2, .
Ðàñïðåäåëåíèÿ y m Ni1 1
1 201,
/~ ( , )( / )� , | | | | ~ /y y1 2
2 2� �
N
d N , ãäå �
N
2 —
ñëó÷àéíàÿ ïåðåìåííàÿ ñ N ñòåïåíÿìè ñâîáîäû è ðàñïðåäåëåíèåì õè-êâàäðàò [10].
Àíàëèç «õâîñòîâ» ðàñïðåäåëåíèÿ õè-êâàäðàò ïîçâîëÿåò íàéòè ðàçìåðíîñòü N ,
äëÿ êîòîðîé äëÿ ëþáîé ïàðû âåêòîðîâ èç L ñ çàäàííîé âåðîÿòíîñòüþ è òî÷íîñòüþ
( )| | | | | | | | ( )| | | | .1 11 2
2
1 2
2
1 2
2� � � � � � �� �x x y y x x
Ê íåäîñòàòêàì ïðåîáðàçîâàíèÿ ãàóññîâîé ïðîåêöèîííîé ìàòðèöû îòíîñÿòñÿ:
— íåîáõîäèìîñòü ãåíåðàöèè áîëüøîãî ÷èñëà ( )A N� ãàóññîâûõ ñëó÷àéíûõ
âåëè÷èí, êîòîðûå ïðåäñòàâèìû ÷èñëàìè ñ ïëàâàþùåé çàïÿòîé;
— íåîáõîäèìîñòü óìíîæåíèÿ èñõîäíîé ìàòðèöû íà ïðîåêöèîííóþ, ÷òî òðå-
áóåò áîëüøèõ âû÷èñëèòåëüíûõ çàòðàò äëÿ ìàòðèö áîëüøîãî ðàçìåðà.
Êîíêðåòíûé âèä (îäèíàêîâîãî è íåçàâèñèìîãî) ðàñïðåäåëåíèÿ ýëåìåíòîâ
ïðîåêöèîííîé ìàòðèöû R â íåêîòîðîé ñòåïåíè âëèÿåò íà îøèáêè àïïðîêñèìà-
öèè ðàññòîÿíèé è ãîðàçäî ñèëüíåå — íà âû÷èñëèòåëüíóþ ñëîæíîñòü ïðîåöèðîâà-
íèÿ. Âû÷èñëèòåëüíàÿ ñëîæíîñòü ïðîåöèðîâàíèÿ çàâèñèò îò âèäà ýëåìåíòîâ R
(äëÿ äåéñòâèòåëüíûõ òðåáóåòñÿ îïåðàöèÿ óìíîæåíèÿ ñ ïëàâàþùåé òî÷êîé, äëÿ
äèñêðåòíûõ {– 1,0, + 1} — òîëüêî ñëîæåíèå), à òàêæå îò ðàçðåæåííîñòè R (äëÿ
ðàçðåæåííîé R — ñ áîëüøîé äîëåé íóëåâûõ ýëåìåíòîâ — ìîæíî îáðàáàòûâàòü
òîëüêî íåíóëåâûå ýëåìåíòû, ÷òî çíà÷èòåëüíî ñíèæàåò âû÷èñëèòåëüíóþ ñëîæ-
íîñòü ïðîåöèðîâàíèÿ). Äëÿ ïðåîäîëåíèÿ íåäîñòàòêîâ ãàóññîâîé ïðîåêöèîííîé
ìàòðèöû â [11] ïðåäëàãàåòñÿ èñïîëüçîâàòü ïðîåêöèîííûå ìàòðèöû ñ ýëåìåíòàìè
{– 1,0, + 1}, êîòîðûå ãåíåðèðóþòñÿ c îïðåäåëåííûìè è íå áëèçêèìè ê íóëþ âåðî-
ÿòíîñòÿìè. Òàêèå ñëó÷àéíûå ïðîåêöèè ñ âåðîÿòíîñòÿìè q ýëåìåíòîâ rij ìàòðèöû
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
R (q1 äëÿ ýëåìåíòîâ 1, q0 äëÿ 0, q�1 äëÿ – 1)
r s
q s
q s
q s
ij � �
�
� �
� �
�
�
�
�
{
1 1 2
0 1 1
1 1 2
1
0
1
, / ,
, / ,
, /
(1)
ïðè 1 3� �s òàêæå õîðîøî ñîõðàíÿþò ðàññòîÿíèÿ. Äëÿ s � 3 ýòî ïîçâîëÿåò â
òðè ðàçà ïîâûñèòü ñêîðîñòü âû÷èñëåíèé.
 [2, 8] ïðîâîäèëèñü èññëåäîâàíèÿ ïîâåäåíèÿ êîíòåêñòíûõ âåêòîðîâ, ïîëó-
÷åííûõ ñ ïîìîùüþ ðàçðåæåííîé ìàòðèöû R ñ î÷åíü ìàëûìè âåðîÿòíîñòÿìè ýëå-
ìåíòîâ { }�1 è { + 1 }, â çàäà÷àõ ïîèñêà è îöåíêè ñåìàíòè÷åñêîé áëèçîñòè è ïîëó-
÷åíû ðåçóëüòàòû, ñîïîñòàâèìûå ïî êà÷åñòâó ñ ðåçóëüòàòàìè áåç ïðîåöèðîâàíèÿ,
íî ïðè ñóùåñòâåííî ìåíüøåì âðåìåíè îáðàáîòêè. Â [14] ïîêàçàíî, ÷òî ñâîéñòâà
ïðîåêöèé ñ s q A A A� � �1/ / è äàæå c s A A� / log , ãäå q — äîëÿ íåíóëåâûõ
ýëåìåíòîâ R , àíàëîãè÷íû ñâîéñòâàì ïðîåêöèé ñ s �1è s � 3 [11] è ñâîéñòâàì íîð-
ìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ ïðîåêöèé [9]. Ðàñïðåäåëåíèÿ è äèñïåðñèè
ñïðîåöèðîâàííûõ äàííûõ áûñòðî àñèìïòîòè÷åñêè ñõîäÿòñÿ ê âàðèàíòó ñëó÷àé-
íûõ ïðîåêöèé ñ ãàóññîâîé R. Ñêîðîñòü ñõîäèìîñòè â òåðìèíàõ ñ.ê.î.: O s A( / ) ,
÷òî äëÿ s A� äàåò O A( / )1 4 è äëÿ áîëüøèõ A ïðèâîäèò ê ìàëîé ïîòåðå òî÷íîñòè
ïî ñðàâíåíèþ ñ ïðîåöèðîâàíèåì ãàóññîâîé R, à òàêæå äàåò âîçìîæíîñòü ïîëüçî-
âàòüñÿ ðåçóëüòàòàìè àíàëèçà ãàóññîâîé R — ëåììîé Johnson–Lindenstrauss [9] è
ò.ï. Äëÿ òàêîé ñêîðîñòè ñõîäèìîñòè ðàñïðåäåëåíèé òðåáóåòñÿ îãðàíè÷åííûé
òðåòèé ìîìåíò êîìïîíåíòîâ âõîäíûõ âåêòîðîâ.
Äëÿ î÷åíü ðàçðåæåííîé ïðîåêöèîííîé ìàòðèöû äîïîëíèòåëüíî ñíèæàþòñÿ
âû÷èñëèòåëüíûå çàòðàòû íà ôîðìèðîâàíèå è ïàìÿòü äëÿ õðàíåíèÿ çà ñ÷åò îòñóò-
ñòâèÿ íåîáõîäèìîñòè ãåíåðàöèè è õðàíåíèÿ ÷èñåë ñ ïëàâàþùåé çàïÿòîé. Ýòî
óïðîùàåò óìíîæåíèå èñõîäíîé ìàòðèöû íà ïðîåêöèîííóþ. Îäíàêî ïîñëå ïðîå-
öèðîâàíèÿ âåêòîðû èìåþò ôîðìàò ñ ïëàâàþùåé òî÷êîé. Êðîìå òîãî, â îáùåì
ñëó÷àå âñå çíà÷åíèÿ êîìïîíåíòà âåêòîðà íå ðàâíû íóëþ, ò.å. âûõîäíûå âåêòîðû
íå ÿâëÿþòñÿ ðàçðåæåííûìè. Ýòî äåëàåò îïåðàöèè íàä òàêèìè âåêòîðàìè âû÷èñ-
ëèòåëüíî ñëîæíûìè äëÿ ïîñëåäóþùèõ ìåòîäîâ è àëãîðèòìîâ. Ïîýòîìó
ïåðñïåêòèâíîå íàïðàâëåíèå äàëüíåéøåãî ïîâûøåíèÿ âû÷èñëèòåëüíîé
ýôôåêòèâíîñòè — ôîðìèðîâàíèå áèíàðíûõ âûõîäíûõ âåêòîðîâ.
 [12] ïðåäëàãàåòñÿ òðàíñôîðìèðîâàòü âûõîäíûå âåêòîðû ïóòåì îïåðàöèè
âçÿòèÿ çíàêà sign() ýëåìåíòîâ òðàíñôîðìèðîâàííîé ìàòðèöû Y. Ýòî äàåò âûõîä-
íûå áèíàðíûå âåêòîðû ñ êîìïîíåíòàìè { }01, . Ïîêàçàíî [15,12], ÷òî äëÿ òàêèõ
âåêòîðîâ âåðîÿòíîñòü
p z zi i( ( ) ( )) /, ,sign sign1 2 1� � � � �, (2)
ãäå z zi i1 2, ,, — êîìïîíåíòû âûõîäíûõ âåêòîðîâ z1è z2 , � — óãîë ìåæäó x1è x 2 .
Ïîëó÷åííûå áèíàðíûå âåêòîðû, îäíàêî, ÿâëÿþòñÿ íåðàçðåæåííûìè, ïëîò-
íûìè — âåðîÿòíîñòü åäèíè÷íîãî êîìïîíåíòà p zi( ) ~ .�1 0 5. Õîòÿ îáðàáîòêà òà-
êèõ áèíàðíûõ âåêòîðîâ âû÷èñëèòåëüíî áîëåå ïðîñòàÿ, ÷åì âåêòîðîâ êîìïî-
íåíòîâ ñ ïëàâàþùåé çàïÿòîé, îíè íå ïðèìåíèìû äëÿ ðÿäà ìåòîäîâ è àëãîðèòìîâ,
êîòîðûå ðàáîòàþò òîëüêî ñ áèíàðíûìè ðàçðåæåííûìè âåêòîðàìè, ò.å. ñ âåêòîðà-
ìè, â êîòîðûõ âåðîÿòíîñòü íåíóëåâîãî (åäèíè÷íîãî) êîìïîíåíòà p� 05. . Ê òàêî-
ìó êëàññó îòíîñÿòñÿ, íàïðèìåð, ìåòîäû îáðàáîòêè áèíàðíûõ ðàñïðåäåëåííûõ
ïðåäñòàâëåíèé â àññîöèàòèâíî-ïðîåêòèâíûõ íåéðîííûõ ñåòÿõ [3, 16–19],
ðàñïðåäåëåííàÿ àññîöèàòèâíàÿ ïàìÿòü ìàòðè÷íîãî òèïà [20].
 ðàáîòå [2] ýëåìåíòû ìàòðèöû Y (ðåçóëüòàòà ïðîåöèðîâàíèÿ) ïîäâåðãàþòñÿ
òðàíñôîðìàöèè — ïîðîãîâîé îïåðàöèè ñ äâóìÿ ïîðîãàìè. Â ðåçóëüòàòå ôîðìè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 177
ðóåòñÿ âûõîäíàÿ òåðíàðíàÿ ìàòðèöà Z ñ ýëåìåíòàìè {– 1,0, + 1}. Âîïðîñû êîëè-
÷åñòâåííîãî îöåíèâàíèÿ ñõîäñòâ è ðàçëè÷èé èñõîäíûõ âåêòîðîâ ïî òàêèì
ðåçóëüòèðóþùèì âåêòîðàì íå ðàññìàòðèâàëèñü.
Òàêèì îáðàçîì, äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ðåøåíèÿ íà îñíîâå âåêòîð-
íî-ìàòðè÷íûõ îïåðàöèé çàäà÷ ïîèñêà, ñðàâíåíèÿ, êëàññèôèêàöèè è äðóãîé îáðà-
áîòêè áîëüøèõ ìàññèâîâ èíôîðìàöèè, ïðåäñòàâëåííûõ â âèäå âåêòîðîâ áîëüøîé
ðàçìåðíîñòè, àêòóàëüíûìè ÿâëÿþòñÿ ðàçðàáîòêà, èññëåäîâàíèå è àíàëèç ìåòîäîâ
ïðåîáðàçîâàíèÿ òàêèõ âåêòîðîâ ñëó÷àéíûì ïðîåöèðîâàíèåì.  íàñòîÿùåé ñòàòüå
ðàññìàòðèâàþòñÿ âîïðîñû ôîðìèðîâàíèÿ áèíàðíûõ âåêòîðîâ ñ ðåãóëèðóåìîé äî-
ëåé íåíóëåâûõ êîìïîíåíòîâ, âû÷èñëèòåëüíàÿ ýôôåêòèâíîñòü èõ ïîëó÷åíèÿ,
à òàêæå èññëåäóþòñÿ èõ ñâîéñòâà, ïîçâîëÿþùèå îöåíèòü õàðàêòåðèñòèêè
ñõîäñòâà–ðàçëè÷èÿ èñõîäíûõ âåêòîðîâ.
1. ÔÎÐÌÈÐÎÂÀÍÈÅ ÁÈÍÀÐÍÛÕ ÂÅÊÒÎÐÎÂ È ÎÖÅÍÈÂÀÍÈÅ ÓÃËÀ
ÌÅÆÄÓ ÂÕÎÄÍÛÌÈ ÂÅÊÒÎÐÀÌÈ
Äàííûå î íåëîêàëüíîì ïðåäñòàâëåíèè èíôîðìàöèè â ìîçãå ïðèâåëè ê èäåå
ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ èíôîðìàöèè — ôîðìå âåêòîðíîãî ïðåäñòàâëå-
íèÿ, ãäå êàæäûé îáúåêò åñòü ñîâîêóïíîñòü êîìïîíåíòîâ âåêòîðà. Â òî æå âðå-
ìÿ äëÿ ðàñïðåäåëåííûõ ïðåäñòàâëåíèé ñåìàíòèêà îòäåëüíûõ êîìïîíåíòîâ âåê-
òîðà íå èìååò çíà÷åíèÿ. Âàæíî, ÷òî ñõîäíûì îáúåêòàì ñîîòâåòñòâóþò ñõîä-
íûå ðàñïðåäåëåííûå ïðåäñòàâëåíèÿ.  êà÷åñòâå ìåð ñõîäñòâà èñïîëüçóþòñÿ
òàêèå ìåðû ñõîäñòâà âåêòîðîâ, êàê ñêàëÿðíîå ïðîèçâåäåíèå èëè êîñèíóñ óãëà.
Áóäåì íàçûâàòü êîäâåêòîðàìè ôîðìó ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ èíôîð-
ìàöèè ñî ñâîéñòâàìè áèíàðíîñòè (êîìïîíåíòû âåêòîðîâ {0, 1}) è ðàçðåæåí-
íîñòè (äîëÿ íåíóëåâûõ êîìïîíåíòîâ êîäâåêòîðà ìàëà).
Äëÿ ôîðìèðîâàíèÿ êîäâåêòîðîâ y ñ êîìïîíåíòàìè {0, 1} áóäåì èñïîëüçî-
âàòü äâóõñòóïåí÷àòóþ ïðîöåäóðó, âêëþ÷àþùóþ ýòàï èçìåíåíèÿ ðàçìåðíîñòè èñ-
õîäíûõ âåêòîðîâ x ïóòåì èõ ïðîåöèðîâàíèÿ âî âòîðè÷íîå ïðîñòðàíñòâî ïîñðåä-
ñòâîì óìíîæåíèÿ íà ìàòðèöó R: y x R� T , à òàêæå ýòàï ïðèìåíåíèÿ ïîðîãîâûõ
îïåðàöèé ê ðåçóëüòàòó óìíîæåíèÿ y.
 êà÷åñòâå ïðîåêöèîííîé ìàòðèöû R áóäåì èñïîëüçîâàòü R( )A N� , ýëåìåíòû
êîòîðîé — ñëó÷àéíî ðàñïîëîæåííûå ýëåìåíòû èç ìíîæåñòâà {– 1,0, + 1}. Äëÿ ïîâû-
øåíèÿ âû÷èñëèòåëüíîé ýôôåêòèâíîñòè ïðîåöèðîâàíèÿ îñîáåííî èíòåðåñåí âàðèàíò
ðàçðåæåííîé (ñ ìàëîé äîëåé íåíóëåâûõ ýëåìåíòîâ) ïðîåêöèîííîé ìàòðèöû R.
Êàæäîìó èç A èçìåðåíèé âõîäíîãî ïðîñòðàíñòâà ïîñòàâëåí â ñîîòâåòñòâèå
N -ìåðíûé âåêòîð (ñòðîêà R). Ïðè ðàçìåðíîñòè âåêòîðîâ-ñòðîê R N A� ðàçìåð-
íîñòü y ìåíüøå, ÷åì x. Âåêòîð y ÿâëÿåòñÿ âåêòîðîì ñ êîìïîíåíòàìè — äåéñòâè-
òåëüíûìè ÷èñëàìè, ïðåäñòàâèìûìè â ôîðìàòå ñ ïëàâàþùåé çàïÿòîé.
Íà âòîðîì ýòàïå ïðîöåäóðû ïðèìåíåíèåì ïîðîãîâûõ îïåðàöèé ê êîìïîíåí-
òàì y ôîðìèðóåòñÿ áèíàðíûé êîäâåêòîð z (T — âåêòîð ïîðîãîâ):
z T y� ( ), (3)
z j �1 ïðè y Tj j
1 0, èíà÷å z j � 0, j N�1, ..., . (4)
Äëÿ T j � 0 ïîëó÷àåì z ñ âåðîÿòíîñòüþ åäèíè÷íîãî êîìïîíåíòà ìåíåå 0.5:
ð z j( ) .� �1 05. Âåëè÷èíà T j îáåñïå÷èâàåò çàäàííóþ âåðîÿòíîñòü åäèíè÷íîãî çíà-
÷åíèÿ â êîìïîíåíòå z j . Èññëåäóåì ñëó÷àé, êîãäà â êà÷åñòâå T j èñïîëüçóåòñÿ åäè-
íûé äëÿ âñåõ j ïîðîã T , êîòîðûé îáåñïå÷èâàåò çàäàííóþ âåðîÿòíîñòü íàëè÷èÿ
åäèíè÷íîãî êîìïîíåíòà â âåêòîðå z . Äëÿ âû÷èñëèòåëüíî ýôôåêòèâíîé îáðàáîò-
êè, à òàêæå äëÿ ðàáîòû ðÿäà ìåòîäîâ è àëãîðèòìîâ òðåáóþòñÿ ðàçðåæåííûå
áèíàðíûå êîäâåêòîðû z .
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ðàññìîòðèì ñïîñîá îöåíêè óãëà ìåæäó âõîäíûìè âåêòîðàìè x ïî êîäâåêòî-
ðàì z . Äëÿ R , ãäå âåðîÿòíîñòü 1 è �1 ðàâíà q / 2, ìàòåìàòè÷åñêîå îæèäàíèå
E r xkj k{ } � 0 è äèñïåðñèÿ
D r x E r x pxkj k kj k k
{ } { }� �( )2 2 . (5)
Îáîçíà÷èì y r xkj
k
k� � , | | | |x — l2-íîðìà x. Òîãäà
D y D r x p skj k
k A
{ } { }� � �
�
�
1
2 2
,...,
| | | | | | | | /x x . (6)
 êà÷åñòâå ñëó÷àéíîé ïåðåìåííîé ðàññìîòðèì y j , ïîëó÷åííóþ èç èñõîäíîé
íîðìèðîâàíèåì
y sj / (| | | |/ )x . (7)
Ðàñïðåäåëåíèå y áûñòðî ñõîäèòñÿ ê ãàóññîâîìó ñ íóëåâûì ñðåäíèì è åäè-
íè÷íîé äèñïåðñèåé, ïîýòîìó çíà÷åíèå ïîðîãà t îïðåäåëÿåò âåðîÿòíîñòü åäèíè÷-
íîãî êîìïîíåíòà p( )z âûõîäíîãî êîäâåêòîðà z êàê
p p y t e dy tp
y
t
p
p
( ) ( ) ( )/z � � � � ��
�
�
1
2
1
2 2
�
� , (8)
ãäå � — ôóíêöèÿ íîðìàëüíîãî ðàñïðåäåëåíèÿ.
 [14] ïîêàçàíî, ÷òî ñëó÷àéíûå ïåðåìåííûå ( , ), ,y yj j1 2 èìåþò ñîâìåñòíîå
íîðìàëüíîå ðàñïðåäåëåíèå ñ íóëåâûìè ñðåäíèìè. Äëÿ íàøåãî ñëó÷àÿ íîðìèðî-
âàííûõ y êîððåëÿöèÿ y j1, è y j2, ðàâíà cos( )� , ãäå � — óãîë ìåæäó âõîäíûìè âåê-
òîðàìè x1 è x 2 . Ïîýòîìó âåðîÿòíîñòü ñîâïàäåíèÿ åäèíè÷íûõ êîìïîíåíòîâ
z j1 1, � è z j2 1, � â êîäâåêòîðàõ z1è z2ïîñëå áèíàðèçàöèè y1 ñ ïîðîãîì t1 è y 2
ñ ïîðîãîì t2 ìîæíî îïðåäåëèòü êàê ðåçóëüòàò âû÷èñëåíèÿ èíòåãðàëà îò äâóìåð-
íîãî ãàóññîâà ðàñïðåäåëåíèÿ:
p z z t t p y t y tj j j j( , , , ) ( , | ), , , ,|1 2 1 2 1 1 2 21 1� � � � � �� �
�
�
�
� �
�
��
��
1
2 1 2
2
2 1
1
2
1 2 2
2
2
21
� �
�
�
( )
( )
cos
cos
cose
y y y y
tt
dy dy1 2 .
(9)
Äëÿ óïðîùåíèÿ çàïèñè âûðàæåíèé áóäåì èñïîëüçîâàòü îáîçíà÷åíèÿ z aj1, � ,
z bj2, � , à òàêæå îïóñêàòü � è îòäåëÿòü t çàïÿòîé, òàê ÷òî p z zj j( ,, , |1 21 1� �
�, , ) ( , , , )t t p a b t t1 2 1 21 1� � � .
Çíà÷åíèÿ (9), ïîëó÷åííûå ÷èñ-
ëåííûì èíòåãðèðîâàíèåì ñ èñïîëü-
çîâàíèåì MatLab äëÿ çíà÷åíèé
t p � { }0 1282 2054, . , . , ïðèâåäåíû íà
ðèñ. 1 (ëèíèè 1), ãäå íàáëþäàåòñÿ
«çàâàë» õàðàêòåðèñòèêè èç-çà íàëè-
÷èÿ â (9) äåëåíèÿ íà ìàëûå çíà÷åíèÿ
1 2�cos � (ïðè ìàëûõ �) è îñîáåí-
íîñòåé ðåàëèçàöèè èíòåãðèðîâàíèÿ.
Äëÿ óñòðàíåíèÿ ýòîãî íåäîñ-
òàòêà âûðàæåíèÿ äëÿ âû÷èñëåíèÿ
ìîäèôèöèðîâàíû ñëåäóþùèì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 179
Ðèñ. 1. Çàâèñèìîñòü âåðîÿòíîñòè p ñîâïàäåíèÿ åäè-
íè÷íûõ êîìïîíåíòîâ êîäâåêòîðîâ îò âõîäíîãî óãëà �
p
�
îáðàçîì. Ñäåëàåì çàìåíó ïåðåìåííûõ:
w
y y
w
y y
w
w
1
1 2
2
1 2 11
2 2
1
2 2
2
�
�
�
�
�
cos sin
cos
( / )
,
( / )
, *
( /
� �
� )
( / )
.
� t
sin � 2
Òîãäà äëÿ t t t1 2� �
p a b t( , , )|� � �1 1 �
1
2
1
2
2
2
2
2
1 2
�
�
e dw dw
w w
w
w
t
�
�
�
��
�� �
*
*
( / )cos
� �
��
�
2
2
1
2
2
2
1 2
�
�
�
e F w dw dw f
w
t
cos( / )
( *) ( ), (10)
ãäå F x e dz x
zx
( ) ( )� � �
�
�
1
2
1
2
2
2
0
�
� .
Ëèíèè 1a íà ðèñ. 1 ïîêàçûâàþò îòñóòñòâèå «çàâàëà» ãðàôèêà p a b t( , , )� �1 1
ïðè ìàëûõ �. Ýòî õîðîøî âèäíî ïî ëèíèÿì 2, êîòîðûå ñîîòâåòñòâóþò
p a b t p a b t p b t( , ) ( , , ) / ( , )|� � � � � �1 1 1 1 1 è ïîýòîìó èñõîäÿò èç òî÷êè ( , )01 . Ðàñ-
ñìîòðèì (10) ïðè t � 0 :
p a b t e dw dw
w ww
( , | , )
*
� � � �
�
���
��1 1 0
2
2
1
2
2
2
2
00
1 2�
�
.
(11)
Äëÿ ïåðåõîäà ê ïîëÿðíûì êîîðäèíàòàì ñäåëàåì çàìåíó ïåðåìåííûõ
w r w r1 2� �cos sin� �, . Òîãäà ïðåäåëû èíòåãðèðîâàíèÿ ïî w2 :
0
�
�
w*
èçìåíÿòñÿ
ñëåäóþùèì îáðàçîì: w w w t2 20 0 2 2� � � � � � �� � � �; * ( ) / / , òàê êàê íà
ëèíèè
w w t w2 10 2 2 2 2� � � � �* ( ) ( / ) / ( / ), ( / ) ( /cos sin tg ctg tg� � � � � � � / ).2
Ïîýòîìó
p a b t e rdrd
r
( , , )|
/ /
� � � � �
�
�
���
��1 1 0
2
2 2
1
2
2
0
2 2
0
�
�
�
� �
�
� �
2
1�
�
�
�
�
�
�
�
�
. (12)
Ïîñêîëüêó
p a b p a p b p a b( , ) ( ( ) ( ) ( ))� � � � � � � �1 1
1
2
1 1 ,
à p a t p b t( , ) ( , ) .� � � � � �1 0 1 0 05, òî 2 1 1 0 0p a b t p a b t( , , ) ( , )� � � � � � , ïîýòî-
ìó p a b t( , )� � � �0 1
�
�
. Ýòî âûðàæåíèå ñîâïàäàåò ñ ðåçóëüòàòîì [16, 12], ãäå
ðàññìàòðèâàëñÿ òîëüêî ñëó÷àé t � 0.
Äëÿ t � 0 p a t p b t( , ) ( , ) .� � � � � �1 0 1 0 05, ò.å. t � 0 äàåò íåðàçðåæåííûå êîä-
âåêòîðû. Âûáîð ïîðîãà t � 0 ïîçâîëÿåò óïðàâëÿòü ñòåïåíüþ ðàçðåæåííîñòè âû-
õîäíîãî êîäâåêòîðà, ñì. (8). Ýòî òàêæå âèäíî èç òîãî, ÷òî äëÿ t � 0 è
� � � �0, *w , ïîýòîìó
F w( *) �
1
2
è p a b t e dw
w
t
( , , )|� � � �
��
�1 1 0
1
2
1
2
2
1�
�
. (13)
Äëÿ y áåç íîðìèðîâàíèÿ (7), ïîëó÷åííîãî íåïîñðåäñòâåííî â ðåçóëüòàòå
óìíîæåíèÿ âõîäíîãî âåêòîðà íà ïðîåêöèîííóþ ìàòðèöó c {– 1,0, + 1}, òó æå ðàç-
ðåæåííîñòü (äîëþ åäèíè÷íûõ êîìïîíåíòîâ) âûõîäíîãî êîäâåêòîðà äàåò ïîðîã
T t s� | | /x .
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Äëÿ òîãî ÷òîáû ïîêàçàòü, ÷òî âåðîÿòíîñòü ñîâïàäåíèÿ åäèíè÷íûõ êîìïî-
íåíòîâ ìîíîòîííî óìåíüøàåòñÿ ñ ðîñòîì óãëà �, âû÷èñëèì ïðîèçâîäíóþ
dp
d
e F
d
t
dt
e
t w
� �
��� �
�
�
��
�
�
��
�
�
�
�
�
�
�
� �2
2
0
1
2
2
1
cos cos
( )
2
2
2
1 1
t
dw
dF w
d
dw
cos( / )
( *)
,
�
�
�
�
�
�
�
�
�
�
�
!
!
!
!
F ( )0 0� , ïîýòîìó ïåðâûé ÷ëåí ðàâåí íóëþ. Äëÿ âòîðîãî ÷ëåíà
dF w
d
e
dw
dt
w
( *) *
*
� �
�
�1
2
2
2 ,
dw
dt
w w t* ( / )
( / )
( ( / ) ) ( / )
� � �
�1 12
2 2
2 2
2
sin
sin
cos cos�
�
� �
sin 2 2( / )�
.
Ïîñëåäíåå âûðàæåíèå ìåíüøå íóëÿ, òàê êàê � �"( , )0 è w t1 2 0cos( / ) ,� � � ïî-
ýòîìó ïîäûíòåãðàëüíîå âûðàæåíèå è çíà÷åíèå èíòåãðàëà, ðàâíîå èñêîìîé ïðîèç-
âîäíîé
dp
d�
, ìåíüøå íóëÿ.
Òàêèì îáðàçîì, � ìîæíî îöåíèâàòü êàê � � � � ��f p a b t1 1 1( ( , , )) g p a( ( ,�1
b t�1, )), ãäå f �1 — ôóíêöèÿ, îáðàòíàÿ ê f (10), p îöåíèâàåòñÿ ïî êîäâåêòîðàì.
 ñëåäóþùåì ðàçäåëå ïîêàçàíî, ÷òî ìåíüøóþ äèñïåðñèþ èìååò îöåíêà óãëà ïî
óñëîâíîé âåðîÿòíîñòè p a b p a b p b( | ) ( , ) / ( )� � � � � �1 1 1 1 1 (ñì. òàêæå ðèñ. 1),
îñîáåííî ïðè îöåíêå p a b( | )� �1 1 êàê
| |
| |
( )
| |
z z
z
z
z
1 2
2
1
1
# p Nt , ãäå # — ïîêîìïîíåíò-
íàÿ îïåðàöèÿ êîíúþíêöèè, | |z — ÷èñëî åäèíè÷íûõ êîìïîíåíòîâ â z , pt ( )z1 —
òåîðåòè÷åñêàÿ îöåíêà ðàçðåæåííîñòè êîäâåêòîðà, îïðåäåëÿåìàÿ ïî 1�� (8).
Ýêñïåðèìåíòàëüíî èññëåäî-
âàëàñü çàâèñèìîñòü îöåíêè óãëà
ìåæäó âõîäíûìè âåêòîðàìè
x x1 2, ïî ýêñïåðèìåíòàëüíî ïîëó-
÷åííûì çíà÷åíèÿì ñîâïàäåíèÿ
êîìïîíåíòîâ èõ ðåçóëüòèðóþùèõ
êîäâåêòîðîâ z z1 2, äëÿ ðàçíûõ
A N s, , è p( )z , êîòîðàÿ îïðåäåëÿåò-
ñÿ ïîðîãîì t. Íà ðèñ. 2 ïðåäñòàâ-
ëåíû ðåçóëüòàòû îäíîãî èç ýêñïå-
ðèìåíòîâ äëÿ âõîäíûõ âåêòîðîâ
x x1 2, ðàçìåðíîñòüþ A �1000
(êîìïîíåíòû âåêòîðà — ïîëîæè-
òåëüíûå ñëó÷àéíûå ÷èñëà â äèàïà-
çîíå [ , ]0 A ) , s �10, N �1000,
p( ) . , .z � { }05 01 (ò.å. t � { }001282. , . ), óñðåäíåíèå ðåçóëüòàòîâ ïðîèçâîäèëîñü ïî 1000
ðåàëèçàöèÿì ïðîåêöèîííîé ìàòðèöû.
Ïðèâåäåíû çàâèñèìîñòè îöåíêè �* âõîäíîãî óãëà � ( , )1 2x x îò ðÿäà ôóíêöèé
èõ êîäâåêòîðîâ: �( * ( )), ,1 1 2� �p z zj j (ëèíèè 1E); arccos( , )1 2z z (ëèíèè AE) è
ñ èñïîëüçîâàíèåì ïîëó÷åííîé âûøå ôóíêöèè g p a b t( * ( , , ))� �1 1 (ëèíèè 3E).
Âèäíî, ÷òî âñå îöåíêè èìåþò ìîíîòîííóþ çàâèñèìîñòü îò âõîäíîãî óãëà. Îäíà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 181
Ðèñ. 2. Îöåíêè óãëà ìåæäó èñõîäíûìè âåêòîðàìè ïî
ôóíêöèÿì ñîâïàäåíèÿ êîìïîíåíòîâ èõ êîäâåêòîðîâ
�
�� ( )p
êî îöåíêà � �* ( ( ))� � �1 p a b áëèçêà ê � òîëüêî äëÿ t � 0 ; arccos( , )1 2z z íåëèíåéíî
(è ïî-ðàçíîìó äëÿ ðàçíûõ t) çàâèñèò îò �, à ïðåäëàãàåìàÿ íàìè îöåíêà �* áëèçêà
ê � äëÿ ðàçíûõ t.
2. ÌÀÒÅÌÀÒÈ×ÅÑÊÎÅ ÎÆÈÄÀÍÈÅ È ÄÈÑÏÅÐÑÈß ÎÖÅÍÊÈ ÂÅËÈ×ÈÍÛ ÓÃËÀ
Îïðåäåëèì ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèþ îöåíêè âåëè÷èíû óãëà ìåæäó
èñõîäíûìè âåêòîðàìè ïî îöåíêàì âåðîÿòíîñòåé ñîâïàäåíèÿ êîìïîíåíòîâ âûõîä-
íûõ áèíàðíûõ êîäâåêòîðîâ. Ðàñïðåäåëåíèå ÷èñëà k ñîâïàäàþùèõ åäèíè÷íûõ
êîìïîíåíòîâ («åäèíèö») êîäâåêòîðîâ äëÿ ëþáîãî ïîðîãà t áèíîìèàëüíîå:
P k k N( ) ( , ,� � p a b( , ))� �1 1 c E k Np a b{ } � � �( , )1 1 è
D k Np a b Np a b{ } � � � � � �( , )( ( , ))1 1 1 1 1 . Ïîýòîìó
E p a b E k N p a b{ } { }* ( , ) / ( , );� � � � � �1 1 1 1
D p a b D k N D k N p a b p a b{ } { } { }* ( , ) / / ( , )( ( ,� � � � � � � � �1 1 1 1 1 12 �1)) / N .
Ðàñïðåäåëåíèå ÷èñëà n ñîâïàäàþùèõ êîìïîíåíòîâ êîäâåêòîðîâ (êàê åäèíè÷-
íûõ, òàê è íóëåâûõ) äëÿ ëþáîãî ïîðîãà t áèíîìèàëüíîå: P n n N p a b( ) ( , , ( ))� ��
ñ E n Np a b{ } � �( ) è D k Np a b p a b{ } � � � �( )( ( ))1 . Òîãäà
E p a b E n N E n N p a b{ } { } { }* ( ) / / ( );� � � � �
D p a b D n N D n N p a b p a b N{ } { } { }* ( ) / / ( )( ( )) /� � � � � � �2 1 .
Äëÿ îïðåäåëåíèÿ ìàòîæèäàíèÿ è äèñïåðñèè óãëà ïî çàâèñèìîñòè � � g p( ),
èñïîëüçóÿ äåëüòà-ìåòîä (ëèíåàðèçàöèþ ôóíêöèé ñëó÷àéíîãî àðãóìåíòà [21] ïðè
ìàëûõ îòêëîíåíèÿõ p îò ñðåäíåãî ñ ïðèìåíåíèåì îäíîøàãîâîãî ðàçëîæåíèÿ
Òåéëîðà), ïîëó÷àåì
E g E p{ } { }�* ( * ),� (14)
D D p g E p g
dg
dp
{ } { } { }�* * [ ( * )] , .� $ $ �2
(15)
Ðàññìîòðèì ñëó÷àé t � 0 è p a b t( , )� � 0 . Äëÿ íåãî (ñì. (12)) � �� � �( ( ,1 p a b
t g p
d
dp
� � � �0)) ( ),
�
�, ïîýòîìó
D t p a b D p a b{ } { }� �* , * ( ) * ( )| � � � � �0 2
� � � � � � �� 2 0 1 0p a b t p a b t N( , )( ( , )) /
� �
�
�
�
�
�
� � �
�
�
�
�
�
� � �
� �
�
�
�
�
�
�
�
� � �
2
1 1
N N
N( ) / .
(16)
Çäåñü D{�* )� �0 0. Òåïåðü ðàññìîòðèì îöåíèâàíèå âåëè÷èíû óãëà íà îñíîâå
îöåíîê p a b( , )� �1 1 . Ïðè t � 0, òàê êàê p a b t p a b t( , ) ( , , )� � � � � �0 2 1 1 0
(ñì. (12)), àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ ïîëó÷àåì
D t p a b
N
{ }�
� �
* , * ( , )| � � � �
�
0 1 1
2 2
. (17)
Ïðè t � 0 äëÿ ÷èñëåííîãî îïðåäåëåíèÿ [ ( )]g E p$ { } 2 ìîæíî âîñïîëüçîâàòüñÿ
òàáëèöåé çíà÷åíèé � � g p( ), ïîëó÷åííîé ïî (10), è âû÷èñëèòü g
p p
$ �
�� �
2
1 1
%�
� �| |
,
ãäå %� — øàã óãëîâ â òàáëèöå, ïîñòðîåííîé ïî (10), p p� �� �1 1, — çíà÷åíèÿ p èç
ñëåäóþùåé è ïðåäûäóùåé îòíîñèòåëüíî � ÿ÷ååê òàáëèöû.
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ïðè âû÷èñëåíèè âåëè÷èíû óãëà íà îñíîâå îöåíîê p a b( , )� �1 1 ïîëó÷àåì
ïðèìåðíî îäèíàêîâûå è ãîðàçäî áîëüøèå, ÷åì äëÿ îöåíîê p a b( )� , çíà÷åíèÿ äèñ-
ïåðñèè D{ }�* .
Òàê, ïðè t � 0 çíà÷åíèå ND{ }�* óáûâàåò îò � 2 äî 0 75 2. � ïðè èçìåíåíèè � îò 0
äî 90, à ïðè t � 0 çíà÷åíèÿ åùå áîëüøå. Äëÿ óìåíüøåíèÿ äèñïåðñèè âîñïîëüçóåìñÿ
óñëîâíûìè âåðîÿòíîñòÿìè p a b p a b p b( ) ( , ) / ( )|� � � � � �1 1 1 1 1 (ñì. ðèñ. 1). Òîãäà
D p a b
p a b p a b
Np b
{ }* ( )
( , )( ( , ))
( )
|� � �
� � � � �
�
1 1
1 1 1 1 1
1
. (18)
Ïðè � � 0 p a b( )|� � �1 1 1 è D p a b{ }( )|� � �1 1 0, ò.å. D{ }�* � 0. Òàêèì îáðà-
çîì, â ýòîì ñëó÷àå äèñïåðñèÿ ïðè � � 0 ðàâíà íóëþ è ðàñòåò ñ ðîñòîì óãëà. Çàìå-
òèì, îäíàêî, ÷òî âáëèçè � � 0 è � �� èç-çà âûñîêîé íåëèíåéíîñòè ëèíåàðèçà-
öèÿ (15) äàåò íåíàäåæíûå ðåçóëüòàòû.
Íà ðèñ. 3 ïðåäñòàâëåíû òåî-
ðåòè÷åñêèå çàâèñèìîñòè äèñïåð-
ñèè îöåíêè óãëà (â ãðàä2) îò åãî
çíà÷åíèÿ ïðè îöåíêå ïî âåðîÿò-
íîñòè ñîâïàäåíèÿ êîìïîíåíòîâ
p a b t( , )� � 0 (ëèíèè 1T), ñîâìåñò-
íîé âåðîÿòíîñòè p a b( , )� �1 1 (ëè-
íèÿ 2T), óñëîâíîé âåðîÿòíîñòè
p a b( )|� �1 1 (ëèíèè 3T). Ðèñóíîê
ïîñòðîåí äëÿ N �1000, s �10,
t � { }00 1 282. , . , E — ýêñïåðèìåíò,
T — òåîðèÿ. Âèäíî, ÷òî ïðè ìà-
ëûõ óãëàõ äèñïåðñèÿ îöåíêè óãëà
ïî p a b( , )� �1 1 ìàêñèìàëüíà è
íåçíà÷èòåëüíî óìåíüøàåòñÿ ïðè óâåëè÷åíèè óãëà äî � / 2 . Ïðè îöåíêå óãëà ïî
p a b( , )� �1 1 äèñïåðñèÿ ðàñòåò îò íóëÿ äî ìàêñèìàëüíûõ çíà÷åíèé ïðè � / 2 , êî-
òîðûå ñðàâíèìû ñ äèñïåðñèÿìè äëÿ p a b( , )� �1 1 .
Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû îöåíîê p a b( )|� �1 1 ïî êîäâåêòîðàì (ëè-
íèÿ 3Å) õîðîøî ñîâïàäàþò ñ òåîðåòè÷åñêèìè. Ïðåâûøåíèå ýêñïåðèìåíòàëüíûìè
çíà÷åíèÿìè òåîðåòè÷åñêèõ ïðè � �~ / 2 , t �1 282. îáóñëîâëåíî ïîÿâëåíèåì ïàð
êîäâåêòîðîâ z z1 2, ñ íóëåâûì ïåðåêðûòèåì, äëÿ êîòîðûõ îöåíêà � ðàâíà �.
Äëÿ äàëüíåéøåãî óìåíüøåíèÿ äèñïåðñèè èñïîëüçîâàëàñü ñêîððåêòèðîâàí-
íàÿ îöåíêà p a b( )|� �1 1 , âû÷èñëÿ-
åìàÿ êàê
| |
| |
( )
| |
z z
z
z
z
1 2
2
1
1
# p Nt , ãäå
pt ( )z1 — òåîðåòè÷åñêàÿ îöåíêà
ïëîòíîñòè êîäâåêòîðà, îïðåäåëÿå-
ìàÿ ïî 1��. Ïðè òàêîé ñêîððåêòè-
ðîâàííîé îöåíêå äèñïåðñèÿ (ëè-
íèÿ CE) óìåíüøàåòñÿ ïðè t � 0 äî
çíà÷åíèé äèñïåðñèè îöåíêè � ïî
p a b t( )|� � 0 .
Íà ðèñ. 4 ïðåäñòàâëåíà çàâè-
ñèìîñòü äèñïåðñèè îöåíêè óãëà îò
N äëÿ ôèêñèðîâàííîãî çíà÷åíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 183
Ðèñ. 3. Çàâèñèìîñòü äèñïåðñèè îöåíêè óãëà � îò åãî
âåëè÷èíû, N � 1000
�
D �� )
Ðèñ. 4. Çàâèñèìîñòü äèñïåðñèè îöåíêè óãëà � îò
ðàçìåðíîñòè êîäâåêòîðà N
N
D �� )
óãëà � � 60� ïðè s �10, t A� �{ }001282 1000. , . , (îáîçíà÷åíèÿ òàêèå æå, êàê íà
ðèñ. 3). Äèñïåðñèÿ áûñòðî óìåíüøàåòñÿ ñ ðîñòîì N . Ïðè N � 200 òåîðåòè÷åñêèå
çàâèñèìîñòè õîðîøî ñîâïàäàþò ñ ýêñïåðèìåíòàëüíûìè. Ïðè ìàëûõ N � 100 ýêñ-
ïåðèìåíòàëüíûå çíà÷åíèÿ äèñïåðñèè ïðåâûøàþò òåîðåòè÷åñêèå êàê èç-çà íàðó-
øåíèÿ ãàóññîâîñòè ðàñïðåäåëåíèé, òàê è èç-çà ïîÿâëåíèÿ ïàð âåêòîðîâ ñ íóëåâûì
ïåðåêðûòèåì è íóëåâûì ÷èñëîì åäèíè÷íûõ êîìïîíåíòîâ. Äèñïåðñèÿ îöåíêè
óãëà ïî p a b( )|� �1 1 2T íàèáîëüøàÿ.
Çíàÿ åâêëèäîâû äëèíû èñõîäíûõ âåêòîðîâ | | | | , | | | |x x1 2 , ìîæíî îöåíèòü èõ
ñêàëÿðíîå ïðîèçâåäåíèå ( , )*x x1 2 ïî âåëè÷èíå óãëà �*, îöåíåííîãî ïî
êîäâåêòîðàì:
( , )* | | | | | | | | *x x x x1 2 1 2� cos � . (19)
Ñîãëàñíî äåëüòà-ìåòîäó
D D{ } {cos }( , )* | | | | | | | | *x x x x1 2 1
2
2
2� ��
�
�
�
�
�
�
� �| | | | | | | | * | | | | | | | |x x x x1
2
2
2
2
1
2
2
2D
d
d
D{ }
cos
�
�
�
{ }sin� �* 2 . (20)
Äëÿ t � 0 D D N{ } { } sin( , )* | | | | | | | | * ( ) ( ) /x x x x1 2 1
2
2
2 2� �� � � � � .
Îòìåòèì, ÷òî ýòî ïðèáëèæåíèå ñïðàâåäëèâî ïðè íåíóëåâîì sin �, ÷òî íàðó-
øàåòñÿ ïðè � �� { }0, . Ïîýòîìó âáëèçè 0 è � èç-çà âûñîêîé íåëèíåéíîñòè îöåíêè
çíà÷åíèé äèñïåðñèè, ïîëó÷åííûå ñ ïîìîùüþ òàêîãî ïðèáëèæåíèÿ, íåíàäåæíû.
3. ÃÅÎÌÅÒÐÈ×ÅÑÊÀß ÈÍÒÅÐÏÐÅÒÀÖÈß
Ñîãëàñíî (4) b �1, åñëè ñêàëÿðíîå ïðîèçâåäåíèå ( , ) | | | |/x r x
�T t s. Äëÿ áîëü-
øèõ A èìååì E A s{ }| | | | /r & è b �1 ïðè cos( , ) /x r
t A. Òàêèì îáðàçîì, âå-
ðîÿòíîñòü ñîâïàäåíèÿ åäèíè÷íûõ êîìïîíåíòîâ êîäâåêòîðîâ p a b( , )� �1 1 åñòü
îòíîøåíèå ïåðåêðûòèÿ ïëîùàäåé, âûñåêàåìûõ íà ñôåðå êîíóñàìè ñ óãëàìè
ðàñòâîðà
, ãäå
/ ( / )2 � arccos t A , ê ïëîùàäè ñôåðû. Îñÿìè êîíóñîâ ÿâëÿ-
þòñÿ âåêòîðû x x1 2, ñ óãëîì � �� { }0, ìåæäó ñîáîé, à âíóòðåííÿÿ ÷àñòü êîíó-
ñîâ ñîîòâåòñòâóåò ñëó÷àéíûì âåêòîðàì r ïðîåêöèîííîé ìàòðèöû ñ ïîëîæè-
òåëüíûìè ïðîåêöèÿìè íà x x1 2, (ðèñ. 5).
Äëÿ ïîðîãà t � 0 êîíóñû èìåþò òåëåñíûé óãîë
�� , ò.å. «ðàñêðûâàþòñÿ»
â ïëîñêîñòè. Òîãäà óãîë ìåæäó âåêòîðàìè åñòü óãîë ìåæäó ïëîñêîñòÿìè (ðèñ. 6).
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ðèñ. 5. Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ p( , )z z1 2
äëÿ t � 0
�
Ðèñ. 6. Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ p( , )z z1 2
äëÿ t � 0
�
�
�
Çäåñü äëèíà âåêòîðîâ x r, óæå íå èìååò çíà÷åíèÿ, òàê êàê äëÿ îïðåäåëåíèÿ çíàêà
êîìïîíåíòîâ êîäâåêòîðîâ âàæåí òîëüêî çíàê cos( , )x r , à íå åãî âåëè÷èíà.
Îáëàñòü, ãäå ïðîåêöèè x x1 2, íà âåêòîðû ïðîåêöèîííîé ìàòðèöû r j ïîëî-
æèòåëüíûå, ò.å. ãäå âûïîëíÿåòñÿ óñëîâèå ( . , , )a b b t� � �1 1 0 , ïîìå÷åíà íà ðèñ. 6
êàê y y� �1 2, . Ýòà îáëàñòü çàíèìàåò äâóãðàííûé óãîë � �� . Ïîýòîìó âåðîÿòíîñòü
ñîâïàäåíèÿ åäèíè÷íûõ êîìïîíåíòîâ êîäâåêòîðîâ p a b t( , , ) ( ) /� � � � �1 1 0 2� � �,
ãäå 2� — äâóãðàííûé óãîë âñåãî ïðîñòðàíñòâà (ãèïåðñôåðû). Îáëàñòü ñîâïàäå-
íèÿ íóëåâûõ êîìïîíåíòîâ êîäâåêòîðîâ òàêàÿ æå, ïîýòîìó p a b t( , , )� � � �0 0 0
� �( ) /� � �2 . Òîãäà p a b t( , ) ( ) /� � � �0 � � �, p a b( , ,� �1 1 t p a b� � �0) ( ,
t � 0 2) / , ñì. (12).
Îöåíêà p a b t( , ) /� � �0 � � ïî êîäâåêòîðàì åñòü H N N/ | | /� 'z z1 2 , ãäå
H M M� � � #1 2 1 22| |z z — ðàññòîÿíèå Õåììèíãà, ' — ïîêîìïîíåíòíàÿ îïåðà-
öèÿ «èñêëþ÷àþùåå èëè», | |� — ÷èñëî åäèíèö â êîäâåêòîðå, M M1 1 2 2� �| | , | |z z .
Ñîîòâåòñòâåííî îöåíêà p a b t H N( , ) / /� � � � � �0 1 1� � .
Ïðîåöèðîâàíèå â ñî÷åòàíèè ñ áèíàðèçàöèåé ìîæíî ðàññìàòðèâàòü êàê èç-
âëå÷åíèå N ïðèçíàêîâ èç âõîäíîãî âåêòîðà (èíäèêàòîðîâ åãî ïîëîæåíèÿ îòíîñè-
òåëüíî ñëó÷àéíûõ ãèïåðïëîñêîñòåé), àíàëîãè÷íîå ïðîèçâîäèìîìó ïåðâûì ôèê-
ñèðîâàííûì ñëîåì ïåðñåïòðîíà Ðîçåíáëàòòà. Çàìåòèì, ÷òî åñëè ïîðîã ðàâåí ÷èñ-
ëó åäèíèö â r j , îñóùåñòâëÿåòñÿ èçâëå÷åíèå ïðèçíàêîâ–ïðåäèêàòîâ (ñì. â [22–24]
ïðèìåð òàêîãî âûäåëåíèÿ ïðèçíàêîâ LIRA íà èçîáðàæåíèè).
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå èññëåäóþòñÿ ñâîéñòâà ðàíäîìèçèðîâàííûõ áèíàðíûõ âåê-
òîðíûõ ïðåäñòàâëåíèé ñ ðåãóëèðóåìîé ñòåïåíüþ ðàçðåæåííîñòè (äîëåé íåíó-
ëåâûõ êîìïîíåíòîâ), êîòîðûå ôîðìèðóþòñÿ èç âõîäíûõ ìàññèâîâ âåêòîðîâ,
èìåþùèõ ôîðìàò ñ ïëàâàþùåé çàïÿòîé, ïóòåì ïðîåöèðîâàíèÿ ñëó÷àéíîé ìàò-
ðèöåé ñ òåðíàðíûìè êîìïîíåíòàìè {–1,0, + 1}. Ïðîàíàëèçèðîâàíà òî÷íîñòü
îöåíèâàíèÿ ìåð ñõîäñòâà-ðàçëè÷èÿ èñõîäíûõ âåêòîðîâ, âû÷èñëèìûõ íà îñíîâå
óãëà, ïî ýìïèðè÷åñêèì âåðîÿòíîñòÿì ñîâïàäåíèÿ êîìïîíåíòîâ âûõîäíûõ âåê-
òîðîâ. Âûõîäíûå áèíàðíûå âåêòîðû ìîãóò èñïîëüçîâàòüñÿ âìåñòî âõîäíûõ
(èëè â ñî÷åòàíèè ñ íèìè) äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ïîèñêà è êëàññèôè-
êàöèè [2, 5], ôîðìèðîâàíèÿ ïðåäñòàâëåíèé ñëîæíî ñòðóêòóðèðîâàííîé èíôîð-
ìàöèè [3, 16], â íåéðîñåòåâîé ðàñïðåäåëåííîé àññîöèàòèâíîé ïàìÿòè [20] è
äðóãèõ ïðèëîæåíèÿõ èíòåëëåêòóàëüíîé îáðàáîòêè èíôîðìàöèè.
Ïðèìåíåíèå ñëó÷àéíûõ ðàçðåæåííûõ ïðîåêöèîííûõ ìàòðèö ñ êîìïîíåíòà-
ìè {–1,0, + 1} è äîëåé íåíóëåâûõ êîìïîíåíòîâ â ïðîåêöèîííîé ìàòðèöå p1 1��
ïîçâîëÿåò ñíèçèòü âû÷èñëèòåëüíóþ ñëîæíîñòü ïðîåöèðîâàíèÿ ïî ñðàâíåíèþ ñî
ñëó÷àéíûìè ìàòðèöàìè ñ êîìïîíåíòàìè, ðàñïðåäåëåííûìè ïî íîðìàëüíîìó çà-
êîíó, çà ñ÷åò îáðàáîòêè òîëüêî íåíóëåâûõ êîìïîíåíòîâ ìàòðèöû. Âû÷èñëèòåëü-
íàÿ ñëîæíîñòü ïðîåöèðîâàíèÿ (óìíîæåíèÿ âõîäíîãî âåêòîðà íà ïðîåêöèîííóþ
ìàòðèöó) ñîñòàâëÿåò O ANp p( )1 2 ( p2 — äîëÿ íåíóëåâûõ êîìïîíåíòîâ âî âõîäíîì
âåêòîðå, A — ðàçìåðíîñòü âõîäíîãî âåêòîðà, N — ðàçìåðíîñòü âûõîäíîãî âåêòî-
ðà), ÷òî äàåò çíà÷èòåëüíûé âûèãðûø ïî ñðàâíåíèþ ñ íåðàçðåæåííûìè ïðîåêöè-
îííûìè ìàòðèöàìè ñ p1 1~ . Êðîìå òîãî, âû÷èñëèòåëüíûå çàòðàòû ìîãóò áûòü
óìåíüøåíû çà ñ÷åò èñïîëüçîâàíèÿ îïåðàöèé ñëîæåíèÿ âìåñòî óìíîæåíèÿ.
Áèíàðèçàöèÿ ñ ïîðîãîì îáåñïå÷èâàåò ïîëó÷åíèå âûõîäíûõ áèíàðíûõ âåêòî-
ðîâ ñ íóæíîé äîëåé íåíóëåâûõ êîìïîíåíòîâ. Ôîðìèðîâàíèå âûõîäíîãî âåêòîðà
âûáîðîì M ìàêñèìàëüíûõ êîìïîíåíòîâ âåêòîðà, ïîëó÷åííîãî â ðåçóëüòàòå óìíî-
æåíèÿ âõîäíîãî âåêòîðà íà ïðîåêöèîííóþ ìàòðèöó, òðåáóåò O N M( )log îïåðàöèé
ïî ñðàâíåíèþ ñ N îïåðàöèÿìè ïðè àíàëèòè÷åñêîì âû÷èñëåíèè ïîðîãà, ÷òî äåëàåò
âòîðîé âàðèàíò áîëåå ïðåäïî÷òèòåëüíûì ñ òî÷êè çðåíèÿ âû÷èñëèòåëüíûõ çàòðàò.
Âåðîÿòíîñòü ñîâïàäåíèÿ êîìïîíåíòîâ âûõîäíûõ êîäâåêòîðîâ ÿâëÿåòñÿ ìîíî-
òîííîé ôóíêöèåé óãëà ìåæäó âõîäíûìè âåêòîðàìè è ïîçâîëÿåò îöåíèâàòü óãîë
ìåæäó âõîäíûìè âåêòîðàìè. Ïî óãëó òàêæå ìîæíî îöåíèòü ðàññòîÿíèå d è ñêà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 185
ëÿðíîå ïðîèçâåäåíèå, åñëè èçâåñòíû l2-íîðìû âõîäíûõ âåêòîðîâ | | | | , | | | | :x x1
2
2
2
d 2
1 2
2
1
2
2
2
1 22� � � � �| | | | | | | | | | | | | | | | | | | |x x x x x xcos � (íîðìû âõîäíûõ âåêòîðîâ
âû÷èñëÿþòñÿ îäèí ðàç, à õðàíåíèå îäíîé íîðìû òðåáóåò òîëüêî îäíîãî ÷èñëà).
Èñïîëüçîâàíèå áèíàðíûõ âåêòîðîâ ïîçâîëÿåò ñîêðàòèòü çàòðàòû ïàìÿòè è
âû÷èñëèòåëüíûõ ðåñóðñîâ íà èõ õðàíåíèå è îáðàáîòêó íà îáû÷íûõ êîìïüþòåðàõ.
Ýòî äîñòèãàåòñÿ èñïîëüçîâàíèåì îäíîãî áèòà äëÿ õðàíåíèÿ êîìïîíåíòà áèíàðíî-
ãî âåêòîðà âìåñòî 32–64 áèò äëÿ ôîðìàòà ñ ïëàâàþùåé òî÷êîé, ïðèìåíåíèåì ëî-
ãè÷åñêèõ îïåðàöèé è ñóììèðîâàíèÿ âìåñòî îïåðàöèé ñ ïëàâàþùåé çàïÿòîé,
à òàêæå âîçìîæíîñòüþ ýôôåêòèâíîé àïïàðàòíîé ïîääåðæêè â âèäå ñïåöèàëèçè-
ðîâàííûõ âû÷èñëèòåëåé è íåéðîêîìïüþòåðîâ [25]. Ðàçðåæåííûå áèíàðíûå âåê-
òîðû (ò.å. âåêòîðû ñ ìàëûì ÷èñëîì íåíóëåâûõ êîìïîíåíò) äîïîëíèòåëüíî ïîâû-
øàþò ýôôåêòèâíîñòü îáðàáîòêè (íàïðèìåð, ïóòåì èñïîëüçîâàíèÿ ïðîöåäóð, ïî-
ñòðîåííûõ íà îáðàòíîì èíäåêñå, è äð.).
Ïðè ÷èñëå áèò äëÿ ïðåäñòàâëåíèÿ âûõîäíûõ âåêòîðîâ, ìåíüøåì, ÷åì äëÿ âõîä-
íûõ, ïîëó÷àåì âûèãðûø â ïàìÿòè äëÿ õðàíåíèÿ è â ñêîðîñòè îáðàáîòêè. Ðàçìåð-
íîñòü âûõîäíûõ âåêòîðîâ ìîæíî âûáèðàòü â çàâèñèìîñòè îò òðåáóåìîé òî÷íîñòè
îöåíêè ñõîäñòâà âõîäíûõ âåêòîðîâ. Êðîìå òîãî, âûõîäíûå âåêòîðû ìàëîé ðàçìåð-
íîñòè ìîæíî èñïîëüçîâàòü äëÿ áûñòðîé îãðóáëåííîé îöåíêè ñõîäñòâà è âûáîðà êàí-
äèäàòîâ íà ïîñëåäóþùåå áîëåå òî÷íîå ñðàâíåíèå. Âîçìîæíûå îáëàñòè ïðèìåíåíèÿ
áèíàðíûõ ïðåäñòàâëåíèé âõîäíûõ âåêòîðîâ — ïîâûøåíèå ýôôåêòèâíîñòè èíôîð-
ìàöèîííîãî ïîèñêà (ïîèñê â Èíòåðíåò, ïîèñê áëèçêèõ ê çàïðîñó è äðóã äðóãó äîêó-
ìåíòîâ â õðàíèëèùàõ, ïîèñê äðóãîé èíôîðìàöèè â áàçàõ äàííûõ è çíàíèé, ïîèñê
áàçèñíûõ ôóíêöèé â áîëüøèõ ñëîâàðÿõ äëÿ ìåòîäîâ ìàøèííîãî îáó÷åíèÿ è äð.); ïî-
âûøåíèå ýôôåêòèâíîñòè êëàññèôèêàöèè è êëàñòåðèçàöèè ðàçíîãî ðîäà èíôîðìàöèè
â âåêòîðíîì ôîðìàòå (òåêñòîâ, èçîáðàæåíèé, çâóêîâ, ðåçóëüòàòîâ èçìåðåíèé è äð.);
ïîâûøåíèå ýôôåêòèâíîñòè äðóãèõ ìåòîäîâ îáðàáîòêè èíôîðìàöèè è èíôîðìàöèîí-
íûõ òåõíîëîãèé, òðåáóþùèõ îïåðèðîâàíèÿ áîëüøèìè ìàññèâàìè âåêòîðîâ.
Âûõîäíûå ðàçðåæåííûå áèíàðíûå ðàíäèìèçèðîâàííûå âåêòîðû, â êîòîðûõ
íå âàæíà ñåìàíòèêà îòäåëüíûõ êîìïîíåíòîâ, íî âàæíî îòðàæåíèå èìè ñõîäñòâà
âõîäíûõ âåêòîðîâ, íåîáõîäèìû òàêæå äëÿ ðÿäà ìåòîäîâ è ïàðàäèãì èíòåëëåê-
òóàëüíîé îáðàáîòêè èíôîðìàöèè, êîòîðûå òðåáóþò èìåííî òàêîãî ôîðìàòà. Ïðè-
ìåðîì ÿâëÿåòñÿ êîíöåïöèÿ àññîöèàòèâíî-ïðîåêòèâíûõ íåéðîííûõ ñåòåé [3], ãäå
ïðåäñòàâëåíèÿ ñëîæíûõ ñòðóêòóðèðîâàííûõ îáúåêòîâ ñàìîé ðàçíîé ïðèðîäû
ñòðîÿòñÿ èç áèíàðíûõ ðàçðåæåííûõ âåêòîðíûõ ðàíäîìèçèðîâàííûõ ïðåäñòàâëåíèé
(èçâåñòíûõ êàê «ðàñïðåäåëåííûå ïðåäñòàâëåíèÿ èíôîðìàöèè»), è ìåòîäû õðàíå-
íèÿ, îáîáùåíèÿ, è âîññòàíîâëåíèÿ èíôîðìàöèè â ðàñïðåäåëåííîé àññîöèàòèâíîé
ïàìÿòè [20], à òàêæå ïîäõîäû ê îáðàáîòêå ñòðóêòóð [16–19] è ó÷åòà ñåìàíòèêè [2],
êîòîðûå îðèåíòèðîâàíû èìåííî íà òàêîé ôîðìàò ïðåäñòàâëåíèÿ èíôîðìàöèè.
Ïåðñïåêòèâíûìè íàïðàâëåíèÿìè äàëüíåéøèõ ðàáîò ÿâëÿþòñÿ èññëåäîâàíèå
õàðàêòåðèñòèê ñõîäñòâà âûõîäíûõ âåêòîðîâ, îáåñïå÷èâàþùèõ áîëüøóþ òî÷íîñòü
îöåíèâàíèÿ ñõîäñòâà âõîäíûõ âåêòîðîâ, àíàëèç ñâîéñòâ äðóãèõ òèïîâ ïðîåöèðîâà-
íèÿ, èññëåäîâàíèå ïîëó÷åííûõ âåêòîðíûõ ïðåäñòàâëåíèé â ðàçëè÷íûõ çàäà÷àõ.
Ä.À. Ðà÷êîâñêèé âûðàæàåò áëàãîäàðíîñòü À.À. Ôðîëîâó è È.Ï. Ìóðàâüåâó
çà ïëîäîòâîðíûå îáñóæäåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. S a l t o n G . Automatic text processing: The transformation, analysis, and retrieval of information
by computer. — Reading, MA: Addison-Wesley, 1989. — 530 p.
2. Ì è ñ ó í î È . Ñ . , Ð à ÷ ê î â ñ ê è é Ä . À . , Ñ ë è ï ÷ å í ê î Ñ . Â . , Ñ î ê î ë î â À . Ì . Ïîèñê
òåêñòîâîé èíôîðìàöèè ñ ïîìîùüþ âåêòîðíûõ ïðåäñòàâëåíèé // Ïðîáëåìû ïðîãðàììèðîâà-
íèÿ. — 2005. — ¹ 4. — C. 50–59.
3. Ê ó ñ ñ ó ë ü Ý . Ì . Àññîöèàòèâíûå íåéðîïîäîáíûå ñòðóêòóðû. — Êèåâ: Íàóê. äóìêà, 1992. — 144 ñ.
4. Ð à ÷ ê î â ñ ê è é Ä . À . Ìîäåëèðîâàíèå ìûøëåíèÿ êàê ïóòü ïîâûøåíèÿ èíòåëëåêòóàëüíîñòè èí-
ôîðìàöèîííûõ òåõíîëîãèé è ñèñòåì // Ñèñòåìíûå òåõíîëîãèè. — 2008. — ¹ 4(57). — Ñ. 154–162.
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
5. R a c h k o v s k i j D . A . Linear classifiers based on binary distributed representations // Intern. J.
Inform. Theories & Appl. — 2007. — 14, N 3. — P. 270–274.
6. Ð à ÷ ê î â ñ ê è é Ä . À . , Ì è ñ ó í î È . Ñ . , Ð å â ó í î â à Å . Ã . , Ñ ë è ï ÷ å í ê î Ñ . Â . , Ñ î -
ê î ë î â À . Ì . Êîíöåïöèÿ è ìåòîäû íåéðîñåòåâîãî ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ èíôîð-
ìàöèè â çàäà÷àõ ÈÈ // 14-ÿ Ìåæäóíàð. êîíô. «Ïðîáëåìû íåéðîêèáåðíåòèêè». — Ò. 2. — Ðîñ-
òîâ-íà-Äîíó, Ðîññèÿ, 2005. — Ñ. 30–33.
7. Ð à ÷ ê î â ñ ê è é Ä . À . , Ñ ë è ï ÷ å í ê î Ñ . Â . , Ô ð î ë î â À . À . , Ã ó ñ å ê Ä . Ðàçðåøàþùàÿ
ñïîñîáíîñòü áèíàðíîãî êîäèðîâàíèÿ ÷èñëîâûõ âåêòîðîâ ãèïåðïðÿìîóãîëüíûìè ðåöåïòèâíû-
ìè ïîëÿìè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 5. — C. 3–16.
8. K a n e r v a P . , S j o d i n G . , K r i s t o f e r s o n J . , K a r l s s o n R . , L e v i n B . ,
H o l s t A . , K a r l g r e n J . a n d S a h l g r e n M . Computing with large random patterns //
Foundations of Real-World Intelligence. — CSLI Publications, Stanford, California, 2001. — P. 251–311.
9. 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 Lipshitz mapping into Hilbert space //
Contemporary Mathemat. — 1984. — 26. — P. 189–206.
10. V e m p a l a S . S . The Random Projection Method. — Providence, RI: American Mathemat. Soc.,
2004. — 105 p.
11. A c h l i o p t a s D . Database-friendly random projections: Johnson–Lindenstrauss with binary coins
// J. of Comput. and System Sci. — 2003. — 66, N 4. — P. 671–687.
12. C h a r i k a r M . Similarity estimation techniques from rounding algorithms // ACM Symp. on
Theory of Comput. — Montreal, Canada: ACM, 2002. — 1. — P. 380–388.
13. L i u K . , K a r g u p t a H . , R y a n J . Random projection-based multiplicative data perturbation
for privacy preserving distributed data mining // IEEE Transact. on Knowledge and Data Engineer.
— 2006. — 18, N 1. — P. 92–106.
14. 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, PA, USA: ACM Press,
2006. — P. 287–296.
15. M i c h e l X . G . , D a v i d P . W . Improved approximation algorithms for maximum cut and
satisfiability problems using semidefinite programming // J. of the Associat. for Comput. Machinery.
— 1995. — 42, N 6. — P. 1115–1145.
16. R a c h k o v s k i j D . A . Representation and processing of structures with binary sparse distributed
codes // IEEE Transac. on Knowledge and Data Engineer. — 2001. — 13, N 2. — P. 261–276.
17. R a c h k o v s k i j D . A . Some approaches to analogical mapping with structure sensitive distributed
representations // J. of Experiment. and Theoret. Artificial Intell. — 2004. — 16, N 3. — P. 125–145.
18. R a c h k o v s k i j D . A . , K u s s u l E . M . Binding and normalization of binary sparse distributed
representations by context-dependent thinning // Neural Comput. — 2001. — 13, N 2. — P. 411–452.
19. Ð à ÷ ê î â ñ ê è é Ä . À . , Ñ ë è ï ÷ å í ê î Ñ . Â . , Ê ó ñ ñ ó ë ü Ý . Ì . , Á à é ä û ê Ò . Í . Ïðîöå-
äóðà ñâÿçûâàíèÿ äëÿ áèíàðíîãî ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ äàííûõ // Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. — 2005. — ¹ 3. — C. 3–18.
20. Ô ð î ë î â À . À . , Ã ó ñ å ê Ä . , Ð à ÷ ê î â ñ ê è é Ä . À . Âðåìÿ ïîèñêà ïî ñõîäñòâó â àññîöèà-
òèâíîé ïàìÿòè äëÿ áèíàðíûõ âåêòîðîâ // Òàì æå. — 2006. — ¹ 5. — C. 3–13.
21. Â å í ò ö å ë ü Å . Ñ . Òåîðèÿ âåðîÿòíîñòåé. — Ì.: Íàóêà, 1969. — 576 ñ.
22. K u s s u l E . M . , B a i d y k T . N . , K a s a t k i n a L . M . , L u k o v i c h V . V . Rosenblatt
perceptrons for handwritten digit recognition // Intern. Joint Conf. on Neural Networks. —
Washington, DC: IEEE, 2001. — 2. — P. 1516–1521.
23. K u s s u l E . , B a i d y k T . , W u n s c h D . , M a k e y e v O . , M a r t i n A . Permutation coding
technique for image recognition systems // IEEE Transact. on Neural Networks. — 2006. — 17, N 6.
— P. 1566–1579.
24. Ì è ñ ó í î È . Ñ . , Ð à ÷ ê î â ñ ê è é Ä . À . , Ñ ë è ï ÷ å í ê î Ñ . Â . Ýêñïåðèìåíòàëüíîå èññëå-
äîâàíèå êëàññèôèêàöèè ðóêîïèñíûõ öèôð // Ñèñòåìíûå òåõíîëîãèè. — 2005. — ¹ 4(39). —
C. 110–133.
25. À ì î ñ î â Í . Ì . , Á à é ä û ê Ò . Í . , Ã î ë ü ö å â À . Ä . , Ê à ñ à ò ê è í À . Ì . , Ê à ñ à ò ê è -
í à Ë . Ì . , Ê ó ñ ñ ó ë ü Ý . Ì . , Ð à ÷ ê î â ñ ê è é Ä . À . Íåéðîêîìïüþòåðû è èíòåëëåêòóàëü-
íûå ðîáîòû. — Êèåâ: Íàóê. äóìêà, 1991. — 272 ñ.
Ïîñòóïèëà 07.07.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 187
|