خطادار

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

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

در نظریّهٔ کدگذاری، کدهای Reed–Solomon یا به اختصار (RS) در واقع کدهای غیردودویی هستند که نشانه ورودی از نوع مجموعه ای بزرگتر از ۲ هستند. کدهای تصحیح خطا دایره ای توسط ایروینگ اس رید و گوستاو سولومون اختراع شد. آن‌ها یک روش سیستماتیک برای ساختن کدهایی که می‌توانند چندین خطای نشانه تصادفی توصیف کردند. با اضافه کردن t نشانه بررسی به داده، یک کد RS می‌تواند هر ترکیب از t نشانه خطادار را تشخیص دهد، و تا ⌊t/۲⌋ نشانه را تصحیح کند. به عنوان یک کد قابل حذف شدن، می‌تواند تا t نشانه قابل پاک شدن را تصحیح کنkد، یا به نوعی می‌توان گفت که می‌تواند ترکیبی از خطاها و کدهای قابل پاک شدن را تشخیص و تصحیح کند.

این کدگذاری، روشی ساختاریافته برای تولید کدهایی با قابلیت شناسایی و تصحیح خطاهای مُمتد تصادفی (Burst errors) در سمبول‌های اطلاعات (هر سمبول (Symbol)، چندین بیت است) است، که توانایی تشخیص هر ترکیبی از t سمبول خطادار، و تصحیح تا ⌊t/۲⌋ سمبول را داراست. سمبول‌های منبع اطلاعات به‌صورت ضرایب یک چندجمله‌ای (p(x در نظر گرفته می‌شوند، و n سمبول کد از k سمبول منبع با استفاده از فرانمونه‌برداری (p(x در n> k نقطه متفاوت تولید می‌شود. کدهای RS به صورت کد BCH دوره‌ای است که سمبول‌های کدکننده از روی ضرایب یک چندجمله‌ای به‌دست می‌آید که با استفاده از حاصلضرب p(x) و یک چندجمله‌ای مولد دوره‌ای ساخته می‌شود. این کار به یک الگوریتم رمزگشایی مؤثر منجر می‌شود که توسط Elwyn Berlekamp و James Massey کشف شد و به الگوریتم رمزگشایی Berlekamp-Massey معروف است.