Ықтимал пайдаланушыларға ұсыныс жасау алгоритмі

Кіріспе

Алгоритм

Бірлесіп сүзгілеу (CF) – ұсыным жүйелері қолданатын техника. Бірлесіп сүзгілеудің екі түсінігі бар: тар және жалпы. Жаңа, тар мағынасында, бірлесіп сүзгілеу – көптеген пайдаланушылардан қалаулар немесе талғам туралы ақпарат жинау арқылы пайдаланушының қызығушылықтарын автоматты түрде болжау (сүзгілеу) әдісі. Бірлесіп сүзгілеу тәсілінің негізгі болжамы: егер А адамының Б адамымен бір мәселе бойынша пікірлері сәйкес келсе, А кездейсоқ таңдалған адамға қарағанда Б-нің басқа мәселе бойынша пікірін білдіруі мүмкін. Мысалы, телебағдарламаларға қатысты қалауларды анықтау үшін бірлесіп сүзгілеу ұсыным жүйесі пайдаланушыға қандай телешоу ұнауы мүмкін екенін болжауға болады, осы пайдаланушының талғамдарының ішінара тізімі (ұнаған немесе ұнамағандары) негізінде. Бұл болжамдар пайдаланушыға тән, бірақ көптеген пайдаланушылардан алынған ақпаратты пайдаланады. Бұл әрбір қызығушылық тудыратын элемент үшін орташа (нақты емес) балл беруден өзгеше, мысалы, оның дауыс санына сүйене отырып. Жалпы мағынасында, бірлесіп сүзгілеу – бірнеше агенттердің, көзқарастардың, дерек көздерінің және т.б. арасындағы ынтымақтастықты қамтитын әдістерді қолдана отырып, ақпаратты немесе үлгілерді сүзгілеу процесі. Пайдаланушыға негізделген ең жақсы N ұсыным алгоритмі белсенді пайдаланушыға ең ұқсас k пайдаланушыны анықтау үшін ұқсастыққа негізделген векторлық модельді қолданады. Ең ұқсас k пайдаланушы табылғаннан кейін, олардың сәйкес келетін пайдаланушы-элемент матрицалары ұсынылатын элементтер жиынтығын анықтау үшін біріктіріледі. Ұқсас пайдаланушыларды табудың танымал әдісі – сызықтық уақытта ең жақын көрші механизмін іске асыратын жергілікті сезімтал хэштеу. Бұл тәсілдің артықшылықтары: нәтижелердің түсіндірілуі, ұсыным жүйелерінің маңызды аспектісі; оңай құру және пайдалану; жаңа деректерді оңай қосу; ұсынылатын элементтердің мазмұнына тәуелді еместігі; тең бағаланған элементтермен жақсы масштабталуы. Бұл тәсілдің де бірнеше кемшіліктері бар. Деректер сиректеген кезде оның тиімділігі төмендейді, бұл вебке қатысты элементтерде жиі кездеседі. Бұл осы тәсілдің масштабталуына кедергі келтіреді және үлкен деректер жиынтығымен проблемалар тудырады. Ол деректер құрылымына сүйенгендіктен жаңа пайдаланушыларды тиімді түрде басқара алады, бірақ жаңа элементтерді қосу қиынға түседі, өйткені бұл бейнелеу әдетте белгілі бір векторлық кеңістікке сүйенеді. Жаңа элементтерді қосу үшін жаңа элементті қосу және құрылымдағы барлық элементтерді қайтадан енгізу қажет.

Collaborative filtering (CF) is a technique used by recommender systems. Collaborative filtering has two senses, a narrow one and a more general one. In the newer, narrower sense, collaborative filtering is a method of making automatic predictions (filtering) about the interests of a user by collecting preferences or taste information from many users (collaborating). The underlying assumption of the collaborative filtering approach is that if a person A has the same opinion as a person B on an issue, A is more likely to have B's opinion on a different issue than that of a randomly chosen person. For example, a collaborative filtering recommendation system for preferences in television programming could make predictions about which television show a user should like given a partial list of that user's tastes (likes or dislikes). These predictions are specific to the user, but use information gleaned from many users. This differs from the simpler approach of giving an average (non specific) score for each item of interest, for example based on its number of votes. In the more general sense, collaborative filtering is the process of filtering for information or patterns using techniques involving collaboration among multiple agents, viewpoints, data sources, etc. The user based top N recommendation algorithm uses a similarity based vector model to identify the k most similar users to an active user. After the k most similar users are found, their corresponding user item matrices are aggregated to identify the set of items to be recommended. A popular method to find the similar users is the Locality sensitive hashing, which implements the nearest neighbor mechanism in linear time. The advantages with this approach include: the explainability of the results, which is an important aspect of recommendation systems; easy creation and use; easy facilitation of new data; content independence of the items being recommended; good scaling with co rated items. There are also several disadvantages with this approach. Its performance decreases when data gets sparse, which occurs frequently with web related items. This hinders the scalability of this approach and creates problems with large datasets. Although it can efficiently handle new users because it relies on a data structure, adding new items becomes more complicated since that representation usually relies on a specific vector space. Adding new items requires inclusion of the new item and the re insertion of all the elements in the structure.

Үлгіге негізделген

Бұл тәсілде модельдер әртүрлі деректерді өндіру, машиналық оқыту алгоритмдерін пайдалана отырып, бағаланбаған элементтерге қатысты пайдаланушылардың бағасын болжау үшін жасалады. Модельге негізделген CF алгоритмдері көптеген. Байес желілері, кластерлік модельдер, синглярлық құндылықты ыдырату, ықтималдық семантикалық талдау, көптік көбейту факторы, латентті Дирихлет бөлісі және Марков шешім қабылдау процесіне негізделген модельдер сияқты жасырын семантикалық модельдер бар. Осы тәсіл арқылы өлшемді азайту әдістері көбінесе жадқа негізделген тәсілдің беріктігі мен дәлдігін арттыру үшін қосымша техника ретінде қолданылады. Осыған орай, синглярлық құндылықты ыдырату, бас компоненттік талдау сияқты әдістер, жасырын факторлар модельдері деп аталады, пайдаланушы-элемент матрицасын жасырын факторлар тұрғысынан төмен өлшемді ұсынысқа дейін қысқартады. Бұл тәсілді қолданудың бір артықшылығы – жоғалған мәндердің көп санын қамтитын жоғары өлшемді матрицамен емес, төмен өлшемді кеңістіктегі әлдеқайда кіші матрицамен жұмыс істеуге мүмкіндік береді. Азайтылған ұсыныс бұрынғы бөлімде ұсынылған пайдаланушыға немесе элементке негізделген жақын алгоритмдер үшін пайдаланылуы мүмкін. Бұл парадигманың бірнеше артықшылықтары бар. Ол бастапқы матрицаның сиректігін жадқа негізделгендерге қарағанда жақсырақ шешеді. Сонымен қатар, алынған матрицадағы ұқсастықты салыстыру, әсіресе үлкен, сирек деректер жиынтықтарымен жұмыс істегенде, әлдеқайда кеңейтілуге болады.

Гибридті

Бірқатар қолданбалар жадқа негізделген және модельге негізделген CF алгоритмдерін үйлестіреді. Олар нақты CF әдістерінің кемшіліктерін жойып, болжамның дәлдігін арттырады. Маңыздысы, олар сиректік және ақпаратты жоғалту сияқты CF проблемаларын шешеді. Дегенмен, олардың күрделігі артып, іске асыруы қымбатқа түседі. Көбінесе коммерциялық ұсыну жүйелері гибридтік болып келеді, мысалы, Google жаңалықтар ұсыну жүйесі.

Терең оқыту

Соңғы жылдары нейрожелілік және терең оқытудың бірқатар әдістері ұсынылды. Олардың кейбіреулері дәстүрлі матрицалық факторлау алгоритмдерін сызықтық емес нейрондық архитектура арқылы кеңейтеді немесе Вариациялық автокодерлер сияқты жаңа модельдерді қолданады. Терең оқыту көптеген әртүрлі сценарийлерде қолданылды: контекстке бейімделу, реттілікке бейімделу, әлеуметтік тегтеу және т.б. Бірақ қарапайым бірлескен ұсынымдар сценарийінде оның нақты тиімділігі күмәнді. Жоғары деңгейдегі конференцияларда (SIGIR, KDD, WWW, RecSys) жарияланған терең оқыту немесе нейрондық әдістерді топ-k ұсынымдар мәселесіне қолдану туралы жарияланымдарды жүйелі талдау көрсетті, орташа есеп бойынша мақалалардың 40%-дан азы қайта өндіріледі, ал кейбір конференцияларда – 14%-ға дейін. Жалпы зерттеуде 18 мақала анықталды, олардың тек 7-сі қайта өндірілді, ал 6-сы ескі, қарапайым және дұрыс реттелген базалық модельдерден де жақсы нәтижелер көрсетті. Мақала сонымен қатар қазіргі зерттеулердегі бірқатар мәселелерді атап өтеді және осы саладағы ғылыми тәжірибені жақсартуға шақырады. Осы сияқты мәселелерді басқалар да анықтады, сондай-ақ реттілікке бейімделетін ұсыным жүйелерінде де кездеседі.

Контекстке бейімделген бірлескен сүзгілеу

Көптеген ұсыным жүйелері пайдаланушының бағасымен қатар болатын басқа да контексттік ақпаратты ескермейді, бұл өнім ұсынысын жасауда қарапайымдыққа әкеледі. Дегенмен, уақыт, орын, әлеуметтік ақпарат және пайдаланушы қолданатын құрылғының түрі сияқты контексттік ақпараттың кең таралған болуымен, табысты ұсыным жүйесі үшін контекстке сезімтал ұсыным жасау бұрынғыдан да маңыздырақ болып келеді. Шару Агравалдың айтуынша, "Контекстке бейімделген ұсыным жүйелері ұсыным жасалатын нақты жағдайды анықтайтын қосымша ақпаратқа сәйкес ұсынымдарын өзгертеді. Осы қосымша ақпарат контекст деп аталады". Ықтимал сүзгілеуді және әсіресе жақын көршілер әдісін пайдалану үшін, тәсілдерді екі өлшемді рейтингтік матрицадан жоғары реттік тензорға дейін кеңейтуге болады. Осы мақсатта, мақсатты пайдаланушыға ең ұқсас көзқарастың иесі болған пайдаланушыларды табу қажет; әрбір пайдаланушыға сәйкес келетін кесінділердің (мысалы, өнім-уақыт матрицасы) ұқсастығын шығарып, есептеуге болады. Контекстке сезімсіз жағдайда екі рейтингтік вектордың ұқсастығы есептелетін болса, контекстке бейімделген тәсілдерде әрбір пайдаланушыға сәйкес келетін рейтингтік матрицалардың ұқсастығы Пирсон коэффициенттерін қолдану арқылы есептеледі. Ықтимал сүзгілеудің бір қолданылуы – қоғамдық пікір бойынша қызықты немесе танымал ақпаратты ұсыну. Мысалы, Reddit-тің бас бетіндегі жаңалықтар қоғамдық дауыс беру (жағымды бағалау) арқылы көрсетіледі. Қоғамның мөлшері мен әртүрлілігі арта келе, ілгерілетілген жаңалықтар қоғам мүшелерінің орташа қызығушылықтарын жақсырақ көрсетеді. Wikipedia – Ықтимал сүзгілеудің тағы бір мысалы. Волонтёрлер энциклопедияға жалған ақпаратты сүзіп тастау арқылы үлес қосады. Ықтимал сүзгілеу жүйелерінің тағы бір ерекшелігі – белгілі бір пайдаланушының бұрынғы әрекеттерінен алынған ақпаратты немесе сол пайдаланушыға ұқсас талғамға ие деп саналатын басқа пайдаланушылардың тарихын талдау арқылы жекелендірілген ұсынымдар жасау мүмкіндігі. Бұл ресурстар пайдаланушының профилін жасау үшін қолданылады және сайтқа әр пайдаланушы үшін мазмұн ұсынуға көмектеседі. Пайдаланушы жүйеден қаншалықты көп пайдаланса, ұсынымдар соғұрлым жақсы болады, өйткені жүйе осы пайдаланушының моделін жақсарту үшін деректер жинақтайды.

Many recommender systems simply ignore other contextual information existing alongside user's rating in providing item recommendation. However, by pervasive availability of contextual information such as time, location, social information, and type of the device that user is using, it is becoming more important than ever for a successful recommender system to provide a context sensitive recommendation. According to Charu Aggrawal, "Context sensitive recommender systems tailor their recommendations to additional information that defines the specific situation under which recommendations are made. This additional information is referred to as the context." In order to take advantage of collaborative filtering and particularly neighborhood based methods, approaches can be extended from a two dimensional rating matrix into a tensor of higher order. For this purpose, the approach is to find the most similar/like minded users to a target user; one can extract and compute similarity of slices (e. g. item time matrix) corresponding to each user. Unlike the context insensitive case for which similarity of two rating vectors are calculated, in the context aware approaches, the similarity of rating matrices corresponding to each user is calculated by using Pearson coefficients. One scenario of collaborative filtering application is to recommend interesting or popular information as judged by the community. As a typical example, stories appear in the front page of Reddit as they are "voted up" (rated positively) by the community. As the community becomes larger and more diverse, the promoted stories can better reflect the average interest of the community members. Wikipedia is another application of collaborative filtering. Volunteers contribute to the encyclopedia by filtering out facts from falsehoods. Another aspect of collaborative filtering systems is the ability to generate more personalized recommendations by analyzing information from the past activity of a specific user, or the history of other users deemed to be of similar taste to a given user. These resources are used as user profiling and helps the site recommend content on a user by user basis. The more a given user makes use of the system, the better the recommendations become, as the system gains data to improve its model of that user.

Қиындықтар

Бірлескен сүзгілеу жүйесі мазмұнды автоматты түрде адамның қалауынша келтіруде міндетті түрде табысқа жете бермейді. Егер платформа ерекше түрлілікке және пікірлердің тәуелсіздігіне қол жеткізбесе, нақты бір қауымдастықта бір көзқарас әрқашан екіншісінен басым болады. Жекелендірілген ұсынымдар жасау жағдайындағыдай, жаңа пайдаланушылардың немесе жаңа заттардың енгізілуі салқын старт мәселесін тудыруы мүмкін, себебі бірлескен сүзгілеудің дұрыс жұмыс істеуі үшін осы жаңа жазбалар туралы жеткілікті мәлімет болмайды. Жаңа пайдаланушыға тиімді ұсынымдар жасау үшін, жүйе алдымен бұрынғы дауыс беру немесе бағалау әрекеттерін талдау арқылы пайдаланушының қалауын анықтауы керек. Бірлескен сүзгілеу жүйесі жаңа затты ұсыну үшін көптеген пайдаланушылардың оны бағалауын қажет етеді.

Деректердің аздығы

Іс жүзінде көптеген коммерциялық ұсыным жүйелері үлкен деректер жиынтығына негізделген. Осының салдарынан, бірлескен сүзгілеу үшін қолданылатын пайдаланушы-тауар матрицасы өте үлкен және сирек болуы мүмкін, бұл ұсынымның тиімділігіне кедерес келтіреді. Деректердің сиректігінен туындайтын әдеттегі мәселелердің бірі – «суық старт» мәселесі. Бірлескен сүзгілеу әдістері пайдаланушылардың бұрынғы таңдауларына сүйене отырып тауарларды ұсынатындықтан, жаңа пайдаланушылар жүйеге олардың таңдауларын дәл анықтап, сенімді ұсыныстар беру үшін жеткілікті мөлшерде тауарларды бағалауы керек. Сол сияқты, жаңа тауарлар да осындай мәселеге тап болады. Жүйеге жаңа тауарлар қосылғанда, оларды ұқсас талғамдарға ие пайдаланушыларға ұсыну үшін, оларды көптеген пайдаланушылар бағалауы қажет. «Жаңа тауар» мәселесі контентке негізделген ұсынымдарға әсер етпейді, себебі тауардың ұсынымы оның бағаларына емес, сипаттамалық ерекшеліктерінің дискретті жиынтығына негізделген.

Өлшегіштігі

Пайдаланушылар мен тауарлардың саны арта түскен сайын, дәстүрлі CF алгоритмдері ауқымдылық мәселелеріне тап болады. Мысалы, ондаған миллион клиент және миллиондаған тауар болғанда, күрделілігі бар CF алгоритмі қазірдің өзінде тым ауыр болып табылады. Сонымен қатар, көптеген жүйелер онлайн сұраныстарға дереу жауап беруі және миллиондаған пайдаланушыға қарамастан, барлық пайдаланушыларға ұсыныстар жасауы керек, ал көптеген есептеулер өте үлкен жадты машиналарда орындалады.

Синонимдер

Синонимдер – бір немесе өте ұқсас заттардың әртүрлі атауларымен немесе тізімдемелерде кездесуі. Көптеген ұсыныс жүйелері осы жасырын байланысты анықтай алмайды, сондықтан осы өнімдерді әртүрлі қарастырады. Мысалы, сырттай әртүрлі көрінетін "балалар фильмі" және "балалар киносы" бір және со aynı нәрсені білдіреді. Шындығында, сипаттамалық терминдерді қолданудағы айырмашылықтар күдіктелгеннен де жоғары. Синонимдердің көп болуы ұсыныс жүйелерінің (КФ) тиімділігін төмендетеді. Тақырыптық модельдеу (мысалы, Latent Dirichlet Allocation әдісі) бір тақырыпқа жататын әртүрлі сөздерді топтастыру арқылы бұл мәселені шеше алады.

Сұр қой

Сұр қой – пікірлері тұрақты түрде ешбір топпен келіспейтін немесе келісетін пайдаланушыларды білдіреді, осылайша олар бірлескен сүзуден (коллаборативті сүзуден) пайда көре алмайды. Қара қой – ерекше талғамдары кеңес беруді дерлік мүмкін емес ететін топ. Бұл ұсыныс жүйесінің сәтсіздігі болғанымен, электрондық емес кеңес берушілер де осындай жағдайларда үлкен қиындықтарға тап болады, сондықтан қара қойлардың болуы – қабылданатын сәтсіздік.

Шиллингтік шабуылдар

Кез келген адам баға бере алатын ұсыным жүйесінде, адамдар өз өнімдеріне көптеген оң бағалар мен бәсекелестеріне теріс бағалар беруі мүмкін. Ықпалдастыру сүзгілеу жүйелері үшін мұндай манипуляциялардың алдын алу үшін шаралар қабылдау жиі қажет болады.

Түрлілігі мен ұзын құйрығы

Бірлескен сүзгілер жаңа өнімдерді табуға көмектесетіндіктен, әртүрлілікті арттыруы күтілуде. Дегенмен, кейбір алгоритмдер қасақана емес, кері нәтиже беруі мүмкін. Бірлескен сүзгілер өнімдерді өткен сатулар немесе бағалаулар негізінде ұсынатындықтан, тарихи деректері шектеулі өнімдерді ұсыну мүмкіндігі азаяды. Бұл танымал өнімдерге артықшылық тудырып, оларды одан да танымал етеді, бұл жағымды кері байланысқа ұқсас. Осы танымалдылыққа бейімділік, әдетте жақсы болатын тұтынушы мен өнім арасындағы сәйкестіктің бұзылуына әкелуі мүмкін. Уортон университетінің зерттеуі осы құбылысты және әртүрлілікті арттыру мен "ұзын құйрықты" дамытуға бағытталған бірнеше идеяны егжей-тегжейлі сипаттайды. Әртүрлілікті және "ұзын құйрықты" қолдау үшін жаңа, күтпеген және сүйіншілі элементтерді ұсынатын бірнеше бірлескен сүзгілеу алгоритмдері жасалған.

Жаңалықтар

Netflix сыйлығының нәтижесінде CF үшін жаңа алгоритмдер әзірленді. Бірнеше ұсыным жүйесіндегі пайдаланушы профильдері көпміндетті түрде біріктірілетін жүйелер аралық ынтымақтастық сүзгілеу; осы арқылы модельдер арасында қалау үлгілерін ортақ пайдалануға қол жеткізіледі. Ұсынымдарды манипуляциялау әрекеттеріне төтеп беретін сенімді ынтымақтастық сүзгілеу. Бұл зерттеу саласы әлі де дамып жатыр және толыққанды шешілмеген.

Қосалқы ақпарат

Пайдаланушы-элемент матрицасы дәстүрлі бірлескен сүзгілеу әдістерінің негізгі құралы болып табылады, бірақ деректердің сиректігі (яғни, «суық старт») мәселесіне ұшырайды. Осының салдарынан, зерттеушілер пайдаланушы-элемент матрицасынан өзге, ұсынымдардың сапасын арттыру және жекелендірілген ұсыным жүйелерін дамыту үшін қосымша ақпарат жинауға тырысады. Жалпы, екі кең таралған қосымша ақпарат бар: атрибут ақпараты және өзара әрекеттесу ақпараты. Атрибут ақпараты пайдаланушының немесе элементтің қасиеттерін сипаттайды. Мысалы, пайдаланушы атрибуты жалпы профильді (мысалы, жынысы мен жасы) және әлеуметтік байланыстарды (мысалы, әлеуметтік желілердегі ізбасарлар немесе достар) қамтуы мүмкін; элемент атрибуты санат, бренд немесе мазмұн сияқты қасиеттерді білдіреді. Сонымен қатар, өзара әрекеттесу ақпараты пайдаланушылардың элементпен қалай өзара әрекеттесетінін көрсететін жасырын деректерді білдіреді. Көп қолданылатын өзара әрекеттесу ақпаратына тегтер, пікірлер, шолулар және шолу тарихы жатады. Қосымша ақпарат түрлі жағдайларда маңызды рөл атқарады. Сенімділік немесе достықтың сенімді көрсеткіші болып табылатын әлеуметтік байланыстар, мақсатты пайдаланушымен қызығушылықтары ортақ жандарды табу үшін ұқсастық есептеуінде жиі қолданылады. Өзара әрекеттесумен байланысты ақпарат – тегтер – озық бірлескен сүзгілеуде үшінші өлшем (пайдаланушы мен элементтен өзге) ретінде қабылданып, ұсынымды зерттеу үшін 3 өлшемді тензор құрылымын құруға мүмкіндік береді.