2012-04-23 21 views
8

मैं बस सोच रहा हूं कि कंप्यूटिंग ओवरहेड पर कंप्यूटिंग करने पर विचार करने वाले एन-ग्राम्स (एन> 3) (और उनकी घटना आवृत्ति) का उपयोग क्या है। क्या कोई ऐसे अनुप्रयोग हैं जहां बिग्राम या ट्रिग्राम बस पर्याप्त नहीं हैं?एन-ग्राम्स (एन> 3) कब बड़े बिग्राम या ट्रिग्राम के विपरीत महत्वपूर्ण हैं?

यदि हां, तो एन-ग्राम निष्कर्षण में अत्याधुनिक क्या है? कोई सुझाव? मैं निम्नलिखित के बारे में पता कर रहा हूँ:

+1

यह शायद जानकारी पौराणिक कथा के स्तर की तलाश में है तक पहुँचने नहीं है, लेकिन Pycon 2012 से इस वीडियो को एक बहुत अच्छा अजगर में कंप्यूटिंग एन-ग्राम की मूल बातें समझा (और उन्हें प्रयोग एक खोज इंजन का निर्माण करने) का काम करता है: http://pyvideo.org/video/715/building-a-python-based-search-engine। किसी और के लिए जो इस सवाल पर ठोकर खाती है। – Wilduck

+0

कंप्यूटिंग ngrams के "कम्प्यूटेशनल ओवरहेड" नगण्य है: आप इसे अपने कॉर्पस के माध्यम से एक ही पास में कर सकते हैं। यहां तक ​​कि उच्च-आदेश ngrams भंडारण भी एक बड़ा सौदा नहीं है। वास्तविक लागत यह है कि बड़े एन के लिए, आपको दुर्लभता समस्याओं को दूर करने के लिए एक बड़ा और बड़ा कॉर्पस चाहिए। – alexis

+0

@alexis: यदि आप अधिक जानकारी प्रदान कर सकते हैं तो यह बहुत अच्छा होगा। विशेष रूप से, स्पार्सिटी समस्याओं से संबंधित कुछ, कोई भी शोध जो "एन-ग्राम कंप्यूटिंग के कम्प्यूटेशनल ओवरहेड नगण्य है" दिखाता है? धन्यवाद। – Legend

उत्तर

3

मैं यहाँ सूचीबद्ध टैग की एक अच्छा सौदा के साथ परिचित नहीं हूँ, लेकिन, n- ग्राम (अमूर्त अवधारणा) अक्सर सांख्यिकीय मॉडल से संबंधित उपयोगी होते हैं। (विशेष रूप से पीपीएम किस्म)

  • संपीड़न एल्गोरिदम जहां ग्राम की लंबाई कितना डेटा विशिष्ट संदर्भों प्रदान करने के लिए उपलब्ध है पर निर्भर करता है: नतीजतन, यहां कुछ अनुप्रयोगों जो केवल Bigrams तक ही सीमित हैं नहीं और Trigrams है।
  • लगभग स्ट्रिंग मिलान (आनुवंशिक अनुक्रम मिलान के लिए जैसे ब्लास्ट)
  • भविष्य कहनेवाला मॉडल (जैसे नाम जनरेटर)
  • भाषण मान्यता (स्वनिम ग्राम वर्तमान स्वनिम के दौर से गुजर मान्यता के लिए संभावनाओं की संभावना मूल्यांकन करने में मदद करने के लिए इस्तेमाल कर रहे हैं)

वे मेरे सिर के ऊपर से हैं, लेकिन on Wikipedia सूचीबद्ध हैं।

जहां तक ​​"अत्याधुनिक" एन-ग्राम निष्कर्षण, कोई विचार नहीं है। एन-ग्राम "निष्कर्षण" एन-ग्राम शैली मॉडलिंग के लाभों को बनाए रखने के दौरान कुछ प्रक्रियाओं को तेज करने का एक प्रयास है। संक्षेप में, "अत्याधुनिक" इस बात पर निर्भर करता है कि आप क्या करने की कोशिश कर रहे हैं। यदि आप अस्पष्ट मिलान या अस्पष्ट समूह को देख रहे हैं, तो यह इस बात पर निर्भर करता है कि आप किस प्रकार का डेटा मिलान/समूह कर रहे हैं। के बारे में उच्च आदेश एन-ग्राम में सोचने के लिए एक unnormalized autocorrelation function के लिए कनेक्शन बनाने के द्वारा किया जा सकता है (उदाहरण के लिए सड़क के पते पहला नाम से फजी मैच के लिए बहुत अलग होने जा रहे हैं।)

3

एक (अपरंपरागत) जिस तरह से, सहसंबंध यानी खुद के साथ एक सिग्नल का। एक 2 ग्राम कॉर्पस एक शब्द के सहसंबंध को एक "शब्द" के साथ मापता है - एक शब्द के अंतराल, जबकि 3-ग्राम हमें "समय" के लिए जानकारी दे सकता है-दो चरणों के अंतराल। उच्च आदेश एन-ग्राम किसी विशेष कॉर्पस की संभाव्यता वितरण का एक उपाय देते हैं (चाहे यह मोबी डिक या मानव डीएनए हो)। इस तरह, यदि एन-ग्राम शून्य अपेक्षित मूल्य से अलग है, तो एन के उस मान के लिए उपयोगी सांख्यिकीय जानकारी है।

2

Kaganar के जवाब के अलावा:

(शैलियों लेखन, या, एक पाठ के युग का पता लगाने की कोशिश कर के आधार पर उदाहरण के लिए, लेखक की रूपरेखा) stylometric analysis किसी भी तरह का उथले वाक्यात्मक पार्सिंग के लिए लंबे समय तक एन-ग्राम की आवश्यकता होगी। आम तौर पर इस तरह के तरीकों गहरी वाक्यात्मक पार्सिंग PCFG, TAG के आधार पर, आदि से पूरित कर रहे हैं

3

मुझे नहीं लगता कि आपके सवाल का बहुत सही उत्पन्न किया जाता है: Ngrams एक उपकरण, नहीं एक समस्या को हल किया जा करने के लिए कर रहे हैं, तो कोई " कला की स्थिति "ngrams में।जैसा कि @ हुक ने बताया, एक एनजीआरएम एक प्रकार का ऑटो-सहसंबंध समारोह (या "स्वैच्छिक कार्य") है। तो आप वास्तव में क्या जानना चाहते हैं कि क्या ऐसी कोई समस्या है जिसके लिए कला समाधान की स्थिति में लंबे समय तक नागाम शामिल हैं।

फिटिंग वित्तीय या मौसम मॉडल, या भाषण मान्यता जैसे संख्यात्मक अनुप्रयोगों के लिए, आप निश्चित रूप से आयाम > 3 के वैक्टर का उपयोग करेंगे। उदाहरण के लिए, autoregressive छिपे हुए मार्कोव मॉडल पिछले n माप, जहां n मामूली बड़ा हो सकता है अगर अतीत राज्यों भविष्य की भविष्यवाणी के लिए प्रासंगिक हैं की एक piecewise समारोह फिट।

लेकिन आपके सभी उदाहरण शब्द ngrams की चिंता करते हैं, और मैं उस डोमेन में उपयोगी होने के लिए n> 3 किसी भी काम के बारे में नहीं सोच सकता। मुझे नहीं लगता कि यह कम्प्यूटेशनल लागत का सवाल है या पर्याप्त प्रशिक्षण डेटा ढूंढ रहा है: भाषा में सतही ऑटो-सहसंबंध 3 शब्दों के बाद बाहर निकलता प्रतीत होता है। यादृच्छिक उदाहरण: this article ngram- आधारित सूचना सामग्री के संदर्भ में ज़िफ के कानून को दोबारा परिभाषित करने का प्रयास करता है। वे एन 4 तक मानते हैं, लेकिन ट्रिग्राम गणनाओं के लिए उच्चतम समग्र सहसंबंध प्राप्त करते हैं।

मेरा मतलब यह नहीं है कि n> 3 उपयोगी नहीं है; लेकिन आपका अवलोकन यह है कि यह बहुत अधिक प्रतीत नहीं होता है अच्छी तरह से स्थापित है।

लेकिन ध्यान दें कि एक पाठ में ngrams गिनती की जटिलता कोई मुद्दा नहीं है: आप लंबाई एल के एक tokenized कोष है, तो आप इस तरह कोष के सभी ngrams एकत्र कर पाया:

for i in range(0, L-n): 
     tuple = corpus[i:i+n] 
     ngrams[tuple] += 1 

आप के रूप में इस की आवश्यकता है केवल हे (एल) कदम, यानी देख सकते हैं, यह कोष के आकार पर रेखीय है और साथ n भी नहीं बढ़ता है। तो किसी भी आयाम के ngrams इकट्ठा करना एक गैर मुद्दा है। लेकिन संभावित ngrams जल्दी मशरूम की संख्या। उदाहरण के लिए, यदि आप 32 अक्षर टोकन (अक्षरों और कुछ विराम चिह्नों) को अलग करते हैं, तो 1024 अक्षर बिग्राम हैं लेकिन 1048576 टेट्रैग्राम हैं। अपनी आवृत्ति सारणी को पॉप्युलेट करने के लिए पर्याप्त रूप से खोजने के लिए, आपको तेजी से अधिक टेक्स्ट की आवश्यकता है।

शब्द के लिए ngrams विरलता समस्या और भी बदतर है, न केवल जब से तुम एक बहुत 32 से अधिक विभिन्न शब्द टोकन की क्या ज़रूरत है, लेकिन शब्दावली आकार बढ़ता है (धीरे ​​धीरे) कोष के आकार के साथ: प्रसिद्ध "लंबी पूंछ" संपत्ति । तो अपने डेटा कोई फर्क नहीं पड़ता कि आप कैसे एक बड़े कोष इकट्ठा विरल हो जाएगा (यहां तक ​​कि छोटे n के लिए)। इसके बाद आपको जटिल सांख्यिकीय मॉडल फिट करने की आवश्यकता होगी, जिनकी गणना लागत अलग-अलग ngrams की संख्या पर निर्भर करती है।

नतीजतन, विरलता हमेशा शब्द ngram अनुप्रयोगों में एक मुद्दा (अतः "चौरसाई" आम तौर पर आवश्यक है)। यदि आप "ngram sparsity" google पर हैं तो आपको संदर्भों का एक टन मिलेगा।

0

तुम भी n> 3 भाषा मॉडल का उपयोग कर सकते हैं यदि आपके datset बहुत बड़ी है।

+0

एक टिप्पणी होना चाहिए – Robert