Один из способов думать о науке о данных — извлекать шаблоны, создавая модели, чтобы понять мир вокруг нас, а не просто предсказывать то, чего не было. Что такое модель? Это что-то вроде экспериментального устройства, позволяющего понять что-то, что либо уже произошло, либо построить модель, объясняющую явления, которые мы видим каждый день, или позволяющую нам предсказывать будущее. Например, мы можем построить модель, которая может понимать различные изменения климата, а затем мы можем построить модель, которая может делать прогноз погоды. Итак, по сути, происходит то, что наука перемещается из мокрой лаборатории в компьютер, все больше полагаясь на вычисления, а не на традиционные эксперименты. Эксперименты останутся важными, но теперь они действительно должны быть дополнены вычислениями.
3 типа моделей:
- Модели оптимизации
- Статистические модели
- Имитационные модели
Оптимизация.
Начнем с целевой функции, которую нужно либо максимизировать, либо минимизировать. Нам часто нужно иметь слой поверх целевой функции, набор ограничений, иногда пустых, которым мы должны подчиняться. Например, карты Google используют модель оптимизации для поиска кратчайшего маршрута. Мы увидим здесь асимметрию, то, как мы по-разному справляемся с этими вещами.
Оптимизация везде. Сегодня вы действительно не можете избежать использования алгоритма оптимизации в своей жизни.
Проблема с рюкзаком.
Итак, вы собираетесь сесть за стол, вы знаете, насколько вы цените разные продукты, например, вы любите пончики больше, чем яблоки, но у вас есть бюджет калорий, например, вы не хотите потреблять более 750 калорий . Та часть, где вы выбираете, что поесть, связана с проблемой рюкзака.
Вот что говорит википедия:
По заданному набору элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, которое необходимо включить в коллекцию, чтобы общий вес был меньше или равен заданному пределу, а общее значение не превышало возможно.
Задача о рюкзаке изучается уже более века, первые работы датируются 1897 годом. Название задача о рюкзаке восходит к ранним работам математика Тобиаса Данцига (1884–1956) и относится к банальная проблема упаковать наиболее ценные или полезные предметы, не перегружая багаж.
Давайте посмотрим на его формулировку.
- Каждый элемент представлен парой ‹значение, вес›.
- Предположим, что рюкзак может вместить предметы общим весом не более W.
- Вектор L длины n представляет набор доступных элементов. Каждый элемент вектора является элементом.
- Вектор V длины n используется, чтобы указать, взяты ли предметы. 1 для Истина и 0 для Ложь. Теперь я могу представить то, что я сделал, с помощью одного вектора с 0 и 1.
Мы собираемся попробовать вектор V, который максимизирует сумму V[I] * L[I].value, т.е. мы хотим получить наибольшее значение V, которое мы можем получить с учетом ограничения, которое, если я посмотрю на точечный вес элементов и умножу его на V сумма весов не больше, чем W. Итак, теперь проблема формализована, как нам ее решить?
Очевидным решением является грубая сила, то есть сгенерировать набор мощности (перечислить все возможные наборы элементов), а затем удалить все комбинации, общее количество единиц которых превышает допустимый вес, и из оставшихся комбинаций выбрать любую, значение которой равно самый большой.
Итак, довольно очевидно, что это даст вам правильный ответ. К сожалению, это не очень практично. Если элементов 100, размер мощного набора составляет: 1 267 650 600 228 229 401 496 703 205 376. Это немного разочаровывает. Это даст вам лучший ответ, но также откроет возможность не быть глупым и оптимизировать.
Жадный алгоритм:
пока рюкзак не полон, кладите в рюкзак лучший доступный предмет.
Что значит лучше всего? Является ли лучший предмет наибольшей ценностью? или наименее дорогой? или, может быть, вы используете соотношение сущностей? На самом деле это не решает проблему, в том смысле, что мы попросили себя что-то оптимизировать, но, что еще хуже, мы не знаем оптимального решения и даже не знаем, насколько мы далеки от оптимального решения.
Динамическое программирование.
Это было изобретено Ричардом Беллманом, весьма выдающимся математиком/компьютерщиком. Он решил назвать это динамическим программированием, потому что это описание ничего не значило, потому что он хотел скрыть, что занимается математикой, поскольку там, где он работал, это было запрещено. Итак, вместо задачи о рюкзаке давайте рассмотрим более простую задачу. Числа Фибоначчи.
Ряд Фибоначчи занимает много времени. Почему это так? Давайте посмотрим на Фибоначчи 6.
Чего бы не сделал разумный человек, чтобы просто решить эту проблему? Что ж, достаточно плохо сделать что-то один раз, но делать что-то снова и снова просто расточительно. Что нам тогда с этим делать?
Ответ лежит в основе динамического программирования. Каков ответ? Вы сохраняете ответ и ищете его, когда он вам нужен, то есть имеете память. Это основной прием динамического программирования, и это то, что называется мемоизацией, когда вы создаете заметку и сохраняете ее в заметке.
Это действительно работает. Это потрясающе, поверьте мне. Но когда вы можете использовать его? Это не похоже на то, что мемоизация — это волшебная пилюля, которая решит все проблемы. Проблемы, которые он может решить, это когда есть 2 вещи:
- Оптимальная подструктура: глобально оптимальное решение может быть найдено путем объединения оптимальных решений локальных подзадач.
- Перекрывающиеся подзадачи: поиск оптимального решения предполагает многократное решение одной и той же проблемы.
поэтому его нельзя использовать для улучшения сортировки слиянием или чего-то подобного. А проблема с рюкзаком? Есть ли у него эти 2 свойства?
Мы можем решить эту проблему с помощью динамического программирования, но это не поможет нам сократить объем вычислений, потому что на каждом этапе мы каждый раз решаем другую задачу. У него нет пересекающихся подзадач.
Теперь, если мы возьмем это дерево, мы будем решать одну и ту же задачу более одного раза. Итак, теперь мы в том же месте. Я хочу, чтобы вы заметили, что нас на самом деле не волнует, что мы взяли, нас даже не волнует ценность, все, что нас волнует, это сколько места у нас есть в рюкзаке и какие предметы нам нужны. рассматривать. Потому что то, что я возьму дальше, не имеет ничего общего с тем, сколько ценности у меня уже есть, потому что я пытаюсь максимизировать ценность, с которой я остаюсь, и точно так же мне все равно, потратил ли я ее на пиво или гамбургеры, все, что имеет значение, это что у меня осталось 100. Таким образом, мы видим, что в большой сложной проблеме легко может быть ситуация, когда различные варианты того, что принимать и что не принимать, оставят вас в ситуации, когда у вас будет одинаковое количество оставшихся калорий. И, следовательно, вы решаете проблему, которую уже решили.
Так что теперь мы сократили наши звонки. Как это может быть? Мы знаем, что проблема по своей сути экспоненциальна. Мы перенастроили законы Вселенной? Является ли динамическое программирование чудом в литургическом смысле?
Нет. Сложность вычислений может быть тонким понятием 😄
Стохастическое мышление
Это если говорить о неопределенности. Ньютоновская механика говорит, что у каждого следствия есть причина, мир можно понять причинно. Была выдвинута Копенгагенская доктрина, которая на фундаментальном уровне утверждает, что поведение физического мира невозможно предсказать, то есть допустимо делать утверждения в форме «х, вероятно, произойдет», но не в форме «х». обязательно произойдет». Эйнштейн возражал против этого и сказал: «Бог не играет в кости».
Подбрасываем 2 монеты. Положите их на стол. А теперь задайте вопрос: у нас 2 решки, 1 решка 1 решка или 2 решки? Это решение является вероятностным. Здесь нет никакой недетерминированности. Я знаю ответ, верно? так что в некотором смысле не имеет значения, является ли оно детерминированным, потому что на самом деле оно не является причинно-недетерминированным. Ответ вполне ясен, но вы не знаете ответа, и поэтому независимо от того, предсказуем мир или нет, тот факт, что мы никогда не обладаем полным знанием мира, нам лучше относиться к нему как к непредсказуемому. Это называется прогностическим недетерминизмом. И это действительно подчеркивает спектр науки о данных.
Ссылки:
Пожалуйста, проголосуйте, если вам понравилось! Ценить это!
