Microsoft ΠΎΡ‚ΠΊΡ€Ρ‹Π» ΠΊΠΎΠ΄ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ Π²Π΅ΠΊΡ‚ΠΎΡ€Π½ΠΎΠ³ΠΎ поиска, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ Π² Bing

Компания Microsoft ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π»Π° исходныС тСксты Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ машинного обучСния SPTAG (Space Partition Tree And Graph) с Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠ΅ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ поиска блиТайшСго сосСда. Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½Π° Π² ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΡΠΊΠΎΠΌ ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠΈ Microsoft Research ΠΈ Ρ†Π΅Π½Ρ‚Ρ€Π΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ поисковых Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ (Microsoft Search Technology Center). На ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ SPTAG примСняСтся Π² поисковой систСмС Bing для опрСдСлСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Ρ€Π΅Π»Π΅Π²Π°Π½Ρ‚Π½Ρ‹Ρ… Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² с ΡƒΡ‡Ρ‘Ρ‚ΠΎΠΌ контСкста поисковых запросов. Код написан Π½Π° языкС Π‘++ ΠΈ распространяСтся ΠΏΠΎΠ΄ Π»ΠΈΡ†Π΅Π½Π·ΠΈΠ΅ΠΉ MIT. ΠŸΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ΡΡ сборка для Linux ΠΈ Windows. Π˜ΠΌΠ΅Π΅Ρ‚ΡΡ обвязка для языка Python.

НСсмотря Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ ΠΈΠ΄Π΅ΠΈ примСнСния Π²Π΅ΠΊΡ‚ΠΎΡ€Π½Ρ‹Ρ… Ρ…Ρ€Π°Π½ΠΈΠ»ΠΈΡ‰ Π² поисковых систСмах Π²ΠΈΡ‚Π°ΡŽΡ‚ ΡƒΠΆΠ΅ достаточно Π΄Π°Π²Π½ΠΎ, Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ ΠΈΡ… Π²Π½Π΅Π΄Ρ€Π΅Π½ΠΈΡŽ ΠΌΠ΅ΡˆΠ°Π΅Ρ‚ большая Ρ€Π΅ΡΡƒΡ€ΡΠΎΡ‘ΠΌΠΊΠΎΡΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ с Π²Π΅ΠΊΡ‚ΠΎΡ€Π°ΠΌΠΈ ΠΈ ограничСния Π² ΠΌΠ°ΡΡˆΡ‚Π°Π±ΠΈΡ€ΡƒΠ΅ΠΌΠΎΡΡ‚ΠΈ. Π‘ΠΎΠ²ΠΌΠ΅Ρ‰Π΅Π½ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² Π³Π»ΡƒΠ±ΠΈΠ½Π½ΠΎΠ³ΠΎ машинного обучСния с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ поиска блиТайшСго сосСда ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ»ΠΎ довСсти ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΈ ΠΌΠ°ΡΡˆΡ‚Π°Π±ΠΈΡ€ΡƒΠ΅ΠΌΠΎΡΡ‚ΡŒ Π²Π΅ΠΊΡ‚ΠΎΡ€Π½Ρ‹Ρ… систСм Π΄ΠΎ уровня, ΠΏΡ€ΠΈΠ΅ΠΌΠ»Π΅ΠΌΠΎΠ³ΠΎ для ΠΊΡ€ΡƒΠΏΠ½Ρ‹Ρ… поисковых систСм. НапримСр, Π² Bing для Π²Π΅ΠΊΡ‚ΠΎΡ€Π½ΠΎΠ³ΠΎ индСкса Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠΌ Π±ΠΎΠ»Π΅Π΅ 150 ΠΌΠΈΠ»Π»ΠΈΠ°Ρ€Π΄ΠΎΠ² Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ² врСмя Π²Ρ‹Π±ΠΎΡ€ΠΊΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Ρ€Π΅Π»Π΅Π²Π°Π½Ρ‚Π½Ρ‹Ρ… Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² укладываСтся Π² 8 мс.

Π’ состав Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ Π²ΠΊΠ»ΡŽΡ‡Π΅Π½Ρ‹ срСдства для построСния индСкса ΠΈ ΠΎΡ€Π³Π°Π½ΠΈΠ·Π°Ρ†ΠΈΠΈ поиска Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ², Π° Ρ‚Π°ΠΊΠΆΠ΅ Π½Π°Π±ΠΎΡ€ инструмСнтов для сопровоТдСния распрСдСлённой систСмы online-поиска, ΠΎΡ…Π²Π°Ρ‚Ρ‹Π²Π°ΡŽΡ‰Π΅ΠΉ ΠΎΡ‡Π΅Π½ΡŒ большиС ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ². ΠŸΡ€Π΅Π΄Π»Π°Π³Π°ΡŽΡ‚ΡΡ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ ΠΌΠΎΠ΄ΡƒΠ»ΠΈ: index builder для индСксации, searcher для поиска с использованиСм индСкса, распрСдСлённого Π² кластСрС ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΡƒΠ·Π»ΠΎΠ², сСрвСр для запуска ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΎΠ² Π½Π° ΡƒΠ·Π»Π°Ρ…, Aggregator для объСдинСния Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… сСрвСров Π² ΠΎΠ΄Π½ΠΎ Ρ†Π΅Π»ΠΎΠ΅ ΠΈ ΠΊΠ»ΠΈΠ΅Π½Ρ‚ для ΠΎΡ‚ΠΏΡ€Π°Π²ΠΊΠΈ запросов. ΠŸΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ΡΡ Π²ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ Π½ΠΎΠ²Ρ‹Ρ… Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ² Π² индСкс ΠΈ ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ² Π½Π° Π»Π΅Ρ‚Ρƒ.

Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π΅ΠΌΡ‹Π΅ ΠΈ прСдставлСнныС Π² ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π΄Π°Π½Π½Ρ‹Π΅ ΠΎΡ„ΠΎΡ€ΠΌΠ»Π΅Π½Ρ‹ Π² Π²ΠΈΠ΄Π΅ связанных Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ Π½Π° основС Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Ρ‹Ρ… (L2) ΠΈΠ»ΠΈ косинусных расстояний. ΠŸΡ€ΠΈ поисковом запросС Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°ΡŽΡ‚ΡΡ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ‹, расстояниС ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌΠΈ ΠΈ исходным Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠΌ минимально. Π’ SPTAG прСдоставляСтся Π΄Π²Π° ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠΎΡ€Π³Π°Π½ΠΈΠ·Π°Ρ†ΠΈΠΈ Π²Π΅ΠΊΡ‚ΠΎΡ€Π½ΠΎΠ³ΠΎ пространства: SPTAG-KDT (K-ΠΌΠ΅Ρ€Π½ΠΎΠ΅ Π΄Π΅Ρ€Π΅Π²ΠΎ (kd-tree) ΠΈ Π³Ρ€Π°Ρ„ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… окрСстностСй) ΠΈ SPTAG-BKT (Π΄Π΅Ρ€Π΅Π²ΠΎ k-срСдних (k-means tree ΠΈ Π³Ρ€Π°Ρ„ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… окрСстностСй). ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ мСньшС рСсурсов ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с индСксом, Π° Π²Ρ‚ΠΎΡ€ΠΎΠΉ дСмонстрируСт Π±ΠΎΠ»Π΅Π΅ Π²Ρ‹ΡΠΎΠΊΡƒΡŽ Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² поиска ΠΏΡ€ΠΈ ΠΎΡ‡Π΅Π½ΡŒ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… коллСкциях Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ².

ΠŸΡ€ΠΈ этом Π²Π΅ΠΊΡ‚ΠΎΡ€Π½Ρ‹ΠΉ поиск Π½Π΅ ограничиваСтся тСкстом ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ ΠΊ ΠΌΡƒΠ»ΡŒΡ‚ΠΈΠΌΠ΅Π΄ΠΈΠΉΠ½ΠΎΠΉ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ ΠΈ изобраТСниям, Π° Ρ‚Π°ΠΊΠΆΠ΅ для Π² систСмах автоматичСского формирования Ρ€Π΅ΠΊΠΎΠΌΠ΅Π½Π΄Π°Ρ†ΠΈΠΉ. НапримСр, Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ· ΠΏΡ€ΠΎΡ‚ΠΎΡ‚ΠΈΠΏΠΎΠ² Π½Π° Π±Π°Π·Π΅ Ρ„Ρ€Π΅ΠΉΠΌΠ²ΠΎΡ€ΠΊΠ° PyTorch Π±Ρ‹Π»Π° Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π° вСкторная систСма для поиска с ΡƒΡ‡Ρ‘Ρ‚ΠΎΠΌ сходства ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π½Π° изобраТСниях, построСнная с использованиСм Π΄Π°Π½Π½Ρ‹Ρ… ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… эталонных ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΉ с изобраТСниями ΠΆΠΈΠ²ΠΎΡ‚Π½Ρ‹Ρ…, кошСк ΠΈ собак, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±Ρ‹Π»ΠΈ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½Ρ‹ Π² Π½Π°Π±ΠΎΡ€Ρ‹ Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΎΠ². ΠŸΡ€ΠΈ поступлСнии входящСго изобраТСния для поиска ΠΎΠ½ΠΎ прСобразуСтся с использованиСм ΠΌΠΎΠ΄Π΅Π»ΠΈ машинного обучСния Π² Π²Π΅ΠΊΡ‚ΠΎΡ€, Π½Π° основС ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° SPTAG ΠΈΠ· индСкса Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ΡΡ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΏΠΎΡ…ΠΎΠΆΠΈΠ΅ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ‹ ΠΈ ΠΊΠ°ΠΊ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°ΡŽΡ‚ΡΡ связанныС с Π½ΠΈΠΌΠΈ изобраТСния.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ: opennet.ru