_readme_lab2.md

Linear regression

Table of contents

Used software:

• Python-IDE: PyCharm Community 2017.2;
• Project Interpreter: python 3.5.3 (amd64);
• Used python packeges:
  • matplotlib v2.1.0;
  • tabulate v0.8.1;
  • numpy v1.13.3.

Problem

1. Implement linear regression;
2. Configure the coefficient vector in two ways - gradient descent and evolution algorithm;
3. To assess the quality of use MSE;
4. Select hyperparameters and methods arbitrarily;
5. Perform data visualization;
6. Teach the code to take additional points from the console to check the already trained model.

Start dataset

Dataset.txt - dependence of objects: area, number of rooms, price.

Program structure

• DatasetProcessing:
  • getDataset;
  • getSeparetedData;
  • getAvgData;
  • getStandardDeviationData;
  • getNormalizeDataset;
  • getNormalizeInputDataset;
  • getCombinedInputData.
• GradientDescent:
  • calculateGradientDescent;
  • calculateInputPrice.
• Visualization:
  • build3DStartDataset (start dots);
  • build3DRegressionLinearPlusInput (gradient);
  • build3DRegressionLinear (all);
  • build3DRegressionLinearGradientVsEvolution (together);
  • build3DCostFunction (gradient);
  • build2DInfo (together);
  • build2DIndividualMSEEvolution (evolution).
• Evolution:
  • startEvolution;
  • calculateNewPrice (off):
  • testEvo;
  • weightStartIntialization;
  • calculateMSE;
  • mutationProbability;
  • selectionIndividuals;
  • testEvo;
  • selection (off);
  • crossing (off).
• presentation files:
  • main.

Output (one start)

• example-outputGradient
• example-outputEvolution

Other results:

• google table
• outputGradient500Dynamic
• outputEvolution60000-50percentMutation
• outputEvolution60000-100percentMutation

Graphics (example-output):

FAQ

Gradient descent:

Evolution algorithm:

1. Generate 7 coefficient vector (np.random.randn(3, 1));

2.1 Calculate MSE for each coefficient vector:

2.2 Find the top three MSE and coefficient vectors.

3. Produce selection with mutation:

• top one on step 2.2 record to new_w0 without changes/mutations;
• other six descendats have two mandatory parents (mutation replaces first parent with probability given in main.py);
• for one descendats possibly only one mutation (probability 33% for each chromosome).

4. evolution goes through a certain number of iterations given in main.py.

1. Question: Что такое линейная регрессия?

   Answer: Линейная регрессия — метод восстановления зависимости между двумя переменными.

2. Question: Что такое среднеквадратичное отклонение/ошибка?

   Answer:

   

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

   Для линейной модели (вместо , подставляя получается не функционал, а функция:

   

   Ошибка зависит не от некоторой функции , а от вектора весов , который возможно подвергнуть оптимизации.

3. Question: Как записать в матричном виде среднеквадратичную ошибку?

   Answer:

   Среднеквадратичная ошибка в матричном виде:

   , где:

   - матрица "объекты-признаки".

   - все признаки i-ого объекта.

   - значения j-ого признака на всех объектах.

   - вектор ответов.

4. Question: Зачем использовать градиентный спуск, если существует способ получения аналитического решения задачи минимизации среднеквадратичной ошибки без оптимизации?

   Аналитическое решение:

   Answer:
   Основная проблема состоит в том, что необходимо обращать матрицу (число признаков на признаков) - число операций . На тысяче признаков - критическая сложность вычислений.

   Кроме того, при обращении могут возникнуть численные проблемы при определенном устройстве матриц.

5. Question: Что такое градиентый спуск?

   Answer: Градиентый спуск - это способ поиска решения оптимизационным подходом.

   Подход основан на том, что среднеквадратичная ошибка обладает свойствами выпуклой и гладкой функции.

   Из выпуклости функции следует, что у функции существует один минимум, а из гладкости, что в каждой точки функции возможно вычислить градиент.

   Градиент - это вектор, указывающий направление наибольшего возрастания некоторой величины.

   Другими словами, градиент показывает сторону наискорейшего возрастания функции, а антиградиент показывает сторону наискорейшего убавания функции.

   Алгоритм:

   1. Инициализация:

   Каким-то образом находится начальное приближение для вектора весов: либо вектор заполняется нулями : , либо случайными небольшими числами.

   2. Цикл t:

      , где

      - вектор градиентов этой точки;

      - шаг, регулирует, на сколько далеко шагаем в сторону антиградиента (оптимальный шаг не слишком большой).

      Градиентные шаги повторяются до наступления сходимости.

      Сходимость можно определять:

      • как ситуацию, когда векторы весов от шага к шагу меняются не очень сильно: ;

      • производить сравнение функционала ошибки между текущей иттерацией и предыдущей.

6. Question: Настройка коэффециентов линейной регрессии генетикой

   Answer:

7. Question: Среднеквадратичная линейная регрессия

   Answer:

other: параметры сглаживания (2) регуляризация коэффициент сглаживания матрица весов (нули) градиент ошибки - производная по всем направлениям эвристики для подбора матрицы весов (веса в отрезке) критерий останова (епсилон) \количество итераций (2000), ошибка (0,063) задача линейной регрессии эмпирический риск псевдообразная матрица (точное решение)

включать случайные в алгоритм для генетического разнообразия (чтобы не застрять в локальном минимуме) цель - оптимизация функции ошибки (эмперического риска)

Links

1. линейная регрессия; https://ru.coursera.org/learn/supervised-learning/lecture/hCGR6/obuchieniie-linieinoi-rieghriessii https://basegroup.ru/deductor/function/algorithm/linear-regression http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf
2. London Machine Learning Stydy Group. Lecture 1;
3. Trace in linear algebra;
4. Evolution algohithms [RUS].