بایگانی‌های ;kjvg jvnn

بایگانی برچسب برای: ;kjvg jvnn

تعریف فیلتر کالمن (Kalman filter) قسمت 1

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

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

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

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

مثال کاربردی

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

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

نام‌گذاری و تاریخچه توسعه

اگر چه Thorvald Nicolai Thiele و Peter Swerling قبلاً الگوریتم مشابهی ارائه داده بودند، این فیلتر به افتخار Rudolf E. Kalman، فیلتر کالمن نام‌گذاری شد و Stanley F. Schmidt عموماً به خاطر توسعه اولین پیاده‌سازی فیلتر کالمن شهرت یافت. این رخداد هنگام ملاقات با کالمن در مرکز تحقیقاتی ناسا (NASA Ames Research Center) روی داد و وی شاهد کارایی ایده کالمن در برآورد مسیر پرتاب پروژه آپولو بود، که منجر به الحاق آن به رایانه ناوبری آپولو شد. این فیلتر بر روی کاغذ در ۱۹۵۸ توسط Swerling، در ۱۹۶۰ توسط Kalman و در ۱۹۶۱ توسط Kalman and Bucy ایجاد و بسط داده شد.

این فیلتر بعضی مواقع فیلتر Stratonovich-Kalman-Bucy نامیده می‌شود، چرا که یک نمونه خاص از فیلتر بسیار معمولی و غیر خطی ای است که قبلاً توسط Ruslan L. Stratonovich ایجاد شده، در حقیقت معادله این نمونه خاص، فیلتر خطی در اسنادی که از Stratonovich قبل از تابستان ۱۹۶۰، یعنی زمانی که کالمن ،Stratonovich را در کنفرانسی در مسکو ملاقات کرد به چاپ رسید بود.

در تئوری کنترل، فیلتر کالمن بیشتر به برآورد مرتبه دوم (LQE) اشاره دارد. امروزه تنوع گسترده‌ای از فیلتر کالمن بوجود آمده، از فرمول اصلی کالمن در حال حاضر فیلترهای: کالمن ساده، توسعه یافته اشمیت، اطلاعاتی و فیلترهای گوناگون جذر بیرمن، تورنتون و بسیاری دیگر بوجود آمده‌اند. گویا مرسوم‌ترین نوع فیلتر کالمن فاز حلقهٔ بسته (phase-locked loop) می‌باشد که امروزه در رادیوها، رایانه‌ها و تقریباً تمامی انواع ابزارهای تصویری و ارتباطی کاربرد دارد.

اساس مدل سیستم پویا

فیلترهای کالمن بر اساس سیستم‌های خطی پویا (linear dynamical systems) گسسته در بازه زمانی هستند. آن‌ها بر اساس زنجیره مارکوف (Markov chain) به کمک عملگرهای خطی ساخته شده‌اند و توسط نوفه گاوسی (Gaussian noise) تحریک می‌شوند. حالت سیستم توسط برداری از اعداد حقیقی بیان می‌شود. در هر افزایش زمانی که در بازه‌های گسسته صورت می‌گیرد، یک عملگر خطی روی حالت فعلی اعمال می‌شود تا حالت بعدی را با کمی پارازیت ایجاد کند و اختیاراً در صورت شناخت روی کنترل‌کننده‌های سیستم برخی اطلاعات مرتبط را استخراج می‌کند. سپس عملگر خطی دیگر به همراه مقدار دیگری پارازیت خروجی قابل مشاهده‌ای از این حالت نامشخص تولید می‌کند. فیلتر کالمن قادر است مشابه مدل نامشخص مارکوف برخورد کند. با این تفاوت کلیدی که متغییرهای حالت نامشخص در یک فضای پیوسته مقدار می‌گیرند (نقطهٔ مقابل فضای حالت گسسته در مدل مارکوف). بعلاوه، مدل نامشخص مارکوف می‌تواند یک توزیع دلخواه برای مقادیر بعدی متغییرهای حالت ارائه کند، که در تناقض با مدل پارازیت گاوسی‌ای است که در فیلتر کالمن استفاده می‌شود. در اینجا یک دوگانگی بزرگ بین معادلات فیلتر کالمن و آن مدل مارکوف وجود دارد. مقاله‌ای در رابطه با این مدل و دیگر مدل‌ها در Roweis and Ghahramani و فصل ۱۳ Hamilton ارائه شده‌است.

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

F_{k: مدل انتقال حالات،}

H_{k: مدل مشاهده شده،}

Q_{k: کوواریانس پارازیت فرایند،}

R_{k: کوواریانس پارازیت مشاهده شده،}

B_{k: مدل ورودی-کنترل}

فیلتر کالمن بیان می‌کند که می‌توان حالت k را با استفاده از حالت (k – 1) با استفاده از رابطه زیر محاسبه کرد:

$\mathbf {x} _{k}=\mathbf {F} _{k}\mathbf {x} _{k-1}+\mathbf {B} _{k}\mathbf {u} _{k}+\mathbf {w} _{k}$

به‌طوری‌که:

F_{k: حالت انتقالی اعمال شده به xk−۱،}

B_{k: مدل ورودی-کنترل اعمال شده به بردار کنترلی uk,}

w_{k: فرایند نویزی با توزیع نرمال، میانگین صفر و واریانس Qk}

در زمان k،مشاهده z_k با توجه به حالت x_k به صورت زیر بدست می‌آید:

$\mathbf {z} _{k}=\mathbf {H} _{k}\mathbf {x} _{k}+\mathbf {v} _{k}$

به‌طوری‌که H_k مدل مشاهده شده که به فضای مشاهده شده نگاشت می‌شود و همچنین v_k نویز مشاهده شده با توزیع گاوسی، میانگین صفر و کوواریانس R_k است.

لازم است ذکر شود که حالت اولیه و بردار نویزی در هر محله از هم مستقل هستند.

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

شرح بیشتر

فیلتر کالمن یک تخمین‌گر بازگشتی است، یعنی تنها تخمین حالت قبل و مشاهده فعلی برای محاسبه تخمین حالت فعلی لازم است. برعکس بسیاری از تخمین‌گرها نیازی به نگهداری اطلاعات تخمین‌ها و مشاهدات تمام حالات قبل نیست. در اینجا ${\hat {\mathbf {x} }}_{n\mid m}$ بیانگر تخمینی از ${\mathbf {x}}$ در زمان n به شرط از مشاهدات پیش از این زمان است.

حالت فعلی فیلتر توسط دو متغیر تشریح می‌شود:

${\hat {\mathbf {x} }}_{k\mid k}$ تخمین حالت پسینی در زمان k به شرط مشاهدات پیش از k.
$\mathbf {P} _{k\mid k}$ ماتریس کوواریانس خطای پسین.

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

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

پیش‌بینی

تخمین حالت پیش‌بینی شده (پیشین)	${\hat {\mathbf {x} }}_{k\mid k-1}=\mathbf {F} _{k}{\hat {\mathbf {x} }}_{k-1\mid k-1}+\mathbf {B} _{k}\mathbf {u} _{k}$
تخمین کوواریانس پیش‌بینی شده (پیشین)	$\mathbf {P} _{k\mid k-1}=\mathbf {F} _{k}\mathbf {P} _{k-1\mid k-1}\mathbf {F} _{k}^{\text{T}}+\mathbf {Q} _{k}$

آپدیت

مشاهده جدید وابسته	${\tilde {\mathbf {y} }}_{k}=\mathbf {z} _{k}-\mathbf {H} _{k}{\hat {\mathbf {x} }}_{k\mid k-1}$
کوواریانس جدید وابسته	$\mathbf {S} _{k}=\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{T}+\mathbf {R} _{k}$
نتیجه بهینه کالمن	$\mathbf {K} _{k}=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{T}\mathbf {S} _{k}^{-1}$
تخمین حالت آپدیت شده (پسین)	${\hat {\mathbf {x} }}_{k\mid k}={\hat {\mathbf {x} }}_{k\mid k-1}+\mathbf {K} _{k}{\tilde {\mathbf {y} }}_{k}$
تخمین کوواریانس آپدیت شده (پسین)	$\mathbf {P} _{k\|k}=(I-\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\|k-1}$

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

ثابت‌ها

اگر مدلسازی دقیق باشد و ${\hat {\mathbf {x} }}_{0\mid 0}$ و $\mathbf {P} _{0\mid 0}$ بیانگر توزیع حالات ابتدایی سیستم باشند، مقادیر ثابت زیر بدست می‌آیند:

$\operatorname {E} [\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k}]=\operatorname {E} [\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k-1}]=0$
$\operatorname {E} [{\tilde {\mathbf {y} }}_{k}]=0$

به‌طوری‌که $\operatorname {E} [\xi ]$ امید ریاضی متغیر تصادفی $\xi$ است. در بالا تمامی تخمین‌ها دارای امید ریاضی صفر هستند.

همچنین:

$\mathbf {P} _{k\mid k}=\operatorname {cov} (\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})$ $\mathbf {P} _{k\mid k-1}=\operatorname {cov} (\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k-1})$
$\mathbf {S} _{k}=\operatorname {cov} ({\tilde {\mathbf {y} }}_{k})$

به این ترتیب ماتریس‌های کوواریانس نشان‌دهنده مقادیر تخمینی کوواریانس‌ها هستند.

تخمین کوواریانس‌های نویز Q_k و R_k

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

بهینگی و کارایی

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

مثال کاربرد عملی

کامیونی دارای اصطکاک در مسیری مستقیم را در نظر بگیرید. کامیون در مکان صفر ثابت است و سپس در مسیری تحت تأثیر نیروهای تصادفی به حرکت در می‌آید. موقعیت کامیون را در هر Δt ثانیه اندازه‌گیری می‌کنیم. اما این اندازه‌گیری مبهم است چرا ما تنها مدلی از مکان و سرعت کامیون را در نظر می‌گیریم. در اینجا فیلتر کالمن را برای این مدل بیان می‌کنیم.

چون $\mathbf {F} ,\mathbf {H} ,\mathbf {R} ,\mathbf {Q}$ ثابت هستند، شاخص‌های زمانی آن‌ها حذف می‌شوند.

موقعیت و سرعت کامیون در فضای خطی موقعیت آن توصیف می‌شود:

$\mathbf {x} _{k}={\begin{bmatrix}x\\{\dot {x}}\end{bmatrix}}$

${\dot {x}}$ سرعت، یعنی مشتق مکان نسبت به زمان است.

فرض کنیم در بازه زمانی میان (k − ۱) و k شتاب a_k که دارای توزیع طبیعی با میانگین صفر و واریانسσ_a است به آن اعمال شود. طبق قوانین حرکت نیوتن داریم:

$\mathbf {x} _{k}=\mathbf {F} \mathbf {x} _{k-1}+\mathbf {G} a_{k}$

$\mathbf {G}$ نتیجه شتابa_k را به سیستم اعمال می‌کند و همچنین داریم

$\mathbf {F} ={\begin{bmatrix}1&\Delta t\\0&1\end{bmatrix}}$

$\mathbf {G} ={\begin{bmatrix}{\frac {\Delta t^{2}}{2}}\\[6pt]\Delta t\end{bmatrix}}$

به این ترتیب

$\mathbf {x} _{k}=\mathbf {F} \mathbf {x} _{k-1}+\mathbf {w} _{k}$

به‌طوری‌که $\mathbf {w} _{k}\sim N(0,\mathbf {Q} )$ و

$\mathbf {Q} =\mathbf {G} \mathbf {G} ^{\text{T}}\sigma _{a}^{2}={\begin{bmatrix}{\frac {\Delta t^{4}}{4}}&{\frac {\Delta t^{3}}{2}}\\[6pt]{\frac {\Delta t^{3}}{2}}&\Delta t^{2}\end{bmatrix}}\sigma _{a}^{2}$

توزیع $N(0,\mathbf {Q} )$ کاملاً پیوسته نیست و بنابراین هیچ تابع توزیع احتمالی ندارد. روش دیگر بیان این توزیع به صورت زیر است:

$\mathbf {w} _{k}\sim \mathbf {G} \cdot N(0,\sigma _{a})$

در هر بازه زمانی، موقعیت کامیون که با نویزی آمیخته‌است در دست است. فرض کنیم این نویز v_k دارای توزیع طبیعی با میانگین صفر و واریانس σ_z باشد،

$\mathbf {z} _{k}=\mathbf {Hx} _{k}+\mathbf {v} _{k}$

به‌طوری‌که

$\mathbf {H} ={\begin{bmatrix}1&0\end{bmatrix}}$

$\mathbf {R} ={\textrm {E}}[\mathbf {v} _{k}\mathbf {v} _{k}^{\text{T}}]={\begin{bmatrix}\sigma _{z}^{2}\end{bmatrix}}$

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

${\hat {\mathbf {x} }}_{0\mid 0}={\begin{bmatrix}0\\0\end{bmatrix}}$

برای اینکه در فیلتر آگاهیمان نسبت به این موضوع را مشخص کنیم، یک ماتریس کوواریانس صفر تعریف می‌کنیم:

$\mathbf {P} _{0\mid 0}={\begin{bmatrix}0&0\\0&0\end{bmatrix}}$

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

$\mathbf {P} _{0\mid 0}={\begin{bmatrix}\sigma _{x}^{2}&0\\0&\sigma _{\dot {x}}^{2}\end{bmatrix}}$

به این ترتیب فیلتر قادر به محاسبه اطلاعات مدل بر اساس مقادیر اولیه می‌شود.

مشتقات

مشتق‌گیری از ماتریس تخمینی کوواریانس پسین

با توجه به مقدار ثابت کوواریانس خطا P_k | k در بالا

$\mathbf {P} _{k\mid k}=\mathrm {cov} (\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})$

با جایگذاری ${\hat {\mathbf {x} }}_{k\mid k}$ از روابط اثبات شده خواهیم داشت

$\mathbf {P} _{k\mid k}={\textrm {cov}}(\mathbf {x} _{k}-({\hat {\mathbf {x} }}_{k\mid k-1}+\mathbf {K} _{k}{\tilde {\mathbf {y} }}_{k}))$

حال مقدار ${\tilde {\mathbf {y} }}_{k}$ را جایگزین می‌کنیم

$\mathbf {P} _{k\mid k}={\textrm {cov}}(\mathbf {x} _{k}-({\hat {\mathbf {x} }}_{k\mid k-1}+\mathbf {K} _{k}(\mathbf {z} _{k}-\mathbf {H} _{k}{\hat {\mathbf {x} }}_{k\mid k-1})))$

همچنین $\mathbf {z} _{k}$ را نیز در رابطه جایگذاری می‌کنیم

$\mathbf {P} _{k\mid k}={\textrm {cov}}(\mathbf {x} _{k}-({\hat {\mathbf {x} }}_{k\mid k-1}+\mathbf {K} _{k}(\mathbf {H} _{k}\mathbf {x} _{k}+\mathbf {v} _{k}-\mathbf {H} _{k}{\hat {\mathbf {x} }}_{k\mid k-1})))$

با توجه به بردار خطا

$\mathbf {P} _{k|k}={\textrm {cov}}((I-\mathbf {K} _{k}\mathbf {H} _{k})(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k-1})-\mathbf {K} _{k}\mathbf {v} _{k})$

چون خطای اندازه‌گیری شدهv_k نسبت به سایر متغیرها ناهمبسته است، می‌توان گفت

$\mathbf {P} _{k|k}={\textrm {cov}}((I-\mathbf {K} _{k}\mathbf {H} _{k})(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k-1}))+{\textrm {cov}}(\mathbf {K} _{k}\mathbf {v} _{k})$

با توجه به ویژگی‌های ماتریس کوواریانس

$\mathbf {P} _{k\mid k}=(I-\mathbf {K} _{k}\mathbf {H} _{k}){\textrm {cov}}(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k-1})(I-\mathbf {K} _{k}\mathbf {H} _{k})^{\text{T}}+\mathbf {K} _{k}{\textrm {cov}}(\mathbf {v} _{k})\mathbf {K} _{k}^{\text{T}}$

با توجه به ثابت بودن P_k | k−1 و تعریف R_k نتیجه می‌شود

$\mathbf {P} _{k\mid k}=(I-\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\mid k-1}(I-\mathbf {K} _{k}\mathbf {H} _{k})^{\text{T}}+\mathbf {K} _{k}\mathbf {R} _{k}\mathbf {K} _{k}^{\text{T}}$

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

مشتق نتیجه کالمن

فیلتر کالمن یک تخمین‌گر کمینه مربع میانگین خطا (MMSE) است. خطا در تخمین حالت پسین برابر است با

$\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k}$

هدف ما کمینه کردن میانگین مربع این بردار خطا یعنی ${\textrm {E}}[\|\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k|k}\|^{2}]$ است. این معادل کمینه کردن اثر تخمین پسین ماتریس کوواریانس $\mathbf {P} _{k|k}$ است. با بسط رابطه بالا نتیجه می‌شود:

${\begin{aligned}\mathbf {P} _{k\mid k}&=\mathbf {P} _{k\mid k-1}-\mathbf {K} _{k}\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}-\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}\mathbf {K} _{k}^{\text{T}}+\mathbf {K} _{k}(\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}+\mathbf {R} _{k})\mathbf {K} _{k}^{\text{T}}\\[6pt]&=\mathbf {P} _{k\mid k-1}-\mathbf {K} _{k}\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}-\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}\mathbf {K} _{k}^{\text{T}}+\mathbf {K} _{k}\mathbf {S} _{k}\mathbf {K} _{k}^{\text{T}}\end{aligned}}$

اثر ماتریس زمانی کمینه می‌شود که حساب ماتریس صفر شود. با استفاده از خواص ماتریس گرادیان و تقارن ماتریس‌ها داریم:

${\frac {\partial \;\mathrm {tr} (\mathbf {P} _{k\mid k})}{\partial \;\mathbf {K} _{k}}}=-2(\mathbf {H} _{k}\mathbf {P} _{k\mid k-1})^{\text{T}}+2\mathbf {K} _{k}\mathbf {S} _{k}=0$

اگر این معادله را برای K_k حل کنیم، نتیجه کالمن بدست می‌آید

$\mathbf {K} _{k}\mathbf {S} _{k}=(\mathbf {H} _{k}\mathbf {P} _{k\mid k-1})^{\text{T}}=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}$

$\mathbf {K} _{k}=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}\mathbf {S} _{k}^{-1}$

این عبارت همان نتیجه بهینه کالمن است.

ساده کردن فرمول کوواریانس خطای پسین

با استفاده از نتیجه بهینه کالمن که در بالا بدست آمد می‌توان فرمول کوواریانس خطای پسین را ساده‌تر کرد. اگر طرفیت رابطه نتیجه بهینه کالمن را در S_kK_k^T ضرب کنیم، داریم:

$\mathbf {K} _{k}\mathbf {S} _{k}\mathbf {K} _{k}^{\mathrm {T} }=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\mathrm {T} }\mathbf {K} _{k}^{\mathrm {T} }$

با استفاده از فرمول بسط داده شده کوواریانس خطای پسین

$\mathbf {P} _{k\mid k}=\mathbf {P} _{k\mid k-1}-\mathbf {K} _{k}\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}-\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\mathrm {T} }\mathbf {K} _{k}^{\mathrm {T} }+\mathbf {K} _{k}\mathbf {S} _{k}\mathbf {K} _{k}^{\mathrm {T} }$

با ساده‌سازی دو جملهٔ آخر نتیجه می‌شود

$\mathbf {P} _{k\mid k}=\mathbf {P} _{k\mid k-1}-\mathbf {K} _{k}\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}=(I-\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\mid k-1}$

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

تحلیل درستی

معادلات فیلتر کردن کالمن تخمینی بازگشتی برای حالت ${\hat {\mathbf {x} }}_{k\mid k}$ و کوواریانس خطای $\mathbf {P} _{k\mid k}$ ارائه می‌کند. دقت تخمین به پارامترهای سیستم و نویز ورودی تخمین‌گر بستگی دارد. در غیاب مقادیر ماتریس‌های کوواریانس $\mathbf {Q} _{k}$ و $\mathbf {R} _{k}$ عبارت

$\mathbf {P} _{k\mid k}=(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\mid k-1}(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})^{\mathrm {T} }+\mathbf {K} _{k}\mathbf {R} _{k}\mathbf {K} _{k}^{\mathrm {T} }$

مقدار درست کوواریانس خطا را ارائه نمی‌کند. به عبارت دیگر، $\mathbf {P} _{k\mid k}\neq E[(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})^{\mathrm {T} }]$ . در بسیاری از کاربردهای بی‌درنگ، ماتریس‌های کوواریانس مورد استفاده در طراحی فیلتر کالمن با مقادیر واقعی ماتریس‌های کوواریانس تفاوت دارند. این تحلیل بیان می‌دارد که تخمین کوواریانس خطا زمانی که ماتریس‌های ورودی سیستم $\mathbf {F} _{k}$ و $\mathbf {H} _{k}$ باشند، نادرست است.

این بحث به حالتی که عدم قطعیت درمورد خطا داریم محدود می‌شود. حال مقادیر واقعی کوواریانس نویز را $\mathbf {Q} _{k}^{a}$ و $\mathbf {R} _{k}^{a}$ تعریف می‌کنیم به‌طوری‌که مقادیر آن‌ها به ترتیب در روابط جایگزین $\mathbf {Q} _{k}$ و $\mathbf {R} _{k}$ شوند. مقدار واقعی کوواریانس خطا را $\mathbf {P} _{k\mid k}^{a}$ و $\mathbf {P} _{k\mid k}$ با فیلتر کالمن محاسبه می‌شوند. اگر $\mathbf {Q} _{k}\equiv \mathbf {Q} _{k}^{a}$ و $\mathbf {R} _{k}\equiv \mathbf {R} _{k}^{a}$ $\mathbf {P} _{k\mid k}=\mathbf {P} _{k\mid k}^{a}$ خواهد بود. با محاسبه مقدار واقعی کوواریانس خطا $\mathbf {P} _{k\mid k}^{a}=E[(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})(\mathbf {x} _{k}-{\hat {\mathbf {x} }}_{k\mid k})^{\mathrm {T} }]$ و جایگذاری ${\widehat {\mathbf {x} }}_{k\mid k}$ و در نظر داشتن اینکه $E[\mathbf {w} _{k}\mathbf {w} _{k}^{\mathrm {T} }]=\mathbf {Q} _{k}^{a}$ and $E[\mathbf {v} _{k}\mathbf {v} _{k}^{\mathrm {T} }]=\mathbf {R} _{k}^{a}$ معادلات بازگشتی برای $\mathbf {P} _{k\mid k}^{a}$ بدست می‌آید:

$\mathbf {P} _{k\mid k-1}^{a}=\mathbf {F} _{k}\mathbf {P} _{k-1\mid k-1}^{a}\mathbf {F} _{k}^{\mathrm {T} }+\mathbf {Q} _{k}^{a}$

$\mathbf {P} _{k\mid k}^{a}=(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\mid k-1}^{a}(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})^{\mathrm {T} }+\mathbf {K} _{k}\mathbf {R} _{k}^{a}\mathbf {K} _{k}^{\mathrm {T} }$

محاسبه $\mathbf {P} _{k\mid k}$ با فرض $E[\mathbf {w} _{k}\mathbf {w} _{k}^{\mathrm {T} }]=\mathbf {Q} _{k}$ و $E[\mathbf {v} _{k}\mathbf {v} _{k}^{\mathrm {T} }]=\mathbf {R} _{k}$ انجام می‌شود. روابط بازگشتی برای $\mathbf {P} _{k\mid k}^{a}$ و $\mathbf {P} _{k\mid k}$ جز زمانی که $\mathbf {Q} _{k}^{a}$ و $\mathbf {R} _{k}^{a}$ را به ترتیب به جای $\mathbf {Q} _{k}$ و $\mathbf {R} _{k}$ در نظر بگیریم، یکتا هستند.

ریشه مربع

یکی از مشکلات فیلتر کالمن ثبات عددی است. اگر کوواریانس نویز Q_k کوچک باشد، مقدار ویژه آن منفی می‌شود. به این ترتیب ماتریس کوواریانس حالات P نامعین می‌شود در حالیکه باید مثبت معین باشد.

یک ویژگی ماتریس‌های مثبت معین این است که ریشه مربعی ماتریس مثلثی P = S·S^T دارند. این ریشه می‌تواند به کمک روش تفکیک چولسکی (Cholesky decomposition) محاسبه شود. اگر کوواریانس به این فرم نوشته شود، هیچ‌گاه قطری یا متقارن نخواهد بود. یک فرم معادل این ماتریس که با استفاده از تفکیک U-D بدست می‌آید، P = U·D·U^T

است کهU یک ماتریس مثلثی واحد و D یک ماتریس قطری است. در میان این دو فرم، فرم U-D رایج‌تر است و نیاز به محاسبات کمتری دارد.

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

‘تفکیک’L·D·L^T ماتریس کوواریانسS_k مبنای دیگر فیلترهای عددی و ریشه مربعی است. الگوریتم با تفکیک LU آغاز می‌شود و نتایج آن در ساختارL·D·L^T وارد می‌شود تا به روش Golub و Van Loan (الگوریتم ۴٫۱٫۲) در ماتریس قطری غیر واحد انجام شود.

ارتباط با تخمین بازگشتی بیز

فیلتر کالمن یکی از ساده‌ترین شبکه‌های پویای بیزی است. فیلتر کالمن حالات فعلی سیستم را در طول زمان به صورت بازگشتی، با استفاده از اندازه‌گیری‌های ورودی در مدل فرایندی ریاضی تخمین می‌زند. به‌طور مشابه تخمین بازگشتی بیز، توابع توزیع احتمال ناشناخته را به صورت بازگشتی، با استفاده از اندازه‌گیری‌های ورودی در مدل فرایندی ریاضی در طول زمان تخمین می‌زند.^[۲۰]

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

با فرض مارکوف، حالت فعلی سیستم مستقل از تمام حالات پیش از حالت قبلی آن است.

$p({\textbf {x}}_{k}\mid {\textbf {x}}_{0},\dots ,{\textbf {x}}_{k-1})=p({\textbf {x}}_{k}\mid {\textbf {x}}_{k-1})$

به‌طور مشابه اندازه‌گیری در بازه زمانی kام تنها به حالت قبلی وابسته است و مستقل از تمام حالات پیش از حالت قبلی آن است.

$p({\textbf {z}}_{k}\mid {\textbf {x}}_{0},\dots ,{\textbf {x}}_{k})=p({\textbf {z}}_{k}\mid {\textbf {x}}_{k})$

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

$p({\textbf {x}}_{0},\dots ,{\textbf {x}}_{k},{\textbf {z}}_{1},\dots ,{\textbf {z}}_{k})=p({\textbf {x}}_{0})\prod _{i=1}^{k}p({\textbf {z}}_{i}\mid {\textbf {x}}_{i})p({\textbf {x}}_{i}\mid {\textbf {x}}_{i-1})$

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

به این ترتیب گام‌های پیش‌بینی و آپدیت فیلتر کالمن به صورت احتمالاتی بدست می‌آیند. توزیع احتمال حالت پیش‌بینی شده حاصل انتگرال حاصلضرب توابع توزیع احتمال انتقال از حالت (k-1)ام به حالت kام است و حالت قبلی روی تمام $x_{k-1}$ های ممکن است.

$p({\textbf {x}}_{k}\mid {\textbf {Z}}_{k-1})=\int p({\textbf {x}}_{k}\mid {\textbf {x}}_{k-1})p({\textbf {x}}_{k-1}\mid {\textbf {Z}}_{k-1})\,d{\textbf {x}}_{k-1}$

اندازه‌گیری‌ها تا بازه زمانی kام عبارتند از:

${\textbf {Z}}_{t}=\left\{{\textbf {z}}_{1},\dots ,{\textbf {z}}_{t}\right\}$

توزیع احتمال آپدیت از حاصلضرب پیش‌بینی و احتمال بخت (likelihood) بدست می‌آید.

$p({\textbf {x}}_{k}\mid {\textbf {Z}}_{k})={\frac {p({\textbf {z}}_{k}\mid {\textbf {x}}_{k})p({\textbf {x}}_{k}\mid {\textbf {Z}}_{k-1})}{p({\textbf {z}}_{k}\mid {\textbf {Z}}_{k-1})}}$

به‌طوری‌که

$p({\textbf {z}}_{k}\mid {\textbf {Z}}_{k-1})=\int p({\textbf {z}}_{k}\mid {\textbf {x}}_{k})p({\textbf {x}}_{k}\mid {\textbf {Z}}_{k-1})\,d{\textbf {x}}_{k}$

ضریب نرمال‌سازی است.

توابع توزیع احتمال باقی‌مانده عبارتند از:

$p({\textbf {x}}_{k}\mid {\textbf {x}}_{k-1})={\mathcal {N}}({\textbf {F}}_{k}{\textbf {x}}_{k-1},{\textbf {Q}}_{k})$

$p({\textbf {z}}_{k}\mid {\textbf {x}}_{k})={\mathcal {N}}({\textbf {H}}_{k}{\textbf {x}}_{k},{\textbf {R}}_{k})$

$p({\textbf {x}}_{k-1}\mid {\textbf {Z}}_{k-1})={\mathcal {N}}({\hat {\textbf {x}}}_{k-1},{\textbf {P}}_{k-1})$

توجه کنید که تابع چگالی احتمال حالت قبل، یک تخمین است. فیلتر کالمن فیلتری بهینه است و به این ترتیب توزیع احتمال $\mathbf {x} _{k}$ به شرط اندازه‌گیری $\mathbf {Z} _{k}$ یک تخمین بهینه توسط فیلتر کالمن است.

تعریف فیلتر کالمن (Kalman filter) قسمت 1
تعریف فیلتر کالمن (Kalman filter) قسمت 2

مارس 9, 2019/0 دیدگاه /توسط daliri

فصل اول: توابع اولیه متلب

آموزش پردازش تصویر در نرم افزار متلب (Matlab)

مقدمه

آموزش توابع اولیه پردازش تصویر در متلب (فصل اول) : در این مجموعه قصد داریم به آموزش فهرست وار و سریع «جعبه ابزار پردازش تصویر» در نرم افزار متلب (Matlab) بپردازیم. سعی ما بر این است تا در پروژه های رایگانی که در سایت قرار می دهیم با لینک هر دستور به صفحه آموزشی آن، بتوانیم خیلی سریع و آسان با کاربرد دستورات و توابع مورد استفاده آشنا بشویم. در این مجموعه آموزشی فرض ما بر این است که دوستان آشنایی نسبی با نرم افزار متلب دارند و فعلا وارد این حوزه نمی شویم.

«فصل اول: آموزش توابع اولیه پردازش تصویر در متلب»

تابع ()imread :

هدف : هدف از این تابع خواندن تصویر از فایل می باشد.

نحوه استفاده :

imread( مسیر فایل )

مثال :

img= imread('c:\1.jpg');

تابع ()imshow :

هدف : هدف از این تابع نمایش تصویر می باشد.

نحوه استفاده :

imshow(نام متغیر)

مثال :

img= imread('c:\1.jpg');
imshow(img)

خروجی دستور :

تابع ()subplot:

هدف : جهت نمایش تصاویر بطور همزمان و در یک پنجره.

نحوه استفاده :


subplot( rows , columns , image number) , imshow( pic )

مثال :


subplot(131);
imshow(img(:,:,1)); 

subplot(132);
imshow(img(:,:,2)); 

subplot(133);
imshow(img(:,:,3));

خروجی دستور:

تابع ()title:

هدف : جهت نمایش توضیحات در مورد آخرین تصویر نمایش داده شده.

نحوه استفاده :

imshow(img); 
title('Red')

مثال :

subplot(131); 
imshow(img(:,:,1)); 
title('Red'); 

subplot(132); 
imshow(img(:,:,2)); 
title('Green'); 

subplot(133); 
imshow(img(:,:,3)); 
title('Blue'); ;

خروجی دستور :

تابع ()figure :

هدف : جهت نمایش تصویر در پنجره های جداگانه. در صورتی که بخواهیم خروجی دستور imshow در پنجره ای جدید باز شود از این دستور استفاده می شود.

نحوه استفاده :

figure , imshow( pic )

مثال :

figure , imshow( pic )

تابع ()imwrite :

هدف : هدف از این تابع ذخیره تصویر بصورت فایل می باشد.

نحوه استفاده :

imwrite( pic , path)

مثال :

 imwrite( pic , 'c:\1.jpg');

تابع ()iminfo:

هدف : نمایش اطلاعات تصویر.

نحوه استفاده :

iminfo( pic )

مثال :

 iminfo( peppers.png);

خروجی دستور:


ans =

 Filename: '/Applications/MATLAB_R2014a.app/toolbox/matla...'
FileModDate: '02-Apr-2013 15:55:52'
FileSize: 287677
Format: 'png'
FormatVersion: []
Width: 512
Height: 384
BitDepth: 24
ColorType: 'truecolor'
FormatSignature: [137 80 78 71 13 10 26 10]
Colormap: []
Histogram: []
InterlaceType: 'none'
Transparency: 'none'
SimpleTransparencyData: []
BackgroundColor: []
RenderingIntent: []
Chromaticities: []
Gamma: []
XResolution: []
YResolution: []
ResolutionUnit: []
XOffset: []
YOffset: []
OffsetUnit: []
SignificantBits: []
ImageModTime: '16 Jul 2002 16:46:41 +0000'
Title: []
Author: []
Description: 'Zesty peppers'
Copyright: 'Copyright The MathWorks, Inc.'
CreationTime: []
Software: []
Disclaimer: []
Warning: []
Source: []
Comment: []
OtherText: []

تابع ()imtool:

هدف : نمایش اطلاعات تصویر.

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

نحوه استفاده :

imtool( pic )

مثال :

 imtool( coins.png);

خروجی دستور:

پایان آموزش پردازش تصویر در متلب (فصل اول)

ژانویه 22, 2018/0 دیدگاه /توسط admin

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

آموزش های عمومی هوش مصنوعی

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

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

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

ماشین‌های تورینگ
ماشین محاسبه تورینگ ماشین تورینگ متناوب ماشین تورینگ کوانتومی ماشین تورینگ غیرقطعی ماشین خواندنی تورینگ ماشین راستگرد خواندنی تورینگ ماشین تورینگ احتمالی ماشین تورینگ چندمسیره ماشین‌های هم‌ارز با ماشین تورینگ

تاریخچه

زمینه‌های تاریخی:ماشین محاسباتی

معرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش ماشین‌های محاسباتی حالات متناهی به نمایش می‌گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه‌های نظریه ماشین محاسباتی بابیج(۱۸۳۴) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:

آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می‌دهد:

۱-عملگرهای ریاضی + و – و *

۲-هر ترتیبی از عملگرها قابل قبول است

۳-تکرار عملگر

۴-تکرار شرطی

۵-انتقال شرطی

تعریف منطقی (انتزاع ذهنی مفاهیم کلی)

ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0})\!$ ، که در اینجا:

$M\!$ برای نمایش مفهوم ماشین انتخاب شده است.
$Q\!$ مجموعه‌ای است متناهی، از حالات داخلی.
$\Gamma \!$ مجموعه‌ای متناهی موسوم به الفبای نوار و حاوی نمادی مخصوص $B\!$ برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
$\Sigma \!$ زیرمجموعه‌ای است از $\Gamma -\{B\}\!$ و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند بعنوان ورودی استفاده شوند.
$\delta \!$ عبارت است از یک تابع جزئی، موسوم به تابع انتقال از دامنهٔ $Q\times \Gamma \!$ به برد $Q\times \Gamma \times \{L,R\}\!$ .
$q_{0}\!$ حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را درآن آغاز می‌کنیم.

بطور کلی $\delta \!$ یک تابع جزئی روی $Q\!\times \Gamma \!$ است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

تعریف وصفی (عملی دنیای خارج از ذهن)

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

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

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

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

۴. یک جدول محدود (که گاهی جدول عمل یا تابع انتقال نامیده می‌شود)، از دستورالعمل‌ها وجود دارد که در حال حاضر، حالت (q_i) و نماد (a_j) به ماشین داده می‌شود (برای مدل‌های ۵تایی و گاهی ۴تایی) که روی نوار خوانده می‌شود و می‌گوید که ماشین، این موارد را به تزتیب زیر برای مدلهای ۵تایی انجام دهد:

یا پاک کردن یا نوشتن یک نماد (بصورت جایگزین کردن a_i با a_j۱)
حرکت کردن کلاهک نوار (که توسط d_k مشخص می‌شود و می‌تواند مقادیر L برای حرکت به چپ و R برای حرکت به سمت راست به خود بگیرد. همچنین مقدار N نشان دهنده ساکن بودن نوار است).
فرض کنید یک حالت مشابه یا یک حالت جدید مشخص شده است (رفتن به وضعیت q_i۱)

در مدل‌های ۴تایی پاک کردن یا نوشتن یک نماد (a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) بصورت دستورالعمل‌های جداگانه مشخص شده‌اند. بطور خاص، جدول به ماشین می‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده‌اند. اما عملیات‌های (ia) و (ib) دستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی‌ها دارند تا پر شوند. توجه داشته باشید که هر بخش از ماشین- حالتها و نمادها، مجموعه‌ها، اقدامات، چاپ کردن، پاک کردن و حرکت نوار- محدود، گسسته و تشخیص پذیر است. این، پتانسیل نامحدود نوارهاست که خود مقدار نامحدودی از یک فضای ذخیره‌سازی است.

مقایسه با ماشین‌های واقعی

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

چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟

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

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

۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.

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

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

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

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

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

نظریه پیچیدگی محاسباتی

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

همزمانی

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

منبع

ایده ماشین تورینگ چگونه مطرح شد و چه چیزی را دنبال می‌کرد؟

بخش اول

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

سرآغاز

تاریخچه محاسبات دیجیتال به دو بخش عهد عتیق و عهد جدید قابل تقسیم است. پیشوایان عهد قدیم به سرپرستی لایبنیتز (Gottfreid Wilhelm Leibniz) در سال 1670 میلادی منطق مورد نیاز ماشین‌های محاسباتی دیجیتال را فراهم کرده و پیشروان عهد جدید به سرپرستی فون نویمان (John von Neumann) در سال 1940 خود این ماشین‌ها را ساختند. آلن تورینگ، که در سال 1912 متولد شده است، جایی در میان این دو عصر مهم قرار گرفته و شاید بتوان وی را به نوعی پیوند دهنده این دو عهد مهم به شمار آورد. وی در سال 1936، درست در زمانی که به تازگی از کالج کینگ در دانشگاه کمبریج فارغ‌التحصیل شده و به دانشگاه پرینستون در نیوجرسی امریکا رفته بود، با نگارش و انتشار مقاله‌ای با عنوان «درباره اعداد رایانش‌پذیر، ‌با کاربردی بر مسئله تصمیم‌گیری» (On Computable Numbers, with an application to the Entscheidungs problem )، راهنمای پیاده‌سازی ماشین‌های با منطق ریاضی شد.

در این مقاله، تورینگ قصد داشت تا مسئله Entscheidungs problem ریاضی‌دان آلمانی، دیوید هیلبرت (David Hilbert) را که در سال 1928 طرح کرده بود، حل کند. موضوع نهایی مسئله فوق، تصمیم‌گیری درباره این بود که آیا یک روال مکانیکی می‌تواند صحت یک عبارت منطقی را در تعداد محدودی حرکت تعیین کند یا خیر؟ تورینگ در این مقاله، ایده و تصور رایج در دهه 1930 از یک کامپیوتر (یک شخص مجهز به یک مداد، کاغذ و دستورالعمل‌های مشخص) را در نظر گرفته و با حذف تمام رگه‌های هوشمندی (Intelligence) از آن به غیر از امکان پیروی از دستورالعمل‌ها و امکان خواندن و نوشتن علامت‌هایی از یک الفبای خاص روی یک رول کاغذ با طول بی نهایت، ماشینی را معرفی کرد که بعدها به ماشین تورینگ معروف شد و سرآغاز طلوع ماشین‌های محاسباتی دیجیتال امروزی شد.

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

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

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

بر همین اساس، وی پاسخ مسئلهEntscheidungs problem را منفی دانسته و از این طریق، پايه‌گذار طراحی ماشین‌های محاسباتی دیجیتال شد. در سال 1949، فون‌نویمان در یک سخنرانی با اشاره به این مفهوم مطرح شده توسط تورینگ عنوان کرد: «شما می‌توانید چیزی بسازید که کاری را که می‌شود انجام داد، انجام دهد. اما نمی‌توانید نمونه‌ای بسازید که به شما بگوید که آیا آن کار انجام‌پذیر است یا خیر؟»
تورینگ با درک محدودیت‌های ماشین‌های با قطعیت مشخص، شروع به جست‌وجو در زمینه محاسبات غیر‌قطعی با ماشین‌های پیشگو کرد. از نظر او، این نوع ماشین‌ها، همان روال گام به گام را مورد استفاده قرار می‌دهند اما با استفاده از نوعی پیشگویی، گاهی جهش‌هایی غیرقابل پیش‌بینی نیز انجام می‌دهند.

رمزگشایی

پس از پایان تحصیلات در دوره دکترا، تورینگ در سال 1938 به انگلیس بازگشت و گسترش جنگ جهانی دوم منجر به بروز نیاز هرچه بیشتر به ایده‌های وی شد. به همین دلیل، وی در مدرسه رمز و کدهای محرمانه دولت به خدمت گرفته شد. در آنجا، تورینگ و همکارانش به همراه استادش، ماکسول نیومن (Maxwell Newman) ارتباطات دشمن را، از جمله پیام‌های کدگذاری شده توسط ماشین آلمانی انيگما، رمزگشایی کردند. انیگما، ماشینی شبیه به ماشین تورینگ بود که امکان کد‌گذاری متن ورودی خود را با مکانیزمی مکانیکی فراهم می‌کرد. آن‌ها کار کدگشایی رمزهای انیگما را با مجموعه‌ای از دستگاه‌های الکترومکانیکی که بمب (bombe) نامیده می‌شدند، شروع کردند که هر کدام می‌توانست در هر لحظه 36 حالت احتمالی پیکربندی انیگما را شبیه‌سازی کند.

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

پس از پایان جنگ، نیاز به کامپیوترهای پیشرفته‌تر، از کاربردهای رمزگشایی به سمت طراحی بمب‌های اتمی پیش رفت. در سال 1946 ایالات‌متحده با داشتن کامپیوتر زمان جنگ خود، یعنی ENIAC (سرنام Electronic Numerical Integrator and Computer)، کار روی طراحی سلاح‌های اتمی را در پیش گرفت. در انستیتو مطالعات پیشرفته پرینستون و با حمایت مالی ارتش ایالات‌متحده، دفتر تحقیقات نیروی دریایی و همچنین کمیسیون انرژی اتمی امریکا، فون‌نویمان موظف شد تا نمونه الکترونیکی ماشین جامع تورینگ را بسازد. در آن زمان، هدف او ساخت ماشین تورینگی بود که حافظه آن با سرعت نور قابل دسترسی بوده و به پردازش در زمینه‌های مختلف می‌پرداخت. اما هدف دولت ایالات متحده امریکا از سرمایه‌گذاری روی چنین ماشینی تعیین امکان ساخت بمب هیدروژنی بود و به همین دلیل، فون نویمان قول داد که ماشین مذکور که از 5 کیلوبایت فضای ذخیره‌سازی بهره می‌برد، امکان اجرای کدهای داینامیک مذکور را داشته باشد.

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

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

ژانویه 18, 2018/1 دیدگاه/توسط daliri

بایگانی برچسب برای: ;kjvg jvnn

مثال کاربردی

نام‌گذاری و تاریخچه توسعه

اساس مدل سیستم پویا

شرح بیشتر

پیش‌بینی

آپدیت

ثابت‌ها

تخمین کوواریانس‌های نویز Qk و Rk

بهینگی و کارایی

مثال کاربرد عملی

مشتقات

مشتق‌گیری از ماتریس تخمینی کوواریانس پسین

مشتق نتیجه کالمن

ساده کردن فرمول کوواریانس خطای پسین

تحلیل درستی

ریشه مربع

ارتباط با تخمین بازگشتی بیز

مقدمه

«فصل اول: آموزش توابع اولیه پردازش تصویر در متلب»

تابع ()imread :

تابع ()imshow :

تابع ()subplot:

تابع ()title:

تابع ()figure :

تابع ()imwrite :

تابع ()iminfo:

تابع ()imtool:

پایان آموزش پردازش تصویر در متلب (فصل اول)

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

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

تاریخچه

تعریف منطقی (انتزاع ذهنی مفاهیم کلی)

تعریف وصفی (عملی دنیای خارج از ذهن)

مقایسه با ماشین‌های واقعی

چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟

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

نظریه پیچیدگی محاسباتی

همزمانی

ایده ماشین تورینگ چگونه مطرح شد و چه چیزی را دنبال می‌کرد؟

سرآغاز

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

رمزگشایی

تلفن های تماس:

ساعات کاری

پیوند ها :

محصولات :

تخمین کوواریانس‌های نویز Q_k و R_k