بایگانی برچسب برای: ca vnhca jw

یادگیری ماشین – SVM یا ماشین بردار پشتیبان به زبان ساده

یکی از الگوریتم ها و روشهای بسیار رایج در حوزه دسته بندی داده ها، الگوریتم SVM یا ماشین بردار پشتیبان است که در این مقاله سعی شده است به زبان ساده و به دور از پیچیدگیهای فنی توضیح داده شود.

آشنایی با مفهوم دسته بندی

فرض کنید مجموعه داده ای داریم که ۵۰٪ افراد آن مرد و ۵۰٪ افراد آن زن هستند. این مجموعه داده می تواند مشتریان یک فروشگاه آنلاین باشد. با داشتن یک زیرمجموعه از این داده ها که جنسیت افراد در آن مشخص شده است، می خواهیم قوانینی ایجاد کنیم که به کمک آنها جنسیت بقیه افراد مجموعه را بتوانیم با دقت بالایی تعیین کنیم. تشخیص جنسیت بازدیدکنندگان فروشگاه، باعث می شود بتوانیم تبلیغات جداگانه ای را برای زنان و مردان نمایش دهیم و سودآوری فروشگاه را بالا ببریم . این فرآیند را در علم تحلیل داده، دسته بندی می نامیم .

برای توضیح کامل مسأله، فرض کنید دو پارامتری که قرار است جنسیت را از روی آنها تعیین کنیم، قد و طول موی افراد است . نمودار پراکنش قد و طول افراد در زیر نمایش داده شده است که در آن جنسیت افراد با دو نماد مربع (مرد) و دایره (زن) به طور جداگانه نمایش داده شده است .

SVM-1

 

با نگاه به نمودار فوق، حقایق زیر به سادگی قابل مشاهده است :

  1. مردان در این مجموعه، میانگین قد بلندتری دارند.
  2. زنان از میانگین طول موی بیشتری برخوردار هستند.

اگر یک داده جدید با قد ۱۸۰cm و طول موی ۴cm به ما داده شود، بهترین حدس ما برای ماشینی این شخص، دسته مردان خواهد بود .

بردارهای پشتیبان و ماشین بردار پشتیبان

بردارهای پشتیبان به زبان ساده، مجموعه ای از نقاط در فضای n بعدی داده ها هستند که مرز دسته ها را مشخص می کنند و مرزبندی و دسته بندی داده ها براساس آنها انجام می شود و با جابجایی یکی از آنها، خروجی دسته بندی ممکن است تغییر کند . به عنوان مثال در شکل فوق ، بردار (۴۵,۱۵۰) عضوی از بردار پشتیبان و متعلق به یک زن است . در فضای دوبعدی ،‌بردارهای پشتیبان، یک خط، در فضای سه بعدی یک صفحه و در فضای n بعدی یک ابر صفحه را شکل خواهند داد.

SVM یا ماشین بردار پشتیبان ، یک دسته بند یا مرزی است که با معیار قرار دادن بردارهای پشتیبان ، بهترین دسته بندی و تفکیک بین داده ها را برای ما مشخص می کند.

در SVM فقط داده های قرار گرفته در بردارهای پشتیبان مبنای یادگیری ماشین و ساخت مدل قرار می گیرند و این الگوریتم به سایر نقاط داده حساس نیست و هدف آن هم یافتن بهترین مرز در بین داده هاست به گونه ای که بیشترین فاصله ممکن را از تمام دسته ها (بردارهای پشتیبان آنها) داشته باشد .

چگونه یک ماشین بر مبنای بردارهای پشتیبان ایجاد کنیم ؟

به ازای داده های موجود در مثال فوق، تعداد زیادی مرزبندی می توانیم داشته باشیم که سه تا از این مرزبندی ها در زیر نمایش داده شده است.

 

SVM-2

 

سوال اینجاست که بهترین مرزبندی در این مسأله کدام خط است ؟

یک راه ساده برای انجام اینکار و ساخت یک دسته بند بهینه ، محاسبه فاصله ی مرزهای به دست آمده با بردارهای پشتیبان هر دسته (مرزی ترین نقاط هر دسته یا کلاس) و در نهایت انتخاب مرزیست که از دسته های موجود، مجموعاً بیشترین فاصله را داشته باشد که در شکل فوق خط میانی ، تقریب خوبی از این مرز است که از هر دو دسته فاصله ی زیادی دارد. این عمل تعیین مرز و انتخاب خط بهینه (در حالت کلی ، ابر صفحه مرزی) به راحتی با انجام محاسبات ریاضی نه چندان پیچیده قابل پیاده سازی است .

توزیع غیر خطی داده ها و کاربرد ماشین بردار پشتیبان

اگر داده ها به صورت خطی قابل تفکیک باشند، الگوریتم فوق می تواند بهترین ماشین را برای تفکیک داده ها و تعیین دسته یک رکورد داده، ایجاد کند اما اگر داده ها به صورت خطی توزیع شده باشند (مانند شکل زیر )، SVM را چگونه تعیین کنیم ؟

 

SVM-3

 

در این حالت، ما نیاز داریم داده ها را به کمک یک تابع ریاضی (Kernel functions) به یک فضای دیگر ببریم (نگاشت کنیم ) که در آن فضا، داده ها تفکیک پذیر باشند و بتوان SVM آنها را به راحتی تعیین کرد. تعیین درست این تابع نگاشت در عملکرد ماشین بردار پشتیبان موثر است که در ادامه به صورت مختصر به آن اشاره شده است.

با فرض یافتن تابع تبدیل برای مثال فوق،‌ فضای داده ما به این حالت تبدیل خواهد شد :

 

SVM-4

 

در این فضای تبدیل شده، یافتن یک SVM به راحتی امکان پذیر است .

نگاهی دقیق تر به فرآیند ساخت SVM

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

در شکل زیر داده ها در دو دوسته آبی و قرمز نمایش داده شده اند و خطوط نقطه چین ، بردار های پشتیبان متناظر با هر دسته را نمایش می دهند که با دایره های دوخط مشخص شده اند و خط سیاه ممتد نیز همان SVM است . بردار های پشتیبان هم هر کدام یک فرمول مشخصه دارند که خط مرزی هر دسته را توصیف می کند.

SVM-5

SVM‌ در پایتون

برای استفاده از ماشین بردار پشتیبان در پایتون، توصیه بنده استفاده از کتابخانه یادگیری ماشین پایتون به نام scikitlearn است که تمام کرنل ها و توابع نگاشت را به صورت آماده شده دارد. سه تا تابعSVC , NuSVC , LinearSVC وظیفه اصلی دسته بندی را برعهده دارند . (SVC = Support Vector Classifier) . نمونه ای از دسته بندی با این توابع را در زیر می توانید مشاهده کنید :

 

SVM-6

ماشین بردار پشتیبانی در عمل

برای استفاده از SVM در مورد داده های واقعی ، چندین نکته را باید رعایت کنید تا نتایج قابل قبولی را بگیرید

  1. ابتدا داده ها را پالایش کنید (نقاط پرت ،‌ داده های ناموجود و …..)
  2. داده را عددی و نرمال کنید . این مباحث را در مقالات پیش پردازش داده ها دنبال کنید. به طور خلاصه ، داده هایی مانند جنسیت، رشته تحصیلی و … را به عدد تبدیل کنید و سعی کنید مقادیر همه صفات بین یک تا منهای یک [۱,-۱] نرمال شوند تا بزرگ یا کوچک بودن مقادیر یک ویژگی داده ها،‌ ماشین را تحت تاثیر قرار ندهد .
  3. کرنل های مختلف را امتحان و به ازای هر کدام، با توجه به مجموعه داده آموزشی که در اختیار دارید و دسته بندی داده های آنها مشخص است، دقت SVM را اندازه گیری کنید و در صورت نیاز پارامتر های توابع تبدیل را تغییر دهید تا جواب های بهتری بگیرید. این کار را برای کرنل های مختلف هم امتحان کنید . می توانید از کرنل RBF شروع کنید .

نقاط ضعف ماشین بردار پشتیان

  • این نوع الگوریتم ها، محدودیت های ذاتی دارند مثلا هنوز مشخص نشده است که به ازای یک تابع نگاشت ، پارامترها را چگونه باید تعیین کرد.
  • ماشینهای مبتنی بر بردار پشتیبان به محاسبات پیچیده و زمان بر نیاز دارند و به دلیل پیچیدگی محاسباتی، حافظه زیادی نیز مصرف می کنند.
  • داده های گسسته و غیر عددی هم با این روش سازگار نیستند و باید تبدیل شوند.

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

سخن پایانی

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

ساختار اصلی این نوشتار از روی یک مقاله سایت آنالیتیکزویدیا برداشته شده است و برای دو بخش پایانی مقاله هم از کتاب «داده کاوی پیشرفته : مفاهیم و الگوریتم ها» دکتر شهرابی استفاده شده است .

منبع


آشنایی با ماشین بردار پشتیبان (SVM) – مرور کلی

SVM یک مدل یادگیری نظارت شده است.

پس قبل از این که به سراغ آن برویم باید یک مجموعه داده(Dataset) که از قبل برچسب‌گذاری شده(Labeled) را داشته باشیم.

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

من به دنبال راهی هستم که این ایمیل‌ها را هرچه سریع‌تر تشخیص بدهم(پیدا کنم) و پاسخ آن‌ها را زودتر از بقیه ارسال کنم.

رویکرد اولمن می‌توانم برچسب‌هایی با عنوان‌های: اورژانسی، شکایت و راهنمایی در جیمیل(GMail) خود ایجاد کنم.

اشکال این روش این است که من باید مدتی فکر کنم و همه کلمه‌های کلیدی(Keyword) بالغوه که مشتری‌های عصبانی ممکن است در ایمیل‌های خود استفاده کنند را پیدا کنم. طبیعی است که بعضی از آن‌ها را هم از قلم انداخته شوند. با گذشت زمان هم لیست این کلمه‌ها به احتمال زیاد شلوغ و مدیریت کردن آن‌ها به کار مشکلی تبدیل می‌شود.

رویکرد دوممن می‌توانم از یک الگوریتم یادگیری ماشین نظارت شده استفاده کنم.

قدم اولبه تعدادی ایمیل نیاز دارم.(هرچه بیشتر بهتر)

قدم دومعنوان ایمیل‌های قدم اول رو می‌خوانم و آن‌ها را در یکی از دو گروه «شکایت است» و یا «شکایت نیست» طبقه‌بندی می‌کنم. اینجوری می‌توانم ایمیل‌ها را برچسب ‌گذاری کنم.

قدم سومروی این مجموعه داده، مدلی را آموزش می‌دهم.

قدم چهارمکیفیت یا صحت پیش‌بینی های مدل آموزش داده‌شده را ارزیابی می‌کنم.(با استفاده از روش Cross Validation)

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

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

همچنین باید به این نکته هم توجه داشته باشیم که قدم دوم اهمیت زیادی دارد و دلیلش این است که اگر در شروع کار، ایمیل‌های برچسب‌گذاری نشده را به SVM بدهیم، کار خاصی را نمیتواند انجام دهد.

SVM یک مدل خطی را یاد می‌گیرد

در مثال قبل دیدیم که در قدم سوم یک الگوریتم یادگیری نظارت شده مثل SVM به کمک داده‌هایی که از قبل برچسب‌گذاری شده‌اند آموزشداده شد. اما برای چه چیزی آموزش داده شد؟ برای این که چیزی را یاد بگیرد.

چه چیزی را یاد بگیرد؟

در مورد SVM، یک مدل خطیرا یاد میگیرد.

مدل خطی چیست؟ اگر بخواهیم به زبان ساده بیان کنیم یک خط است.(و در حالت پیچیده‌تر یک ابر صفحه).

اگر داده‌های شما خیلی ساده و دو بعدی باشند، در این صورت SVM خطی را یاد می‌گیرد که آن خط می‌تواند داده‌ها را به دو بخش تقسیم کند.

 

svm

SVM قادر است که خطی را پیدا کند که داده‌ها را جدا می‌کند.

 

خب پس اگر SVM فقط یک خط است، پس چرا ما داریم راجع به مدل خطی صحبت می‌کنیم؟

برای این که ما همینطوری نمی‌توانیم به یک خط چیزی را آموزش بدهیم.

در عوض:

  1. در نظر می‌گیریم که داده‌هایی که می‌خواهیم طبقه‌بندی کنیم، می‌توانند به وسیله یک خط از هم تفکیک شوند.
  2. می‌دانیم که یک خط می‌تواند به کمک معادله y=wx+by=wx+b نمایش داده شود.(این همان مدل ما است)
  3. می‌دانیم با تغییر دادن مقدار w و b بی‌نهایت خط وجود خواهد داشت.
  4. برای تعیین این که کدام مقدار w و b بهترینخط جداکننده داده‌ها را به ما می‌دهد، از یک الگوریتم استفاده می‌کنیم.

SVM یکی از این الگوریتم‌ها هست که می‌تواند این کار را انجام دهد.

الگوریتم یا مدل؟

در شروع این پست من نوشتم که SVM یک مدل یادگیری نظارت شده است، و الآن می‌نویسم که آن یک الگوریتم است. چه شده؟ از واژه الگوریتم معمولا آزادانه استفاده می‌شود. برای نمونه، ممکن است که شما جایی بخوانید یا بشنوید که  SVM یک الگوریتم یادگیری نظارت شده است. اگر این نکته را در نظر بگیریم که الگوریتم مجموعه‌ای از فعالیت‌ها است که انجام می‌شوند تا به نتیجه مشخصی دست یابیم، می‌بینیم که استفاده از این واژه در اینجا صحیح نیست(منظور از واژه الگوریتم اینجا الگوریتمی است که برای آموزش از آن استفاده می‌کنیم). بهینه‌سازی متوالی کمینه(Sequential minimal optimization) پر استفاده ترین الگوریتم برای آموزش SVM است. با این حال می‌توان از الگوریتم‌های دیگری مثل کاهش مختصات(Coordinate descent) هم استفاده کرد. در کل بیشتر به جزییاتی مثل این علاقمند نیستند، در نتیجه ما هم برای ساده‌تر شدن فقط از واژه الگوریتم SVM استفاده می‌کنیم(بدون ذکر جزییات الگوریتم آموزشی که استفاده می‌کنیم).

SVM یا SVMها؟

بعضی وقت‌ها می‌بینیم که مردم راجع به SVM و بعضی وقت‌ها هم راجع به SVMها صحبت می‌کنند.

طبق معمول ویکی‌پدیا در روشن و شفاف کردن چیزها به ما کمک می‌کند:

در یادگیری ماشینی، ماشین‌های بردار پشتیبان (SVMsمدل‌های یادگیری نظارت شده به همراه الگوریتم‌های آموزش مربوطههستندکه در تحلیل داده‌های استفاده شده در  رگرسیون و طبقه‌بندی از آن‌ها استفاده می‌شود.(ویکی‌پدیا)

پس حالا ما این را می‌دانیم که چندین مدل‌ متعلق به خانواده SVM وجود دارند.

SVMها – ماشین‌های بردار پشتیبان

بر اساس ویکی‌پدیا SVMها همچنین می‌توانند برای دو چیز استفاده شوند، طبقه‌بندی و رگرسیون.

  • SVM برای طبقه‌بندی استفاده می‌شود.
  • SVR یا(Support Vector Regression) برای رگرسیون.

پس گفتن ماشین‌های بردار پشتیبان هم دیگه الآن منطقی به نظر میاد. با این وجود این پایان داستان نیست!

طبقه‌بندی

در سال ۱۹۵۷ یک مدل خطی ساده به نام پرسپترون توسط فردی به نام فرانک روزنبلت برای طبقه‌بندی اختراع شد(که در واقع اساس شبکه‌های عصبی ساده‌ای به نام پرسپترون چند لایه است).

چند سال بعد، واپنیک و چروننکیس مدل دیگری به نام «طبقه‌بندی کننده حداکث حاشیه» پیشنهاد دادند و همان‌جا بود که SVM متولد شد.

در سال ۱۹۹۲ واپنیک و همکارانش ایده‌ای داشتند که یک چیزی به نام کلک کرنل(Kernel Trick) را به روش قبلی اضافه کنند تا به آن‌ها اجازه دهد که حتی داده‌هایی که به صورت خطی تفکیک‌پذیر نیستند را هم طبقه‌بندی کنند.

سرانجام در سال ۱۹۹۵، کورتز و واپنیک، طبقه‌بندی کننده حاشیه نرم را معرفی کردند که به SVM اجازه می‌دهد تا بعضی از اشتباهات در طبقه‌بندی را هم بپذیرد.

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

  1. طبقه‌بندی کننده حاشیه حداکثر.
  2. نسخه‌ای که از کلک کرنل استفاده می‌کند.
  3. نسخه‌ای که از حاشیه نرم استفاده می‌کند.
  4. نسخه‌ای که ترکیب همه موارد قبلی است.

و البته آخرین روش معمولا بیشترین کاربرد را دارد. دلیل اصلی این که قهمیدن SVMها در نگاه اول کمی گیج کننده به نظر می‌رسد هم همین موضو ع است که ‌آن‌ها از چندین قطعه تسکیل شده اند که در طول زمان به ‌‌آن‌ها چیزهایی اضافه شده است.

به همین دلیل است که وقتی از یک زبان برنامه‌‌نویسی استفاده می‌کنید می‌پرسید از کدام کرنل باید استفاده کنیم(بخاطر کرنل‌های مختلفی که وجود دارند) و یا کدام مقدار ابرپارامتر C را باید استفاده کنید(برای کنترل تاثیر حاشیه نرم).

رگرسیون

در سال ۱۹۹۶، واپنیک و همکارانش، نسخه‌ای از SVM را پیشنهاد دادند که به جای طبقه‌بندی، عمل رگرسیون را انجام می‌دهد. این مورد به Support Vector Regression یا SVR معروف است. همانند SVM در این مدل نیز از کلک کرنل و ابرپارامتر C  استفاده می‌شود.

در آینده مقاله ساده‌ای در مورد توضیح چگونگی استفاده از  SVR در زبان R خواهم نوشت و آدرس آن را همین‌جا قرار خواهم داد.

اگر علاقمند هستید که راجع به SVR بیشتر بدانیند، می‌توانید به این آموزش خوب که نوشته Smola and Schölkopft است، مراجعه کنید.

خلاصه تاریخچه

  • طبقه‌بندی کننده حاشیه حداکثر (۱۹۶۳ یا ۱۹۷۹)
  • کلک کرنل (۱۹۹۲)
  • طبقه‌بندی کننده حاشیه نرم (۱۹۹۵)
  • رگرسیون بردار پشتیبان (۱۹۹۶)

در صورتی که مایلید بیشتر راجع به تاریخچه بدانید، می‌توانید به مقاله مرور همراه با جزییات از تاریخچه مراجعه کنید.

انواع دیگری از ماشین‌های بردار پشتیبان

به دلیل این که SVMها در طبقه‌بندی خیلی موفق بودند، مردم شروع به فکر کردن راجع به این موضوع کردند که چطور می‌توانند از همین منطق در انواع دیگر مسائل استفاده کنند یا این‌ که چطور مشتقات آن را ایجاد کنند. در نتیجه چندین روش مختلف و جالب در خانواده SVM به وجود آمد.

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

نتیجه‌گیری

دیدیم که سختی در درک کردن این که SVMها دقیقا چه چیزی هستند، امری طبیعی است. علتش هم این است که چندین SVM برای چندین منظور وجود دارند. مثل همیشه تاریخ به ما اجازه می‌دهد که دید بهتری راجع به چگونگی به وجود آمدن SVMهایی که امروزه وجود دارند، داشته باشیم.

امیدوارم این مقاله دید وسیع‌تری از چشم‌انداز  SVM به شما داده باشد و کمک کرده باشد که بهتر این ماشین‌ها را بشناسید و درک کنید.

اگه مایلید که بیشتر راجع به نحوه کار SVM در طبقه‌بندی بدانید، می‌توانید به آموزش‌های ریاضی مربوط به آن مراجعه کنید.

شبکه عصبی مصنوعی به زبان ساده

یک شبکه عصبی مصنوعی (Artificial Neural Network – ANN) ایده ای برای پردازش اطلاعات است که از سیستم عصبی زیستی الهام گرفته و مانند مغز به پردازش اطلاعات می‌پردازد. عنصر کلیدی این ایده، ساختار جدید سیستم پردازش اطلاعات است. این سیستم از شمار زیادی عناصر پردازشی فوق العاده بهم پیوسته به نام نورون‌ها (neurons) تشکیل شده که برای حل یک مسئله با هم هماهنگ عمل می‌کنند.

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

شبکه های عصبی مصنوعی (ANN) که به اختصار به آن شبکه عصبی نیز گفته می‌شود، نوع خاصی از مدل یادگیری است که روش کارکرد سیناپس‌ها در مغز انسان را تقلید می‌کند.

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

ساختار شبکه عصبی

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

شبکه عصبی-05

 

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

در این ساختار با ایجاد شبکه‌ای بین این گره‌ها و اعمال یک الگوریتم آموزشی به آن، شبکه را آموزش می‌دهند. در این حافظه یا شبکه عصبی گره‌ها دارای دو حالت فعال (روشن یا ۱) و غیرفعال (خاموش یا ۰) اند و هر یال (سیناپس یا ارتباط بین گره‌ها) دارای یک وزن می‌باشد. یال‌های با وزن مثبت، موجب تحریک یا فعال کردن گره غیر فعال بعدی می‌شوند و یال‌های با وزن منفی، گره متصل بعدی را غیر فعال یا مهار (در صورتی که فعال بوده باشد) می‌کنند.

مثالی برای  شبکه عصبی

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

 

شبکه عصبی-02

 

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

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

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

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

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

شبکه عصبی-ترجمه

 

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

چنین وضعیتی در تشخیص گفتار نیز به وجود آمد. پس از افزودن یادگیری با شبکه های عصبی در Google Voice نرخ خطای این برنامه تا ۴۹% کاهش یافت. البته این قابلیت هیچوقت بدون نقص نخواهد بود، اما به مرور زمان شاهد پیشرفت آن هستیم.

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

شبکه های عصبی در مقابل کامپیوتر های معمولی

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

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

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

امتیاز شبکه عصبی در آن است که چگونگی حل مسئله را خودش کشف می‌کند!

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

 

شبکه عصبی-03

مزیت‌های شبکه عصبی

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

شبکه های عصبی معجزه نمی‌کنند اما اگر خردمندانه به کار گرفته شوند نتایج شگفت آوری خلق می‌کنند.

مزیت‌های دیگر شبکه های عصبی

  • یادگیری انطباق پذیر (Adaptive Learning)

یادگیری انطباق پذیر، قابلیت یادگیری و نحوه انجام وظایف بر پایه اطلاعات داده شده برای تمرین و تجربه‌های مقدماتی.

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

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

خرابی جزئی یک شبکه منجر به تنزل کارایی متناظر با آن می‌شود، اگر چه تعدادی از قابلیت‌های شبکه حتی با خسارت بزرگی هم به کار خود ادامه می‌دهند.

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

انواع شبکه عصبی مصنوعی

شبکه‌های پیش خور، شبکه‌هایی هستند که مسیر پاسخ در آن‌ها همواره رو به جلو پردازش شده و به نرون‌های لایه‌های قبل خود باز نمی‌گردد. در این نوع شبکه‌ به سیگنال‌ها تنها اجازه عبور از مسیر یکطرفه (از ورودی تا خروجی) داده می‌شود. بنابراین بازخورد یا فیدبک وجود ندارد به این معنی که خروجی هر لایه تنها بر لایه بعد اثر میگذارد و در لایه‌ی خودش تغییری ایجاد نمی‌کند.

شبکه عصبی-شبکه عصبی-پیش‌خور-01

 

تفاوت شبکه هاِی پس خور با شبکه‌های پیش خور در آن است که در شبکه‌های برگشتی حداقل یک سیگنال برگشتی از یک نرون به همان نرون یا نرون‌های همان لایه یا نرون‌های لایه‌های قبل وجود دارد و اگر نرونی دارای فیدبک باشد بدین مفهوم است که خروجی نرون در لحظه حال نه تنها به ورودی در آن لحظه بلکه به مقدار خروجی خود نرون در لحظه ی گذشته نیز وابسته است.

شبکه عصبی-پس خور

 

 یادگیری در شبکه‌ های عصبی

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

یادگیری تشدیدی حالت خاصی از یادگیری با ناظر و یک یادگیری بر‌خط (On-Line) از یک نگاشت ورودی-خروجی است. این کار از طریق یک پروسه سعی و خطا به صورتی انجام می‌پذیرد که شاخصی موسوم به سیگنال تشدید، ماکزیمم شود که در آن بجای فراهم نمودن خروجی هدف، به شبکه عددی که نشان‌دهنده میزان عملکرد شبکه است ارائه می‌گردد.

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

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

ساختار شبکه های عصبی مصنوعی به زبان ساده (Artificial Neural Network)

 

ساختار شبکه‌های عصبی مصنوعی به زبان ساده (Artificial Neural Network)

 

شبکه عصبی مصنوعی روشی عملی برای یادگیری توابع گوناگون نظیر توابع با مقادیر حقیقی، توابع با مقادیر گسسته و توابع با مقادیر برداری می‌باشد.

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

گمان می‌رود که مغز انسان از تعداد ‌1011 نرون تشکیل شده باشد که هر نرون با تقریبا 104 نرون دیگر در ارتباط است. سرعت سوئیچنگ نرونها در حدود 310 ثانیه است که در مقایسه با کامپیوترها 1010 ثانیه  بسیار ناچیز می‌نماید. با این وجود آدمی قادر است در 0.1 ثانیه  تصویر یک انسان را بازشناسائی نماید. ولی برای کامپیتر دقایقی طول می کشد که این بازشناسی انجام شود.

شاید بد نباشد ابتدا به این سوال فکر کنید، چرا با اینکه سرعت سوئیچنگ نرونهای کامپیوتر از مغز انسان بیشتر است ولی انسان‌ها سریعتر چهره یک شخص را به یاد می‌آورند؟

ساختار شبکه عصبی

 

 

هر دو تصویر بالا را مشاهده کنید. چه شباهت‌هایی می‌بینید؟

همانطور که ملاحظه می کنید، تصویر اول یک نرون طبیعی بیولوژیکی است. اطلاعات از طریق ورودی یا همان دندریت وارد نرون می شوند، همان ورودی‌ها در تصویر دوم با مقادیر (x1,…….,xm) قابل مشاهده هستند. در مدل شبکه عصبی مصنوعی به هر ورودی یک وزن (w1,…….,wm) اختصاص می دهیم. این وزن‌ها در واقع اهمیت ورودی‌ها برای ما هستند، یعنی هر چه وزن بیشتر باشد، ورودی برای آموزش شبکه مهمتر است. سپس تمامی ورودی‌ها با هم جمع (Σ) شده و به صورت یک‌لایه به آکسون وارد می شوند. در مرحله بعد Activation Function را بر روی داده‌ها اعمال می‌کنیم.

Activation Function در واقع نسبت به نیاز مسئله و نوع شبکه عصبی ما (در آموزش های بعدی به آن می پردازیم) تعریف می شود. این function شامل یک فرمول ریاضی برای بروزرسانی وزن‌ها در شبکه است.

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

منبع

شبکه های عصبی مصنوعی چیست؟ قسمت 1
شبکه های عصبی مصنوعی چیست؟ قسمت 2
شبکه های عصبی مصنوعی چیست؟ قسمت 3
شبکه های عصبی مصنوعی چیست؟ قسمت 4

هوش مصنوعی جدید وحشت آور سامسونگ می تواند Deepfakeهای سخنگو از یک تصویر تولید کند.

مشکل deepfake ما در مورد بدتر شدن است: مهندسان سامسونگ در حال حاضر سرهای سخنگوی واقع گرایانه ای را توسعه داده اند که می تواند از یک تصویر تولید شود، بنابراین AI حتی می تواند کلمات را در دهان مونا لیزا قرار دهد.

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

 

 

 

مدل جدید نه تنها می تواند از یک پایگاه داده اولیه کوچکتر از تصاویر استفاده کند، هم چنین می تواند طبق نظر محققان پشت آن، فیلم های کامپیوتری را در مدت کوتاه تری تولید کند.

و در حالی که همه انواع برنامه های جالب وجود دارد که از تکنولوژی می توان برای آن استفاده کرد – مانند قرار دادن یک نسخه فوق واقع گرایانه از خودتان در واقعیت مجازی – این نگرانی وجود دارد که فیلم های ویدئویی کاملاً تقلبی را می توان از یک تصویر کوچک تولید کرد.

محققان در مقاله خود نوشتند: “چنین توانایی دارای کاربردهای عملی برای تلوزیون است،، از جمله ویدئو کنفرانس و بازی های چند نفره، و همچنین صنعت جلوه های ویژه.”

deepfake

سیستم با آموزش خود در مجموعه ای از ویژگی های چهره برجسته کار می کند که پس از آن می تواند دستکاری شود. بسیاری از آموزش ها بر روی یک پایگاه داده قابل دسترس عمومی از بیش از 7000 تصویر از افراد مشهور، به نام VoxCeleb، و همچنین تعداد زیادی از فیلم ها از صحبت کردن مردم با دوربین انجام شده است.

از آنجا که این رویکرد جدید کار گذشته را با آموزش دادن به شبکه عصبی در مورد چگونگی تبدیل ویژگی های چهره برجسته به فیلم های متحرک با نگاه واقع گرایانه، بیش از چندین بار، بهبود می دهد. سپس این دانش می تواند بر روی چند عکس (یا فقط یک عکس) از کسی که AI قبل از آن هرگز ندیده است، مستقر شود.

 

deepfake new

 

این سیستم از یک شبکه عصبی کانولوشن، یک نوع شبکه عصبی بر اساس فرآیندهای بیولوژیکی در قشر بینایی حیوان استفاده می کند. این منحصراً در پردازش پشته های تصاویر و شناخت آنچه در آنها متخصص است – “convolution” اساساً بخش هایی از تصاویر را شناسایی و استخراج می کند (آن همچنین برای نمونه، در جستجوهای تصویری در وب و تکنولوژی خودرو خود راننده استفاده می شود).

همانند سایر ابزارهای تولید چهره هوش مصنوعی گرا که ما شاهد آن هستیم، آخرین مرحله در این فرآیند برای “واقع گرایی کامل” مورد بررسی قرار می گیرد – از لحاظ فنی یک مدل مولد رقابتی. هر فریمهایی که بیش از حد عجیب و غریب و غیر طبیعی هستند، دوباره برش داده و ارائه میشوند، ویدئو نهایی با کیفیت بهتر را به نمایش میگذارند.

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

سیستم و دیگران مانند آن، برای بهتر شدن محدود می شوند به طوریکه الگوریتم ها بهبود یابند و مدل های آموزشی موثرتر شوند – و این بدان معنی است که مجموعه ای کامل از سوالات در مورد اینکه آیا می توانید به آنچه که می بینید یا می شنوید اعتماد کنید، اگر در فرم دیجیتال باشد.

از طرف دیگر، ستاره های تلویزیون و فیلم مورد علاقه شما هرگز نباید رشد کنند و بمیرند – AI شبیه به این است که به زودی به اندازه کافی هوشمند خواهد بود تا نمایش های کاملا واقعی را فقط از چند عکس تولید کند و همچنین در زمان ذخیره.

 

 

ماشین تورینگ کوانتومی

ماشین تورینگ کوانتومی (QTM) و همچنین ماشین جامع تورینگ کوانتومی، ماشیني انتزاعی است که با بهره‌گیری از قدرت رایانش کوانتومی برای مدل‌سازی ساده کامپیوترهای کوانتومی مورد استفاده قرار می‌گیرد.

در اصل، می‌توان هر الگوریتم کوانتومی را با یک ماشین تورینگ کوانتومی تفسیر و تشریح کرد. چنین ماشین‌هایی برای نخستین‌بار در سال 1985 و در یک مقاله از طرف دیوید دویچ (David Deutsch) فیزیکدان در دانشگاه آکسفورد مطرح شد. وی در این مقاله تلاش داشت تا نشان دهد گیت‌های کوانتومی می‌توانند همانند نمونه‌های سنتی دیجیتال با منطق دودویی نیز کار کنند. می‌توان ماشین‌های تورینگ کوانتومی را با استفاده از ماتریس‌های انتقالی خاص که توسط لنس فورت‌نو (Lanc Fortnow) تهیه و تدوین شده‌اند، به انواع کلاسیک و احتمالاتی ماشین‌های تورینگ مرتبط کرد.

همچنین، نمونه‌هایی از چنین ماشین‌هایی تحت عنوان Linear Quantum Turing Machine توسعه داده شده است که کلیت یافته ماشین‌های معمولی کوانتومی تورینگ بوده و علاوه بر مدل‌سازی مفهوم حالات ترکیبی، امکان استفاده از توابع غیر قابل بازگشت را نیز فراهم می‌سازند. نتیجه استفاده از چنین ماشین‌هایی، ارزیابی کوانتومی بدون وجود عواقب کلاسیک آن است که در نوع خود بسیار ارزشمند است. لازم به ذکر است با این‌که ماشین‌های تورینگ کوانتومی مدلی ساده و جالب برای تحلیل الگوریتم‌های کوانتومی هستند اما مدارهای کوانتومی که از لحاظ محاسباتی با آن‌ها معادل هستند، بیشتر مورد استفاده قرار می‌گیرند.

با مراجعه به آدرس www.mathematica-journal.com/issue/v8i3/features/hertel/index.html می‌توانید یک شبیه‌ساز ماشین کوانتومی تورینگ را که با استفاده از Mathematica توسعه داده شده است، دانلود کرده و برای آشنایی بیشتر با QTM از آن استفاده کنید.

نکته قابل توجه در تئوری مطرح شده از طرف تورینگ این است که وی‌ در مقاله اولیه خود میان «ماشین اتوماتیک» یا a-Machine و «ماشین انتخاب کننده» یا c-Machine تفاوت قائل بوده است چراکه در بخشی از نوشتار خود ذکر کرده است «حرکات ماشین خودکار، به‌طور کامل در پیکربندی تعیین شده است اما حرکات ماشین انتخاب کننده، به‌طور نسبی در پیکربندی آن تعیین شده است. زمانی که چنین ماشینی به یکی از این حالت‌های مبهم می‌رسد، باید تا زمان تعیین یک انتخاب از طرف عامل بیرونی منتظر باقی بماند. این می‌تواند در زمینه استفاده از ماشین‌ها در سیستم‌های axiomatic کاربرد داشته باشد.»

نمای شماتیک جدول‌گذار Busy Beaver
شكل1: نمای شماتیک جدول‌گذار Busy Beaver

در انتظار یادگیری ماشینی کوانتومی خواهیم بود

در کنار این دو ماشین، وی صحبت از وجود نوع دیگری از ماشین را به میان می‌آورد که از آن‌ها به Oracle Machine (ماشین پیشگو) یا o-Machine تعبیر می‌شود. ماشین پیشگو، ماشین تورینگی است که محاسبات خود را برای تکمیل کردن، در حالت o متوقف می‌کند. در این حالت، این ماشین تا زمان تصمیم‌گیری توسط پیشگو(که مفهومی نامشخص بوده و شاید نتوان آن را ماشین به شمار آورد)منتظر می‌ماند. این ایده هم‌اکنون به شدت مورد توجه و استفاده ریاضیدانان است.

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

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

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

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

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

– ماشین تورینگ فهم و تحلیل الگوریتم‌ها را ساده می‌کند. الگوریتم‌های معادلی که روی ماشین‌های مجرد معادل با ماشین تورینگ اجرا می‌شوند، عموماً در مقابل نمونه‌های مشابه خود در سیستم‌های واقعی کلیت بیشتری داشته و به‌عنوان مثال، معضلات مرتبط با انواع دقیق داده‌ای در آن‌ها مطرح نیست.

نمونه دیاگرام پیشرفت محاسبات یک ماشین Busy Beaver  سه حالته 
شكل2 : نمونه دیاگرام پیشرفت محاسبات یک ماشین Busy Beaver  سه حالته


بخش سوم

محدودیت‌های ماشین تورینگ

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

محدودیت دیگری که می‌توان برای ماشین تورینگ بر‌شمرد، در حوزه پیچیدگی محاسباتی مطرح می‌شود و آن این است که ماشین تورینگ به خوبی امکان مدل‌سازی اهمیت در ترتیب‌هایی خاص (که در بعضی الگوریتم‌ها مورد نیاز است، مانند حلقه‌های تکرار) را ندارد. به عنوان مثال، کامپیوترهای مدرن با برنامه ذخیره‌شده، نمونه‌ای از یک فرم خاص از ماشین‌های مجرد هستند که RASP(سرنام Random Access Stored Program Machine) نامیده می‌شوند. این نوع ماشین‌ها برنامه را در حافظه‌ای جدا از فضای دستورالعمل‌های ماشین حالت متناهی ذخیره می‌کنند. این ماشین‌ها معمولاً به قابلیت آدرس‌دهی غیر‌مستقیم حافظه و رجیسترها مجهز هستند و به همین دلیل، هر برنامه RASP می‌تواند به راحتی به هر رجیستر مورد نیاز خود دسترسی پیدا کند. نتیجه این تفاوت آن است که در این ماشین‌ها بر‌خلاف ماشین تورینگ، بر‌اساس شاخص‌های حافظه می‌توان بهینه‌سازی‌های محاسباتی را پیاده‌سازی کرد؛ امری که در مدل ماشین تورینگ امکان‌پذیر نیست و به همین دلیل، زمانی که ماشین تورینگ برای تعداد محدودی اجرا در نظر گرفته می‌شود، می‌توان در تعداد مشخصی از اجراهای برخی الگوریتم ها بروز «خطای حد پایینی نادرست» را اثبات کرد (این امر به دلیل ساده‌‌سازی ناصحیح فرضیات در ماشین تورینگ است). مثالی از این مورد، الگوریتم جست‌وجوی باینری است که روی مدل‌های RASP بسیار سریع‌تر از ماشین تورینگ اجرا می‌شود.

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

مشکل دیگری که ماشین تورینگ با آن مواجه است، مسئله توقف است که یکی از کلیدی‌ترین مشکلات آن به شمار می‌آید. بر این اساس، هیچ ماشین تورینگی وجود ندارد که بتواند متوقف شدن در برابر یک ورودی خاص را محاسبه کند! برای درک عدم امکان محاسبه تابع توقف، تصور کنید ماشینی وجود دارد که از ترکیب ماشین کپی و اضافه‌کردن حالت توقف به ابتدای حالت‌های آن ساخته شده است. در این صورت، اگر ورودی شروع شونده با 1 به چنین ماشینی اعمال شود، ماشین به حالت انتقالی بی نهایتی از شروع و توقف وارد می‌شود و راهی برای خروج از این وضعیت نیز ارائه نمی‌کند. چنین مشکلی در انواع دیگری از ماشین‌های تورینگ نیز موجود است.

نمونه‌ای امروزين از ماشين سنتی تورينگ

یکی از بهترین نمونه‌هایی که از ماشین تورینگ ساخته شده است، پروژه «یک ماشین تورینگ» است که می‌توانید با رفتن به آدرس اینترنتی http://aturingmachine.com/index.php مشخصات و اطلاعات مربوط به آن را مشاهده و دریافت کنید.
در این ماشین که با استفاده از میکروکنترلر Parallax Propeller ساخته شده، انتقال حالت از روی قوانینی که روی یک SD Card ذخیره می‌شود، برداشت شده و داده‌ها از روی نوار تأمین می‌شوند. در ساخت این ماشین سعی شده حداکثر شباهت فیزیکی به آن چه تورینگ مد نظر داشته است، حفظ شده و مدلی مناسب از عملکرد ماشین اصلی تورینگ ارائه شود. اما این ماشین چگونه و از چه اجزایی ساخته شده و چگونه کار می‌کند؟

جزء اصلی سیستم هد خواندن و نوشتن ماشین است که عملیات ورودی خروجی را روی نوار 1000 اینچی سفید انجام می‌دهد. کاراکترهای لازم با استفاده از یک ماژیک پاک شونده روی نوار نوشته می‌شوند و با توجه به عرض یک اینچی هر خانه، کل نوار امکان ذخیره‌سازی 10 کیلو بیت داده را دارد. (شکل 1)
عملیات عقب و جلو بردن نوار به‌وسیله یک موتور پله‌ای مجهز به سنسور حالت اولیه و متصل به تسمه دندانه‌دار انجام می‌گیرد. این دندانه‌ها و چرخش موتور طوری تنظیم شده است که هر حرکت موتور، یک سلول از نوار را جابه‌جا کند. (شکل 2)

اسکنر این ماشین با استفاده از یک دوربین اسکن خطی با نور روشن‌کننده پیاده‌سازی شده است. مدل دوربین به‌کار رفته، TS-1401 است و 128 بیت داده را در هر خط برداشت می‌‌کند. زمان تمرکز چیزی حدود 200/1 ثانیه است (شکل 3).

 

نمونه‌ای امروزين از ماشين سنتی تورينگ و مراحل کار آن

عملیات پاک‌کردن سمبل‌ها از روی نوار با استفاده از یک غلطک پاک کننده به انجام می‌رسد. برای پاک کردن، غلطک با استفاده از یک پین به پایین آمده و سپس به میزانی می‌چرخد تا مقادیر روی نوار پاک شود. پس از انجام عملیات پاک کردن، غلطک به بالا باز می‌گردد. (شکل۴) ماشین مذکور با استفاده از کنسولی که با تعدادی نمایشگر و دکمه کنترلی تجهیز شده است، کنترل می‌شود. از این طریق می‌توان برنامه‌های مورد نظر را که از روی کارت حافظه SD بارگذاری می‌شوند، انتخاب کرده و کارکرد ماشین را تعیین کرد. (شکل 5)

کنترل ماشین مذکور توسط چیپ میکروکنترلر Parallax Propeller که در سمت چپ قرار گرفته است، به انجام می‌رسد. در این مدار، تمام 32 پورت ورودی/خروجی میکروکنترلر مذکور استفاده شده است. مدار سمت راست نیز وظیفه تأمین توان مصرفی مدار و همچنین کنترل و تأمین توان موتورهای پله‌ای و کنترل  ‌هد را بر عهده دارد. (شکل 6)

 

نمونه‌ای امروزين از ماشين سنتی تورينگ و مراحل کار آن

نوار کاغذی از هر طرف روی قرقره‌ای که به یک موتور DC با سرعت 4 دور در دقیقه متصل است، سوار شده است. (شکل 7 و 8) در پایگاه اینترنتی پروژه می‌توانید شماتیک  مدارهای به کار رفته در این ماشین را به صورت مفصل مشاهده کنید.  نرم‌افزار این ماشین با استفاده از زبان Spin مخصوص Propeller نوشته شده است که دو بخش مهم و اساسی دارد: بخشی که با کاربر مرتبط است و بخش دیگری که عملیات ماشین تورینگ را به انجام می‌رساند. بخش اول وظیفه بارگذاری برنامه‌ها از SD Card، تولید داده‌های پیش فرض روی نوار و کارهای جنبی را انجام می‌دهد در حالی که بخش دوم وظیفه انجام عملیات خواندن و نوشتن و پاک‌کردن نوار و همچنین عملکرد ماشین در برابر داده‌های ورودی را بر عهده دارد. در شکل 9 دیاگرام نرم‌افزاری این ماشین را مشاهده می‌کنید.

 

دیاگرام نرم افزاری نمونه‌ای امروزين از ماشين سنتی تورينگ
دياگرام نرم‌افزاری اين نمونه از ماشين تورينگ

ماشین جامع تورینگ

ماشین تورینگی که بتواند هر ماشین تورینگ دیگری را شبیه‌سازی کند، ماشین جامع تورینگ یا Turing Universal Machine خوانده می‌شود. به طور همزمان، تبیین ریاضی‌وارتری از ماشین جامع تورینگ با طبیعتی مشابه نیز توسط فردی به‌نام آلونزو چرچ (Alonzo Church )که کار وی روی Lambda Calculus با تئوری محاسبات تورینگ همپوشانی داشت، مطرح شده که اکنون با عنوان تئوری چرچ -تورینگ (Church-Turing) شناخته می‌شود.

تورینگ در این زمینه می‌گوید: «می‌توان ماشینی اختراع کرد که ‌بتواند هر عبارت محاسباتی را محاسبه کند. اگر ماشین U با نواری تغذیه شود که روی آن رشته‌های توصیف‌کننده عملکرد ماشین M نوشته شده باشد، آنگاه ماشین U عباراتی مشابه با M را محاسبه خواهد کرد.»

دیاگرامی ازنحوه عملکرد یک ماشین تورینگ عمومی (U) که با دریافت کدهای عملکرد ماشین تورینگ M، عملکرد آن را شبیه‌سازی می‌کند.
شكل3: دیاگرامی ازنحوه عملکرد یک ماشین تورینگ عمومی (U) که با دریافت کدهای عملکرد ماشین تورینگ M، عملکرد آن را شبیه‌سازی می‌کند.

ماشین تورینگ زیستی

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

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

مفهوم ژن، که توصیف نمادینی از ارگانیسم مرتبطش است (یک کد اسکریپتی) بنیان اساسی دنیای موجودات زنده است و می‌تواند هسته اصلی یک تئوری جامع و جدید را در بیولوژی تشکیل دهد.
تورینگ در سال 1954‌، درست یک سال پس از کشف ساختار جفت پیچشی DNA توسط جیمز واتسون و فرانسیس کریک و البته قبل از وقوع انقلاب حاصل از این کشف در علوم زیست‌شناسی، درگذشت و هیچ‌گاه فرصت بسط و توسعه ایده‌هایش در این حوزه را نیافت. اگرچه وی و فون‌نویمان هیچ تأثیر مستقیمی بر زیست‌شناسی مولکولی نداشتند، کارهای آن‌ها می‌تواند در راستای منظم‌سازی دانش انسان درباره ماشین‌های طبیعی و مصنوعی مورد استفاده قرار گیرد.

 

ماشین تورینگ زیستی

 

تورینگ کامپیوتر با برنامه ذخیره شده را اختراع کرد وفون نویمان نشان داد که توصیف، از خود ماشین سازنده جامع جدا است. این کشفیات به هیچ وجه ساده و ابتدایی نیستند چرا که صحت آن‌ها مدت ها بعد مشخص شد. در سال 1944، اروین شرودینگر(Erwin Schrödinger) در کتابی با عنوان «زندگی چیست؟»، کروموزوم‌‌ها را نقشه معمار و ابزار سازنده عناصر زنده به‌صورت یکجا می‌دانست که اکنون اشتباه بودن آن کاملاً مشخص شده است چراکه کد اسکریپتی موجود در ماشین‌های زنده، تنها حاوی توصیفی از توابع اجرایی مورد نیاز هستند نه خود این توابع. بر همین اساس است که می‌توان گفت معادلات Hogkin ، خصوصیات پالس‌های عصبی را به‌صورت یک مدار الکتریکی مدل می‌‌کند، اما کانال‌های ارتباطی آن‌ها از روی توصیفاتی که توسط ژن‌ها ذخیره می‌شود، ساخته می‌شوند.

با این حال، هم اکنون مشکل اصلی بشر در درک بخش سازنده این ماشین‌های زنده است و پرسش‌های مربوط به توصیفات تقریباً پاسخ داده شده است. بر این اساس، بهترین چیزی که می‌تواند در کانون توجه قرار گیرد، سلول‌ها به‌عنوان ماشین تورینگ یا ماشین سازنده فون‌نویمان است که شاید بتواند راهگشای بسیاری از معماهای موجود در علوم زیستی قرار گیرد. گرچه زیست‌شناسان همواره درباره ماشین‌های زیستی سؤالاتی از قبیل «چگونه کار می‌کند؟»، «چگونه ساخته می‌شود ؟» و «چگونه به این مرحله رسیده است؟» را مطرح می‌کنند و این که ممکن است آن‌ها را مربوط به حوزه فیزیولوژی امبریولوژی یا تکامل دانست، اما در مرکز مسائلی این چنین و مرتبط با موجودات زنده، نوارهایی وجود دارد که حاوی توصیف‌هایی برای ساخت ماشین‌های تورینگ زنده است!

 با این‌که این ایده اکنون پذیرفته شده است، اما در آن زمان بسیار عجیب و شگفت‌انگیز به شمار می‌آمد. بعدها اما این مدل ماشین Universal ارائه شده از طرف تورینگ که به طور اختصاری U نامیده می‌شود از طرف بسیاری مانند مارتین دیویس(Martin Davis)، در سال 2000 به‌عنوان تئوری پایه‌ای که منجر به شکل‌گیری و تولید «کامپیوتر با برنامه ذخیره‌شده» شد، انتخاب و معرفی شد. همچنین، ماشین جامع تورینگ از طرف جان فون نویمان (John von Neumann) برای ساخت ابزار الکترونیکی محاسبه مورد استفاده قرار گرفته و منجر به معرفی مفهوم مهمی با نام معماری فون نویمان شد.

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

مارتین دیویس معتقد است که ایده جایگذاری جدول عملکرد ماشین به همراه ورودی‌ها روی حافظه ماشین سرآغاز رایانه‌های با برنامه ذخیره‌شونده است و به شدت بر درک فون نویمان از ماشین‌ها و تلاش وی برای تولید کامپیوتر علامت گسسته دیجیتال که EDVAC نام گرفت، تأثیر‌گذار بوده است. همچنین، وی معتقد است که موتور محاسبات خودکار (ACE) تورینگ، رشد و توسعه مفاهیمی مانند programming micro یا code micro و همچنین پردازنده‌های RISC را تسریع کرده است و آن را نخستین کاربرد پشته سخت‌افزاری (Hardware Stack) در دنیای کامپیوترها می‌داند. به اعتقاد وی، همان‌طور که ماشین تورینگ یکی از عوامل اصلی تولید کامپیوتر به شمار می‌آید، ماشین جامع تورینگ نیز یکی از عوامل اصلی توسعه علوم نوپای کامپیوتر (Computer Science) است.

منبع


منابع

https://fa.wikipedia.org/wiki

http://www.shabakeh-mag.com

 

ماشین تورینگ چیست ؟ قسمت 1
ماشین تورینگ چیست ؟ قسمت 2
ماشین تورینگ چیست ؟ قسمت 3