Uchanganuzi wa Neno la Kipande kwa Kasi: Algorithm ya Muda Mstari kwa BERT na Zaidi

Yaliyomo

1. Utangulizi

Uchanganuzi wa neno (Tokenization) ni hatua ya msingi ya utayarishaji wa awali kwa karibu kazi zote za Usindikaji wa Lugha ya Asili (NLP), kutoka uchambuzi wa hisia hadi tafsiri ya mashine. Mifano ya kisasa kama BERT, GPT-3, na XLNet hutegemea uchanganuzi wa neno la kipande (subword tokenization), hasa algorithm kama WordPiece, kuvunja maandishi kuwa vitengo vyenye maana huku kikishughulikia maneno yasiyoko kwenye msamiati. Karatasi hii inashughulikia kikwazo muhimu: ufanisi wa algorithm ya uchanganuzi wa neno la WordPiece yenyewe.

Waandishi wanaonyesha kuwa mkakati wa kawaida wa tamaa ya mechi ndefu zaidi (MaxMatch) unaotumika katika WordPiece una utata wa wakati usio bora—$O(n^2)$ au $O(nk)$, ambapo $n$ ni urefu wa pembejeo na $k$ ni urefu wa juu wa neno la kipande. Wanapendekeza LinMaxMatch, algorithm mpya inayofikia utata wa wakati wa mstari $O(n)$ kwa uchanganuzi wa neno moja, na algorithm iliyounganishwa ya Neno la Kipande wa Mwisho-hadi-Mwisho (E2E) kwa maandishi ya jumla.

2. Usuli & Kazi Inayohusiana

Uchanganuzi wa neno la WordPiece, kama inavyotumika katika BERT, unajumuisha hatua mbili: (1) kutayarisha maandishi kuwa maneno kulingana na nafasi nyeupe na alama za uakifishaji, na (2) kutumia algorithm ya MaxMatch kwa kila neno dhidi ya msamiati uliowekwa. MaxMatch, pia inayotumika katika mgawanyiko wa maneno ya Kichina, huchagua kwa kurudia kiambishi kirefu zaidi cha mfuatano uliobaki unaolingana na neno la kipande katika msamiati.

Algorithm za ufanisi za awali zilikuwa na kikomo cha $O(n^2)$ au $O(nk)$. Kipengele $k$ kina tatizo kwani misamiati inaweza kuwa na maneno marefu ya kipande (mfano, "supercalifragilisticexpialidocious"). Mchango wa karatasi hii upo katika kuondoa kabisa kipengele hiki kinachotegemea msamiati.

3. Algorithm ya LinMaxMatch

3.1 Wazo la Msingi & Ushauri

LinMaxMatch imeongozwa na algorithm ya kulinganisha mfuatano ya Aho-Corasick. Ufahamu muhimu ni kuchukulia msamiati kama seti ya muundo na neno la pembejeo kama maandishi. Kwa kuhesabu awali miundo ya data ya usaidizi kwenye mti wa msamiati (trie), algorithm inaweza kuepuka kurudi nyuma wakati wa kulinganisha, ambayo ndio chanzo cha utata wa quadratic katika MaxMatch ya kawaida.

3.2 Miundo ya Data: Trie, Viungo vya Kushindwa, na Matokeo ya Kushindwa

Algorithm hutumia miundo mitatu ya msingi iliyojengwa kutoka kwa msamiati wakati wa awamu ya utayarishaji wa nje ya mtandao:

• Trie: Mti wa kawaida wa kiambishi ambapo kila nodi inawakilisha herufi na njia kutoka mzizi zinawakilisha maneno ya kipande ya msamiati.
• Kiungo cha Kushindwa (kama Aho-Corasick): Kwa nodi inayowakilisha mfuatano $s$, kiungo chake cha kushindwa kinaelekeza kwenye nodi inayowakilisha kiambishi sahihi kirefu zaidi cha $s$ ambacho pia ni kiambishi cha neno fulani la kipande katika msamiati. Hii inaruhusu algorithm "kushindwa kwa ufanisi".
• Matokeo ya Kushindwa: Ongezeko jipya. Wakati wa kuvuka kutoka nodi kupitia kiungo chake cha kushindwa, algorithm inaweza "kutoa" neno moja au zaidi la kipande ambalo limefananishwa na kumalizika kwenye nodi hiyo. Orodha hii imehesabiwa awali na kuhifadhiwa.

3.3 Uelekezaji wa Algorithm

Kwa neno la pembejeo la urefu $n$, algorithm inachakata herufi kutoka kushoto kwenda kulia kwa mpito mmoja. Inadumisha nodi ya sasa kwenye mti wa trie. Kwa kila herufi mpya:

1. Jaribu kufuata ukingo unaolingana kutoka nodi ya sasa.
2. Ikiwa imefanikiwa, nenda kwenye nodi ya mtoto. Ikiwa nodi hii ni sehemu ya mwisho ya neno la kipande la msamiati, rekodi kama mechi inayowezekana.
3. Ikiwa hakuna ukingo unaolingana, fuata kiungo cha kushindwa cha nodi ya sasa. Kusanya maneno yoyote ya kipande yaliyohifadhiwa kwenye orodha inayohusishwa ya "matokeo ya kushindwa". Kisha, jaribu tena kulinganisha herufi ile ile ya pembejeo kutoka nodi mpya.

Mchakato huu unahakikisha kila herufi inachakatwa mara moja tu, ikihakikisha wakati wa $O(n)$.

4. Uchanganuzi wa Neno la Kipande wa Mwisho-hadi-Mwisho (E2E)

Kwa uchanganuzi wa sentensi kamili au hati, waandishi wanapendekeza kuunganisha hatua ya utayarishaji wa awali (kugawanya kwa nafasi nyeupe/alama za uakifishaji) na LinMaxMatch kuwa algorithm moja, iliyounganishwa. Algorithm hii ya E2E WordPiece pia inafanya kazi kwa wakati wa mstari ukilinganishwa na urefu wa jumla wa maandishi, ikiepuka mzigo wa hatua tofauti. Inachanganya kwa ujanja ugunduzi wa mpaka na kulinganisha kwa neno la kipande ndani ya mfumo mmoja wa uvuvio wa trie.

5. Matokeo ya Majaribio & Utendaji

Karatasi inawasilisha viwango vya kulinganisha vinavyoshawishi vya utekelezaji wao dhidi ya maktaba mbili zinazotumika sana: HuggingFace Tokenizers na TensorFlow Text.

Matokeo yanaonyesha kuwa faida ya kinadharia ya $O(n)$ inabadilika kuwa mafanikio makubwa ya utendaji wa ulimwenguni halisi, hasa kwa maandishi marefu au katika mazingira yanayohitajia ucheleweshaji mdogo kama vile utambuzi wa simu.

6. Ufahamu Muhimu & Uchanganuzi

Ufahamu wa Msingi

Mafanikio ya msingi ya karatasi hii sio tu kichanganuzi cha neno cha kasi zaidi; ni utambuzi rasmi wa uchanganuzi wa neno kama tatizo la kulinganisha mfuatano linaloweza kutatuliwa na nadharia ya zamani ya automata. Kwa kuibadilisha MaxMatch ya WordPiece kutoka kwa utafutaji wa tamaa wa kawaida kuwa tofauti ya Aho-Corasick, waandishi wanavuka pengo la miongo kadhaa kati ya sayansi ya kompyuta ya kinadharia na uhandisi wa NLP unaotumika. Hii inakumbusha jinsi karatasi ya CycleGAN ilivyobadilisha tafsiri ya picha kuwa tatizo la kujifunza la kupingana lenye mzunguko thabiti, na kuunda dhana mpya.

Mtiririko wa Mantiki

Hoja hii ina mantiki kamili: 1) Tambua kikwazo (utata wa $O(n^2)$/$O(nk)$). 2) Pata ushauri kutoka kwa algorithm iliyothibitishwa, bora (Aho-Corasick). 3) Irekebishe kwa vikwazo maalum vya MaxMatch (haja ya kutoa maneno yote ya kipande yaliyolinganishwa, sio uwepo tu). 4) Tambulisha miundo mpya ya data (Matokeo ya Kushindwa) kushughulikia vikwazo hivi. 5) Panua suluhisho kwenye mfumo mzima (E2E). Mtiririko kutoka tatizo hadi ushauri hadi marekebisho hadi ujumla ni utafiti bora unaotumika.

Nguvu & Mapungufu

Nguvu: Hakikisho la $O(n)$ ni la nadharia zuri na imethibitishwa kivitendo. Gharama ya utayarishaji wa awali ni mzigo wa wakati mmoja. Athari kwenye NLP ya simu/kingo inaweza kuwa kubwa, kama ilivyoelezwa na waandishi na kusaidishwa na mienendo katika utafiti wa AI kwenye kifaa kutoka taasisi kama Google AI.

Mapungufu/Uachaji: Karatasi inagusa kidogo lakini haichambui kwa kina mzigo wa kumbukumbu kwa trie iliyoboreshwa (viungo vya kushindwa & matokeo). Kwa misamiati mikubwa sana (mfano, mifano ya lugha nyingi), hii inaweza kuwa kubwa. Zaidi ya hayo, kiwango cha kulinganisha, ingawa kinashangaza, ni dhidi ya utekelezaji maalum. Ulinganisho dhidi ya tofauti zingine zilizoboreshwa za MaxMatch (mfano, kutumia safu za kiambishi) ungeimarisha madai.

Ufahamu Unaotumika

Kwa wataalamu wa NLP: Pima mara moja ucheleweshaji wa uchanganuzi wako wa neno. Ikiwa ni zaidi ya 1-2% ya wakati wako wa jumla wa utambuzi, hasa kwa programu za mtiririko au za simu, kupitisha algorithm kama LinMaxMatch ni ubora wa faida kubwa. Kwa watafiti: Kazi hii inafungua mlango. Je, njia zinazofanana za msingi wa automata zinaweza kuboresha Usimbaji wa Jozi ya Byte (BPE) au SentencePiece? Wazo la msingi—kubadilisha kurudi nyuma na mabadiliko ya hali yaliyohesabiwa awali—linatumika kwa upana kwa algorithm zingine za mgawanyiko wa tamaa katika NLP.

7. Maelezo ya Kiufundi & Uundaji wa Hisabati

Kiini cha LinMaxMatch kinaweza kuwekwa rasmi. Acha:

• $V$ = Msamiati, seti ya mifuatano.
• $T$ = Trie iliyojengwa kutoka $V$.
• Kwa nodi ya trie $u$, acha $L(u)$ iwe mfuatano ulioundwa na herufi kutoka mzizi hadi $u$.
• Kitendakazi cha Kushindwa $f(u)$: Nodi $v$ ambayo $L(v)$ ni kiambishi sahihi kirefu zaidi cha $L(u)$ ambapo $v$ pia ni nodi katika $T$.
• Matokeo ya Kushindwa $P(u)$: Seti ya maneno ya kipande ya msamiati $t \in V$ ambapo $t$ ni kiambishi cha $L(u)$ na kuna nodi $w$ kwenye njia kutoka mzizi hadi $f(u)$ (au $u$ yenyewe) ambapo $L(w) = t$. Hii imehesabiwa awali kwa nodi zote.

Uchanganuzi wa neno wa mfuatano wa pembejeo $S[1..n]$ unaendelea kwa kudumisha nodi ya sasa $u$ (mwanzoni mzizi) na faharasa $i$. Wakati $i \leq n$:

1. Ikiwa kuna mtoto $v$ wa $u$ na lebo ya ukingo $S[i]$, weka $u = v$, $i = i+1$. Ikiwa $u$ inaashiria mwisho wa neno la kipande la msamiati, andika.
2. Vinginevyo, toa maneno yote ya kipande katika $P(u)$. Weka $u = f(u)$. Usiongeze $i$. Ikiwa $u$ ni mzizi na hakuna mtoto anayelingana na $S[i]$, basi $i = i+1$ (shughulikia herufi zisizojulikana).

Utata wa $O(n)$ wa kitanzi huu ni wazi, kwani $i$ ama huongezeka au $u$ hufuata viungo vya kushindwa, ambavyo vinaweza kusawazishwa kuwa mara kwa mara kwa kila hatua.

8. Mfumo wa Uchanganuzi: Uchunguzi wa Kesi

Hali: Kuboresha uchanganuzi wa neno kwa msaidizi wa sauti wa wakati halisi kwenye simu. Mfumo wa sasa unatumia kichanganuzi cha kawaida cha WordPiece kutoka kwa maktaba maarufu.

Utumizi wa Mfumo:

1. Kipimo cha Msingi: Profaili inaonyesha uchanganuzi wa neno unatumia ~15ms kwa kila swali, ambayo ni 12% ya ucheleweshaji wa jumla wa mfumo (125ms). Lengo ni <100ms.
2. Uchanganuzi wa Kikwazo: Maswali mara nyingi ni marefu (sentensi zilizosemwa). Kipengele $O(nk)$ ni muhimu kwa sababu msamiati una maneno ya kiufundi yaliyochanganywa.
3. Ubunifu wa Suluhisho: Badilisha kichanganuzi cha neno na LinMaxMatch. Gharama ya wakati mmoja ya kujenga trie iliyoboreshwa na viungo/matokeo ya kushindwa inakubalika wakati wa utekelezaji wa mfano.
4. Matokeo Yanayotarajiwa: Kulingana na kasi ya 5-8x ya karatasi, wakati wa uchanganuzi wa neno unapaswa kupungua hadi ~2-3ms, na kupunguza ucheleweshaji wa jumla hadi ~112ms, hatua thabiti kuelekea lengo. Hakikisho la wakati wa mara kwa mara pia linaboresha utabiri wa ucheleweshaji.

Uchunguzi huu wa kesi unaonyesha jinsi sifa za kinadharia za algorithm zinashughulikia moja kwa moja vikwazo vya vitendo katika mifumo ya kisasa ya AI.

9. Mtazamo wa Matumizi & Mwelekeo wa Baadaye

Matokeo ya uchanganuzi wa neno wenye ufanisi, wa wakati wa mstari yanaenea zaidi ya BERT:

• AI ya Kwenye Kifaa & Kingo: Kadiri mifano kama usanifu kama GPT inavyochujwa kwa ajili ya simu, kila millisecond iliyookolewa katika utayarishaji wa awali huongezeka. Kazi hii ni msingi kwa kizazi kijacho cha programu za NLP zinazoweza kujibu na kufanya kazi nje ya mtandao.
• Uchanganuzi wa Neno wa Mtiririko: Kwa tafsiri ya wakati halisi au maelezo ya moja kwa moja, utata wa $O(n)$ unahakikisha utendaji unaotabirika. Kazi ya baadaye inaweza kuchunguza uchanganuzi wa neno unaoongezeka kwa mitiririko isiyo na kikomo.
• Lugha Nyingi & Misamiati Mikubwa: Kuongeza ukubwa kwa misamiati yenye maneno ya kipande 1M+ katika lugha 100+. Utafiti unahitajika kuboresha kumbukumbu ya miundo iliyohesabiwa awali, labda kwa kutumia trie zilizobanwa au njia za takriban.
• Unganisho na Usanifu wa Mfano: Je, uchanganuzi wa neno unaweza kujifunza kwa sehemu au kuunganishwa na safu ya kwanza ya transformer? "Uchanganuzi wa Neno wa Nguvu" kulingana na muktadha bado ni changamoto wazi, lakini algorithm za msingi zenye ufanisi kama hii ni sharti la uchunguzi kama huo.

10. Marejeo

1. Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. NAACL-HLT.
2. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Communications of the ACM.
3. Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL.
4. Wolf, T., et al. (2020). HuggingFace's Transformers: State-of-the-art Natural Language Processing. arXiv preprint arXiv:1910.03771.
5. Google. (2020). TensorFlow Text. https://www.tensorflow.org/text
6. Brown, T. B., et al. (2020). Language Models are Few-Shot Learners. NeurIPS.
7. Zhu, J.-Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. ICCV. (Imetajwa kama mfano wa ubadilishaji wa dhana).