{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "cX41C8dLN_Y0"
   },
   "source": [
    "## Введение в линейную алгебру для машинного обучения"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Vu4-ISBgN_Y-"
   },
   "source": [
    "### Векторы  и операции с ними"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oaPSPf_IN_Y_"
   },
   "source": [
    "**Вектором размера $n$** мы будем называть набор из $n$ вещественных чисел: \n",
    "    \n",
    "$x = (x_1, x_2, ..., x_n) \\in R^n$,\n",
    "\n",
    "где $R$ — множество вещественных чисел. Элемент (число) $x_i$ вектора $x$ будем называеть **$i$-ой компонентой вектора $x$**.\n",
    "\n",
    "Обратите внимание: векторы $(1,2,3)$ и $(3,2,1)$ — разные векторы, то есть порядок чисел в векторе имеет значение. Поэтому про вектор обычно говорят \"упорядоченный набор чисел\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Qt9Ru4IeN_ZA"
   },
   "source": [
    "Векторы размера 1 можно отождествить с обычными числами (**скалярами**)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qpigUIWeN_ZB"
   },
   "source": [
    "В анализе данных и машинном обучении для различных операций, связанных с линейной алгеброй, используют библиотеку `Numpy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "j8QdYeDhN_ZD",
    "outputId": "fb8ded1c-e697-4240-adf2-43d79a2c0a81"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Вектор: [-1  0  1  2  3  4  5]\n",
      "Тип вектора: <class 'numpy.ndarray'>\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "a = np.array([-1,0,1,2,3,4,5])\n",
    "print('Вектор:', a)\n",
    "print('Тип вектора:', type(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "680Afs7iN_ZH"
   },
   "source": [
    "Выше мы создали вектор длины 7 ($n=7$), состоящий из вещественных чисел. То есть $a \\in R^7$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aGpoEDVXN_ZI"
   },
   "source": [
    "Так же, как и со скалярами, векторы можно поэлементно складывать, вычитать, умножать и делить. Пусть есть два вектора:\n",
    "$$\n",
    "a = (a_1, a_2, ..., a_n) \\in R^n \\\\\n",
    "b = (b_1, b_2, ..., b_n) \\in R^n\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HydU_GCSN_ZJ"
   },
   "source": [
    "Тогда **поэлементные операции** с ними определим так:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "RNCtD2DPN_ZK"
   },
   "source": [
    "* (поэлементное) сложение:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "o55LeFxvN_ZL"
   },
   "source": [
    "$$\n",
    "a + b = (a_1 + b_1, a_2 + b_2, ..., a_n + b_n) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Znkh8BHvN_ZM"
   },
   "source": [
    "* (поэлементное) вычитание:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BbWlUNn4N_ZM"
   },
   "source": [
    "$$\n",
    "a - b = (a_1 - b_1, a_2 - b_2, ..., a_n - b_n) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "C3X-TMNhN_ZN"
   },
   "source": [
    "* (поэлементное) умножение:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "p3YHMey6N_ZO"
   },
   "source": [
    "$$\n",
    "a * b = (a_1 * b_1, a_2 * b_2, ..., a_n * b_n) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "a8hAcod_N_ZP"
   },
   "source": [
    "* (поэлементное) деление:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zUmxxpjMN_ZP"
   },
   "source": [
    "$$\n",
    "a~/~b = (a_1 / b_1, a_2 / b_2, ..., a_n / b_n) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fWL98ro4N_ZQ"
   },
   "source": [
    "Поэлементные операции **для векторов разного размера НЕ определены**. Можно было бы просто \"дополнять нулями\" недостающие элементны одного из векторов, но мы договоримся, что так делать не будем, поскольку, например, библиотека питона `Numpy` не позволит сложить два вектора разного размера."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "EouD41ZtN_ZQ"
   },
   "source": [
    "**Примеры**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0FXyOyW5N_ZR"
   },
   "source": [
    "> $(1, 2, 3) + (0, -1, -1.5) = (1, 1, 1.5)$ \n",
    "\n",
    "> $(1, 2, 3) + (0, -1, -1.5, 5, 6) = \\text{не определено}$ \n",
    "\n",
    "> $(1, 2, 3) * (0, -1, -1.5) = (0, -2, -4.5)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WW_T2s3GN_ZS"
   },
   "source": [
    "В `numpy` все эти операции делаются очень просто:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "JCHi_of-N_ZS",
    "outputId": "50ef5b7a-db62-428b-8d17-5e02af4f0380"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5 6]\n",
      "[ 0 10 20 30 40 50 60 70 80 90]\n"
     ]
    }
   ],
   "source": [
    "a = np.array([1,2,3,4,5,6])\n",
    "b = np.arange(0, 100, 10)  # второй способ создать массив из последовательных чисел\n",
    "print(a)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fV-s5VODN_ZV",
    "outputId": "d52f5aba-d203-4c57-fa73-2fe8097408ca"
   },
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "operands could not be broadcast together with shapes (6,) (10,) ",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-4-5b800affa569>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0ma\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mb\u001b[0m  \u001b[0;31m# не можем сложить векторы разного размера\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m: operands could not be broadcast together with shapes (6,) (10,) "
     ]
    }
   ],
   "source": [
    "a + b  # не можем сложить векторы разного размера"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "D1TcXSkJN_ZW",
    "outputId": "ca12a94f-5d35-480e-c77d-8b1c905ba796"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1, 12, 23, 34, 45, 56])"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = b[:6]\n",
    "a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jcd5Z7TaN_ZY",
    "outputId": "cc2295d8-aaa9-49c6-f4fc-bc0de9dbea4c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  1,  -8, -17, -26, -35, -44])"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a - b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hW8BVw3fN_Za",
    "outputId": "40f4c73d-f9e6-40ef-d617-3b7286d1abf3"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  0,  20,  60, 120, 200, 300])"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "-kedpQlRN_Zc",
    "outputId": "ab47229c-de1d-40a5-ae7a-84f870de563b"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/izakharkin/opt/anaconda3/lib/python3.7/site-packages/ipykernel_launcher.py:1: RuntimeWarning: divide by zero encountered in true_divide\n",
      "  \"\"\"Entry point for launching an IPython kernel.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([       inf, 0.2       , 0.15      , 0.13333333, 0.125     ,\n",
       "       0.12      ])"
      ]
     },
     "execution_count": 8,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a / b  # делим на 0, поэтому интерпретатор питона выводит Warning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eTEC9X4aN_Ze"
   },
   "source": [
    "Также определим операцию **умножения вектора на число (скаляр)**:  \n",
    "\n",
    "$$\n",
    "a = (a_1, a_2, ..., a_n)  \\in R^n \\\\\n",
    "k \\in R\n",
    "$$\n",
    "где $R$ — множество вещественных чисел."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "DCGiK8MUN_Ze"
   },
   "source": [
    "$$\n",
    "k * a = a * k = (a_1 * k, a_2 * k, ..., a_n * k) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SWcxa0EgN_Zf"
   },
   "source": [
    "Деление вектора на число так же определено, поскольку $a~/~k = a * (1~/~k)$, то есть это просто умножение на \"1 поделить на это число\". \n",
    "\n",
    "В математике строго не определены операции **сложения и вычитания вектора и числа (скаляра)**, однако мы введем их, поскольку во всех библиотеках для линейной алгебры и машинного обучения эти операции есть и осуществляются так:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qxxkYUsdN_Zf"
   },
   "source": [
    "$$\n",
    "k + a = a + k = (a_1 + k, a_2 + k, ..., a_n + k) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "i9Bdk5GwN_Zf"
   },
   "source": [
    "$$\n",
    "a - k = (a_1 - k, a_2 - k, ..., a_n - k) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XhHgx0wTN_Zg"
   },
   "source": [
    "Обратным к вектору $a$ будем называть такой вектор $b$, что:\n",
    "    \n",
    "$$\n",
    "a + b = 0\n",
    "$$\n",
    "\n",
    "Отсюда следует, что $b = -a$, то есть обратным к любому вектору является он же, оно со знаком \"минус\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "moSdJ3hmN_Zh"
   },
   "source": [
    "**Примеры**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ev3h9SCuN_Zi"
   },
   "source": [
    "> $5 * (1, 2, 3) = (5, 10, 15)$ \n",
    "\n",
    "> $10.2 + (1, 2, 3) = (1, 2, 3) + 10.2 = (11.2, 12.2, 13.2)$\n",
    "\n",
    "> $(1, 2, 3) - 100 = (-99, -98, -97)$\n",
    "\n",
    "> $-(1, 2, 3) = (-1, -2, -3)$ — вектор, обратный к вектору $(1,2,3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "NnrZTv6aN_Zi",
    "outputId": "ad93bffe-b394-4430-f9ea-c6e377e3ba5c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5 6]\n",
      "42\n"
     ]
    }
   ],
   "source": [
    "a = np.array([1,2,3,4,5,6])\n",
    "k = 42\n",
    "print(a)\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "o2B44sjhN_Zk",
    "outputId": "1fd51fec-3cdb-4903-9e5e-afcc2f72984a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([43, 44, 45, 46, 47, 48])"
      ]
     },
     "execution_count": 10,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hZgQ37dtN_Zl",
    "outputId": "c48c4c8a-ea17-40f7-c058-7c0dd50144ec"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-41, -40, -39, -38, -37, -36])"
      ]
     },
     "execution_count": 11,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a - k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "CbSCMjuLN_Zn",
    "outputId": "0d3173c1-d95e-4007-8ddc-c88cf42b0f3f"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 42,  84, 126, 168, 210, 252])"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qHGFP8RWN_Zp",
    "outputId": "09a36326-2c58-4357-862b-74c38a8162f7"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.02380952, 0.04761905, 0.07142857, 0.0952381 , 0.11904762,\n",
       "       0.14285714])"
      ]
     },
     "execution_count": 13,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a / k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5fNaBmN1N_Zr"
   },
   "source": [
    "Помимо поэлементных операций и операций с числами, существуют специально определенная для векторов операция **скалярного произведения (dot product)**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nr30g_u3N_Zr"
   },
   "source": [
    "Пусть есть два вектора:\n",
    "$$\n",
    "a = (a_1, a_2, ..., a_n) \\in R^n \\\\\n",
    "b = (b_1, b_2, ..., b_n) \\in R^n\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QC2lJGhmN_Zs"
   },
   "source": [
    "Тогда скалярное произведение двух векторов определяется как:\n",
    "\n",
    "$$\n",
    "\\text{dot_product}(a, b) = a \\cdot b = \\sum_{i=1}^n a_i * b_i\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JRxnX3gFN_Zt"
   },
   "source": [
    ", то есть скалярное произведение векторов $a$ и $b$  — это число (скаляр), равное сумме поэлементных произведений компонтент этих векторов. Оно называется скалярным как раз потому, что результатом является число (**скаляр**). Чаще вместо $a \\cdot b$ пишут просто $ab$ или $(a, b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kiNhUaKHN_Zt"
   },
   "source": [
    "**Примеры**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "FV0BAD31N_Zu"
   },
   "source": [
    "> $(1,2,3) \\cdot (5,10,15) = 1 * 5 + 2 * 10 + 3 * 15 = 70$\n",
    "\n",
    "> $(0,0,0,0,0,0) \\cdot (1,1,1,1,1,1) = 0 * 1 + 0 * 1 + 0 * 1 + 0 * 1 + 0 * 1 + 0 * 1 = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "S9Q9K7ikN_Zu"
   },
   "source": [
    "На `numpy` скалярное произведение можно посчитать так:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "wHZTkK6KN_Zu",
    "outputId": "2208243e-96bf-4bf2-c2c4-6676fc5ce757"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5 6]\n",
      "[-1 -2 -3 -4 -5 -6]\n"
     ]
    }
   ],
   "source": [
    "a = np.array([1,2,3,4,5,6])\n",
    "b = -a  # второй способ создать массив из последовательных чисел\n",
    "print(a)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "-rhXbfkdN_Zw",
    "outputId": "387f8268-8479-4e5d-84c3-2b1fc6916b59"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-91"
      ]
     },
     "execution_count": 15,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a @ b  # скалярное произведение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "229UKtZcN_Zy",
    "outputId": "53f11bae-10f5-4f3a-ffca-22b3cce365b9"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-91"
      ]
     },
     "execution_count": 16,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.dot(a, b)  # или так"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "oa_u953HN_Zz",
    "outputId": "f5dddf7f-71d7-4075-b24a-ad0bb2cbce8a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Проверка, что dot product считается именно по формуле выше:\n",
    "a @ b == np.sum(a * b)  # определение скалярного произведения"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Xt1uW0NkN_Z0"
   },
   "source": [
    "Существуют еще векторное и смешанное произведение векторов, но ими мы в курсе пользоваться не будем. Про **внутреннее (inner)** и **внешнее (outer)** произведения мы узнаем позже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "PmNRwSNXN_Z0"
   },
   "source": [
    "### Линейная зависимость векторов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "x5VkC1hDN_Z1"
   },
   "source": [
    "Пусть есть набор из $m$ векторов одинакового размера $n$:  \n",
    "\n",
    "$$\n",
    "x_1, x_2, ..., x_m \n",
    "$$\n",
    "\n",
    "Договоримся, что с этого момента первым индексом будем обозначать номер вектора в наборе векторов, а нижним индексом чеерз запятую будем обозначать конкретный элемент вектора. Например, 5-ый элемент вектора под номером 16 из набора пишется как $x_{16,5}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KgW-776CN_Z1"
   },
   "source": [
    "Вектора $x_1, x_2, ..., x_m $ называются **линейно зависимыми**, если существует такой набор коэффициентов (вещественных чисел) $\\alpha_1, \\alpha_2,...,\\alpha_m$, что выполнено:\n",
    "\n",
    "$$\n",
    "\\alpha_1 x_1 + \\alpha_2 x_2 + ... + \\alpha_m x_m = 0\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6VcY9TuvN_Z1"
   },
   "source": [
    "Вообще, в математике левую часть такого выражения (сумму с коэффициентами) называют **линейной комбинацией** векторов. \n",
    "\n",
    "Таким образом, если существует набор коэффициентов для векторов такой, что их линейная комбинация равна 0, то эти векторы являются линейно зависимыми. Однако понятно, что если возьмем все коэффициенты $\\alpha_i = 0$ — то получим 0. Поэтому в определении линейной зависимости мы еще требуем, чтобы выполнялось условие — **все коэффициенты одновременно не равны 0.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "EZZBC6UYN_Z2"
   },
   "source": [
    "Правильное определение тогда выглядит так:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UovOMjyPN_Z2"
   },
   "source": [
    "Вектора $x_1, x_2, ..., x_m $ называются **линейно зависимыми**, если существует такой набор коэффициентов (вещественных чисел) $\\alpha_1, \\alpha_2,...,\\alpha_m$, не равных нулю одновременно (говорят \"ненулевой набор коэффициентов\"), что выполнено:\n",
    "\n",
    "$$\n",
    "\\alpha_1 x_1 + \\alpha_2 x_2 + ... + \\alpha_m x_m = 0\n",
    "$$\n",
    "\n",
    "Важно: под нулем здесь понимается именно **нулевой вектор**, равный $(0,0,...,0)$ ($n$ нулей)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fbBVjnufN_Z2"
   },
   "source": [
    "Если такого набора коэффициентов не существует, то набор векторов называется **линейно независимыми**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ytj0Vx9DN_Z2"
   },
   "source": [
    "**Примеры**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gHb4pJQgN_Z3"
   },
   "source": [
    "> Набор: $x_1 = (1,1,1), x_2 = (2,2,2), x_3 = (3,3,3)$.  \n",
    "Эти три вектора являются линейно зависимыми, поскольку:\n",
    "$(-1) * (1,1,1) + (-1) * (2,2,2) + (3,3,3) = 0$.  \n",
    "Коэффициенты здесь: $\\alpha_1 = -1, \\alpha_2 = -1, \\alpha_3 = 1$\n",
    "\n",
    "\n",
    "> Набор: $x_1 = (1,0), x_2 = (0,1), x_3 = (1,1)$.  \n",
    "Эти три вектора являются линейно зависимыми, поскольку:\n",
    "$(1,0) + (0,1) - (1,1) = 0$.  \n",
    "Коэффициенты здесь: $\\alpha_1 = 1, \\alpha_2 = 1, \\alpha_3 = -1$\n",
    "\n",
    "> Набор: $x_1 = (1,0), x_2 = (0,1)$.  \n",
    "Эти два вектора являются линейно независимыми, поскольку вторая компонента вектора $x_1$ всегда будет равна 0 (при умножении на любой коэффициент), а вторая компонента вектора $x_2$ равна 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1IIKNby6N_Z3"
   },
   "source": [
    "**Смысл понятия линейной зависимости:**\n",
    "Понятия линейной зависимости и независимости очень широко используются в анализе данных. Интуитивный смысл такой — если векторы являются линейно зависимыми, то их можно выразить друг через друга. И правда, если, например: $x_1 + 3x_2 - 8.5x_3 = 0$, то можем выразить любой из $x_1$, $x_2$ или $x_3$ через другие два вектора:\n",
    "$$\n",
    "x_1 = 8.5x_3 - 3x_2  \\\\\n",
    "x_2 = 8.5x_3 - x_1  \\\\\n",
    "x_3 = (x_1 + 3x_2)~/~8.5  \\\\\n",
    "$$\n",
    "В анализе данных (и часто в математике в целом) мы обычно заинтересованы именно в наборах линейно независимых векторов. Это мотивировано тем, что если векторы линейно зависимы, то набор \"избыточен\", то есть мы зачем-то используем больше векторов, чем \"нужно\". Такова интуиция этих понятий."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lRN4zdjeN_Z3"
   },
   "source": [
    "### Векторное пространство"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "B2_ANLgFN_Z4"
   },
   "source": [
    "Выше мы определили то, что такое векторы, операции векторов с векторами и операции вектором со скалярами. На самом деле все это можно сделать более формально, как это принято в математике, ведь теперь мы уже понимаем смысл всех этих формализмов:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8PF3I4vsN_Z4"
   },
   "source": [
    "**Линейное** или **векторное пространство** $V$ над полем $R$ действительных чисел — это упорядоченная четвёрка $(V,R,+,*)$, где  $V$ — непустое множество элементов произвольной природы, которые называются **векторами**; $R$ — множество вещественных чисел, элементы которого называются **скалярами**; определена операция **сложения векторов $+$** и **операция умножения векторов на скаляры $*$**. В нашем случае объекты произвольной природы — это упорядоченные наборы чисел, их мы и называем векторами.\n",
    "\n",
    "Чтобы называться линейным (векторным) пространством, это множество должно также удовлетворять следующим свойствам:  \n",
    "\n",
    "1. $a + b = b + a,~~a,b \\in V$\n",
    "2. $(a + b) + c = a + (b + c)$ — складывать можно в любой последовательности\n",
    "3. Существует нулевой вектор (нейтральный по сложению элемент): $0 + a = a + 0 = a, ~~a \\in V$\n",
    "4. Для каждого вектора $x$ существует обратный к нему по сложению элемент $-x$, такой что: $x + (-x) = 0$\n",
    "5. $\\alpha(\\beta a) = (\\alpha\\beta) a,~~a \\in V, \\alpha,\\beta \\in R$ — перемножать можно в любой последовательности\n",
    "6. Существует единичный вектор (нейтральный по умножению элемент): $1 * a = a * 1 = ~~a \\in V$\n",
    "7. $(\\alpha + \\beta)a = \\alpha a + \\beta a, ~~a \\in V, \\alpha,\\beta \\in R$\n",
    "8. $\\alpha(a + b) = \\alpha a + \\alpha b, ~~a,b \\in V, \\alpha \\in R$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SPIccj7iN_Z4"
   },
   "source": [
    "Во многих курсах и [учебниках по линейной алгебре](https://mipt.ru/education/chair/mathematics/upload/ff4/Umnov-AnGeom-i-LinAl-arph0duocc9.pdf) более подробно рассматриваются подобные пространства. С ними связано много теории и задач, однако в нашем курсе нам это понятие не пригодится в степени большей, чем на уровне определения."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2k3QZlv8N_Z4"
   },
   "source": [
    "### Базис"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZxEQceXGN_Z5"
   },
   "source": [
    "В примерах на линейную зависимость выше мы рассматривали набор: $x_1 = (1,0), x_2 = (0,1)$. Мы доказали, что эти векторы линейно независимы. Однако что нам это дает? На самом деле — многое. Ведь, используя только эти два вектора, **их линейной комбинацией мы можем получить любой вектор размера 2**:\n",
    "\n",
    "$$\n",
    "\\alpha_1 x_1 + \\alpha_2 x_2 = (\\alpha_1, 0) + (0, \\alpha_2) = (\\alpha_1, \\alpha_2)\n",
    "$$\n",
    "где $\\alpha_1, \\alpha_2 \\in R$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wvOZKQ2FN_Z5"
   },
   "source": [
    "Такую систему векторов, линейная комбинация которых может образовывать все вектора данного размера, называют **базисом в векторном пространстве** (в данном случае — в векторном пространстве числовых упорядоченных наборов размера 2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Vr0qsuJ8N_Z5"
   },
   "source": [
    "**Ба́зис** (др.-греч. βασις «основа») — упорядоченный (конечный или бесконечный) набор векторов в векторном пространстве, такой, что любой вектор этого пространства может быть единственным образом представлен в виде линейной комбинации векторов из этого набора (базиса). Векторы базиса называются **базисными векторами**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HsJriZCGN_Z5"
   },
   "source": [
    "### Координаты, норма, угол"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "c0tzIonEN_Z6"
   },
   "source": [
    "В школе на уроках математики часто рассматривались векторы размера 2, которые наглядно рисовать на координатной плоскости (\"по клеточкам\"): первая компонента вектора — координата $x$, вторая компонента — координата $y$.\n",
    "\n",
    "Благодаря этому становится понятно, что такое **угол** между векторами, легко найти их **модуль** (длину) и **координаты**.\n",
    "\n",
    "Все это прекрасно обобщается и на **многомерные векторы и векторные пространства** (многомерные — значит произвольного размера $n$ (целое положительное число)). Рассмотрим векторное пространство вещественных векторов размера $n$. Зафиксируем в этом пространстве **стандартный базис**:   \n",
    "\n",
    "$$\n",
    "e_1 = (1,0,...,0,0,0,...,0) \\\\\n",
    "e_2 = (0,1,...,0,0,0,...,0), \\\\\n",
    "..., \\\\\n",
    "e_i = (0,0,...,0,1,0,...,0), \\\\\n",
    "... \\\\\n",
    "e_n = (0,0,...,0,0,0,...,1) \\\\\n",
    "$$, где в векторе $e_i$ единица стоит только на $i$-ом месте, а остальные компоненты — нули. Тогда понятно, что линейной комбинацией этих векторов мы можем представить любой вещественный вектор размера $n$. **Координатами** этого вектора мы назовем коэффициенты в линейной комбинации этих базисных векторов, образующей этот вектор. \n",
    "\n",
    "**Пример**\n",
    "> Пусть $x = (5,-1,0)$ -- вектор.  \n",
    "Тогда можно его представить с помощью стандартного базиса $e_1 = (1,0,0)$, $e_2 = (0,1,0)$,$e_3 = (0,0,1)$:  \n",
    "$5*(1,0,0) - 1 * (0,1,0) + 0 * (0,0,1) = (5,-1,0)$  \n",
    "Таким образом координаты этого вектора будут (5,-1,0) (то есть получается сам этот вектор).\n",
    "\n",
    "В данном случае пример получился странным, поскольку мы взяли вектор в базисе, уже представленный своими координатами в этом базисе, и просто показали как он раскладывается по этому же базису. Куда более интересно брать вектор в одном базисе, и записывать его координаты в другом базисе. Однако мы этим заниматься не будем, поскольку в курсе, опять же, этого навыка не требуется."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "a3897zMDN_Z6"
   },
   "source": [
    "**Модулем** или **евклидовой нормой** вектора размера $n$ мы будем называть вещественное число, равное:  \n",
    "\n",
    "$$||x|| = \\sqrt{x_1^2+x_2^2+...+x_n^2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9ADI4oS7N_Z6"
   },
   "source": [
    "Нормы можно определять по-разному, но главное, о чем говорит норма вектора — о суммарной величине (амплитуде) его компонент. Если у вектора все компоненты меньше 1 по модулю, то и модуль (норма) всего вектора будет маленькой. Если же есть хотя бы одна большая компонента (например, все нули, но одна компонента равна 100000), это напрямую отразится на норме вектора (она будет большой)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "o4RVJlRqN_Z7"
   },
   "source": [
    "Попрактикуемся в подсчете нормы на `numpy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qE23ASNFN_Z7",
    "outputId": "5421c830-8511-417a-b54e-4e75c7dadf42"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.416198487095663"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([1,2,3,4,5])\n",
    "np.sqrt(np.sum(x ** 2))  # корень из суммы квадратов координат"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "thHVoZeuN_Z8"
   },
   "source": [
    "Выше мы сначала возвели элементы вектора в квадрат `**2 `, далее посчитали их сумму с помощью `np.sum()` и взяли квадратный корень `np.sqrt()` из неё.\n",
    "\n",
    "Также в `numpy` есть готовая функция для подсчета евклидовой нормы вектора:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fDEbq_MvN_Z9",
    "outputId": "41d9c3a2-29a7-4067-cd96-bcec5f8d0d5c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.416198487095663"
      ]
     },
     "execution_count": 19,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.linalg.norm(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "XXHlr2qmN_Z-",
    "outputId": "621355bf-533c-4b91-917b-439364a4ca81"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sqrt(np.sum(x ** 2)) == np.linalg.norm(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mJ16rqVtN_Z_"
   },
   "source": [
    "И, наконец, **косинусом угла** между двумя векторами мы будем называть следующее выражение:\n",
    "\n",
    "$$\n",
    "\\text{cosine_similarity}(a,b) = cos(a,b) = \\frac{a \\cdot b}{||a||*||b||}\n",
    "$$  \n",
    "\n",
    "где $a \\cdot b$ — скалярное произведение векторов $a$ и $b$, $||a||$ и $||b||$ — евклидовы нормы векторов. Эту величину еще называют **косинусной мерой похожести** между векторами (**cosine similarity**)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5RwXMlpYN_aA"
   },
   "source": [
    "Также определяют **косинусное расстояние** как:\n",
    "$$\n",
    "\\text{cosine_distance}(a,b) = 1 - cos(a,b) = 1 - \\frac{a \\cdot b}{||a||*||b||}\n",
    "$$  \n",
    "\n",
    "\n",
    "**Важно**: когда говорят, что два вектора \"близки\", имеют в виду, что между ними маленькое косинусное расстояние, или, что то же самое — большая косинусная мера похожести."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "sbFgRPLyN_aA"
   },
   "source": [
    "Заметим очень **важное свойство косинусной меры** похожести — она **принимает значения только от -1 до 1** (прямо как косинус угла в тригонометрии). Почему это верно? Существует [неравенство Коши-Буняковского](https://ru.wikipedia.org/wiki/Неравенство_Коши_—_Буняковского), которое говорит о следующем:\n",
    "\n",
    "$$\n",
    "|a \\cdot b| \\le ||a||*||b||\n",
    "$$  \n",
    "\n",
    "То есть модуль скалярного произведения меньше или равен произведению норм. Для дроби $\\frac{a \\cdot b}{||a||*||b||}$ это значит, что числитель всегда не больше знаменателя, а значит сама дробь меньше или равна 1 по модулю. Мы помним, что скалярное произведение может быть отрицательным, а значит косинусная мера похожести и правда всегда принимает значения в отрезке $[-1, 1]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hdHyc-2QN_aA"
   },
   "source": [
    "Научимся считать косинусную меру похожести векторов на `numpy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_tiLiDJGN_aA",
    "outputId": "8a26d873-5650-4eda-ebc9-5a3bbd42ff2d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5] [ 0 10 20 30 40]\n"
     ]
    }
   ],
   "source": [
    "a = np.array([1,2,3,4,5])\n",
    "b = np.arange(0,50,10)\n",
    "print(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "9RAEKAvnN_aC",
    "outputId": "97dbe245-f9f7-4575-d9d4-d22cf0c945fd"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9847319278346618"
      ]
     },
     "execution_count": 23,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine_similarity = (a @ b) / (np.linalg.norm(a) * np.linalg.norm(b))\n",
    "cosine_similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wwE03FNCN_aD"
   },
   "source": [
    "Интересно, а чему будет равно мера похожести вектора с самим собой и с обратным к нему:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "5yx7IgAiN_aD",
    "outputId": "48b57674-6add-4b0e-8845-56524527aa64"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine_similarity = (a @ a) / (np.linalg.norm(a) * np.linalg.norm(a))\n",
    "cosine_similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "YxBTbwxkN_aE",
    "outputId": "d9e611ca-452a-4a4c-9e9d-b69f349c87ef"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1.0"
      ]
     },
     "execution_count": 27,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine_similarity = (a @ -a) / (np.linalg.norm(a) * np.linalg.norm(-a))\n",
    "cosine_similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "K8-2Id3mN_aF"
   },
   "source": [
    "Получили 1 и -1 соответственно, что согласуется с формулой косинусной меры похожести и её интуитивному смыслу (\"близость\", \"похожесть\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gtr8w_A8N_aF"
   },
   "source": [
    "### Резюме"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kSvVGmKXN_aG"
   },
   "source": [
    "Мы познакомились с понятиями **вектора**, с **поэлементными операциями** и **скалярным произведением**. Обсудили понятия **линейной зависимости и независимости**, дали определение **векторного простанства** и **базиса** в нем. Поговорили о **координатах** векторов, **косинусной мере похожести** векторов и о **норме (модуле) векторов**.  \n",
    "\n",
    "Далее следует пройти тест по этим темам и двигаться дальше — к матрицам и операциям с ними. Также вас ждет подробный ноутбук с практикой по библиотеке `Numpy`, поскольку это одна из самых важных библиотек в анализе данных и машинном обучении."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "[linalg]vectors.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}