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

وبلاگ شخصی بهروز ودادیان

روزنوشته‌های من از هنر، ریاضیات و کامپیوتر

تفریح با OpenCV: رگه‌های کم‌انرژی

توسط بهروز در سیزدهم اسفند ماه ۱۳۹۶ (کامپیوتر،پردازش تصویر)

با کتابخانه‌ی OpenCV کارهای زیادی می‌شود کرد. از عملیات اولیه‌ی کار با تصویر گرفته تا یادگیری ماشین. در این پست – که دیگر پست میانی یک تریلوژی نخواهد بود! – نحوه‌ی استفاده از OpenCV برای کاهش اندازه‌های یک تصویر با حذف کمترین میزان داده را مرور خواهم کرد. به این کار در ادبیات پردازش تصویر، seam carving می‌گویند.

ما می‌خواهیم طی این پست، همین بلا را سر این عکس از پنگوئن‌ها بیاوریم:

عکس پنگوئن‌ها
شکل ۱: عکس بخت برگشته

چشم انسان به تغییرات درون تصویر حساس است. به عبارت دیگر نگهداری داده‌های درون تصویر، نگهداری بخش‌هایی از تصویر است که مشتق آن‌ها بزرگتر از بقیه‌ی نقاط باشد: $$D(X)=|S_x*X|+|S_y*X|$$ عملگر $*$ نماینده‌ی کانولوشن و $S_x$ و $S_y$ کرنل مشتق سوبل در راستای افقی و عمودی هستند: $$S_x=\left[\begin{array}{ccc} -1 & 0 & 1\\ -2 & 0 & 2\\ -1 & 0 & 1 \end{array}\right], S_y=\left[\begin{array}{ccc} -1 & -2 & -1\\ 0 & 0 & 0\\ 1 & 2 & 1 \end{array}\right]$$

اسم خروجی تابع $D$ در عملیات seam carving، ماتریس انرژی است. بنابراین اولین قدم برای انجام عملیات seam carving، نوشتن تابع $D$ یا تابع محاسبه‌ی انرژی است:

cv::Mat computeEnergyMatrix(const cv::Mat& _image)
{
    cv::Mat sobelX, sobelY;
    cv::Sobel(_image, sobelX, CV_32F, 1, 0);
    cv::Sobel(_image, sobelY, CV_32F, 0, 1);
    cv::Mat energyMatrix = cv::abs(sobelX) + cv::abs(sobelY);
    cv::transform(energyMatrix, energyMatrix, cv::Matx13f(1,1,1));
    return energyMatrix;
}

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

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

نمونه‌ی ماتریس انرژی
شکل ۲: ماتریس انرژی عکس پنگوئن‌ها

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

یک seam نمونه

اگر خیلی اهل دقت در کارها باشید حتماً این سؤال برایتان پیش آمده که «خب چرا از هر سطر، نقطه‌ای که کمترین مقدار اهمیت را دارد انتخاب و سپس حذف نکنیم؟» سؤال خوبی است. خیلی خوب است که کد مربوط به این کار را نوشته و خروجی آن را مشاهده کنید. جواب این سؤال را در انتهای این پست می‌نویسم که فرصت برای پیاده‌سازی خودتان و آزمایش آن از دست نرود (می‌توانید کدهای مربوط به این پست را از آدرس https://gitlab.com/vedadian_samples/fun-with-opencv-2.git برداشته و تغییر دهید.)

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

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

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

#define MAX_DEVIATION   2
std::vector<int> findVerticalSeam(const cv::Mat& _energyMatrix)
{
    int m = _energyMatrix.rows, n = _energyMatrix.cols;

    cv::Mat pathEnergy = cv::Mat::zeros(cv::Size(n, m), CV_32FC1) + std::numeric_limits<float>::max();
    _energyMatrix(cv::Rect(0, 0, n, 1)).copyTo(pathEnergy(cv::Rect(0, 0, n, 1)));
    cv::Mat offsets = cv::Mat::zeros(cv::Size(n, m), CV_32SC1);
    for(int i = 1; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int o = -1; o <= 1; ++o) {
                if(j + o >= 0 && j + o < n) {
                    float offsetCost = pathEnergy.at<float>(i - 1, j + o) + _energyMatrix.at<float>(i, j);
                    if(pathEnergy.at<float>(i, j) > offsetCost) {
                        pathEnergy.at<float>(i, j) = offsetCost;
                        offsets.at<int>(i, j) = o;
                    }
                }
            }
        }
    }
    std::vector<int> seam(m);
    seam[m - 1] = 0;
    for(int i = 1; i < n; ++i)
        if(pathEnergy.at<float>(m - 1, i) < pathEnergy.at<float>(m - 1, seam[m - 1]))
            seam[m - 1] = i;
    for(int i = m - 1; i > 0; --i)
        seam[i - 1] = seam[i] + offsets.at<int>(i, seam[i]);
    return seam;
}

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

این دو بخش مسأله که حل شوند، کل مسأله حل شده است. کافیست که در یک حلقه شروع به یافتن seamها و حذف کردنشان بکنیم. این کار را آنقدر انجام دهیم که اندازه‌ی تصویر به میزان دلخواه کاهش یابد:

for(int i = 0; i < 250; ++i) {
    auto energyMatrix = computeEnergyMatrix(image);
    auto seam = findVerticalSeam(energyMatrix);
    image = removeVerticalSeam(image, seam);
    std::cout << (i + 1) << " seam(s) removed." << std::endl;
}

مثلاً در حلقه‌ی بالا، ۲۵۰ ستون از عرض تصویر کاهش پیدا می‌کند.

حالا برای تصویر پنگوئن‌ها که بالاتر آمده، همین کار را انجام می‌دهیم. نتیجه‌اش را می‌توانید در زیر ببینید:

حذف رگه‌های کم‌انرژی یا seam carving
شکل ۴: حذف رگه‌های کم‌انرژی یا seam carving

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

روش ساده‌انگارانه
شکل ۵: روش ساده‌انگارانه

همانطور که اشاره کردم، پیاده‌سازی‌های seam carving به زبان‌های پایتون و c++‎ در آدرس گیت https://gitlab.com/vedadian_samples/fun-with-opencv-2.git در دسترس هستند.

تفریح با OpenCV: یک شروع ساده

توسط بهروز در چهارم بهمن ماه ۱۳۹۶ (کامپیوتر،پردازش تصویر)

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

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

مقدمه

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

import numpy as np
x = np.ones((3,3), np.float)
x[1:,1:] = 0
print(x)

در اینجا اول numpy را به برنامه‌مان اضافه می‌کنیم. اسمش را هم می‌گذاریم np – چون تنبلی اصل اساسی برنامه‌نویسی خوش فرم است! بعدش یک ماتریس ۳ در ۳ که همه‌ی عناصر آن ۱ است می‌سازیم. در انتها، مقادیر زیرماتریس ۲ در ۲ انتهایی آن را صفر می‌کنیم و آن را چاپ می‌کنیم. اگر این را در پایتون اجرا کنید، خروجی زیر را مشاهده خواهید کرد:

[[ 1.  1.  1.]
 [ 1.  0.  0.]
 [ 1.  0.  0.]]

یادم رفت بگویم که برای نصب numpy و OpenCV می‌توانید از دستورات زیر استفاده کنید:

pip install --upgrade pip
pip install --upgrade setuptools
pip install --upgrade numpy
pip install --upgrade opencv_python

البته دو دستور اول برای این هستند که سایر کتابخانه‌ها به درستی نصب شوند و من همیشه آن‌ها را در توضیحات می‌آورم ولی عملاً یکبار اجرا کردنشان کافی است!

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

دامنه‌ی مقادیر موجود در تصاویر بین ۰ تا ۲۵۵ است و نوع آن‌ها np.uint8 – همان بایت خودمان. به همین جهت معمولاً در کار با OpenCV به جای np.float که در قطعه‌ی کد اول همین زیربخش استفاده شد، np.uint8 خواهیم دید.

متوسط‌گیری و بلور کردن تصویر

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

روش‌های مختلفی برای مات‌کردن تصویر وجود دارد که هر کدام برای مقابله با نوع خاصی از نویز مفید هستند (البته هیچکدام این روش‌ها نتایج قابل قبولی به دست نمی‌دهد، آن‌هم وقتی شبکه‌های عصبی عمیق برای حل این مسأله دست به کار شده‌اند!)

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

فرض کنید که تصویر ورودی را با استفاده از دستورات زیر خوانده‌ایم:

import cv2
import numpy as np

image = cv2.imread('robert_de_niro.jpg')

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

متوسط گیری
شکل ۲: متوسط گیری

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

simple = cv2.blur(image, (21, 21))

صد البته، دو عدد ۲۱ که در این دستور هستند طول و عرض پنجره‌ای هستند که معرفی کردم.

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

gaussian = cv2.GaussianBlur(image, (21, 21), 0)

اما این صفر بعد از ابعاد پنجره! این عدد به OpenCV می‌گوید که انحراف معیار مقادیر داخل پنجره را برای محاسبه‌ی وزن مدنظر قرار بده.

راه حل دیگر این است که در آن پنجره‌ی کذایی، بجای محاسبه‌ی متوسط، یا متوسط وزن‌دار، میانه محاسبه کنیم. میانه‌ی یک‌سری عدد، می‌شود عددی که در لیست مرتب‌شده‌ی آن‌ها در وسط قرار گیرد. مثلاً برای اعداد ۲،۳،۴،۴،۴،۵،۱۲،۱۶،۲۵ و ۲۵۵، مقدار میانه برابر ۵ است. این روش برای رفع نویز‌های فلفل نمک مفید است (نویزی که در آن مقادیر نویز یا خیلی بزرگند و یا خیلی کوچک، مثلاً نقاط تصادفی سیاه و سفید که در تصویر بصورت تصادفی بپاشیم.) این یکی هم یک سطر دستور است:

median = cv2.medianBlur(image, 21)

در مورد میانه، ابعاد پنجره‌ی مورد نظر می‌بایست حتماً مربعی باشد، به همین جهت فقط یک عدد نماینده‌ی اندازه‌ی پنجره شده است. البته این محدودیت تئوریک نیست و پیاده‌سازی OpenCV اینطوری است.

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

مقایسه‌ی روش‌های مات‌سازی
شکل ۳: مقایسه‌ی روش‌های بلور کردن

استخراج لبه‌های تصویر

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

لبه‌یابی در تصویر
شکل ۴: مقایسه‌ی روش‌های لبه‌یابی

یکی از روش‌های لبه‌یابی استفاده از عملگر سوبل است. در این روش مقادیر یک پنجره‌ی ۳ در ۳ اطراف هر نقطه در نظر گرفته می‌شود و مقادیر (وزن دار شده‌ی) یک طرف این پنجره از طرف دیگر کسر می‌شود. به طور دقیق بسته به جهت اعمال مشتق‌گیری یک کرنل به شکل زیر برای محاسبه استفاده می‌شود: $$K=\left[\begin{array}{cc} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{array}\right]$$ این کار هم از جنس همان بلورسازی است، فقط نصف وزن‌ها منفی‌اند. دستور این یکی می‌شود:

sobel = np.absolute(cv2.Sobel(image, cv2.CV_32F, 1, 0)).mean(2)

روش دیگر استفاده از لاپلاسین است. خلاصه‌تر از عملگر سوبل بگویم، در این روش کرنل زیر استفاده می‌شود! $$K=\left[\begin{array}{cc} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{array}\right]$$ و دستورش:

laplacian = np.absolute(cv2.Laplacian(image, cv2.CV_32F)).mean(2)

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

canny = cv2.Canny(image, 100, 200)

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

یک مثال با نمک

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

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

برای این مقصود با عملگر سوبل شروع می‌کنیم:

edges = np.absolute(cv2.Sobel(image, cv2.CV_32F, 1, 0)).mean(2)

بعدش مقادیر آن را بین ۰ و ۱ قرار می‌دهیم به نحوی که بیشترین مقدار به ۱ نگاشته شود و کمترین به صفر:

edges = (edges - edges.min()) / (edges.max() - edges.min())

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

edges = edges ** 0.25

اثر این کار را می‌توانید در تصویر زیر ببینید:

اثر ریشه‌ی چهارم گرفتن
شکل ۵: اثر ریشه‌ی چهارم گرفتن

خب، حالا باید یک نسخه‌ی مات شده‌ی تصویر را هم بسازیم:

blurred = cv2.medianBlur(image, 21)

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

edges = np.expand_dims(edges, 2)
edges = np.tile(edges, (1, 1, 3))
blurred = cv2.medianBlur(image, 21)
final = (1 - edges) * blurred + edges * image
final = final.astype(np.uint8)

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

با انجام این مراحل کار تمام می‌شود. نتیجه‌ی کار را می‌توانید در تصویر زیر ببینید:

نرم‌کردن تصویر
شکل ۶: نرم‌کردن تصویر در نقاط غیر لبه

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

کدهای مربوط به این پست در دو نسخه‌ی python و c++‎ از اینجا در دسترس هستند.

بودن یا نبودن

توسط بهروز در بیست و سوم آذر ماه ۱۳۹۶ (داستانک)

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

سعید: این بالا هم هوا بهاری شده است ها! شکوفه‌ها را می‌بینی؟ اصلاً بوی بهار هرجا که باشی خودش را به تو می‌رساند.

صادق: مثلاً قرار بود تحویل سال را با بچّه‌ها خانه‌ی مادرم باشیم. حالا بچّه‌ها هم، بدون من، آنجا نمی‌روند.

سعید: حالا این شیر خام خورده‌ها چطوری به پایگاه خبر داده‌اند؟

صادق: چه می‌دانم خبر مرگشان! حتماً موبایلشان آنتن می‌داده دیگر.

سعید: اینجا را ببین، مدّت زیادی از خاموش شدن این آتش نگذشته، نباید خیلی دورتر از اینجا باشند.

صادق: این «نه چندان دور» می‌تواند دو سه ساعت پیاده‌روی باشد. دلت را خوش نکن.

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

سعید: بالاخره پیدایشان کردیم.

صادق: زودتر برویم شرّ این ماجرا کم شود؛ شاید من هم به شب عید برسم.

نزدیک آنها که شدند دیدند هردو کلاه‌های سیاه به سر دارند که صورتشان را پوشانده و با اسلحه‌ی کمری در دست منتظرشان هستند. صدای شلّیک دو گلوله را شنیدند و بعدش فِیْداَوْت. بعد از مدّتی – که برایشان مشخّص نبود چند روز بوده و یا چند ساعت – در بیمارستان چشمشان باز شد.

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

سعید: خدا را شکر. هنوز زنده‌ام. فکر کردم دامادی پارسا را از دست دادم. چقدر دلم برای مریم تنگ شده. پرستار! پرستار! …

سنجه‌ها و انتگرال: فرایندهای تصادفی

توسط بهروز در شانزدهم آبان ماه ۱۳۹۶ (ریاضیات)

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

فرایندهای تصادفی را هم می‌توان مانند انتگرال در یک چهارچوب غیر دقیق مطالعه کرد؛ اما مطالعه‌ی آن‌ها در چهارچوب نظریه‌ی سنجه‌ها، استوارتر است و دیدگاه‌های بهتری را برای مطالعه کننده به ارمغان می‌آورد (دمش گرم!)

حالا بیایید یک مسأله را که به همین فرایندهای تصادفی مربوط می‌شود بررسی کنیم. فرض کنید که می‌خواهیم انتگرال یک تابع $f$ را در بازه‌ای خاص (مثلاً ۰ تا ۱) محاسبه کنیم، اما خود تابع را نداریم. چیزی که در دست داریم نمونه‌هایی از مقادیر $f$ است که توانسته‌ایم اندازه‌گیری کنیم. این مسأله کاملاً کاربردی است. ما در مورد توابعی که با آن‌ها سر و کار داریم، معمولاً اطلاعات کامل نداریم و فقط اندازه‌گیری‌های محدودی از آنها در دسترس ماست.

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

اما اگر اطلاعاتی راجع به تابع $f$ داشته باشیم که احتمالاتی باشند چه؟ آیا می‌توانیم از آن‌ها در بازسازی تابع یا انتگرال‌گیری از تابع استفاده کنیم؟ اصولاً اطلاعات احتمالاتی راجع به توابع یعنی چه؟

اینجاست که سنجه‌ها سروکله‌یشان پیدا می‌شود. با ابزارهای رایج به راحتی نمی‌شود یک مجموعه از توابع را اندازه گیری کرد (مثلاً احتمال به آن‌ها تخصیص داد.)

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

سنجه‌ی وینر

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

توابع نمونه
شکل ۱: یک فرایند تصادفی

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

اگر تا اینجا را با هم درست پیش آمده باشیم، باید بپرسید، خب این سنجه روی چه سیمگافیلدی تعریف شده است؟ فرض کنید که می‌دانیم توابع مد نظر ما در زمان‌های $t_0$، $t_1$ و همینطور تا $t_n$ مقادیرشان در بازه‌های خاصی است. مثلاً در زمان $t_0$ مقدار توابع مورد نظر ما در بازه‌ی $(5,10)$ قرار دارد، در زمان $t_1$ در بازه‌ی $(8,11)$ و … . برای این بازه‌ها هم اسامی $A_0$ تا $A_n$ را در نظر می‌گیریم. با داشتن این دانسته‌ها، عملاً یک زیرمجموعه از توابع نمونه‌ی فرایند تصادفی را توصیف کرده‌ایم. در میان همه‌ی توابع نمونه، آنهایی که در زمان‌های مشخص، مقادیری در بازه‌های مشخص اختیار می‌کنند. برای سهولت کار بیایید روی این زیر مجموعه یک اسم بگذاریم: $$C(t_0,\ldots,t_n;A_0,\ldots,A_n)$$ حالا برای این زیر مجموعه‌ها مقدار سنجه را تعریف می‌کنیم: $$\begin{array}{l} &&\mu\left(C(t_0,\ldots,t_n;A_0,\ldots,A_n)\right)=\\ &&\int_{A_0}\int_{A_1}\cdots\int_{A_n}p(t_n-t_{n-1},x_n-x_{n-1})\ldots p(t_0,x_0)dx_ndx_{n-1}\ldots dx_0 \end{array}$$ تابع $p$ هم همان فرم گوسی یعنی $p(a,b)=(4\pi a)^{-n/2}e^{-\mid b\mid^2/4t}$ است.

با در دست داشتن این سنجه می‌توانیم کارهای جالبی انجام دهیم. مثلاً امید ریاضی توان دوم توابعی که توزیع احتمالاتی وینر دارند چه تابعی است؟ دقت کنید که زیر مجموعه‌ی خاصی را مشخص نکرده‌ایم پس نه مقادیر $t_i$ داریم و نه بازه‌ی محدود $A_i$: $$\mathbb{E}(|\omega(t)|^2)=\int p(t,x)|x|^2dx=2nt$$

پس امید ریاضی اندازه‌ی تابع نمونه‌ی فرایندی با این قانون می‌شود $\sqrt{2nt}$.

به فرایندی که قانون احتمال آن سنجه‌ی وینر باشد، فرایند وینر می‌گویند (بدیهی نیست؟)

فرایند وینر در ریاضیات مالی و فیزیک، کاربردهای گسترده‌ای دارد.

خاتمه‌ی کلام

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

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

سنجه‌ها و انتگرال: سنجه! و سنجه چیست؟

توسط بهروز در دهم آبان ماه ۱۳۹۶ (ریاضیات)

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

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

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

سیگماجبرها

برای تنوع هم که شده، این بخش را با تعاریف خشک ریاضی شروع می‌کنم.

تعریف فرض کنید $D$ یک مجموعه و $2^D$ مجموعه‌ی توانی آن (مجموعه‌ی همه‌ی زیر مجموعه‌های $D$) باشد. هر زیر مجموعه $\Sigma\subseteq 2^D$ که سه شرط زیر را داشته باشد، یک سیگماجبر است:

  1. $D$ درون $\Sigma$ باشد: $D\in\Sigma$
  2. $\Sigma$ تحت عمل «متمم» گیری بسته باشد: $A\in\Sigma\Rightarrow D-A\in\Sigma$
  3. $\Sigma$ تحت عمل «اجتماع شمارا» بسته باشد: $A_1,A_2,A_3,\ldots\in\Sigma\Rightarrow \cup_{i=1}^\infty A_i\in\Sigma$

حالا این به ما چه ربطی دارد؟

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

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

خب پس دامنه‌ی مناسب سنجه‌ها، سیگماجبرها هستند. از همینجاست که سؤال‌هایی از این دست که «احتمال بی‌نهایت نقطه‌ی شمارا از مقادیر $X$ اگر $X$ چکالی گوسی داشته باشد، چه می‌شود؟» سالبه به انتفاع موضوع می‌شوند.

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

تعریف سنجه

باز هم با تعاریف خشک و دقیق ریاضی شروع می‌کنم:

تعریف فرض کنید $X$ یک مجموعه و $\Sigma$ یک سیگماجبر بر روی $X$ باشد. تابع $\mu$ از $\Sigma$ به $R\cup \{-\infty, \infty\}$ را یک سنجه می‌نامیم اگر:

  1. برد آن فقط شامل مقادیر مثبت و صفر باشد: $\forall E\subseteq X\Rightarrow \mu(E) \ge 0$
  2. مقدار خروجی آن برای مجموعه‌ی تهی صفر باشد: $\mu(\emptyset)=0$
  3. روی شمارا زیر مجموعه از $X$ جمع‌پذیر باشد: $\mu\left(\cup_{i=0}^\infty E_i\right)=\sum_{i=0}^\infty \mu(E_i)$

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

اگر در پاراگراف قبل دقت کرده باشید، متوجه شده‌اید که مقدار خروجی سنجه برای یک مجموعه را اندازه نامیدم. در واقع در فارسی به «نظریه‌ی سنجه‌ها» نظریه‌ی اندازه‌ها می‌گویند که اسم بدی هم نیست؛ اما به نظر من سنجه برای تابعی که اندازه‌ی یک مجموعه را «می‌سنجد» اسم مناسب‌تری است. با این وجود خروجی تابع سنجه، اندازه‌ی مجموعه‌ی ورودی است و من همین نامگذاری را در ادامه هم رعایت خواهم کرد.

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

Empty subset
شکل ۱: اندازه‌ی مجموعه‌ی تهی

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

Partitioning
شکل ۲: سازگاری نسبت به اجتماع

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

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

مثال

بیایید به محاسبه‌ی امید ریاضی، نگاه دیگری بیندازیم. تابعی مثل $f$ داریم که یک توزیع احتمال روی دامنه‌ی آن تعریف شده. مثلاً تابع $f$ می‌تواند میزان خرابی حاصل از وجود ناخالصی در مواد اولیه تولید IC باشد. ناخالصی را هم با میلی‌گرم در لیتر می‌سنجیم. فرض کنیم احتمال وجود مقدار خاصی ناخالصی در مواد اولیه، توزیع گوسی داشته باشد (این فرض، فرض کاملاً معقولی است؛ به قضیه‌ی حد مرکزی مراجعه کنید.)

حالا می‌خواهیم بدانیم بصورت متوسط چه میزان خرابی در ICهای تولیدی خواهیم داشت. برای محاسبه‌ی این مقدار باید امید ریاضی بگیریم: $$l=\mathbb{E}f(X)=\int f(X)dP(X)$$ یک راه محاسبه‌ی عددی یا فرمولی است. راه دیگر این است که تعدادی نمونه از توزیع $P$ درست کنیم. مثلاً ۱۰۰ تا؛ $X_0,\ldots,X_99$. چون این نمونه‌ها از سنجه‌ی $P$ تولید شده اند، تراکمشان هم متناسب با همان سنجه است. به همین خاطر می‌توانیم مقدار خرابی را اینطوری تخمین بزنیم: $$l=\mathbb{E}f(X)\approx \sum_{i=0}^{99} f(X_i)$$ در مسأله‌ی این مثال، محاسبه به این روش خیلی جذاب نیست. اما فرض کنید که توزیع مقدار ناخالصی در مواد اولیه را نداشته باشیم و فقط مقداری اندازه‌گیری از ناخالصی‌های روزهای گذشته در دسترس باشد. حالا دیگر مسأله فرق می‌کند.

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

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

سنجه‌ها و انتگرال: چشم‌ها را باید شست

توسط بهروز در سیزدهم مهر ماه ۱۳۹۶ (ریاضیات)

اگر دانشجوی تحصیلات تکمیلی در رشته‌های فنی و یا ریاضی هستید و یا بوده‌اید، حتماً با انتگرال‌هایی به فرم $$\int_D f(x)d\mu(x)$$ بر خورد کرده‌اید. مخصوصاً اگر به آمار و احتمال در مقالات جدی و جدید رسیده باشید که احتمال بالایی هم دارد.

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

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

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

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

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

چشم‌ها را باید شست

از دبیرستان خاطرمان هست که وقتی می‌خواستیم سطح زیر یک منحنی را که با $f(x)$ مشخص می‌شود حساب کنیم، دامنه‌ی آن را به قطعات خیلی ریز تقسیم می‌کردیم و در هر قطعه، مقدار $f(x)$ را در یک نقطه‌ی دلخواه محاسبه کرده و سطح آن تکه‌ی کوچک از منحنی را با سطح مستطیل کوچکی که تشکیل می‌شد تقریب می‌زدیم

Riemannian integral
شکل ۱: تقسیم دامنه‌ی تابع
و با کوچک‌تر کردن عرض مستطیل، تقریبمان را بهتر می‌کردیم. حد این تقریب‌ها وقتی تعداد مستطیل‌ها بی‌نهایت باشد، سطح زیر منحنی بود: $$\int f(x)dx=\text{lim}_{n\rightarrow \infty} \sum f(x_i)(x_{i+1}-x_{i})$$ اما این کار چندین مشکل دارد. یکی اینکه معتبر بودن این تقریب فقط برای زمانی است که دامنه‌ای که انتگرال روی آن محاسبه می‌شود، محدود باشد. در عمل برای محاسبه‌ی انتگرال‌ها روی دامنه‌های نامحدود، مجبوریم دوباره حد محاسبه‌ی انتگرال محدود را محاسبه کنیم. دوم اینکه وقتی این دامنه‌ی نامحدود، با دامنه‌ی نامحدود دیگری ترکیب شود – مثلاً وقتی یک انتگرال دوگانه را محاسبه می‌کنیم $\int\int$ – انواع و اقسام مشکلات فنی برای محاسبه پیش می‌آید.

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

Lebesgue integral
شکل ۲: تقسیم برد تابع
باز هم به لحاظ شهودی، می‌توانیم سطح زیر نمودار را با جمع سطح این مستطیل‌ها حساب کنیم. حقّه‌ای که باعث می‌شود، این روش محاسبه‌ی انتگرال اینقدر متفاوت شود این است که بجای اینکه این مستطیل‌ها را جداگانه در نظر بگیریم، یک «سنجه» در نظر می‌گیریم که بخش‌هایی از دامنه‌ی تابع را که مقادیر تابع در آنجا درون محدوده‌ی مورد نظر ماست، اندازه بگیرد
Lebesgue integral
شکل ۳: سنجه‌ی دامنه‌ی تابع
در مثال شکل ۳، می‌توانیم مساحت همه‌ی مستطیل‌ها را با عبارت زیر محاسبه کنیم: $$\text{area}=y_i\mu(A)$$ که در آن $A$ همان زیر مجموعه از دامنه‌ی تابع است که با بیضی‌های آبی جدا شده، $\mu$ تابع سنجه است که اندازه‌ی این زیر مجموعه را می‌سنجد و $y_i$ مقدار تابع در این زیر مجموعه‌ی دامنه است.

همین حقّه‌ی ساده، امکان انجام بسیاری از عملیات‌ها را فراهم می‌کند. باز در مثال شکل ۳، اگر تابع $\mu$ برای $A$ مقدار $\mid x_1-x_0\mid+\mid x_3-x_2\mid+\mid x_5-x_4\mid$ را برگرداند، مقدار انتگرالی که محاسبه می‌کنیم، دقیقاً برابر نسخه‌ی ریمانی آن خواهد بود. ولی این تنها سنجه‌ی کاربردی برای انتگرال‌گیری از تابع $f$ نیست. یک مثال مهم دیگر از سنجه‌های کاربردی، سنجه‌ی توزیع احتمال است.

بیایید فرض کنیم احتمال اینکه ورودی تابع ما – همان $f$ – در بازه‌های خاصی باشد، معلوم است. همچنین فرض کنید نام این سنجه را $P$ بگذاریم. به زبان ریاضی چیزی که گفتیم می‌شود: $$P(x\in A)=\mu(A)$$ حالا می‌توانیم انتگرال دیگری را محاسبه کنیم. مقدار این انتگرال، امید ریاضی تابع $f$ است. قبلاً برای محاسبه‌ی امید ریاضی تابع $f$، اول تابع چگالی احتمال را بدست می‌آوردیم که برابر $p(x)=\frac{dP}{dx}$ بود؛ بعدش انتگرال زیر را محاسبه می‌کردیم: $$\mathbb{E}(f(x))=\int f(x)p(x)dx$$ اما با فرم جدید، می‌توانیم بنویسیم: $$\mathbb{E}(f(x))=\int f(x)dP$$ در این فرم، حتی لازم نیست که $P$ مشتق‌پذیر باشد. لازم نیست دامنه‌ی تابع ما، از نوع دامنه‌های خوش‌رفتاری باشد که پیشتر با آن‌ها برخورد داشتیم. مثلاً دامنه‌ی تابع ما می‌تواند خودش مجموعه‌ای از توابع باشد. توابعی که دامنه‌شان خودش یک مجموعه از توابع باشد را در ریاضیات به نام فانکشنال می‌شناسیم.

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

اصلاً اگر این‌ها هم نمی‌تواند کاربردی بودن این زمینه از ریاضیات را خوب آشکار کند، یک مثال از این فانکشنال‌ها می‌زنم. تابع آشنای تبدیل فوریه یک فانکشنال است. یادتان که هست، این فانکشنال یک تابع پیوسته و یک مقدار حقیقی می‌گرفت و یک مقدار حقیقی دیگر بر می‌گرداند: $$F(f,\omega)=\int f(x)e^{j\omega x}d\mu(x)$$ مقصود از $\mu$ در فرمول بالا سنجه‌ی لبگ است. همانی که برای مجموعه‌ی $A$ در مثال شکل ۳، مقدار $\mid x_1-x_0\mid+\mid x_3-x_2\mid+\mid x_5-x_4\mid$ بر می‌گرداند.

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

دوگان‌های لعنتی

توسط بهروز در نوزدهم شهریور ماه ۱۳۹۶ (داستانک)

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

متن داستانک

این را من نمی‌گویم. خود خدا گفته است. هر کوفتی که در عالم هستی آفریده شده، حتماً دوگانش هم آفریده شده.

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

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

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

اولین بار سال ۱۳۷۲ بود که دیدمش. در کلاس اول ب. در یک میز کنار هم نشسته بودیم. درسش مثل من خوب بود. قدش هم مثل من متوسط. قیافه‌ای هم نداشت لاکردار. سرزبان را ولی – چرا دروغ بگویم؟ – داشت.

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

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

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

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

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

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

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

مدل‌های آموزش‌پذیر: ایستگاه آخر

توسط بهروز در نهم شهریور ماه ۱۳۹۶ (کامپیوتر،هوش مصنوعی)

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

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

مدل‌های آموزش‌پذیر واقعی

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

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

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

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

چیز دیگری که جالب توجه است، مثال‌های کاربردی و خوبی است که تیم توسعه دهنده با استفاده از همین کتابخانه نوشته و در اختیار عموم قرار داده‌اند. این مثال‌ها از گیت‌هاب قابل دریافت هستند. پیش از تلاش برای اجرای مثال‌ها، یادتان نرود که خود PyTorch را نصب کنید! دستورات مربوط به نصب PyTorch در صفحه‌ی اول سایت در قسمت «Run this command:» قابل مشاهده‌اند.

برای اینکه انگیزه‌ی بیشتری برای سر زدن به مثال‌ها داشته باشید، عناوینی از میانشان که برای خودم جذاب‌تر بودند را همینجا لیست می‌کنم:

  1. Super Resolution (یک جورهایی افزایش کیفیت تصویر)
  2. Language Model (ابزاری برای تولید متن به سبکی خاص و امتیازدهی به کیفیت جملات)
  3. MNIST (بازشناسی ارقام دستنویس انگلیسی)

یک مثال با نمک دیگر هم انتقال سبک تصویر است:

انتقال سبک تصویر
که می‌توانید هم کد منبع و هم توضیحاتش را اینجا پیدا کنید.

چرا سریال مدل‌های آموزش‌پذیر بوجود آمد

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

برای همین سعی کردم فارغ از جزئیات فنی، چیزی بنویسم که با شفافیت بیشتری شیوه‌ی یادگیری ماشین را نشان دهد. اینکه یادگیری ماشین همان یافتن نقطه‌ی کمینه‌ی یک تابع ریاضی است که نوع ساده‌اش را در ریاضیات دبیرستانی هم می‌بینیم. اینکه اگر شبکه‌های عصبی را با گراف‌هایی زیبا که یادآور ارتباطات نرون‌های داخل مغز است نشان می‌دهیم، یادمان نرود که روابط ریاضی مربوط به ارتباط دو لایه‌ی آن به سادگی $y=\sigma\left(Wx+b\right)$ است.

مدل‌های آموزش‌پذیر: خط راست، تابع ساده‌ی راستکردار

توسط بهروز در چهاردهم مرداد ماه ۱۳۹۶ (کامپیوتر،هوش مصنوعی)

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

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

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

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

نقشه‌ی منطقه

بنابراین تعدادی نقطه نماینده‌ی محل خانه‌های افراد قبیله‌ی آبی داریم و تعدادی نقطه نماینده‌ی خانه‌های افراد قبیله‌ی قرمز. خط راست را هم که در پست قبل دیدیم دو پارامتر دارد. یکی نماینده‌ی شیب خط و دیگری عرض از مبدأ آن ($a$ و $b$ در فرمول $y=f(x)=ax+b$.)

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

با یک نگاه به فرمول خط راست ($y-ax-b=0$) می‌توانیم نتیجه‌ی در یک سمت خط راست بودن چند نقطه را حدس بزنیم. اگر مختصات نقاطی که روی خط راست هستند را درون فرمول بگذاریم که مشخص است و عدد صفر بدست می‌آید. اما اگر چند نقطه در یک طرف خط باشند، علامت مقداری که از قرار دادن مختصات آن‌ها در فرمول بدست می‌آید برابر خواهد بود.

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

خطوط ممکن

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

خطوط پشتیبان

چون گفتیم که خطوط پشتیبان موازی‌اند، پس پارامتر $a$ آن‌ها یکسان است. اما عرض از مبدأ یکسانی ندارند. مثلاً عرض از مبدأ یکی از آن‌ها $b_0$ و دیگری $b_1$ است.

مسأله‌ی مورد نظر ما را می‌شود بصورت زیر بیان کرد: $$\begin{array}{l l} \text{Maximize } \frac{\mid b_0-b_1 \mid}{1+a^2} & \\ \text{subject to} & l_i(y_i-ax_i-0.5(b_0+b_1)) > 0 \end{array}$$

مفهوم رابطه‌ی بالا این است که مقدار $\frac{\mid b_0-b_1 \mid}{1+a^2}$ را بیشینه کن در حالی که برای همه‌ی نقاط (چه مربوط به قبیله‌ی قرمز و چه آبی) مقدار علامت آن نقطه (علامت مربوط به قبیله – $l_i$) ضرب در مقداری که از قرار دادن مختصات نقطه در فرمول خط بدست می‌آید، مقداری مثبت باشد. این یعنی خط به درستی برچسب قبیله را پیش‌بینی کند.

آخ! باز هم یک مشکل دیگر! آنهم برای یک مسأله‌ی ساده مثل این. چیزی که تا اینجا بدست آمده یک مسأله‌ی محدب نیست و جعبه‌ابزارهای بهینه‌سازی نمی‌توانند با تضمین مناسب این مسأله را حل کنند. اما راه حل مسأله چیز دشواری نیست. کافی است فرمول خط راست‌مان را طور دیگری بنویسیم. این را هم در دبیرستان دیده‌ایم: $$ay+bx+c=0$$

با این کار یک درجه‌ی آزادی نالازم به فرمول خط اضافه می‌شود. اما همین درجه‌ی آزادی نالازم می‌تواند خیلی از مشکلات را حل کند. برای نمایش خطوط پستیبان، لازم نیست که عرض از مبدأ آن‌ها را در نظر داشته باشیم. اینبار خط اصلی جداکننده را $ay+bx+c=0$ در نظر می‌گیریم و دو خط پشتیبان را بصورت: $$\begin{array}{l} ay+bx+c-1=0 \Leftarrow y-(-\frac{b}{a})x-(-\frac{c-1}{a})=0\\ ay+bx+c+1=0 \Leftarrow y-(-\frac{b}{a})x-(-\frac{c+1}{a})=0 \end{array}$$ دقت کنید هرچند درجه‌ی آزادی به فرمول خط راست اضافه شده، درجات آزادی کل مسأله تغییری نکرده!

حالا مسأله‌ی ما تبدیل می‌شود به: $$\begin{array}{l l} \text{Maximize } \frac{\mid 2 \mid}{a^2+b^2} & \\ \text{subject to} & l_i(ay_i+bx_i+c) > 0 \end{array}$$ با برداشتن یک قدم دیگر به یک مسأله‌ی محدب می‌رسیم، کافیست که فرم تابع هدف معکوس شود: $$\begin{array}{l l} \text{Minimize } a^2+b^2 & \\ \text{subject to} & l_i(ay_i+bx_i+c) > 0 \end{array}$$

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

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

اگر برنامه را بگیرید و اجرا کنید، نتیجه‌ی زیر را می‌بینید

خروجی برنامه

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

sudo apt-get install python-opencv

کتابخانه‌های بعدی، matplotlib، numpy، cvxopt و cvxpy هستند. همه‌ی اینها را می‌توانید با دستورات زیر نصب کنید

sudo su
pip install --upgrade pip
pip install --upgrade matplotlib
pip install --upgrade numpy
pip install --upgrade cvxopt
pip install --upgrade cvxpy

حالا کافیست برنامه را از git کپی بگیرید و یا از آدرس گیت‌لب دانلود کنید و بعد با دستور زیر آن را اجرا نمایید

python doit.py

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

مدل‌های آموزش‌پذیر: این کامپیوتر فهیم، چگونه می‌آموزد

توسط بهروز در بیست و سوم آبان ماه ۱۳۹۵ (کامپیوتر،هوش مصنوعی)

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

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

اما مگر می‌شود؟ یک مشت فیلیپ فلاپ نادان و چند ده گرم نیمه‌رسانا یاد بگیرند چگونه ببینند و چگونه بشنوند؟

توابع ریاضی از منظری دیگر

اولین گونه‌ای از توابع ریاضی که به ما می‌آموزند – اگر اشتباه نکنم – خط راست است. تابع $f(x)=ax+b$. لااقل این اولین تابع عملیاتی است که با آن آشنا می‌شویم. تابعی با یک متغیر که نماینده‌ی یک خط صاف در یک صفحه‌ی دو بعدی مانند یک ورق کاغذ است. بسته به اینکه مقادیر $a$ و $b$ چه باشد، محل و شیب خط، عوض می‌شود.

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

نمونه‌ی طبقه‌بندی توسط خط راست

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

محققان انواع و اقسام زیادی از این توابع کلّی را طراحی و آزمایش کرده‌اند. شبکه‌های عصبی[۱]، ماشین‌های بردار پشتیبان[۲]، توابع فازی، مدل‌های احتمالاتی گرافی[۳] و مانند این‌ها. باز هم تأکید می‌کنم که همه‌ی این‌ها – از منظر یادگیری ماشین – توابعی با تعداد زیاد پارامتر هستند. این‌ها مدل‌هایی هستند که در عمل روی فضاهایی با ابعاد بسیار بالا – در حد ده‌ها و صدها هزار بعد – کار می‌کنند و تعداد پارمترهاشان خیلی از این مقدار بیشتر هم هست.

چگونه تابع خود را آموزش دهیم

برای بررسی این موضوع بهتر است به مثال شیرین خط مستقیم برگردیم. تابع $f(x;a,b)=ax+b$. این دفعه ورودی‌های تابع را به دو بخش تقسیم کردم. بخش ورودی یا همان $x$ و بخش پارامترها $a$ و $b$. از منظر ریاضیات و محاسبات، این دو دسته ورودی هیچ تفاوتی ندارند. در عمل هم تفاوتی ندارند. این فقط به ما کمک می‌کند که هنگام طراحی بتوانیم مقادیر درست را به ورودی درست بفرستیم. اگر برنامه‌نویس باشید، حتماً با استانداردهای نام‌گذاری بر خورد کرده‌اید! استفاده‌ی هوشمندانه از این نکته می‌تواند مسأله‌ی آموزش دادن تابع را حل کند.

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

فرض کنیم مجموعه‌ی آموزشی ما شامل نمونه‌هایی بصورت $D=\left\{(x_1,f_1),(x_2,f_2),\ldots,(x_N,f_N)\right\}$ است. برای آموزش دادن، تابع جدیدی تعریف می‌کنیم که فقط $a$ و $b$ را به عنوان ورودی می‌گیرد. اسمش را هم می‌گذاریم تابع خطا و با $J$ نمایشش می‌دهیم.

$$J(a,b)=\sum_{i=1}^N \|f(x_i;a,b)-f_i\|^2$$

حالا به کمک معلم مربوطه $a$ و $b$ ای پیدا می‌کنیم که مقدار $J$ برایش کمترین باشد. این یعنی مقادیری که نتیجه‌ی مورد نظر ما را بهتر تأمین کند. اگر به فرم $J$ دقت کنید، تفاوت تابع یادگرفته شده از مقدار مورد نظر ما را محاسبه کرده، به توان ۲ رسانده و این اختلاف را برای همه‌ی نمونه‌هایی که به کامپیوتر نشان داده‌ایم، جمع زده. کوچک بودن مقدار $J$ یعنی، تک تک جملات درون سیگمای جمع کوچک بوده‌اند – چون همگی اعدادی مثبت‌اند.

و امّا معلم فرهیخته‌ی ما، کسی نیست جز «جعبه‌ابزار بهینه‌سازی». جعبه‌ابزاری که محققان «بهینه‌سازی» در ریاضیات و علوم مهندسی، در اختیار ما قرار داده‌اند. اگر به این مبحث علاقه‌مندید، کتاب استفان بوید – یکی از بهترین دانشمندان دوست‌داشتنی – را پیشنهاد می‌کنم که بخوانید. امّا به عنوان استفاده کننده، الگوریتم‌ها وجود دارند و جعبه‌ابزارها نوشته شده‌اند. در مورد مسائل ساده مانند برنامه‌ریزی خطی – به قول بوید عزیز – ابزارها دیگر به تکنولوژی تبدیل شده‌اند و در حالت کلّی هم می‌توان بدون عمیق شدن زیاد، از آن‌ها استفاده کرد.

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


  1. Artificial Neural Network

  2. Support Vector Machine

  3. Probabilistic Graphical Model