Pull to refresh

Математика на пальцах: методы наименьших квадратов

Programming *C++ *Algorithms *Mathematics *
Tutorial

Введение




Я математик-программист. Самый большой скачок в своей карьере я совершил, когда научился говорить:«Я ничего не понимаю!» Сейчас мне не стыдно сказать светилу науки, что мне читает лекцию, что я не понимаю, о чём оно, светило, мне говорит. И это очень сложно. Да, признаться в своём неведении сложно и стыдно. Кому понравится признаваться в том, что он не знает азов чего-то-там. В силу своей профессии я должен присутствовать на большом количестве презентаций и лекций, где, признаюсь, в подавляющем большинстве случаев мне хочется спать, потому что я ничего не понимаю. А не понимаю я потому, что огромная проблема текущей ситуации в науке кроется в математике. Она предполагает, что все слушатели знакомы с абсолютно всеми областями математики (что абсурдно). Признаться в том, что вы не знаете, что такое производная (о том, что это — чуть позже) — стыдно.

Но я научился говорить, что я не знаю, что такое умножение. Да, я не знаю, что такое подалгебра над алгеброй Ли. Да, я не знаю, зачем нужны в жизни квадратные уравнения. К слову, если вы уверены, что вы знаете, то нам есть над чем поговорить! Математика — это серия фокусов. Математики стараются запутать и запугать публику; там, где нет замешательства, нет репутации, нет авторитета. Да, это престижно говорить как можно более абстрактным языком, что есть по себе полная чушь.
Математика для программистов!
Total votes 125: ↑115 and ↓10 +105
Views 211K
Comments 398

От действий над матрицами к пониманию их сути…

Mathematics *
Sandbox
Очень уважаю людей, которые имеют смелость заявить, что они что-то не понимают. Сам такой. То, что не понимаю, — обязательно должен изучить, осмыслить, понять. Статья "Математика на пальцах", и особенно матричная запись формул, заставили меня поделиться своим небольшим, но, кажется, немаловажным опытом работы с матрицами.

Лет эдак 20 назад довелось мне изучать высшую математику в вузе, и начинали мы с матриц (пожалуй, как и все студенты того времени). Почему-то считается, что матрицы — самая лёгкая тема в курсе высшей математики. Возможно — потому, что все действия с матрицами сводятся к знанию способов расчёта определителя и нескольких формул, построенных — опять же, на определителе. Казалось бы, всё просто. Но… Попробуйте ответить на элементарный вопрос — что такое определитель, что означает число, которое вы получаете при его расчёте? (подсказка: вариант типа «определитель — это число, которое находится по определённым правилам» не является правильным ответом, поскольку говорит о методе получения, а не о самой сути определителя). Сдаётесь? — тогда читаем дальше…
Читать дальше →
Total votes 60: ↑49 and ↓11 +38
Views 127K
Comments 72

Математика на пальцах: линейно-квадратичный регулятор

Programming *C++ *Algorithms *Mathematics *Programming microcontrollers *
Tutorial

Пара часов из жизни математика-программиста или читаем википедию


Для начала в качестве эпиграфа цитирую rocknrollnerd:
— Здравствуйте, меня зовут %username%, и втайне раскрываю суммы из сигма-нотации на листочке, чтобы понять, что там происходит.
— Привет, %username%!


Итак, как я и говорил в своей прошлой статье, у меня есть студенты, которые панически боятся математики, но в качестве хобби ковыряются паяльником и сейчас хотят собрать тележку-сигвей. Собрать-то собрали, а вот держать равновесие она не хочет. Они думали использовать ПИД-регулятор, да вот только не сумели подобрать коэффициенты, чтобы оно хорошо работало. Пришли ко мне за советом. А я ни бум-бум вообще в теории управления, никогда и близко не подходил. Но зато когда-то на хабре я видел статью, которая говорила про то, что линейно-квадратичный регулятор помог автору, а пид не помог.

Если ПИД я ещё себе худо-бедно на пальцах представляю (вот моя статья, которую с какого-то перепугу перенесли на гиктаймс), то про другие способы управления я даже и не слышал толком. Итак, моя задача — это представить себе (и объяснить студентам, а заодно и вам), что такое линейно-квадратичный регулятор. Пока что работы с железом не будет, я просто покажу, как я работаю с литературой, ведь именно это и составляет львиную долю моей работы.

Раз уж пошёл эксгибиционизм про мою работу, то вот вам моё рабочее место (кликабельно):

Математика для программистов!
Total votes 47: ↑44 and ↓3 +41
Views 60K
Comments 85

Математика на пальцах: мендосинский двигатель и теорема Ирншоу

Entertaining tasks Mathematics *

Постановка задачи


На днях я увидел на просторах интернета крайне любопытную вещь: мендосинский двигатель. Ротор на подшипниках крайне низкого трения: оригинальный имел стеклянный цилиндр, подвешенный на двух иголках, современные имеют магнитный подвес оси. Двигатель бесколлекторный, на роторе подвешены солнечные батареи, которые выдают напряжение на катушки, намотанные на роторе. Ротор проворачивается в фиксированном магнитном поле статора, солнечная батарея уходит от направленного света, на её место приходит другая. Крайне элегантное решение, которое вполне под силу сделать дома каждому.

Вот на этом видео крайне подробно описан (на русском языке) принцип работы:



Но ещё больше самого двигателя мне показалась любопытной следующая вещь. В описании этого видео Дмитрий Коржевский написал следующую вещь: «Боковую опору заменить магнитом НЕВОЗМОЖНО!!! Не задавайте больше этот вопрос!»

Читать дальше →
Total votes 98: ↑97 and ↓1 +96
Views 109K
Comments 226

Математика на пальцах: ардуино головного мозга или линейно-квадратичный регулятор для управления электродвигателем

C++ *Algorithms *Mathematics *Robotics development *Programming microcontrollers *
Tutorial

Постановка задачи: как со школьными знаниями дойти до выводов университетского уровня


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

Как я уже говорил в предыдущих статьях, мои знакомые студенты хотят построить обратный маятник, но умаялись подбирать коэффициенты ПИД-регулятора, поэтому я неспешно смотрю, что такое линейно-квадратичный регулятор, ну а заодно и вам пересказываю то, что прочитал. Задача для этой статьи — показать, как воплотить в железе одномерный пример из статьи про линейно-квадратичный регулятор. Грубо говоря, я хочу написать написать управление для сервомотора: у меня есть текущее положение оси привода и текущая скорость её вращения, я хочу её остановить в заданном положении. Я попытался было прочитать схожую статью на эту тему, но, признаться, ничего в ней не понял, поэтому сел разбираться самостоятельно, предпочтительно на пальцах и без страшных слов типа дифференциальных уравнений Лагранжа-Эйлера.

Продолжая рабочий эксгибиционизм, знакомлю вас с Bubble Bobble, который живёт у нас с коллегой в кабинете. Он рецензирует статьи для конференции SIGGRAPH.


Читать дальше →
Total votes 21: ↑21 and ↓0 +21
Views 43K
Comments 78

Разжёвываем линейно-квадратичный регулятор для управления перевёрнутым маятником

Entertaining tasks Algorithms *Mathematics *Robotics development *Programming microcontrollers *
Tutorial

Преамбула


Продолжаю подробное описание использования линейно-квадратичного регулятора на примере управления перевёрнутым маятником. К слову сказать, термин «ЛКР» очень неточно отражает суть происходящего, как мне уже подсказали в комментариях, в русской школе теории управления этот подход называется «аналитическим конструированием оптимальных регуляторов», что существенно точнее.

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

Итак, это уже четвёртая статья, для лучшего понимания происходящего неплохо бы прочитать предыдущие три:


Вот фотография системы (кликабельно):


Читать дальше →
Total votes 36: ↑34 and ↓2 +32
Views 28K
Comments 59

Как работает метод главных компонент (PCA) на простом примере

Python *Algorithms *Machine learning *
Sandbox


В этой статье я бы хотел рассказать о том, как именно работает метод анализа главных компонент (PCA – principal component analysis) с точки зрения интуиции, стоящей за ее математическим аппаратом. Максимально просто, но подробно.
Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Views 189K
Comments 22

Математика на пальцах: давайте посчитаем хотя бы один ряд Фурье в уме

Entertaining tasks Mathematics *Robotics development *
Tutorial

Нужно ли вам читать этот текст?


Давайте проверим. Прочтите следующее:

Тригонометрическим рядом Фурье функции  называют функциональный ряд вида



где







Страшно, но всё же хочется понять, что это значит?


Значит, вам под кат. Постараюсь формул не использовать.
Читать дальше →
Total votes 86: ↑76 and ↓10 +66
Views 83K
Comments 99

Измерение сопротивления и индуктивности двигателя постоянного тока

Programming *C++ *Mathematics *Robotics development *
Tutorial

Постановка задачи


Есть двигатель постоянного тока. Задача — разработать, собрать и протестировать устройство, позволяющиее реализовать контур тока применительно к этому двигателю. Желаемое время переходного процесса на застопоренном двигателе (без противо-ЭДС) — не более 10мс. Интерфес связи с внешним управляющим контроллером — SPI.

Двигатель постоянного тока, коллекторный, максимальное напряжение 24В, рабочий ток до 5А.

Что значит — контур тока? Самые распространённые драйверы для управления двигателями это всякие вариации полумостов, которые усиливают напряжение. А мне хочется, чтобы драйвер брал на вход не напряжение, а силу тока. Сила, развиваемая электроприводом, прямо пропорциональна силе протекающего тока. А значит, и прямо пропорциональна ускорению на валу двигателя. Такой контур тока позволит избежать извращений, на которые нужно идти без него, как я это делал тут.

Я разбил этот текст на две статьи:


Вот так выглядит макет управляющего железа:


Читать дальше →
Total votes 29: ↑28 and ↓1 +27
Views 23K
Comments 53

Футбольный мяч и фуллерены

Mathematics *
Одним из красивейших математических результатов можно смело считать теорему Эйлера, которая впервые появилась в журнале Петербургской Академии наук в работах Леонарда Эйлера «Элементы учения о телах» и «Доказательство некоторых замечательных свойств, которым подчинены тела, ограниченные плоскими гранями».
Читать дальше →
Total votes 19: ↑16 and ↓3 +13
Views 21K
Comments 21

Корректирующие коды «на пальцах»

Algorithms *Mathematics *
Tutorial

Корректирующие (или помехоустойчивые) коды — это коды, которые могут обнаружить и, если повезёт, исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок. Конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам.


Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.


Давайте же разберёмся, что это такое.


Для понимания статьи не нужны никакие специальные знания. Достаточно лишь понимать, что такое вектор и матрица, как они перемножаются и как с их помощью записать систему линейных уравнений.


Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.

Читать дальше →
Total votes 56: ↑55 and ↓1 +54
Views 55K
Comments 21

Сверточная сеть на python. Часть 1. Определение основных параметров модели

Open Data Science corporate blog Algorithms *Image processing *Mathematics *Machine learning *

Несмотря на то, что можно найти не одну статью, объясняющую принцип метода обратного распространения ошибки в сверточных сетях (раз, два, три и даже дающих “интуитивное” понимание — четыре), мне, тем не менее, никак не удавалось полностью понять эту тему. Кажется, что авторы недостаточно внимания уделяют обычным примерам либо же опускают какие-то хорошо понятные им, но не очевидные другим особенности, и весь материал по этой причине становится неподъемным. Мне хотелось разложить все по полочкам для самого себя и в итоге конспекты вылились в статью. Я постарался исключить все недостатки существующих объяснений и надеюсь, что эта статья ни у кого не вызовет вопросов или недопониманий. И, может, следующий новичок, который, также как и я, захочет во всем разобраться, потратит уже меньше времени.
Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Views 62K
Comments 10

Сверточная сеть на python. Часть 2. Вывод формул для обучения модели

Open Data Science corporate blog Algorithms *Image processing *Mathematics *Machine learning *

В прошлой статье мы рассмотрели концептуально все слои и функции, из которых будет состоять будущая модель. Сегодня мы выведем формулы, которые будут отвечать за обучение этой модели. Слои будем разбирать в обратном порядке — начиная с функции потерь и заканчивая сверточным слоем. Если возникнут трудности с пониманием формул, рекомендую ознакомиться с подробным объяснением (на картинках) метода обратного распространения ошибки, и также вспомнить о правиле дифференцирования сложной функции.
Читать дальше →
Total votes 67: ↑66 and ↓1 +65
Views 28K
Comments 0

Сверточная сеть на python. Часть 3. Применение модели

Open Data Science corporate blog Algorithms *Image processing *Mathematics *Machine learning *

Это заключительная часть статей о сверточных сетях. Перед прочтением рекомендую ознакомиться с первой и второй частями, в которых рассматриваются слои сети и принципы их работы, а также формулы, которые отвечают за обучение всей модели. Сегодня мы рассмотрим особенности и трудности, с которыми можно столкнуться при тестировании вручную написанной на python сверточной сети, применим написанную сеть к датасету MNIST и сравним полученные результаты с библиотекой pytorch.
Читать дальше →
Total votes 62: ↑61 and ↓1 +60
Views 30K
Comments 8

Обзор реализаций округления в Go

Badoo corporate blog Perfect code *Go *
Translation


Привет, Хабр! Меня зовут Олег, я PHP-и-не-только-разработчик в Badoo. Меня часто удивляет, насколько по-разному в языках программирования подходят к составлению стандартной библиотеки. Go — не исключение: отсутствие функции math.Round() меня удивило. Однако, покопавшись в этих ваших интернетах, я выяснил, в чём причина. Этими знаниями я и хотел бы поделиться в своём вольном переводе.

Читать дальше →
Total votes 62: ↑61 and ↓1 +60
Views 26K
Comments 29

Сумма сумм арифметических прогрессий

C++ *Mathematics *
Sandbox
Пускай у нас есть некий ряд ячеек, часть которых можно пометить как «занятые»:

01

Нам нужно узнать, сколько всего существует вариантов расположения занятых ячеек.

К этой схеме сводится множество задач. Например, разбиение периода из N + 1 календарных дней на l + 1 следующих друг за другом меньших периодов. Допустим, мы хотим провести оптимизационный расчет методом «грубой силы», рассчитав целевую функцию для каждого возможного варианта разбиения периода, чтобы выбрать наилучший вариант. Чтобы заранее оценить время расчета, нужно определить количество вариантов. Это поможет принять решение, стоит ли вообще начинать расчет. Согласитесь — полезно будет заранее предупредить пользователя вашей программы, что с теми параметрами, которые он задал, расчет займет 10000 лет.

Читать дальше →
Total votes 28: ↑23 and ↓5 +18
Views 12K
Comments 12

Математическое моделирование хабро-будущего

System Analysis and Design *Mathematics *
Recovery mode
image

Неделю назад на Хабре появился очередной пост, что Хабр уже не тот. Безотносительно к затрагиваемым в нем темам заинтересовал вопрос о системе рейтинга и кармы — некоторые видят деградацию или сползание ресурса «не туда» именно в ней.

Ни в коей мере не критикуя нынешнюю систему и не влазя во внутренние дела администрации захотелось исследовать этот вопрос с теоретической стороны — нахождение оптимальной системы градации пользователей с помощью элементарных математических методов.
Читать дальше →
Total votes 16: ↑3 and ↓13 -10
Views 2.3K
Comments 1

В трёх статьях о наименьших квадратах: ликбез по теории вероятностей

Programming *C++ *Algorithms *Mathematics *
Tutorial
Полтора года назад я опубликовал статью «Математика на пальцах: методы наименьших квадратов», которая получила весьма приличный отклик, который, в том числе, заключался в том, что я предложил нарисовать сову. Ну, раз сова, значит, нужно объяснять ещё раз. Через неделю ровно на эту тему я начну читать несколько лекций студентам-геологам; пользуюсь случаем, излагаю тут (адаптированные) основные тезисы в качестве черновика. Моей основной целью не является дать готовый рецепт из книги о вкусной и здоровой пищи, но рассказать, почему он таков и что ещё находится в соответствующем разделе, ведь связи между разными разделами математики — это самое интересное!

На данный момент я предполагаю разбить текст следующим образом:


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

Насколько обоснован теорвер или верите ли вы в теорию эволюции?


Однажды мне задали вопрос, верю ли я в теорию эволюции. Прямо сейчас сделайте паузу, подумайте, как вы на него ответите.


Читать дальше →
Total votes 46: ↑45 and ↓1 +44
Views 21K
Comments 21

Методы наименьших квадратов без слёз и боли

Programming *C++ *Game development *Algorithms *Mathematics *
Tutorial


Итак, очередная статья из цикла «математика на пальцах». Сегодня мы продолжим разговор о методах наименьших квадратов, но на сей раз с точки зрения программиста. Это очередная статья в серии, но она стоит особняком, так как вообще не требует никаких знаний математики. Статья задумывалась как введение в теорию, поэтому из базовых навыков она требует умения включить компьютер и написать пять строк кода. Разумеется, на этой статье я не остановлюсь, и в ближайшее же время опубликую продолжение. Если сумею найти достаточно времени, то напишу книгу из этого материала. Целевая публика — программисты, так что хабр подходящее место для обкатки. Я в целом не люблю писать формулы, и я очень люблю учиться на примерах, мне кажется, что это очень важно — не просто смотреть на закорючки на школьной доске, но всё пробовать на зуб.

Итак, начнём. Давайте представим, что у меня есть триангулированная поверхность со сканом моего лица (на картинке слева). Что мне нужно сделать, чтобы усилить характерные черты, превратив эту поверхность в гротескную маску?



В данном конкретном случае я решаю эллиптическое дифференциальное уравнение, носящее имя Симеона Деми Пуассона. Товарищи программисты, давайте сыграем в игру: прикиньте, сколько строк в C++ коде, его решающем? Сторонние библиотеки вызывать нельзя, у нас в распоряжении только голый компилятор. Ответ под катом.
Читать дальше →
Total votes 54: ↑54 and ↓0 +54
Views 44K
Comments 58

256 строчек голого C++: пишем трассировщик лучей с нуля за несколько часов

Programming *C++ *Working with 3D-graphics *Game development *Mathematics *
Tutorial
Публикую очередную главу из моего курса лекций по компьютерной графике (вот тут можно читать оригинал на русском, хотя английская версия новее). На сей раз тема разговора — отрисовка сцен при помощи трассировки лучей. Как обычно, я стараюсь избегать сторонних библиотек, так как это заставляет студентов заглянуть под капот.

Подобных проектов в интернете уже море, но практически все они показывают законченные программы, в которых разобраться крайне непросто. Вот, например, очень известная программа рендеринга, влезающая на визитку. Очень впечатляющий результат, однако разобраться в этом коде очень непросто. Моей целью является не показать как я могу, а детально рассказать, как подобное воспроизвести. Более того, мне кажется, что конкретно эта лекция полезна даже не столь как учебный материал по комьпютерной графике, но скорее как пособие по программированию. Я последовательно покажу, как прийти к конечному результату, начиная с самого нуля: как разложить сложную задачу на элементарно решаемые этапы.

Внимание: просто рассматривать мой код, равно как и просто читать эту статью с чашкой чая в руке, смысла не имеет. Эта статья рассчитана на то, что вы возьмётесь за клавиатуру и напишете ваш собственный движок. Он наверняка будет лучше моего. Ну или просто смените язык программирования!

Итак, сегодня я покажу, как отрисовывать подобные картинки:


Читать дальше →
Total votes 241: ↑241 and ↓0 +241
Views 124K
Comments 124