Курс Эндрю Ына Машинное Обучение в Стэнфордском университете (CS229 - Machine Learning)

Разделы сайта


Курс Эндрю Ына Машинное Обучение в Стэнфордском университете (CS229 - Machine Learning)

Определение термина Машинное Обучение от Артура Самуэля: "Machine Learning is the field of study that gives computers the ability to learn without being explicitly programmed", т.е. "область исследования, которая дает компьютерам возможность учиться без явного программирования".

Определение термина Машинное Обучение от Тома Митчелла: "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.", т.е. "говорят, что компьютерная программа учится на опыте E по отношению к некоторому классу задач T и измерению производительности P, если ее производительность при выполнении задач в T, измеренная P, улучшается с опытом E".

Пример: игра в шашки. E = опыт, полученный от многочисленных партий. T = задача игры в шашки. P = вероятность того, что программа выиграет следующую игру.

  • GNU Octave (официальный сайт). Введение в Octave для инженеров и математиков. Авторы: Е.Р. Алексеев, О.В. Чеснокова
  • Supervised learning. CS229 Lecture notes by Andrew Ng.
  • Неделя 3. Логистическая регрессия.
  • Неделя 3. Регуляризация.
  • Неделя 4. Нейронные сети.
  • Целью моделей "Обучение с учителем" (Supervised learning) является поиск параметров (весов), которые минимизируют функцию потерь (Cost function). По размерности независимой переменной $x$ можно выделить однофакторные (univariable) и многофакторые (multivariable) модели. Если независимая переменная $x^{(i)}$ является скалярным значением, то имеем одинарную (univariate) модель. Когда независимая переменная является многомерной, то есть представлена вектором, получаем множественную (multivariate ) модель. В последующих примерах, это поиск $\theta_n$ для каждой независимой переменной $x_n$ с использованием линейной регрессии. Отличная статья с примерами кода на Python: Линейные модели: простая регрессия. Начало этой статьи с описанием многообразия линейных моделей здесь .

    Определение термина Cost function (loss function, error function, функция потерь) - это мера того, насколько ошибочна модель с точки зрения ее способности оценивать взаимосвязь между $\theta$ и $y$. Обычно это выражается разницей или расстоянием между прогнозируемым и фактическим значением искомого параметра: $$J(\theta) =\frac{1}{2m}\sum \limits_{i=1}^{m} \left(h_\theta(x^{(i)})-y^{(i)}\right)^2$$ где $J(\theta) =$ $J(\theta_0, \theta_1,\theta_2, ..., \theta_n)$;
    $h_\theta(x)=$ $\theta_0+\theta_1 x_1+\theta_2 x_2+...+\theta_n x_n$.
    Если сделать так, что $x_0=1$, то $h_\theta(x)$ можно записать как $\sum\limits_{i=1}^{n} \theta_i x_i$ $=\theta^Tx$. Соответственно лучший код на Octave для этого задания:

    computeCostMulti.m :

    function J = computeCostMulti(X, y, theta)
                  
      %   COMPUTECOSTMULTI Compute cost for linear regression with multiple variables
      %   J = COMPUTECOSTMULTI(X, y, theta) computes the cost of using theta as the
      %   parameter for linear regression to fit the data points in X and y
    
      %   Initialize some useful values
      m = length(y); % number of training examples
    
      %   You need to return the following variables correctly 
      J = 0;
    
      % ====================== YOUR CODE HERE ======================
      %   Instructions: Compute the cost of a particular choice of theta
      %               You should set J to the cost.
    
      J = (1/(2*m))*(sum(((X*theta)-y).^2));
    
      % =========================================================================
    
    end

    Про назначение коэффициента $\frac{1}{2m}$ в функции потерь можно прочитать в ответах на следующие вопросы: 1. Почему в функции потерь (cost function) используется формула средней квадратичной ошибки (mean squared error, MSE)?, 2. Зачем нужно делить на $2m$?, 3. Функция потерь (cost function) в Методе наименьших квадратов (МНК, Ordinary Least Squares, OLS) регрессионного анализа.

    Определение термина Gradient descent (Градиентный спуск) - метод нахождения локального экстремума (минимума или максимума) функции с помощью движения вдоль градиента. $$\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta)$$ где $j=0, 1, 2...n$, а $n$ - количество шагов, необходимых для вычисления оптимального значения $\theta$;
    $\alpha$ - шаг метода Градиентный спуск, скорость обучения. Основное правило: при каждом шаге значение $\theta_j$ должно уменьшаться, поэтому значение $\alpha$ не должно быть слишком большим. Но если значение $\alpha$ очень маленькое, то метод будет работать очень долго. Поэтому всегда требуется искать золотую середину.
    $\frac{\partial}{\partial \theta_j} J(\theta)$ - частная производная, которая равна $\frac{\partial}{\partial \theta_j} \frac{1}{2m}\sum \limits_{i=1}^{m} \left(h_\theta(x^{(i)})-y^{(i)}\right)^2$ = $2 \cdot \frac{1}{2m} \left(h_\theta(x^{(i)})-y^{(i)}\right) \cdot \frac{\partial}{\partial \theta_j} \left(h_\theta(x^{(i)})-y^{(i)}\right)$ = $\frac{1}{m} \left(h_\theta(x^{(i)})-y^{(i)}\right) \cdot \frac{\partial}{\partial \theta_j} \left(\sum \limits_{i=1}^{m} \theta_i x^{(i)}_j - y^{(i)}\right)$ = $\frac{1}{m} \left(h_\theta(x^{(i)})-y^{(i)}\right) x^{(i)}_j$, в итоге получаем: $$\theta_j := \theta_j + \alpha \frac{1}{m} \left(y^{(i)}-h_\theta(x^{(i)})\right) x^{(i)}_j$$

    Код на Octave для заданий второй недели по определению шага градиентного спуска: theta = theta -((1/m) * ((X * theta) - y)' * X)' * alpha.

    gradientDescentMulti.m :

    function [theta, J_history] = gradientDescentMulti(X, y, theta, alpha, num_iters)
                    
      %   GRADIENTDESCENTMULTI Performs gradient descent to learn theta
      %   theta = GRADIENTDESCENTMULTI(x, y, theta, alpha, num_iters) updates theta by
      %   taking num_iters gradient steps with learning rate alpha
    
      % Initialize some useful values
      m = length(y); % number of training examples
      J_history = zeros(num_iters, 1);
    
      for iter = 1:num_iters
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Perform a single gradient step on the parameter vector
      %               theta. 
      %
      % Hint: While debugging, it can be useful to print out the values
      %       of the cost function (computeCostMulti) and gradient here.
      %
    
      %%%%%%%% CORRECT %%%%%%%%%%   
      error = (X * theta) - y;
      theta = theta - ((alpha/m) * X'*error);
      %%%%%%%%%%%%%%%%%%%%%%%%%%%
    
      % ============================================================
    
      % Save the cost J in every iteration    
      J_history(iter) = computeCostMulti(X, y, theta);
    
      end
    end

    Если features (признаки) отличаются на порядки, то их масштабирование существенно ускоряет работу метода градиентного спуска. Эта процедура называется Feature scaling.

    featureNormalize.m :

    function [X_norm, mu, sigma] = featureNormalize(X)
                        
      %   FEATURENORMALIZE Normalizes the features in X 
      %   FEATURENORMALIZE(X) returns a normalized version of X where
      %   the mean value of each feature is 0 and the standard deviation
      %   is 1. This is often a good preprocessing step to do when
      %   working with learning algorithms.
    
      %   You need to set these values correctly
      X_norm = X;
      mu = zeros(1, size(X, 2));
      sigma = zeros(1, size(X, 2));
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: First, for each feature dimension, compute the mean
      %               of the feature and subtract it from the dataset,
      %               storing the mean value in mu. Next, compute the 
      %               standard deviation of each feature and divide
      %               each feature by it's standard deviation, storing
      %               the standard deviation in sigma. 
      %
      %               Note that X is a matrix where each column is a 
      %               feature and each row is an example. You need 
      %               to perform the normalization separately for 
      %               each feature. 
      %
      % Hint: You might find the 'mean' and 'std' functions useful.
      %       
    
      mu = mean(X);
      sigma = std(X);
      X_norm = (X - mu)./sigma;
    
      % ============================================================
    end

    Помимо градиентного спуска можно использовать метод нормальных уравнений (the normal equations). Вот пост про этот метод.

    normalEqn.m :

    function [theta] = normalEqn(X, y)
      
      %   NORMALEQN Computes the closed-form solution to linear regression 
      %   NORMALEQN(X,y) computes the closed-form solution to linear 
      %   regression using the normal equations.
    
      theta = zeros(size(X, 2), 1);
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Complete the code to compute the closed form solution
      %               to linear regression and put the result in theta.
      %
    
      % ---------------------- Sample Solution ----------------------
    
      theta = pinv(X'*X)*X'*y;
    
      % -------------------------------------------------------------
      % ============================================================
    end

    Логистическая регрессия

    Цель логистической регрессии, как и любого классификатора, состоит в том, чтобы выяснить, каким образом разделить данные, чтобы обеспечить точное предсказание класса данного наблюдения с использованием информации, присутствующей в его признаках (features).

    Логистическая функция (сигмоида): $$\Large{h_\theta }\left( x \right) = \frac{1}{{1 + {e^{ - {\theta ^T}x}}}}$$

    ее вероятностная интерпритация ${h _\theta }\left( {{x _i}} \right) = {\rm{P}}\left( {{y _i} = 1|{x _i};\theta } \right)$.

    sigmoid.m :

    function g = sigmoid(z)
      %SIGMOID Compute sigmoid function
      %   g = SIGMOID(z) computes the sigmoid of z.
    
      % You need to return the following variables correctly 
      g = zeros(size(z));
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Compute the sigmoid of each value of z (z can be a matrix,
      %               vector or scalar).
      g = 1./(1+exp(-z));
    
      % =============================================================
    end
    

    predict.m :

    function p = predict(theta, X)
      %PREDICT Predict whether the label is 0 or 1 using learned logistic 
      %regression parameters theta
      %   p = PREDICT(theta, X) computes the predictions for X using a 
      %   threshold at 0.5 (i.e., if sigmoid(theta'*x) >= 0.5, predict 1)
    
      m = size(X, 1); % Number of training examples
    
      % You need to return the following variables correctly
      
      p = zeros(m, 1);
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Complete the following code to make predictions using
      %               your learned logistic regression parameters. 
      %               You should set p to a vector of 0's and 1's
      %
      % Dimentions:
      % X     =  m x (n+1)
      % theta = (n+1) x 1
    
      p=(sigmoid(X*theta)>=0.5);
    
      %p = double(sigmoid(X * theta)>=0.5);
      % =========================================================================
    end
    

    Функция потерь логистической регрессии (Cost function for logistic regression): $$J\left( \theta \right) = \frac{1}{m}\sum\limits_{i = 1}^m {{\rm{Cost}}({h _\theta }\left( {{x _i}} \right),{y _i})}$$, где $\operatorname{Cost}(h_\theta(x),y) =$ $\begin{cases} -\log(h_\theta(x)), & \text{if $y$ = 1} \\ -\log(1-h_\theta(x)), & \text{if $y$ = 0} \end{cases}$

    или более кратко ${\rm{Cost}}({h _\theta }\left( x \right),y) =$ $- y\log \left( {{h _\theta }\left( x \right)} \right) -$ $\left( {1 - y} \right)\log \left( {1 - {h _\theta }\left( x \right)} \right)$.

    В итоге функция потерь логистической регрессии имеет вид:

    $J\left( \theta \right) =$ $\frac{1}{m}\sum\limits _{i = 1}^m { - {y _i}\log \left( {{h _\theta }\left( {{x _i}} \right)} \right) -}$ ${\left( {1 - {y _i}} \right)\log \left( {1 - {h _\theta }\left( {{x _i}} \right)} \right)}$.

    Здесь подробное объяснение, как взять частную производную фунции потерь логистической регрессии в алгоритме градиентного спуска: ${\theta _j}: = {\theta _j} - \alpha \frac{\partial }{{\partial {\theta _j}}}J\left( \theta \right)$.

    costFunction.m :

    function [J, grad] = costFunction(theta, X, y)
        
      %   COSTFUNCTION Compute cost and gradient for logistic regression
      %   J = COSTFUNCTION(theta, X, y) computes the cost of using theta as the
      %   parameter for logistic regression and the gradient of the cost
      %   w.r.t. to the parameters.
    
      % Initialize some useful values
      m = length(y); % number of training examples
    
      % You need to return the following variables correctly 
      J = 0;
      grad = zeros(size(theta));
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Compute the cost of a particular choice of theta.
      %               You should set J to the cost.
      %               Compute the partial derivatives and set grad to the partial
      %               derivatives of the cost w.r.t. each parameter in theta
      %
      % Note: grad should have the same dimensions as theta
      %
      %DIMENSIONS: 
      %   theta = (n+1) x 1
      %   X     = m x (n+1)
      %   y     = m x 1
      %   grad  = (n+1) x 1
      %   J     = Scalar
    
      z = X * theta;      % m x 1
      h_x = sigmoid(z);   % m x 1 
    
      J = (1/m)*sum((-y.*log(h_x))-((1-y).*log(1-h_x))); % scalar
    
      grad = (1/m)* (X'*(h_x-y));     % (n+1) x 1
    
      % =============================================================
    
    end
    Градиентный спуск — метод оптимизации первого порядка (первая производная). Вот более сложные и быстрые способы оптимизации $\theta$, которые могут быть использованы вместо метода градиентного спуска:
    Conjugate gradient method (метод сопряженных градиентов). Подробное описание алгоритма в статье Jonathan Richard Shewchuk от 1994 года "Введение в метод сопряженного градиента без мучительной боли"
    Метод BFGS - Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm)
    Метод Limited-memory BFGS - (L-BFGS or LM-BFGS)
    Поиск минимума нелинейной функции нескольких переменных без ограничения на переменные можно осуществлять с помощью встроенной в Matlab/Octave функции fminunc. Она позволяет использовать предварительно заданные командой optimset порог сходимости для значения целевой функции, вектор градиентов options, grad-obj, матрицу Гесса, функцию умножения матрицы Гесса или график разреженности матрицы Гесса целевой функции:
    Документация на MathWorks
    Практикум по решению задач оптимизации в пакете MATLAB

    Регуляризация

    Регуляризация в машинном обучении — метод добавления некоторой дополнительной информации к условию с целью решить некорректно поставленную задачу или предотвратить переобучение.

    Функция потерь для линейной регрессии с учетом регуляризации
    Регуляризация линейной регрессии
    Метод градиентного спуска для линейной модели регрессии с учетом регуляризации
    Метод градиентного спуска для линейной модели регрессии с учетом регуляризации
    Функция потерь для логистической регрессии с учетом регуляризации
    Регуляризация логистической регрессии
    Метод градиентного спуска для логистической регрессии с учетом регуляризации
    Метод градиентного спуска для логистической регрессии с учетом регуляризации
    Метод градиентного спуска для логистической регрессии с учетом регуляризации

    costFunctionReg.m :

    function [J, grad] = costFunctionReg(theta, X, y, lambda)
        %COSTFUNCTIONREG Compute cost and gradient for logistic regression with regularization
      %   J = COSTFUNCTIONREG(theta, X, y, lambda) computes the cost of using
      %   theta as the parameter for regularized logistic regression and the
      %   gradient of the cost w.r.t. to the parameters. 
    
      % Initialize some useful values
      m = length(y); % number of training examples
    
      % You need to return the following variables correctly 
      J = 0;
      grad = zeros(size(theta));
    
      % ====================== YOUR CODE HERE ======================
      % Instructions: Compute the cost of a particular choice of theta.
      %               You should set J to the cost.
      %               Compute the partial derivatives and set grad to the partial
      %               derivatives of the cost w.r.t. each parameter in theta
    
      %DIMENSIONS: 
      %   theta = (n+1) x 1
      %   X     = m x (n+1)
      %   y     = m x 1
      %   grad  = (n+1) x 1
      %   J     = Scalar
    
      z = X * theta;      % m x 1
      h_x = sigmoid(z);  % m x 1 
    
      reg_term = (lambda/(2*m)) * sum(theta(2:end).^2);
    
      J = (1/m)*sum((-y.*log(h_x))-((1-y).*log(1-h_x))) + reg_term; % scalar
    
      grad(1) = (1/m)* (X(:,1)'*(h_x-y));                                  % 1 x 1
      grad(2:end) = (1/m)* (X(:,2:end)'*(h_x-y))+(lambda/m)*theta(2:end);  % n x 1
    
      % =============================================================
    end

    Нейронные сети

    Код для lrCostFunction.m такой же как и в costFunctionReg.m из предыдущего урока.

    oneVsAll.m :

    function [all_theta] = oneVsAll(X, y, num_labels, lambda)
        %ONEVSALL trains multiple logistic regression classifiers and returns all
        %the classifiers in a matrix all_theta, where the i-th row of all_theta 
        %corresponds to the classifier for label i
        %   [all_theta] = ONEVSALL(X, y, num_labels, lambda) trains num_labels
        %   logistic regression classifiers and returns each of these classifiers
        %   in a matrix all_theta, where the i-th row of all_theta corresponds 
        %   to the classifier for label i
    
        % num_labels = No. of output classifier (Here, it is 10)
    
        % Some useful variables
        m = size(X, 1);        % No. of Training Samples == No. of Images : (Here, 5000) 
        n = size(X, 2);        % No. of features == No. of pixels in each Image : (Here, 400)
    
        % You need to return the following variables correctly 
        all_theta = zeros(num_labels, n + 1);
        %DIMENSIONS: num_labels x (input_layer_size+1) == num_labels x (no_of_features+1) == 10 x 401
    
        %DIMENSIONS: X = m x input_layer_size
        %Here, 1 row in X represents 1 training Image of pixel 20x20
    
        % Add ones to the X data matrix
        X = [ones(m, 1) X];   %DIMENSIONS: X = m x (input_layer_size+1) = m x (no_of_features+1)
    
        % ====================== YOUR CODE HERE ======================
        % Instructions: You should complete the following code to train num_labels
        %               logistic regression classifiers with regularization
        %               parameter lambda. 
        %
        % Hint: theta(:) will return a column vector.
        %
        % Hint: You can use y == c to obtain a vector of 1's and 0's that tell you
        %       whether the ground truth is true/false for this class.
        %
        % Note: For this assignment, we recommend using fmincg to optimize the cost
        %       function. It is okay to use a for-loop (for c = 1:num_labels) to
        %       loop over the different classes.
        %
        %       fmincg works similarly to fminunc, but is more efficient when we
        %       are dealing with large number of parameters.
        %
        % Example Code for fmincg:
        %
        %     % Set Initial theta
        %     initial_theta = zeros(n + 1, 1);
        %     
        %     % Set options for fminunc
        %     options = optimset('GradObj', 'on', 'MaxIter', 50);
        % 
        %     % Run fmincg to obtain the optimal theta
        %     % This function will return theta and the cost 
        %     [theta] = ...
        %         fmincg (@(t)(lrCostFunction(t, X, (y == c), lambda)), ...
        %                 initial_theta, options);
        %
    
        initial_theta = zeros(n+1, 1);
        options = optimset('GradObj', 'on', 'MaxIter', 50);
    
        for c=1:num_labels
        all_theta(c,:) = ...
                 fmincg (@(t)(lrCostFunction(t, X, (y == c), lambda)), ...
                         initial_theta, options);
        end
    
        % =========================================================================
      end


  • Решение заданий на Python от John Wittenauer.
  • Репозиторий c примерами данного курса от Oleksii Trekhleb.