پردازش زبان های طبیعی

ریخت‌شناسی و گذردهنده‌های حالت متناهی

chortkeh-nlp — Fri, 24 Aug 2007 15:18:18 GMT

ریخت‌شناسی¹ و گذردهنده‌های حالت متناهی²

پویش³ یعنی با گرفتن ورودی، یک ساختار خروجی را بر اساس قواعد موجود بدهد. به عمل بیرون‌آوردن ریشه اصلی یک واژه؛ ریشه‌یابی⁴ گویند. ریخت‌شناسی به علم شناختن اجزای معنی‌دار از یک واژه گویند که آن واژه را می‌سازد؛ به این اجزای معنی‌دار تکواژ یا واژک⁵ گویند. در کل، دو نوع ریخت‌شناسی وجود دارد. نوع اوّل آن را؛ که بیشتر در زبان‌های لاتین مانند انگلیسی مرسوم است؛ ریخت‌شناسی الحاقی⁶ گویند. گونۀ دیگر را ریخت‌شناسی غیرالحاقی می‌گویند. یکی از انواع ریخت‌شناسی غیرالحاقی، ریخت‌شناسی الگویی⁷ و یا ریشه و الگویی⁸ است؛ که در زبان‌هایی مانند عربی، عبری و فارسی این نوع از ریخت‌شناسی کاربرد بسیاری دارد. در ریخت‌شناسی الحاقی تمام اشکال یک واژه در یک کلمه نمود پیدا می‌کند در حالی‌که در ریخت‌شناسی غیرالحاقی، ممکن‌ست که شکل یک واژه در سه مکان جدا از هم در یک جمله پیدا شوند. به زبان‌هایی مانند زبان ترکی که یک واژه آن ممکن‌ست از تعداد بیشتر از یک وند تشکیل شده باشد؛ زبان‌های ترکیبی⁹ گویند. دو نوع روش در ریخت‌شناسی واژه‌‌ها وجود دارد. روش اوّل روش خمش¹⁰ است که از ترکیب یک واژه با اجزای دستوری دیگری، واژه‌ای جدید در همان نوع و ردۀ واژۀ قبلی ایجاد می‌گردد. به عنوان مثال علامت جمع «ها» در فارسی که با اضافه‌کردنش به هر اسمی یک اسم جدید به وجود می‌آید؛ مثلاً واژۀ کتاب با اضافه‌شدن «ها» به کتاب‌ها تبدیل می‌شود که در این صورت، هم کتاب از نوع دستوری اسم است و هم کتاب‌ها. روش دوم، روش اشتقاق¹¹ است. در اشتقاق با افزودن یک جز دستوری به یک واژه، یک واژه در رده جدیدی به وجود می‌آید. به عنوان مثال اگر تکواژِ «-ِش» را به واژۀ مصدری «کن» اضافه کنیم، واژۀ کنش به وجود می‌آید که واژه جدید دیگر از نوع مصدر نیست و یک اسم است.

برای ساختن یک پویشگر ریخت‌شناسی واژگانی به اطلاعات و اجزای زیر نیاز داریم:

1- واژه‌نامه‌ای¹² که حداقل دارای ریشه‌های واژگان و نیز وندهای موجود در زبان مورد نظر باشند. در ضمن باید اطلاعات مختصری از قبیل نوع واژه در آن زبان – مثلاً اسم، فعل، صفت و ... – در این واژه‌نامه موجود باشد.

2- قواعد ریخت‌شناسی¹³ موجود در هر زبان.

3- قواعد املایی¹⁴ در زبان مانند تغییراتی که در روند اشتقاق و ترکیب در واژگان زبان صورت می‌گیرد.

پویش ریخت‌شناسانه با استفاده از گذردهنده‌های حالت متناهی

چهار روش معمول برای تفکر در مورد گذردهنده‌های حالت متناهی وجود دارد:

· گذردهنده‌های حالت متناهی به عنوان تشخیص‌دهنده که در صورتی که رشته‌ای جز یک زبان بود آن را قبول می‌کند و در غیر این صورت آن رشته را نمی‌پذیرد.

· گذردهنده‌های حالت متناهی به عنوان مولد که ماشینی‌ست که تعدادی رشته خروجی و خروجی آری| نه تولید می‌نماید.

· گذردهنده‌های حالت متناهی به عنوان گذردهنده یا مترجم که رشته‌ای را از ورودی می‌گیرد و رشته‌ای دیگر را به خروجی می‌دهد.

· گذردهنده‌های حالت متناهی به عنوان ارتباط‌نما که ارتباط موجود را بین مجموعه‌ای از رشته‌های ورودی پیدا می‌کند.

ترکیب قواعد ریخت‌شناسی و املایی

برای ترکیب قواعد ریخت‌شناسی و املایی، می‌توان از یک گذردهنده‌های حالت متناهی بینابینی استفاده کرد که این گذردهنده مورد بررسی قواعد املایی قرار می‌گیرد و به خروجی فرستاده می‌شود. البته پویش‌کردن با گذردهنده‌های حالت متناهی کار بسیار پیچیده‌تری از ترکیب و اشتقاق است؛ زیرا در پویش امکان ایجاد ابهام¹⁵ وجود دارد به عنوان مثال، واژه back در انگلیسی هم می‌تواند فعل باشد، هم اسم و هم صفت که این باعث ایجاد ابهام در زنجیره پویش می‌شود.

گذردهنده‌های حالت متناهی بدون نیاز به واژه‌نامه: ریشه‌یاب پورتر¹⁶

برای استفاده از گذردهنده‌های حالت متناهی بدون استفاده از یک واژه‌نامه بسیار بزرگ می‌توان از بازیابی اطلاعات¹⁷ استفاده کرد.

پی‌نوشت:

· مطالب فوق از فصل سوم کتاب پردازش مکالمات و زبان‌های طبیعی نوشته جورافسکی تهیه شده است.

· برای یافتن تعاریف دقیق گذردهنده و انواع آتاماتون‌هایی که در این مباحث به آن‌ها اشاره می‌شود می‌توانید به این کتاب مراجعه نمایید.

1. Morphology

2. Finite-State Transducers(FST)

3. Parsing

4. Stemming

5. Morpheme

6. Concatenative

7. Templatic

8. Root and Pattern

9. Agglutinative

10. Inflection

11. Derivation

12. Lexicon

13. Morphotactics

14. Orthographic

15. Ambiguity

16. Porter

17. Information Retrieval (IR)

عبارات منظم و آتاماتا

chortkeh-nlp — Fri, 24 Aug 2007 08:14:05 GMT

عبارات منظم

عبارات منظم در واقع یک زبان برای نشان‌دادن هر چه بهتر رشته‌های واژگانی‌اند. اوّلین بار به‌سال 1956 کلين¹ عبارات منظم را ابداع نمود و تاکنون کاربران زیادی در امور مختلف از عبارات منظم استفاده می‌کنند. برای هر عبارت منظم باید یک الگو² و یک محتوای متنی³ داشته باشیم.

در زبان عبارات منظم تعدادی علامت خاص به نام لنگر⁴ است که نشان‌دهنده خواصی در یک الگوی رشته‌ای است. به عنوان مثال، علامت \b یک لنگر است که نشان‌دهنده پایان یک محدوده واژگانی‌ست. در عبارات منظم عملگرها دارای اولویت‌های مخصوص به خود هستند.

اولویت اول: کمانک ()

اولویت دوم: شمارنده‌ها *؟+{}

اولویت سوم: تواترها و سپرها مثل \b و $

اولویت چهارم: علایم فصل |

یکی از مهم‌ترین کاربردهای عبارات منظم در جایگزینی الگوهای رشته‌ای است که این کاربرد در ماشین الیزا به خوبی پیاده‌سازی شده بود.

آتاماتای حالت متناهی

آتاماتای حالت متناهی در واقع روشی ریاضی برای پیاده‌سازی عبارات منظم است و عبارات منظم هم یک فرازبان است برای پیاده‌سازی زبان‌های منظم که می‌توان یک رابطه سه‌گانه بین این سه قائل شد.

یک آتاماتون حالت متناهی در کل با پنج مولفه صوری تعریف می‌شود:

Q: مجموعه‌ای از حالت‌های متناهی در ماشین.

∑: مجموعه‌ای از حالات محدود در ورودی.

q₀: حالت اوّلیه ماشین.

F : مجموعه‌ای از حالت نهایی که زیرمجموعه Q است.

تابع گذر سیگمای q و i.

زبان‌های صوری

زبان‌های صوری هم برای تولید رده خاصی از رشته‌ها یا یک زبان و نیز برای تشخیص پذیرفتن رشته‌ای در یک زبان به کار می‌رود. زبان‌های صوری از تعدادی محدود از علائم تشکیل می‌شوند که به این علائم الفبا می‌گویند. البته زبان‌های صوری تفاوت‌های بسیاری با زبان‌های طبیعی دارند ولی برای پیاده‌سازی و الگو قرار دادن قسمتی از زبان‌های طبیعی بسیار به کار می‌روند. دستور زبان مولد⁵ در واقع نشان‌دهنده دستور زبان یک زبان صوری است. ریشه اصلی این واژه از آتاماتونی‌ست که برای تعریف زبانی که همه رشته‌های موجود در آن زبان را تولید می‌نماید؛ گرفته شده است.

نوع دیگری از آتاماتای حالت متناهی وجود دارد که به آن آتاماتای حالت متناهی غیرقطعی⁶ گویند که در هر حالت به ازای یک ورودی ماشین ممکن است به چند حالت مختلف برود و یا به هیچ حالتی نرود و یا از طرفی دیگر بدون تغییر در ورودی یا بدون توجه به ورودی ماشین از حالتی به حالت دیگری برود.

برای جست‌و‌جو در یک ماشین حالت متناهی غیرقطعی می‌شود از روش‌های موازی استفاده کرد. به همین منظور الگوریتم‌های جستجوی عمقی یا جستجوی سطحی و ساختمان داده‌ای پشته یا صف به عنوان حافظه کمکی برای این کار بسیار مناسب است. برای مسایل مشکل‌تر می‌توان از الگوریتم‌های برنامه‌سازی پویا و A^* استفاده نمود. البته برای هر ماشین حالت متناهی غیرقطعی، می‌توان ماشین قطعی معادلش را با الگوریتم‌های بسیار ساده‌اش به دست آورد.

زبان‌های منظم و ماشین‌های حالت متناهی

زبان‌های منظم را می‌توان با استفاده از FSAها پیاده‌سازی کرد و هر زبانی که در یک FSA پیاده می‌شود، لاجرم یک زبان منظم است.

تعریف زبان منظم به این صورت است که به ازای یک الفبای ∑، به ازای هر حرف a که عضوی از آن است؛ {a} یک زبان منظم است و نیز الحاق، اشتراک و نیز بسط کلین یا ستاره‌ای⁷ آن نیز یک زبان منظم خواهد بود. زبان‌های منظم در ضمن نسبت به اشتراک، تفاضل، معکوس خود و نیز متمم‌گیری بسته‌اند.

پی‌نوشت:

*مطالب فوق از فصل دوم کتاب پردازش زبان‌ها و مکالمات طبیعی نوشتۀ مارتین و جورافسکی است.

*برای یافتن جزئیات بیشتری در مورد زبان‌ها و عبارات منظم و ماشین‌های حالت متناهی می‌توانید به کتاب‌های نظریه زبان‌ها و ماشین‌ها از جمله کتابی با هین نام نوشته لینز مراجعه کنید. در ضمن کتاب لینز را آقای دکتر صراف‌زاده به فارسی ترجمه کرده‌اند.

*از نظرات، انتقادات و پیشنهادهای شما عزیزان استقبال می‌شود.

1. Kleene

2. Pattern

3. corpus

4. anchor

5. generative grammar

6. NFSA (Nondeterministic FSA)

7. Kleene(star) closure

پردازش واژگان

chortkeh-nlp — Fri, 24 Aug 2007 08:10:18 GMT

واژگان

در کل هر قسمتی از زبان، لاجرم از مجموعه‌ای از واژگان ساخته شده است و مسایلی مهمی فراخور آن قرار می‌گیرند. از مسایل مهم در دایره پردازش واژگانی می‌توان به املای کلمه، ریخت‌شناسی و تلفظ و نیز به مسایل واژگان در دنیای واقع مانند بازشناسی خودکار گفتار¹ و تبدیل نوشتار به گفتار و خطایابی املایی²؛ اشاره کرد.

روش‌‌ها و آتاماتای بسیاری در مورد پردازش واژگانی وجود دارد که از این امور می‌توان به چهار ماشین آتاماتای متناهی³، عبارات منظم، گذردهنده‌های متناهی⁴ و الگوی مخفی مارکوف⁵ اشاره کرد. روش n-gram هم برای یافتن تواتر واژگانِ یک متن، روشی مرسوم است.

پی‌نوشت:

1. Automatic Speech Recognition (ASR)

2. Text-To-Speech Synthesis (TSS)

3. Finite-State Automata (FSA)

4. Finite-State Transducers (FST)

5. Hidden Markov Model (HMM)

پردازش زبان های طبیعی -1-

chortkeh-nlp — Thu, 23 Aug 2007 20:39:18 GMT

پردازش زبان‌ها و مکالمات طبیعی یکی از اموری‌ست که با ورود فناوری رایانه‌ای به زندگی بشر مورد توجه بسیاری از دانشمندان قرار گرفته است. حتی اندیشه‌ای که تورینگ از ماشین هوشمند خود و تعریفی که او از هوش مصنوعی داشت، در مرحله اول مربوط به پردازش زبان‌های طبیعی می‌شد. حتی تلاش‌های بسیاری توسط بشر برای پیگیری این امر صورت گرفته بود. به عنوان مثال ماشین لیزا از این تلاش‌ها حاصل می‌شد که ماشینی بود که با تایپ از راه دور با یک انسان، جملات او را پردازش می‌کرد و جوابی درخور به او می‌داد.

از لحاظ رده‌بندی، علم پردازش زبان طبیعی از شاخه‌های هوش مصنوعی به حساب می‌آید و خود این علم به پنج رده مختلف تقسیم‌بندی می‌شود:

1- آوا شناسی و صدا شناسی (phonetics and phonology) که به تشخیص آواها و صداها و بازشناسی گفتار می‌پردازد.

2- ریخت‌شناسی (morphology) که به ساختار‌های کلمات و ریشه‌یابی واژگان می‌پردازد.

3- نحو (syntax) که به ارتباط کلمات به همدیگر و مباحث دستوری آن‌ها در گروه‌ها و جملات می‌پردازد.

4- معناشناسی (semantics) که به ارتباطات معنایی کلمات ‌می‌پردازد.

5- عمل‌گرایی (pragmatics) که کاربردهای زبان برای رساندن یک مطلب به مخاطب یا مخاطبان، در حالت عملی و یا در نوشتار و گفتار طبیعی می‌پردازد.

6- مباحثه (discourse) که به ارتباطات کلی یک زبان فرای یک یا چند جمله خاص می‌پردازد.

بر همین مبنا الگوریتم‌های بسیاری برای رسیدن به برنامه‌هایی هوشمندتر توسط دانشمندان و متخصصین علوم رایانه، زبان‌شناسی و ریاضیدانان، طراحی و پیشنهاد شده است. به عنوان مثال الگوریتم‌های الگوی مارکوف و الگوی مخفی مارکوف و نیز تلاش‌های چندین ساله دانشمند ارجمند نوام چامسکی در این راه، نمونۀ خوبی برای این امور است. روز به روز بر پیشرفت‌های دانشمندان در این امر افزوده می‌شود و دانشمندان در سراسر دنیا سعی بر بهبود روش‌ها و پیاده‌سازی این روش‌ها در زبان‌های بومی خودشان هستند.