Connectionist Temporal Classification – CTC

CTC الگوریتمی است که در آموزش deep neural network ها در حوزه تشخیص گفتار و تشخیص دست خط و تشخیص عمل(action recognition) و  دیگر مسائل ترتیبی (sequence problems)  به عنوان loss function مورد استفاده قرار می گیرد. 

بطور کلی می توان گفت که CTC  قادر است تا خروجی deep neural network ها را گرفته و با محاسبه loss ، آموزش شبکه را ممکن سازد و همچین برای یک input sequence که تا به حال توسط شبکه رویت نشده خروجی تولید کند. بطور مثال برای یک ورودی صوتی بدون اینکه مشخص باشد چه کلمه ای بیان شده، کلمه را حدس بزند.

برای آشنایی  با  CTC در ادامه نحوه عملکرد آن بر روی صوت و دست نوشته بررسی خواهد شد

 CTC for Speech Recognition

شکل زیر CTC بر روی spectogram مربوط به صوت را نشان می دهد.

برای شروع فرض می کنیم که مجموعه داده ای از clip های صوتی به همراه نوشته ای که مشخص می کند چه چیزی در هر clip گفته شده داریم. مشخص نیست که کاراکتر های نوشته دقیقا در کجای clip صوتی قرار دارند.

یکی از راه ها این است که بخواهیم برای در نظر بگیریم که بطور مثل هر کاراکتر مربوط به ۱۰ عدد از ورودی هاست ولی ادای کلمات برای افراد مختلف متفاوت است بنابراین چنین فرضی برای ورودی های متفاوت که در واقع همگی یک کلمه را بیان می کنند نادرست است.

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

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

برای مثال اگر که بخواهیم ورودی X را به خروجی نوشته متناظر Y نگاشت کنیم هدف این است که یک mapping دقیق بین Xها و Yها بدست آوریم.

به دلیل مشکلات زیر قادر نیستم که از الگوریتم های یادگیری supervised ساده تر استفاده کنیم.

  • طول X و Y ممکن است متفاوت باشد
  • نگاشت دقیقی از مقادیر بین Xو Y وجود ندارد

به کمک CTC می توان با مشکلات بالا مقابله کرد. در واقع برای یک ورودی X توزیع خروجی ها بر روی تمامی Y های ممکن بدست می آید. به کمک این توزیع می توان خروجی محتمل تر را یافت یا اینکه احتمال یک خروجی دلخواه را محاسبه کرد.

Loss Function: مدل باید به گونه ای آموزش داده شود که بیشترین احتمال را به جواب درست نسبت دهد. بنابراین باید مقدار (p(YX محاسبه شود. یعنی به ازای ورودی X به جواب درست Y بیشترین احتمال را نسبت دهد. همچنین این احتمال باید مشتق پذیر باشد تا بتوان از گرادیان استفاده کرد.

Inference: در زمان نتیجه گیری باید مدل قادر باشد که برای X یک Y محتمل را پیشنهاد بدهد که مفهوم زیر را دارد.

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

Alignement

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

برای اینکه درک بهتری از نگاشت ها پیدا کنیم می توان از یک مثال استفاده کرد.

فرض کنیم که ورودی با طول ۶ داریم و خروجی[ Y = [c, a, t می باشد. یک راه ایجاد نگاشت این است که برای هر مرحله از ورودی یک کاراکتر از خروجی را در نظر بگیریم که می تواند بصورت زیر باشد.

و در نهایت تکرار ها را حذف کنیم تا خروجی بدست آید.

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

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

راه حل ارائه شده برای مشکلات بالا در CTC استفاده از blank token یا کاراکتر تهی است. که بصورت   نمایش داده می شود. દ به هیچ کاراکتری در خروجی متناظر نیست و در واقع در پایان کار حذف خواهد شد. در CTC طول خروجی باید با طول ورودی برابر باشد و تمام نگاشت هایی که پس از حذف દ ها و تکرار با Y برابر شوند قابل قبول هستند.

همانطور که در مثال بالا مشخص است برای کلمه hello بین دو حرف l از દ استفاده می کنیم که باعث می شود در خروجی هر دو l حفظ شوند و با کمک દ می توان بین helo و hello تفاوت ایجاد کرد.

اگر که بخواهیم برای همان مثال قبل که ورودی طول ۶ داشت و [Y = [c, a, t تعدادی از نگاشت های قابل قبول(valid) و غیر قابل قبول(invalid) بصورت زیر است. همانطور که دیده می شود در نگاشت های غیر قابل قبول یا یک کاراکتر وجود ندارد یا طول نگاشت کمتر از طول ورودی است. و در نگاشت های قابل قبول ممکنه است که દ در هر مرحله زمانی وجود داشته باشد و یا چند દ پشت سر هم وجود داشته باشد.

یکی از خواص قابل توجه نگاشت ها این است که ارتباط بین ورودی و خروجی بصورت many to one است. یعنی اینکه دو ورودی می توانند به یک خروجی نگاشت شوند ولی عکس این ارتباط برقرار نیست. این خاصیت  باعث ایجاد خاصیت دیگری می شود که آن هم این است که طول خروجی نمی تواند بیشتر از طول ورودی باشد.

Loss function

همانطور که پیش تر بحث شد خروجی یک شبکه RNN  در CTC استفاده می شود.

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

در مثال شکل زیر، ورودی در واقع spectogram یک صوت است که به عنوان ورودی به شبکه RNN داده می شود. در هر مرحله زمانی احتمال اینکه هر کاراکتر وجود داشته باشد(pt) مشخص می شود. که در شکل، مربع اطراف کاراکتر با رنگ تیره تر به معنای آن است که احتمال وجود آن کاراکتر در آن مرحله زمانی بیشتر است. همانطور که مطرح شد، ترکیبات مختلف به عنوان نگاشت های مختلف در نظر گرفته می شود و احتمال هر نگاشت بر اساس احتمالات در هر بازه زمانی محاسبه می شود. پس از آن، با حذف کاراکتر દ و حروف تکراری خروجی نهایی بدست می آید.  آن  سپس احتمالات نگاشت های مختلف با یکدیگر جمع می شود.

درواقع هدف CTC برای یک دوتایی (X, Y) این است که که احتمال (P(Y| X بدست آید.

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

محاسبه کردن CTC می تواند بسیار غیر کارآمد و سنگین باشد. اگر که بخواهیم احتمال تمام نگاشت ها را محاسبه کنیم و باهم جمع کنیم، برای مسائلی که تعداد نگاشت ها بسیار زیاد است، محاسبات بسیار کُند خواهد بود. برای حل این مشکل می توان از یک الگوریتم برنامه نویسی پویا     (Dynamic Programming Algorithm) استفاده کرد. به این صورت که در هر مرحله زمانی اگر خروجی دو نگاشت یکسان شد، دو نگاشت ادغام می شوند به یک نگاشت.

برنامه نویسی پویا روشی است که در آن یک مسئله پیچیده به زیر مسائل ساده تر تبدیل می شود و برای اجتناب از اینکه راه حل زیر مسائل چند بار محاسبه شود، راه حل آن ها ذخیره می شود.

در نهایت با استفاده از (p(X | Y که مشتق پذیر است و همان جمع و ضرب احتمالات در بازه های زمانی است، می توان گرادیان مربوط به loss function را حساب کرد و بر اساس آن عملیات backpropagation انجام می شود.

بر اساس فرمول بالا، منفی احتمال اینکه در مجموعه داده D، خروجی Y متعلق به ورودی X باشد، باید کمینه شود. در واقع همان مفهوم این را دارد که خود احتمال بیشینه شود.

Inference

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

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

در نهایت برای نگاشت انتخاب شده، و کاراکتر های تکراری را حذف می کنیم.

CTC for Handwriting Recognition

شکل زیر مراحل OCR را با کمک CTC نشان می دهد.

همانطور که بحث شد از Neural Networks استفاده می شود تا ویژگی های ورودی استخراج شود و برای هر کاراکتر در هر مرحله زمانی، در خروجی شبکه RNN یک امتیاز یا احتمال وجود دارد. پس می توان گفت که خروجی RNN یک ماتریس است که با کمک این ماتریس CTC loss بروز می شود.

در واقع برای هر عکس ورودی و متن صحیح آن(label) باید CTC loss محاسبه شود تا NN ها آموزش داده شوند.

برای اینکه دیدی از مراحل آموزش داشته باشیم. شکل زیر را در نظر بگیرید.

Training

فرض می کنیم که مجموعا دو بازه زمانی داریم شامل [t1, t0] و مجموعه کاراکتر ها شامل [a, b, -] می باشد. امتیاز هر node در کنار آن نوشته شده است. و در هر مرحله زمانی، مجموع امتیازات(احتمالات) برابر ۱ می باشد. در اینجا દ همان “-” می باشد.

اگر که فرض شود متن واقعی برای عکس ورودی ”a” باشد، باید  احتمال تمام نگاشت هایی که بعد از حذف حروف تکراری و “-” به “a” ختم می شود را یافت. در اینجا نگاشت های قابل قبول شامل “-aa”, “a-“, “a” می شود. برای بدست آموردن احتمال مربوط به هر نگاشت باید احتمال هر کاراکتر در هر بازه زمانی را در هم ضرب کرد. برای مثال در “a-” چون کاراکتر در مرحله زمانی اول برابر “-” می باشد، طبق شکل، احتمال آنکه در t0 کاراکتر “-” وجود داشته باشد برابر ۰.۶ می باشد. و احتمال وجود “a” در t1 برابر ۰.۴ می باشد که حاصل ضرب این دو احتمال برابر ۰.۲۴ می شود. احتمال “-a” و “aa” به ترتیب برابر ۰.۲۴ و ۰.۱۶ می شود که حاصل جمع احتمال سه نگاشت برابر  ۰.۶۴ = ۰.۱۶ +‌۰.۲۴ + ۰.۲۴ می شود. یعنی احتمال اینکه نوشته مربوط به عکس همان “a” باشد برابر ۰.۶۴ می باشد.

Best Path Decoding

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

بر اساس رنگ node ها مشخص است که در هر مرحله کدام node بیشترین احتمال را دارد. طبق احتمال هر کاراکتر در هر بازه زمانی، خروجی بصورت “aaa-b” می شود. که پس حذف حروف تکراری و کاراکتر های “-” خروجی همان “ab” می شود.

منابع

Sequence Modeling With CTC
An intuitive Explanation of Connectionist Temporal Classification

 

فوتر سایت

اسلایدر سایدبار

درباره ما

درباره ما

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

شبکه های اجتماعی

مطالب اخیر