پرسپترون

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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


تاریخچه[ویرایش]

الگوریتم پرسپترون در سال 1957 در لابراتوار کرنل آرونوتیکال توسط فرانک روزنبلت [۱] با سرمایه‌گذاری دفتر تحقیقات دریانوردی ایالات متحده [۲] ابداع شد. پرسپترون بیشتر به عنوان یک دستگاه مد نظر بوده است تا یک برنامه؛ و با این‌که اولین پیاده‌سازی آن به صورت یک نرم‌افزار برای آی بی ام 704 بود؛ پس از آن به صورت سخت‌افزار اختصاصی "پرسپترون مارک 1" پیاده سازی شد. این دستگاه برای تشخیص تصویر طراحی شده بود: مجموعه‌ای از 400 حسگر نور، که به صورت تصادفی به "نورون" ها متصل شده‌اند. وزن‌ها در پتانسیومترها کدگذاری شده بودند، و بروزرسانی وزن‌ها در طول یادگیری با موتور‌های الکتریکی صورت می‌گرفت.[۳]

تعریف[ویرایش]

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

پرسپترون

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

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

اگر داده‌های مثبت و منفی قابلیت جداشدن توسط یک ابرصفحه را نداشته باشند الگوریتم پرسپترون متوقف نمیشود اما اگر داده‌ها خطی تفکیک پذیر باشند الگوریتم پرسپترون در تعداد متناهی مرحله پایان می‌یابد. معروف‌‌ ترین تابعی که الگوریتم پرسپترون قادر به یادگیری آن نیست؛ تابع یا مانع الجمع است. [۴]

در زمینه شبکهٔ های عصبی مصنوعی پرسپترون یک نوع نورون مصنوعی است که تابع فعالیت آن تابع پله‌ای هویساید می‌باشد.

الگوریتم یادگیری[ویرایش]

نحوه کار الگوریتم پرسپترون

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

تعریف مساله[ویرایش]

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

تابع پرسپترون را نیز به صورت زیر تغییر می‌دهیم

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

مراحل الگوریتم[ویرایش]

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



input: A training set 
initialize: 
   for t = 1,2,...
       if()
           
       else
           return 

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

و در این‌صورت خواهیم داشت

بنابر‌این بردار وزن موردنظر است. [۵]

همگرایی الگوریتم[ویرایش]

اثبات[ویرایش]

منابع[ویرایش]

  1. Rosenblatt, Frank (1957), The Perceptron--a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory.
  2. Mikel Olazaran (1996). "A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science 26 (3): 611–659. doi:10.1177/030631296026003005. JSTOR 285702. 
  3. Bishop, Christopher M. (2006). Pattern Recognition and Machine Learning. Springer. 
  4. Liou, D.-R.; Liou, J.-W.; Liou, C.-Y. (2013). Learning Behaviors of Perceptron. iConcept Press. ISBN 978-1-477554-73-9. 
  5. Shwartz, Shai (2014). Understanding Machine Learning. p. 92.