تعلم الآلة

الحل الرياضي للانحدار الخطي

Analytical Solution (Normal Equation)

صورة فارس القنيعير فارس القنيعير تابع على تويتر 8 مايو، 2018
6 2 دقائق

شرحت في الدرسين الانحدار الخطي والانحدار الخطي المتعدد كيف يمكن البحث عن أفضل نموذج (model) باستخدام التحسين (optimization) بالبحث عن المعاملات (coefficients أو parameters) التي تعطينا أقل خطأ. هناك طريقة أخرى لحساب المعاملات في الانحدار الخطي عن طريق الحل الرياضي باستخدام ما يطلق عليه Normal equation. لفهم المعادلة تحتاج إلى خلفية عن الجبر الخطي (Linear Algebra)، هذه مراجعة كتبتها سابقاً فيها ما تحتاجه لفهم المعادلة.

للتذكير، الهدف من الانحدار الخطي إيجاد المعاملات (w) التي تعطينا أقل خطأ (residual error). التوقع (\hat{y}) ممكن يحسب عن طريق المعادلة التالية:

\hat{y}=w_0+w_1x_1+w_2x_2+\quad . . . \quad +w_nx_n

وممكن تكتب باستخدام المتجهات بالشكل التالي:

\hat{y}=\mathbf{w}^T \mathbf{x}

لحساب الخطأ نستخدم معادلة RSS:

RSS = \sum^N_{i=1} (\hat{y}-y)^2

المتغير y هنا هو القيمة التي نعرفها للعينة، والمفترض أن يتم توقعها بشكل صحيح.

في البداية نحتاج أن نضع كل المدخلات في مصفوفة، والمخرجات (أو الهدف) في متجه. المدخلات هي الخصائص التي شرحتها في درس الانحدار الخطي، مثل حجم المنزل وعدد الغرف في مثال توقع أسعار المنازل. والمخرجات هي النتيجة المطلوبة، وهي في هذا المثال أسعار المنازل. المدخلات سنمثلها في المصفوفة X كالتالي:

\begin{bmatrix} x_{0,1} \quad x_{1,1} \quad x_{2,1} \quad . . . \quad x_{n,1} \\ x_{0,2} \quad x_{1,2} \quad x_{2,2} \quad . . . \quad x_{n,2} \\ . \\ . \\ . \\ x_{0,m} \quad x_{1,m} \quad x_{2,m} \quad . . . \quad x_{n,m} \end{bmatrix}

حيث m هو عدد العينات (كل صف يمثل عينة)، و n عدد الخصائص (الأعمدة) لكل عينة. في العمود الأول يتم وضع واحد قيمة للـ bias (x_0)، وهو ما يقابل التقاطع الذي شرحته في درس الانحدار الخطي. وبنفس الطريقة نستطيع تمثيل المخرجات في المتجه y كالتالي:

\begin{bmatrix} y_1 \\ y_2 \\ . \\ . \\ . \\ y_m  \end{bmatrix}

ووضعناها في متجه لأنه لدينا قيمة واحدة فقط للمخرجات، وهي السعر. يمكننا الآن كتابة المعادلة بالطريقة التالية (راجع معادلة الخط المستقيم في الدروس السابقة) لنحل w:

\mathbf{y} = \mathbf{X}\mathbf{w}

وللتوضيح، سيكون شكلها هكذا:

\begin{bmatrix} y_1 \\ y_2 \\ . \\ . \\ . \\ y_m  \end{bmatrix} = \begin{bmatrix} x_{0,1} \quad x_{1,1} \quad x_{2,1} \quad . . . \quad x_{n,1} \\ x_{0,2} \quad x_{1,2} \quad x_{2,2} \quad . . . \quad x_{n,2} \\ . \\ . \\ . \\ x_{0,m} \quad x_{1,m} \quad x_{2,m} \quad . . . \quad x_{n,m} \end{bmatrix} \begin{bmatrix} w_0 \\ w_1 \\ . \\ . \\ . \\ w_n  \end{bmatrix}

نحتاج الآن أن نحل المعادلة لنحصل على القيم w. لحل w نضرب الطرفين في منقول X (لمراجعة العمليات التي سنستخدمها):

\mathbf{X}^T\mathbf{y} = \mathbf{X}^T\mathbf{X}\mathbf{w}

لنتخلص من \mathbf{X}^T\mathbf{X} في طرف w، نضرب معكوسها في الطرفين (على افتراض أنها قابلة لذلك):

(\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} = (\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^T\mathbf{X}\mathbf{w}

وهكذا نحصل على معادلة Normal equation التالية:

\mathbf{w} =  (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}

تنبيه: حاولت الاختصار قدر المستطاع بدون إخلال لإيصال الفكرة الأساسية، ومن أراد الاستزادة ومعرفة لماذا هذه المعادلة تعطينا نتيجة مشابهة لاستخدام Gradient Descent فيمكنه مراجعة هذه الصفحة.

متى أستخدم Normal Equation؟

كما رأينا، فباستخدام هذه المعادلة يمكن حل الانحدار الخطي بدون خوارزمية Gradient Descent، التي تتطلب غالباً العديد من التكرارات (loops) لحلها. كذلك، لا نحتاج أن نبحث عن أفضل قيم (hyper-parameters) لتعمل الخوارزمية، مثل معدل التعلم في Gradient Descent. ولكن مشكلة Normal equation أن تعقيد الخوارزمية لحل المعادلة مرتبط طردياً بعدد الخصائص (تقريباً O(n^3) )، وذلك بسبب عمليات حساب المعكوس. فكلما زاد عدد الخصائص زادت العمليات لحل المعادلة مما يستلزم وقتاً أكبر. لهذا إذا كانت الخصائص قليلة فيمكنك استخدام Normal equation، وإذا كانت كثيرة جداً فيفضل حينها استخدام Gradient Descent كما تم شرحه في الدرسين السابقين.

الوسوم
صورة فارس القنيعير فارس القنيعير تابع على تويتر 8 مايو، 2018
6 2 دقائق
اظهر المزيد
صورة فارس القنيعير

فارس القنيعير

‏‏‏‏‏‏‏‏‏‏‏‏‏مختص بالذكاء الاصطناعي، تعلم الآلة ورؤية الحاسب. مهتم بتحليل ومعالجة البيانات بشكل عام. ضمن خبراء جووجل في تعلم الآلة (ML GDE).

‫6 تعليقات

  1. احياناً
    احد القيم الذاتية للمصفوفة {{mathbf{X}^T\mathbf{X} تكون بصفر، المحدد لها سوف يكون بصفر. في هذه الحالة لانستطيع ايجاد معكوس المصفوفة، اي لايمكن استخدام الحل الرياضي العادي.

    رد

  3. يفضل استخدام normal equation في حال features اقل من 10,000

    عدم وجود معكوس لبعض المصفوفات , قد تكون من بعض الاسباب
    – كثره features بحيث ان بعض features تتداخل خصائهم مثلا احدهم حساب المساحه بالمتر والاخر بالانش
    – عدد العينات اقل من عدد features

    المذكور اعلاه حسب dr. ِAndrew

    رد

  4. معلومات قيمة جداً تفيد في عدة مجالات خاصة من يريد التمعق في مجال الذكاء الاصطناعي وعلم البيانات
    ﻷن اغلب الاوقات نرى اشخاص يتعاملون مع مكتبات الذكاء الاصطناعي كصندوق اسود ولايفهمون المنطق الرياضي الذي يجري داخله
    شكراً جزيلاً

    رد

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى