Մի զվարճալի փորձ, որը ես վերջերս արեցի՝ փորձելով միավորել բառերի վեկտորները և LSH-ը

Եկեք անմիջապես ցատկենք խորը վերջում: Այդպես զվարճալի կլինի: Ասեք, որ ունեք տեքստի կորպուս:

[“dog barked at the tree”, “cat drank milk”]

Այժմ յուրաքանչյուր բառ/նշան ներկայացրեք որպես պայուսակ-նգրամ վեկտոր: Դա անելու համար նախ մեզ անհրաժեշտ են բոլոր n-գրամները բոլոր նշաններում: Վերցնենք 1 և 2 գրամանոց վեկտորները:

[d, o, g, b, a, r, k, e, d, …, m, i, l, k, do, og, ba, ar, …, mi, il, lk]

Այժմ յուրաքանչյուր բառը ներկայացրեք որպես ngram վեկտոր

dog   —>[1, 1, 1, 0, 0, 0, 0, 0, 0, …, 0, 0, 0, 0, 1, 1, 0, 0, …, 0, 0, 0]
barked->[0, 0, 0, 1, 1, 1, 1, 1, 1, …, 0, 0, 0, 0, 0, 0, 1, 1, …, 0, 0, 0]
…
milk  ->[0, 0, 0, 0, 0, 0, 0, 0, 0, …, 1, 1, 1, 1, 0, 0, 0, 0, …, 1, 1, 1]

Երբ դուք ունեք յուրաքանչյուր բառ որպես n-գրամ վեկտոր, հաշվարկեք հետևյալը.

w = xR;-xR

Այստեղ x-ը (V , d) չափի ngram մատրիցն է, իսկ R_____ չափի պատահական նորմալ մատրիցն է: Այսպիսով, մենք վերջանում ենք (V , b)ով: Այստեղ V-ը բառապաշարի չափն է, իսկ b-ը հիպերպարամետր է (հեշ աղբարկղերի քանակը): Այլ կերպ ասած, յուրաքանչյուր նշանի համար մենք ունենք b չափի վեկտոր:

Դուք կարող եք պատկերացնել այս վեկտորները՝ օգտագործելով չափումների կրճատման տեխնիկան, ինչպիսին T-SNE-ն է, և դուք ստանում եք հետևյալը.

Ավելի ուշադիր նայելով,

watch ['wat.', 'always', 'Wat', 'wat', 'Was']
Free ['free', 'FREE', 'here,', 'fine.', 'alone']
My ['my', 'MY', 'whole', '<DECIMAL>', '<#>']
sending ['Send', 'send', 'end', 'dinner', 'seeing']
May ['may', 'mayb', 'mail', 'well', 'Well']
was ['was', 'WAS', 'office', 'wan', 'wana']
Enjoy ['Enjoy', 'write', 'wit', 'sorry', 'Sorry']

դուք կարող եք տեսնել, որ նմանատիպ կազմով բառերը վերջանում են միասին:

*տեղադրել խելագարված մեմ*

Կոդը՝Այստեղ

Հոլուպ! Ի՞նչ դժբախտ պատահեց:

Մի՛ վախեցիր։ Ես ձեզ չեմ թողնի վերևի պես ժայռի վրա առանց բացատրության: Այս հնարավորության հիմքում ընկած հիմնական գաղափարը տեղայնացման զգայուն հաշինգն է (LSH): Հիմա թույլ տվեք պատմել ձեզ այն մասին, թե ինչպես ես առաջին հերթին տեղեկացա այս հետաքրքիր գույքի մասին:

Նախաբան

Քիչ առաջ կարդում էի Reformer (Տրանսֆորմեր մոդելի տարբերակ) թերթը։ Այն հատկանիշը, որը գողացավ ուշադրության կենտրոնում այդ թերթում, LSH (Locality Sensitive Hashing) ալգորիթմն էր, որը նրանք օգտագործում էին տրանսֆորմեր մոդելի հարցումներն ու բանալիները պահելու համար: Ես ապշած էի դրա պարզությամբ և ահռելի ուժով: LSH-ի ամենահեշտ բացատրությունը (կարծում եմ) հետևյալն է.

LSH-ն անում է նորմալ հեշ ֆունկցիայի հակառակը: Հեշ ֆունկցիան փորձում է նվազեցնել բախումները եզակի տարրերի համար, որտեղ LSH ալգորիթմը փորձում է առավելագույնի հասցնել նմանատիպ տարրերի բախումները (հիմնվելով որոշ մուտքային ներկայացման վրա):

Բայց լամպի իրական պահն ինձ համար այլ էր: Ես մտածում էի, թե կա՞ տարբերակ օգտագործելու Reformer-ում օգտագործված LSH ալգորիթմը՝ կոպիտ, բայց արագ բառերի վեկտորներ գտնելու համար: Այն փաստը, որ ես շատ ժամանակ եմ անցկացրել բառերի վեկտորների հետ (որին չեմ կարող հիմնավոր պատճառաբանել, թե ինչու՞) կարող էր սերմը տնկել:

Հիմա, երբ մենք համատեքստ ունենք, եկեք հասնենք դրա էությանը: Առաջին կանգառ, LSH.

Գաղափարը LSH-ի հետևում

LSH-ն բխում է մոտավոր ամենամոտ հարևաններին (ANN) գտնելու շատ անհանգստացնող ընդհանուր խնդրից: Մոտավոր NN (Nearest Neighbors) նշանակում է արագ գտնել NN՝ զոհաբերելով որոշակի աստիճանի ճշգրտություն: Օրինակ, առաջարկությունների մոդելները զարգանում են ANN-ում, քանի որ 100 միլիոնանոց օգտատերերի բազայից տվյալ օգտատերերին նման օգտվողներ գտնելը զբոսանք չէ այգում: Մի մոռացեք այն փաստի մասին, որ դա պետք է տեղի ունենա օգտվողի արագ գործարկմամբ (օրինակ՝ սեղմելով կոճակը, ոլորելով էջը և այլն):

Լավ, վերադարձ դեպի LSH: Կան բազմաթիվ տարբեր LSH ալգորիթմներ, ներառյալ հայտնիները, ինչպիսիք են minhash-ը: Գաղափարն այն է, որ ստեղծվի հեշ ֆունկցիա, որը կ

մեծացնել բախման հավանականությունը (նույն հեշ ելքը) խիստ նմանատիպ մուտքերի համար

Մինհաշը փոքր-ինչ բարդույթ է, սակայն մեզ համար դուրս է: Կապի տակ գտնվող Reformer-ին սնուցող ալգորիթմը շատ ու շատ ավելի պարզ է: Ալգորիթմը հայտնի է որպես Անկյունային LSH (կամ Գնդաձև LSH): Իրականում, դա կարող է արտահայտվել մեկ շերտով, եթե դուք սափրում եք ավելորդ ճարպը (հետևաբար, սեղմեք-խայծ վերնագիրը): Այժմ անդրադառնանք Reformer թերթում օգտագործվող LSH ալգորիթմի առանձնահատկություններին:

bins = 32
R = np.random.normal(size=(5, bins//2))
inputs = np.array([[1,1,0,0,1], [1, 1, 1, 0, 0], [0, 0, 1, 1, 0]])
h_x = np.dot(inputs, R)
# The crux of the computation is a single line
# outs is a hash bin that is similar for similar inputs
hash_bins = np.argmax(np.concatenate([h_x, -h_x], axis=-1), axis=-1)

Դա այն ամենն է, ինչ ձեզ հարկավոր է: Այո, և ես ենթադրում եմ, որ ուզում եք, որ ես հավատամ, որ պաղպաղակը նույնպես սառեցված կովերից է: Ոչ, իսկապես, այն աշխատում է: Ահա թե ինչու.

Ինտուիցիա՝ գնդաձև LSH

Գնդաձև LSH-ը պտտվում է միավորի երկարությամբ գնդիկի շուրջ (որոշ D չափում) և նույն չափման D հարցման վեկտորի շուրջ: Գաղափարն այն է, որ.

Եթե ​​դուք ունեք B պատահականորեն պտտվող գագաթներ այս ոլորտում, հարցման վեկտորները նմանատիպ ներկայացումներով կստանան նույն գագաթը, ինչ իրենց մոտակա հարևանը:

Դա հենց այն է, ինչ անում է վերը նշված հաշվարկը, մասնավորապես,

R (r_j)-ի յուրաքանչյուր սյունակ կարելի է համարել որպես մեր հիպերոլորտի պատահականորեն պտտվող գագաթ (սա մի դետալ է, որը դուք կարող եք թողնել այնպես, ինչպես կա, բայց մաթեմատիկական գիտելիքներ ունեցող անհատների համար կա մի փոքրիկ հավելված): x_i.r_j-ը պարզապես վերցնում է կետային արդյունքը: Կետային արտադրանքի մեկ այլ անուն է «նմանություն» (որքան բարձր է կետային արտադրանքը, այնքան ավելի նման է): Այնուհետև argmax -ը տալիս է գագաթի ինդեքսը, որը հարցման NN-ն է: Սա երբեմն մեկնաբանվում է որպես «աղբարկղին հանձնարարություն», բայց նույն սկզբունքով: Այո, այնքան պարզ!

Կարևոր բաներից մեկը, որը թույլ է տալիս ներթափանցել, x_i.r_j էությունն է, սա վեկտոր է, որը ներկայացնում է, թե տվյալ հարցումը որքանով է նման տարածության կամայական գագաթին: Եվ նմանատիպ հարցումները կտեղադրվեն մոտակայքում: Եվ երբ դուք դա անում եք շատ պատահական գագաթներով, յուրաքանչյուր հարցման համար հայտնվում եք վեկտոր:

Ինչպե՞ս կապել LSH-ում, որպեսզի ստանամ լավ բառերի վեկտորներ:

Ուրախ եմ, որ հարցրիր. Առաջին հերթին, և՛ LSH, և՛ բառային վեկտորները ուղղված են նմանատիպ նպատակներին՝ «գտնելով մուտքերի նմանատիպ միավորներ մեծ կորպուսի մեջ»: Այսպիսով, այն հարցը, որին ես փորձում եմ պատասխանել այստեղ, այն է, որ կարո՞ղ ենք LSH մեխանիզմ ստեղծել՝ որոշ արագ բառերի վեկտորներ դուրս բերելու համար:

Մենք պարզապես հանում ենք argmax-ը հավասարումից: Որովհետև դա մեզ թողնում է մեր բարձր ծավալային տարածության յուրաքանչյուր պատահական գագաթի հեռավորությունների վեկտորով: Եվ նմանատիպ բառերի համար (յուրաքանչյուր բառը ներկայացված է որպես նգրամների պարկ), այս վեկտորները նման կլինեն:

Ինչո՞ւ մենք պարզապես չպահենք պայուսակ-նգրամ վեկտորները:

Այսպիսով, մյուս հարցն այն է, որ մենք օգտագործում ենք արդեն գոյություն ունեցող նմանությունը մեր պայուսակի նգրամ ներկայացման մեջ: Ինչու՞ այս վերափոխումը առաջին հերթին: Երկու հիմնական պատճառ կա

  • n-գրամ վեկտորների պարկը կարող է կամայականորեն մեծանալ, քանի որ չափը վերահսկվում է կորպուսի տարբեր n-գրամների քանակով, որտեղ այս մեթոդով b-ը վերահսկում է վեկտորների չափը:
  • Բարձր ծավալային n-գրամներին ավելի ցածր հարթությունում ստիպելը ստիպում է ավելի շատ նմանություններ սովորել: Նույն սկզբունքը վերաբերում է բառերի վեկտորներին: Երբ չափականությունը փոքր է, այն ստիպում է բառերի վեկտորներին սովորել բառերի նմանությունների մասին:

SPAM-ի դասակարգման առաջադրանքի կատարումը

Բառերի վեկտորների գնահատման տիպիկ մեթոդը դրանք ներքևային առաջադրանքում օգտագործելն է: Այստեղ ես գնահատել եմ հետևյալը սպամ-դասակարգման տվյալների բազայում:

  • Hash2vec վեկտորներ
  • Bag-of-ngram վեկտորներ
  • Իրական բառերի վեկտորներ

Փորձերի կոդը կարող եք գտնել այստեղ։ Մոդելը պարզ լոգիստիկ ռեգրեսիոն մոդել է վեկտորների վերևում: 10 փորձարկումներից հետո (յուրաքանչյուրը մարզվել է 10 դարաշրջան) ես ստանում եմ հետևյալ արդյունքը.

  • Hash2vec՝ 82,18 +/- 0,93 %
  • Multihot՝ 83,99 +/- 0,28%
  • Word2vec՝ 92.04 + /- 0.36%

Մենք կարող ենք տեսնել, որ Hash2vec-ը օրակուլ չէ: Բայց այն գործում է միանգամայն համարժեք, չնայած ունի ավելի փոքր չափ, քան Multihot (պայուսակ-նգրամ) մոտեցումը: Այստեղ մենք ավարտում ենք մեթոդի մասին մեր քննարկումը: Դուք կարող եք տեսնել այս փորձի կոդը՝ Այստեղ:

Ինչու և ինչու ոչ Hash2Vec

Ինչու Hash2Vec

  • Նկարում է միայն կոմպոզիցիոն նմանություններ. Դա լավ միջոց է համոզվելու, որ նմանատիպ կառուցվածք ունեցող բառերը (օրինակ՝ քայլել և քայլել) կամ ուղղագրական փոքր սխալներով բառերը (օրինակ՝ երրորդ ընդդեմ երրորդի) համընկնում են նմանատիպ վեկտորների հետ։
  • Պարզ բառերի վեկտորներ առանց ուսուցման — Դասընթացի կարիք չկա: Պարզ մատրիցային բազմապատկումը տալիս է վեկտորները
  • Համապատասխանում է ցանկացած մոդելի. Ի տարբերություն բառերի վեկտորների, դրանք պետք չէ լինել ծայրից ծայր տարբերվող ճարտարապետության մեջ (օրինակ՝ կարող են օգտագործվել xgboost նման մոդելների հետ):
  • Հաշինգը կարող է սխալ լինել. LSH-ում երաշխիք չկա, որ շատ հակառակ բաները կլինեն շատ տարբեր աղբարկղերում: Հազվագյուտ դեպքերում դրանք կարող են քարտեզագրվել նույն աղբարկղում: Ահա թե ինչու ես մի քանի փորձարկումներ անցկացրեցի այս փորձերի վրա:

Ինչու ոչ Hash2Vec

  • Գրում է իմաստաբանությունը — Իսկ բառերի վեկտորները կգրանցեն իմաստաբանությունը (օրինակ՝ կատու ընդդեմ կատվախոտի), որտեղ վերը նշված մեթոդը չի:
  • Վեկտորային թվաբանություն չկա — Ի տարբերություն Word2vec-ի, դուք չեք կարող վեկտորային հաշվարկներ կատարել (օրինակ՝ արքա — տղամարդ = թագուհի — կին) Hash2vec-ով, քանի որ այն չի ընդգրկում իմաստաբանությունը։
  • Ճշգրտություն – Word2vec-ը շատ ավելի արդյունավետ է, քան այս մեթոդը: Այսպիսով, եթե դուք հետևում եք ճշգրտությանը, Word2vec-ն ավելի խելամիտ ընտրություն է:

Եթե ​​չեք կարող հաղթել նրանց, միացեք նրանց

Այս մեթոդները (Hash2vec և Word2vec) կարիք չունեն միմյանց բացառելու: Նրանք կարող են նաև միմյանց հզորացնել: Օրինակ,

  • Դուք կարող եք օգտագործել Hash2vec-ը՝ բառերի վեկտորների լավ սկզբնավորումն ապահովելու համար, այնուհետև նորմալ վարժեցնել բառերի վեկտորները:
  • Դուք կարող եք օգտագործել LSH-ը՝ ուղղագրության ուղղագրման պարզ մեխանիզմ մշակելու համար: Քանի որ LSH-ը նույն բառերը քարտեզագրում է նմանատիպ դույլերի հետ, դուք կարող եք օգտագործել այս հատկությունը՝ զարգացնել ուղղագրական ուղղագրության որոնման պարզ բառարան: Այնուհետև նույն դույլի բառերը քարտեզագրեք նույն վեկտորի վրա word2vec շերտով:

Եզրակացություն

Այս հոդվածի նպատակը word2vec-ի համար մրցակից ներկայացնելը չէր, այլ պարզ LSH մեխանիզմի հզորությունը ցույց տալն ու այն բառի վեկտորների վարժանքով ամրացնելը: Այն մեզ հնարավորություն տվեց ստեղծելու ցածրաչափ բառերի վեկտորներ՝ առանց որևէ ուսուցման անհրաժեշտության: Ավելին, այս վեկտորները կարող են ֆիքսել բառերի միջև կոմպոզիցիոն նմանությունները: Ի վերջո, այս մեթոդները կարող են օգուտ քաղել նաև միմյանցից:

PS.Ես չեմ տեսել, որ նման տեխնիկան փորձարկվի կամ նախկինում օգտագործվի: Դա ինձ դրդեց գրել այս հոդվածը: Բայց կորած լինելով տարածության մեջ հրապարակված ՓԼ փաստաթղթերի հսկայական ծավալի մեջ, հազվադեպ չէ, որ նմանատիպ աշխատանքն աննկատ է մնում: Եթե ​​տեսնում եք մի թուղթ, որն աշխատում է նմանատիպ գծի վրա: Ազատորեն գրեք նրանց մասին:



Միացեք Medium-ին իմ ուղղորդման հղումով - Թուշհան Գանեգեդարա
Որպես Medium անդամ, ձեր անդամավճարի մի մասը գնում է ձեր կարդացած գրողներին, և դուք ստանում եք լիարժեք մուտք դեպի յուրաքանչյուր պատմություն… thushv89.medium.com



Հավելված

Պատահական ռոտացիա և մատրիցային բազմապատկում

Մենք ասում էինք, որ R-ը h(x) = argmax(xR;-xR)-ում ներկայացնում է պատահականորեն պտտվող կառուցվածք հիպերծավալային տարածության մեջ: Հասկանալու համար, թե ինչու է դա այդպես, մենք պետք է գլուխներս շրջենք դեպի Գնդաձև LSH՝ միավորի հիպերսֆերայի մոտ մոտակա հարևանների որոնման համար թղթին: Այս հոդվածում իրական հաշվարկը նման է.

որտեղ R-ը պատահական մատրիցա է (թղթում օգտագործվում է A), իսկ v_j-ը ներկայացնում է կանոնավոր հիպերոլորտի j^th գագաթը: Այսպիսով, այստեղ մենք հատուկ օգտագործում ենք պատահական պտույտի մատրիցը՝ կանոնավոր հիպերսֆերայի գագաթները պտտելու համար։ Այսպիսով, ինչպես ենք մենք x_i(R v_j)-ը կրճատել մինչև xR;-xR (որտեղ «;»-ը կապակցումն է): Խաբեությունը կայանում է նրանում, թե ինչ ենք մենք օգտագործում որպես ձև: Այստեղ մենք օգտագործում ենք հատուկ պոլիտոպ (բազմանկյունի ընդհանրացում դեպի բարձր չափեր), որը կոչվում է «օրթոպլեքս»: Օրթոպլեքսի գագաթները պարզապես {+/- 1, 0, 0, 0,…}-ի բոլոր փոխարկումներն են: Օրինակ, 2D տարածության մեջ դա [1, 0], [0, 1], [-1, 0] և ​​[0, -1] է:

Այլ կերպ ասած, գագաթները I և -I են, որտեղ ես ինքնության մատրիցն է: Այսպիսով, v_j-ը I-ով և -I-ով փոխարինելով, մենք ստանում ենք xR և — xR: Եվ պարզ ձևափոխումը կտա xR;-xR: