Введение

При функционировании больших сложно устроенных систем в них, как правило, протекают многообразные процессы, сущность которых состоит в различного рода преобразованиях физико-химической субстанции из сырья в конечный продукт, поставляемый на рынок. Наряду с материальной субстанцией в производственных процессах широко используется информация управленческая и технологическая. Когда-то не в столь давние времена достаточно сложным механизмом, системой считался часовой механизм, реализуемый зацеплением шестеренок. Механизм преобразовывал временную субстанцию в информацию. Выходным продуктом такого механизма была информация - сведения о текущем временном моменте, к точности которой уже в те времена предъявлялись жесткие требования. Все процессы сложных производственных систем также, подобно механизму часов, постоянно должны быть в "зацеплении", тесно взаимодействовать, протекать синхронно и согласованно. Главным требованием к такой системе с шестеренками была точность отсчетов временных промежутков. И сегодня точность нужна везде от водных, наземных, воздушных транспортных систем до спутниковых космических, атомных энергетических станций. Исследуя операции, следует помнить об истории их появления и проявления в различных отраслях хозяйства и производства.

Начнем с рассмотрения типичной простой и понятной задачи. Пусть в пределах населенного пункта в точках (х₀, х₁) имеется n складов с товарами. На каждом складе припаркован под погрузку автоприцеп, который загружается товарами. В других точках (х₀, х₁) района (окрестности населенного пункта) размещаются заказчики (потребители товаров), которым необходимо эти товары доставить. В n точках (х₀, х₁) размещены n тягачей, которые должны доставить заказчикам загруженные товарами по их заявкам автоприцепы. Такая доставка связана с расходом топлива, с затратами времени и многими другими явлениями и событиями.

Владелец транспортных средств располагает матрицей:

стоимости (затрат) топлива в операции перевозки.

Очевидно, что в операции желательно ограничить расход топлива при условии выполнения доставки товаров всем заказчикам. Математическая модель затрат представляется простой линейной формой:

Это соотношение называют целевой функцией (ЦФ). Неизвестными здесь являются переменные (x_ij) , т.е. куда тягач с номером (i) должен доставить груженый прицеп с номером (j). Ясно, что суммарные затраты будут определяться планом Х[i, j] перевозок или выбором переменных (x_ij) в совокупности. Постоянно будем иметь ввиду очевидное ограничивающее условие: один тягач везет один прицеп, каждый прицеп обслуживается одним тягачом. Из этого условия следует, что каждый элемент (x_ij), выбираемый для подстановки в ЦФ, не может быть дробным значением, а принимает одно из значений 0 или 1, т.е. (x_ij 0, i = 1(1)n, j = 1(1)n).Приведенное выше условие интерпретируется в модели как ограничения, накладываемые напеременные (x_ij).

(i = 1) х₁₁ +х₁₂ ++ х_1j + + x_1n = 1, j = 1(1)n;

(i = 2) х₂₁ +х₂₂ ++ х_2j + + x_2n = 1, j = 1(1)n;

(i = 3) х₃₁ +х₃₂ ++ х_3j + + x_3n = 1, j = 1(1)n;

.. .

(i = i) х_i1 + х_i2 + + х_ij + + x _in = 1, j = 1(1)n;

. .. .. . . .. .

(i = n) х_n1 +х_n2 ++ х_nj + + x _nn = 1; j = 1(1)n.

Каждая (i-я) строка обозначает возможность прибытия на (j-й) склад любого (j-го) из (n) тягачей и представляется суммой, в которой будет выбран один единственный элемент (x_ij = 1). Относительно столбцов j = 1(1)n системы уравнений также составляются суммы, и каждая из таких сумм также равна единице. В столбцовых суммах также выбирается единственный элемент(x_ij = 1) Таким образом, будет выбрана таблица (0,1-матрица), заполненная единицами и нулями, но так, что в каждой строке и в каждом столбце оказывается единственная единица. Такие матрицы в математической статистике называются дважды стохастическими. Каждая матрица реализует план Х перевозок и ему соответствует определенное (после подстановки переменных плана в выражение целевой функции) значение ЦФ. Сколько же планов-решений Х можно построить? Это легко посчитать. Первый тягач можно направить в любой из n складов, но второму тягачу будут доступны только n1 складов, третьему n2 складов. Этим трем тягачам соответствует n(n1)(n2) количество планов равное произведению трех сомножителей. Далее число возможностей выбора склада будет сокращаться (для 4-го тягача только n3 выборов), а для последнего nго тягача останется единственная возможность, так как все остальные склады уже распределены между n1 тягачами, всего планов будет |Х[i, j]|= n! Например, если n = 20, то

|Х[i, j]| = 20! = 2 432 902 008 176 640000.

Это 20-ти значное число показывает, что простой перебор хоть и решает все задачи дискретного программирования, но жизни нескольких поколений не хватит, чтобы такой перебор выполнить. Хотя тягачей и складов всего по 20 штук, но самые совершенные компьютеры "повиснут" на подобных вычислениях. Подобная картина в настоящее время имеет место в криптографии. Путем подстановки пробного ключа в дешифратор на выходе можно в случае успеха получить исходный открытый текст. Но ожидать этого, право не стоит. Среди моих публикаций есть одна, где ключ шифра раскрывается за три шага. Но это скорее промах автора примера, который я использовал из пособия для подготовки криптографов, чем везение или мое уменье проводить атаку на шифр. По аналогии с диагональной матрицей (единицы расставлены на главной диагонали) все дважды стохастические матрицы называют диагональными.

В терминах задачи конкретная диагональная матрица Х называется планом-решением. Множество возможных планов классифицируется: планы игнорирующие ограничения называются возможными, планы, учитывающие ограничения (не нарушающие ограничений), называются допустимыми, а подмножество допустимых планов, доставляющее целевой функции экстремум называются оптимальными планами.

Основные понятия и термины ИО

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

Цель это описание желаемого состояния или запланированного результата деятельности, на создание (получение) которого направлены ресурсы, усилия. Чаще всего цель или цели (дерево целей) оформляются в форме требуемых значений различных показателей (в ТТЗ на НИР, ОКР и др.)

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

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

Допустимые решения - те решения, которые удовлетворяют наложенным в задаче ограничениям.

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

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

Эффективность операции степень ее приспособленности к выполнению задачи, часто измеряется вероятностью выполнения задачи, количественно выражается значением показателя целевой функции.

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

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

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

Критерий эффективности (КЭ) правило, обеспечивающее фиксирование итогового успешного результата исследования. Рассматриваются три типа КЭ: критерий пригодности системы (система удовлетворяет требованиям, предъявляемым к ней); критерий сравнения систем (из двух или более выбирается та, ПЭ которой предпочтительнее); критерий оптимальности (из всех возможных значений ПЭ выбирается экстремальное при условии допустимости решения). Сам ПЭ не является критерием, так как критерий - это правило, обеспечивающее окончательное принятие решения о пригодности, превосходстве или оптимальности процесса (системы). КЭ не вычисляется, а проверяется.

Характеристика научной дисциплины ИО

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

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

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

Предметные процессы ИО и задачи

В зависимости от типов системных процессов методы и средства их реализации можно разнести по нескольким классам. Приводимые ниже примеры процессов и задач дают представление о предметной области теории ИО, но конечно, не исчерпывают их множества и разнообразия.

Процессы обслуживания

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

Для решения описанной задачи с ожиданиями применима теория очередей. Для задачи определения порядка обслуживания клиентов применима теория расписаний. Наконец, к задачам определения распределения и группировки каналов и других элементов процессов обслуживания в систему обслуживания применима теория балансирования линий.

Процессы распределения

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

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

Процессы управления запасами

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

Процессы замены

Существуют два основных класса, связанных с видами износа оборудования: во-первых, оно устаревает и становится несовременным (менее эффективным) в результате длительного срока службы, или появления нового оборудования (например, станки), во-вторых, не устаревает, но полностью выходит из строя, гибнет (например, электролампы). Замена шифрключей, алгоритма шифрования требует определения временного интервала несменяемости шифрключа.

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

Состязательные процессы

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

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

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

Этапы операционного исследования

Как можно представить процесс, порядок операционного исследования? Принято в такое исследование включать следующие пункты.

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

2. Построение математической модели изучаемой системы

3. Нахождение решения с помощью модели.

4. Проверка модели и получение с ее помощью решения.

5. Построение процедуры подстройки решения.

6. Осуществление решения.

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

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

где Е показатель эффективности системы; х,у неуправляемые переменные, u_i управляемые переменные, F(x,y, u_i) - целевая функция модели. Ограничения, накладываемые на переменные модели, выражаются системами равенств или неравенств дополнительно к основному соотношению показателю эффективности модели, Аrgextr F(x,y, u_i) критерий эффективности примененный к целевой функции. Следует заметить, что в публикациях авторы критерием эффективности называют показатель эффективности, а критерий вообще опускается из рассмотрения. КЭ, трактуемый как правило (руководство), не измеряется числом. К этим вопросам следует отнести и вопрос о существовании разных шкал для проведения измерений с учетом отношения, отвечающего той или иной шкале.

Вычисления в рамках модели могут выполняться аналитическими или численными методами. Первые выполняются подстановкой значений переменных в формулы, полученные на основе выводов в рамках модели или на основе теорем теории. Численный метод состоит в подборе различных значений для управляемых переменных модели, сопоставлении полученных результатов и выборе того набора значений, который дает наиболее выгодное решение. Численный путь может охватывать широкий диапазон от простого метода проб и ошибок до сложных итераций, которыми пользуются, чтобы подойти к оптимальному решению. При имитационном моделировании для расчетов применяется метод Монте-Карло.

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

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

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

Методы реализации процессов ИО и их логическая структура

Рене Декарт, описывая развитый им метод научного исследования, формулирует четыре основных его правила [3].

1. Разбиение сложной проблемы на более простые последовательно до тех пор, пока не будут найдены далее неразложимые компоненты.

2. Нерешенные проблемы следует сводить к решенным. Этим путем находятся решения простых проблем.

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

4. После получения решения исходной проблемы необходимо рассмотреть все промежуточные, чтобы удостовериться, не пропущены ли какие-нибудь звенья. В случае, когда полнота решения установлена, то исследование завершается; при обнаружении пробела в решении необходимо дополнительное исследование в соответствии с перечисленными правилами. Метод рекомендуется применять всегда при разработке операций

Следует сказать несколько слов о логике исследований и методологических понятиях [2}. В методологии науки разработаны общие понятия для описания конкретных методов и проводимых в их рамках процессов научного исследования. Эти описания играют важную роль при выявлении связей между различными методами в составе сложных исследований. Поэтому необходимо использовать эти понятия для методологического описания логики проводимых исследований.

Так проверка и корректировка гипотез производятся с помощью хорошо известных пяти методов индукции, создание и развитие которых связано с именами Ф. Бэкона и Дж. Милля [4, 5].

Причинная связь явлений устанавливается методами единственного сходства (на основе фактов, полученных в наблюдении), единственного различия ( на основе фактов, полученных в эксперименте), объединенным методом (на основе совместно используемых фактов обоих видов). Метод остатков применяется при выявлении неизвестной причины изучаемого явления, а с помощью метода сопутствующих изменений анализируется динамика причинных зависимостей [6, 7 , 9].

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

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

При проведении исследований обычно стремятся скорее включиться в работу, но не надо торопиться следует руководствоваться некоторыми стандартными процедурами постановки задачи и выделять для этого определенное время. Здесь рассмотрим идеализированный процесс постановки задачи, который является наилучшим из существующих, при условии, что нет никаких ограничений. На самом деле на практике редко встречаются такие идеализированные условия.

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

Практики стремятся удешевить схему (в рамках проведения тендера, антимонопольное ведомство не спит), что удается сделать относительно близких тактических целей, но теряется ощущение стратегического восприятия, что в итоге обходится дороже. Идеальный подход, наоборот, во главу угла ставит стратегические вопросы, минимизируя затраты времени и средств, но в тактических вопросах сопряжен с большими расходами. Правильное экономическое решение удачный компромисс между затратами, связанными с достижением тактических и стратегических целей. Важны точное знание идеального решения необходимость и понимание того к чему следует стремиться. Недооценивание возможностей идеального решения может дорого обойтись впоследствии.

Элементы задачи ИО

Рассмотрим в деталях элементы задачи. Очевидно, что перед руководителем или группой лиц должна стоять задача. Эти люди не удовлетворены положением дел в какой-то предметной области и стремятся найти решение, чтобы изменить ситуацию в лучшую сторону. Назовем такую группу или отдельного руководителя лицом, принимающим решение (ЛПР). Таким образом, первым элементом задачи является лицо, принимающее решение (часто это заказчик).

Во-вторых, для существования задачи необходимо, чтобы человек, принимающий решение, желал изменить положение, т.е. должны быть понятными некоторые цели, которых надо достичь. Цели, по существу это требования к выходному эффекту системы. Цели второй элемент задачи.

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

В-четвертых, необходима (должна существовать) возможность выбора между различными (по крайней мере двумя) способами действия или политиками. При отсутствии выбора задача не возникает. Задача всегда включает вопрос: что делать? Но сам этот вопрос становится задачей только в том случае, если существуют различные пути достижения цели. Различные способы действия (стратегии) являются четвертым элементом задачи.

Чтобы сформулировать исследовательскую задачу, необходимо выполнить следующие операции.

1. Уточнить перечень целей, определенных на первом этапе постановки задачи.

2. Уточнить перечень различных стратегий достижения целей.

3. Определить меру (показатель и критерий) эффективности исследуемой системы.

Взаимодействие исполнения и управления при ИО

Планирующая система связывает объект управления с управляющими органами. В процессе деятельности объекта (рис. 3) происходит преобразование одного состояния объекта в другое (10), что зависит от изменения внешних обстоятельств (9) и предписаний (8), вырабатываемых органами управления на основании плановых представлений объекта (5) и оценок текущего состояния объекта управления (7). Оценки вырабатываются на основании показателей и критериев эффективности (5) и информации (6) от объекта управления. Вся эта цепочка определяет один такт в преобразовании объекта из одного состояния в другое. Для каждого такта необходима своя часть плана. Поэтому после выполнения одного такта в самом плане управление передается следующей его части, что обозначается стрелкой (2) на рис. 3.

Настройка плана на объект осуществляется с помощью информации (стрелки 1 и 4) об объекте управления и плановых органах. Все текстовые предложения, входящие в планы, подразделяются на два вида дескриптивные (описывающие) и прескриптивные (предписывающие). С помощью первых представляются состояния, отражаемых в плане объектов, а вторые - служат для выражения предписаний по использованию того или иного способа перехода из одного состояния в другое. Посредством выделения предложений рассматриваемых видов определяются семантические свойства планов.

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

Итак, логическая структура планов, их синтаксические и семантические характеристики непосредственно связаны с обобщенным анализом поведения соответствующих объектов. Оно представляется как чередование двух операций тактов преобразований состояний объектов управления и настройки планов на их объекте. На практике это позволяет проводить логический анализ процессов реализации планов как процессов применения знаний.

На рубеже четвертого и третьего тысячелетия до нашей эры на Земле возникли две первые цивилизации. В долине Нила после объединения верхнего и нижнего Египта образовалось Египетское царство, а в междуречье Тигра и Евфрата появились города-государства, объединенные общей культурой, которые мы сегодня называем Шумером. Одновременно с появлением этих цивилизаций возникли две системы развитого письма египетские иероглифы и шумерское письмо, которое позже превратилось в клинопись.

Если древний Египет со своими памятниками всегда был на виду, то о существовании шумеров наука узнала только в середине XIX века. Проделав огромный труд и расшифровав аккадскую клинопись, историки внезапно столкнулись с неожиданной проблемой. Часть клинописных текстов никак не получалось прочитать. Знаки были те же, но смысл не складывался. Сначала грешили на тайнопись жрецов, но потом поняли, что на самом деле столкнулись с другим более древним языком, письменность которого совпадала с аккадской. Так начался новый виток расшифровки клинописи, который в итоге привел к открытию великой шумерской цивилизации.

В чем тайна?

Сейчас мы знаем, что шумерская культура ни в чем не уступала египетской. Шумеры создали первые своды законов, ввели шестидесятиричную систему счисления, изобрели колесо, выделили зодиакальные созвездия. И это только малая часть их достижений.

Шумерская цивилизация просуществовала около тысячи лет. В конце третьего, тысячелетия до н.э. кочевые семитские племена амореев вторглись в Шумер и как волны потопа поглотили великую державу.

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

В этот день я спущусь в подземный мир. Когда я попаду в подземный мир, оплакивай меня на развалинах. Бей за меня в барабан в святилище. Обходи за меня дома богов. Разорви себе глаза за меня, разорви себе нос за меня. Наедине разорви себе ягодицы для меня. Как нищая, одетая в одну одежду и совсем одна ступит твоя нога в Екур, дом Энлиля. Фрагмент мифа Спуск Инанны в подземный мир.

На фоне общего безумия дошедший до нас шумерских мифов отдельно стоит список шумерских царей. На КДПВ как раз призма с этим списком. Она называется призмой Вельда-Бланделла и имеет каталожный номер wb444.

Список длинный. Начинается он с перечня из восьми царей.

1-39. После того, как царство сошло с небес, царство было в Эриду. В Эриду Алулим стал царем, он правил 28800 лет. Аллалгар правил 36000 лет. 2 короля; они правили 64800 лет. Затем Эриду пал и царство перешло в Бад-Тибир. В Баде-Тибире Эн-Менлуана правил в течение 43200 лет. Эн-Менгалана правил 28800 лет. Пастух Думузи правил 36000 лет. 3 короля, они правили 108000 лет. Затем Бад-Тибир пал (?), И царство перешло в Ларак. В Лараке Эн-Сипадзидана правил 28800 лет. 1 король, он правил 28800 лет. Затем пал Ларак (?) и царство перешло к Сиппар . В Сиппаре Эн-Мендурана стал царем. Он правил 21000 лет. 1 король; он правил 21000 лет. Затем Сиппар пал (?) И царство перешло в Шуруппак. В Шуруппаке Убар-Туту стал царем. Он правил 18600 лет. 1 король, он правил 18600 лет. В 5 городах 8 королей, они правили 241200 лет. Затем нахлынул потоп.

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

Но особая ценность царского списка в том, что в отличие от мифов он содержит множество вполне конкретных чисел. А значит если удастся найти рациональное объяснение, то сами числа послужат и инструментом проверки этого объяснения и его доказательством. А доказанное объяснение тайны списка, возможно, прольет свет и на историю Шумера, и на природу шумерских мифов.

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

Принятое объяснение лежит на поверхности. Дескать, Ветхий Завет это компиляция более древних текстов. Их пересказ был сделан небрежно, коверкая и искажая оригиналы. Текст собирался воедино без особого усердия. Компиляторы лишь приблизительно сохраняли исходные сюжеты, тащили одну легенду, затем другую и как-то пытались их склеить вместе.

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

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

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

И то же самое происходит с пятой главой Генезиса. Есть три разных источника: еврейская Библия, ее греческий перевод Септуагинта и самаритянское Пятикнижие. И во всех трех вариантах числа достаточно сильно отличаются друг от друга. Причем как и в случае царских списков, это не ошибка в одном-двух числах, что можно было бы списать на ошибки копирования, а некое сознательное изменение всей схемы.

В итоге имеем, что либо верно простое объяснение и предки действительно были наивны и крайне неаккуратны в переписывании, либо есть некий общий смысл, спрятанный и в царских списках, и в пятой главе и мы просто пока не понимаем этот смысл.

Машина времени

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

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

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

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

Каталог звезд можно скачать, например, с сайта NASA. Нас в нем будут интересовать только видимые невооруженным глазом звезды. Еще во II веке до н.э. древнегреческий астроном Гиппарх разделил все звезды на шесть величин. Первая величина самые яркие светила, шестая находящиеся на грани видимости. Позже оказалось, что наше зрение воспринимает яркость логарифмически, то есть каждое увеличение видимой яркости на одну звездную величину соответствует увеличению реальной яркости в определенное число раз, точнее, в 2.512 раза. В результате появилось современное деление звезд по видимым величинам. Изначально в нем за нулевую величину принимался блеск Веги, позже это значение было незначительно переопределено. Кстати, Солнце имеет видимую величину 26,7, что в 400 000 раз ярче полной Луны видимая величина которой 12,74. Оба значения со знаком минус, поскольку оба этих светила несколько ярче Веги.

Упорядочим звезды в каталоге по их видимой величине и оставим только видимые невооруженным глазом.

Фрагмент звездного каталога

Координаты звезд чаще всего принято задавать во второй экваториальной системе координат. Звездное небо это сфера, которая для наблюдателя с Земли вращается вдоль экватора. Первая экваториальная система задает положение звезд относительно земли, что неудобно, поскольку эти координаты меняются по мере суточного вращения. Вторая экваториальная система неподвижна относительно звезд, что делает их координаты постоянными. Положение каждой звезды определяется двумя величинами: склонением (dec) и прямым восхождением (ra).

Склонение равно угловому расстоянию на небесной сфере от плоскости небесного экватора до светила. Чуть сложнее с прямым восхождением. Понятно, что это величина, показывающая положение звезды на экваториальном круге, но от чего ее считать? Поскольку земля вращается, то земные ориентиры для этого непригодны. Оказалось удобно мерить от точки весеннего равноденствия (vernal equinox).

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

С течением времени положение звезд несильно, но меняется. Это связано с собственных движением светил. Чем ближе звезда к Земле, тем заметнее это движение. В каталоге приводятся скорости для каждой из звезд, что позволяет рассчитать их правильные координаты на любой момент времени. Но это только малая часть проблемы, связанной с получением древнего неба.

Основная сложность в том, что со временем меняется направление, в котором ориентирована земная ось. Это результат прецессии и нутации.

Прецессия заставляет земную ось вращаться, постепенно меняя свое направление. Период этого вращения 25 765 лет. Угол наклона земной оси от оси эклиптики около 23.5 градуса, за 13 000 лет положение севера, который сейчас в районе Полярной звезды, меняется на 47 градусов. Естественно, что на интервале требуемых нам 4000 лет влияние прецессии очень заметно.

Нутация небольшие колебания земной оси, накладывающиеся на прецессионное движение. Вклад нутации не столь велик, но он приводит к изменению самого угла наклона земной оси, что тоже стоит учитывать.

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

Я воспользовался статьей New precession expressions, valid for long time intervals, 2011, J. Vondrk, N. Capitaine, and P. Wallace. В ней любезно был приведен код для расчета матрицы поворота. Которая в свою очередь позволяет пересчитать координаты звезд на требуемую юлианскую дату.

Кстати, в астрономии в расчетах принято пользоваться юлианскими датами, и надо сказать, это сильно упрощает жизнь. Современный григорианский календарь более точно соответствует цикличности обращения Земли вокруг Солнца, но когда задача состоит в том, чтобы просто отмерить время, куда проще считать, что в году 365.25 дней и не заморачиваться с разрывами, возникающими из-за сложной системы вставки високосных лет.

В результате мы имеем звездное небо таким, как оно выглядело в 1840 году до н.э., а приблизительно так датируется призма wb444. Теперь попробуем полученный результат изобразить. Проблемы все те же, что и с земными картами, чем дальше от экватора, тем сильнее искажения. Будем помнить об этом. Обозначим звезды кружочками, радиусом которых обыграем их видимую звездную величину. Отложим по горизонтали прямое восхождение, а по вертикали склонение.

Млечный путь обозначим черным. Наша галактика Млечный путь имеет форму диска. Так как плоскость галактики не совпадает с плоскостью земного экватора, то на рисунке мы увидим синусоиду.

Все видимые невооруженным глазом звезды (до 6.5 видимой звездной величины). Центральная линия - линия звездного экватора

Теперь нам надо понять, что происходит со звездами во время суточного вращения Земли. И тут нам пригодится привязанная к Земле первая экваториальная система координат. Так как вращение происходит вдоль экватора, то склонения звезд не меняются и остаются теми же, что и во второй экваториальной системе. Значит, одну координату мы уже знаем. Теперь надо задать некую угловую координату, которая будет аналогом прямого восхождения. Для этого используют часовой угол.

Часовой угол светила это угол между двумя плоскостями: одна содержит ось Земли и проходит через точку на Земле, где происходит наблюдение, а другая содержит ось Земли и данную точку (часовой круг, проходящий через точку). Измеряется часовой угол либо в градусах от 0 до 360, либо в часах от 0 до 24.

Помните про точку весеннего равноденствия? В ней эклиптика, то есть годовой путь солнца по небесной сфере, весной пересекает экватор. Так вот, как и звезды, она вращается, описывая за сутки полный оборот. Ее часовой угол называют местным звездным временем. Местное это время потому, что привязано к долготе того места, где производится наблюдение.

И местное звездное время, и часовые углы звезд, и их прямые восхождения это углы, отсчитываемые вдоль экватора. Естественно, что их связывает несложная формула:

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

cos = -tan tan

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

Арккосинус даст два значения. Отрицательное значение часового угла соответствует восходу, положительное закату. Добавив к часовому углу восхода звезды ее прямое восхождение, мы получим местное звездное время ее восхода.

Почему мы заговорили о восходах и закатах? В списке царей приведены сроки неких событий. Можно предположить, что эти сроки это замеры временных интервалов между какими-то событиями, происходящими в течении ночи. А самое очевидное для наблюдения это время появления какой-либо звезды над горизонтом и момент ее захода за горизонт.

Посчитаем время восхода и заката для всех восходящих звезд. Сделаем это для широты 31.3 градуса. Именно на этой широте находится город Ларса, где была найдена призма wb444. Изобразим результат. Для этого отложим по горизонтали, например, звездное время восхода. По вертикали же изобразим положение звезды на горизонте Земли в этот момент. Нулевым значением будем считать направление на восток, сверху сделаем север, снизу юг. Для этого вычислим азимут восхода (A_восход).

cos A = sin /cos A_восход = 360 А

Азимут отсчитывается от севера. Но чтобы было нагляднее перейдем к отсчету от востока.

В результате мы получим временную развертку появления звезд на горизонте вместе с картиной того, в каком направлении этот восход происходит.

Видно, что по сравнению с предыдущей картиной синусоида млечного пути сильно исказилась. Это связано с тем, что время восхода для звезд, имеющих одинаковое прямое восхождение, будет разным в зависимости от их склонения. Ниже картина звездного неба, сделанная с длинной экспозицией. На ней видно, что для наблюдателя на Земле звезды вращаются вокруг оси, проходящей через северный полюс.

Линия, отходящая от полюса, показывает место звезд, имеющих одинаковый часовой угол. Видно, что, если одна из звезд уже взошла, то другая может быть еще глубоко за горизонтом.

Теперь надо понять, когда восходит и заходит Солнце в течение года. Для этого надо узнать экваториальные координаты Солнца на каждый из дней. Зная их, можно рассчитать звездное время восхода и захода по тем же формулам, что и для остальных звезд.

Солнце двигается по кругу эклиптики со скоростью около 1 градуса в сутки, делая полный оборот за год. В эклиптических координатах его склонение 0, а прямое восхождение меняется в течение года от 0 до 360.

Зная эклиптические координаты, можно получить экваториальные и наоборот. Для этого используются формулы перевода координат, основанные на идее вращения единичного вектора, записанного в декартовых координатах.

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

В итоге можно получить требуемые времена солнечных восходов и заходов. Но есть небольшая сложность. Так как орбита Земли не круговая, а эллиптическая, то двигается Земля по ней неравномерно. Так же неравномерно перемещается для наблюдателя с Земли и Солнце по эклиптике. Быстрее Солнце движется около 3 января (приблизительно 1 1 в сутки), а медленнее около 3 июля (57 за сутки). Это приводит к тому, что весна и лето продолжаются 186 суток, а осень и зима 179 суток.

Чтобы внести соответствующие поправки, надо применить уточненное уравнение восхода солнца.

Саму идею расчета понять несложно. Если считать, что Солнце двигается равномерно, то его долгота на эклиптике в момент весеннего равноденствия 0, в день она увеличивается на 1/365.25 градуса и за год проходит полный круг. Поправки призваны учесть эллиптичность орбиты и слегка подправить долготу в каждый из дней года. Основной вопрос: как понять, с какой фазы начинается отсчет? Для этого используют уже упомянутую нами юлианскую дату. Для удобства использования сегодня берут n, которое дает отсчет от 1 января 2000 г. В 2000 году равноденствие было на 79 день от начала года. Поэтому, рассчитывая на нашу древнюю дату и беря начало отсчета дней от равноденствия, J* можно брать как 79 + день от равноденствия - долгота места / 360.

Ниже звезды до пятой величины. По горизонтали время восхода, по вертикали положение на восточном горизонте (сверху север, снизу юг). Красные вертикальные линии - границы дня. Горизонтальная черная линия - ночь. Границы приведены на день весеннего равноденствия.

В этот момент стоит проверить себя и убедиться, что в расчетах нет ошибок. Я для этого сверялся с проектом starCharts, который кроме самого движка и интерфейса имеет подробное описание используемой математики.

Теперь пришла пора задуматься о том, что же мы, собственно, хотим увидеть. Сначала я полагал, что, возможно, в списке царей речь идет о самых ярких звездах, восходящих в течении ночи. Была идея гелиакических восходов звезд и их дат в течение года. Но все идеи, связанные со звездами, не понравились тем, что сроки правления в списке царей приведены достаточно грубо. Они указаны в сарах и нерах, один сар 3600, нер 600 единиц. Первый царь правил ровно 8 саров (28800 лет), второй ровно 10 саров (36000 лет) и так далее. Общий срок 66 саров и 6 неров. То есть точность порядка 1/60. В проекции на небо это дает неоправданно высокую погрешность в 6 градусов, странную и недопустимую для звезд. О чем тогда еще может идти речь?

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

Созвездия, лежащие на пути Солнца, называются зодиакальными. Эклиптика пересекает 13 таких созвездий: Овен, Телец, Близнецы, Рак, Лев, Дева, Весы, Скорпион, Змееносец, Стрелец, Козерог, Водолей, Рыбы. Змееносец со Скорпионом имеют близкую эклиптическую долготу, поэтому когда говорят о знаках зодиака, то оставляют только созвездие Скорпиона.

Принято считать, что представление о зодиакальных созвездиях, известное нам сегодня, сформировалось в Древней Греции в IV веке до н.э. во времена Евдокса Книдского. При этом известно, что еще до греков схожие представления были у вавилонян.

Самый достоверный источник относительно вавилонских знаний об астрономии это каталог звезд MUL.APIN. Самый древний его текст сохранился в копии 7-го века до н.э. на паре табличек. В них приведена разнообразная астрономическая информация и в том числе перечислены звезды и созвездия на пути Луны. А поскольку путь Луны очень близок к эклиптике, то список включил в себя всех вавилонских предшественников зодиакальных созвездий.

Кроме того, известен так называемый ниппурский календарь. Первое упоминание об этом шумерском календаре относится к XXIV веку до н.э. В этом календаре 12 месяцев и, что важно для нас, прослеживается связь названий этих месяцев с названиями вавилонских зодиакальных созвездий.

Можно предположить, что вавилонские созвездия сохранили в себе многие черты более ранних шумерских. Главное, что сам принцип деления пути Солнца на 12 приблизительно равных частей был введен шумерами и остался неизменным, перекочевав в зодиакальные созвездия. Скорее всего описанные греками зодиакальные созвездия, форма которых близка к современным, не сильно отличались от созвездий, придуманных шумерскими астрономами.

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

Есть три основных параметра для настройки. День года, он изменяет время восхода и заката Солнца и, соответственно, продолжительность ночи. Масштаб сетки царей. Чтобы наложить линии царей на ось, которая измеряется в часах, надо найти коэффициент, который переводит сроки правления в эти часы. Сам коэффициент будет указывать, сколько мифических лет содержится в одном часе. Ну и, кроме того, следить можно либо за восходом звезд, глядя на восток, либо за их закатом, глядя на запад.

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

Зодиакальные созвездия (восход) и линии царей для дня летнего солнцестояния.

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

Алексей Редозубов (2021 год)

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

Прочитав это руководство, вы узнаете:

• что линейный поиск это алгоритм оптимизации для одномерных и многомерных задач оптимизации;

• что библиотека SciPy предоставляет API выполнения линейного поиска, который требует знания о том, как вычисляется первая производная вашей целевой функции;

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

Давайте начнём.

Обзор

Этот учебный материал разделён на три части:

1. Что такое линейный поиск?

2. Линейный поиск на Python.

3. Как выполняется линейный поиск? Он состоит из:

a) определения целевой функции;

б) выполнения линейного поиска;

в) работы со сбоями алгоритма.

Что такое линейный поиск?

Линейный поиск это алгоритм оптимизации для одномерной или многомерной оптимизации. Он требует начальной позиции в пространстве поиска, а также указания направления поиска. Затем он из начальной выбирает следующую позицию в пространстве поиска, которая приведёт к значению лучше или же к наилучшему значению целевой функции.

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

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

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

Алгоритмы оптимизации, 2019. С. 54.

Альфа коэффициент масштаба для направления, поэтому при поиске учитываются только значения в диапазоне от 0,0 до 1,0. Один шаг линейного поиска решает задачу минимизации, которая минимизирует целевую функцию для текущей позиции в сумме с масштабируемым направлением, то есть:

• Минимизирует objective(position + alpha * direction).

Таким образом, линейный поиск работает в одном измерении за один раз и возвращает расстояние перемещения в выбранном направлении.

Каждая итерация метода линейного поиска вычисляет направление поиска pk, а затем решает, как далеко двигаться в этом направлении.

Численная оптимизация, 2006. С. 30.

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

Решение приблизительно или неточно и в зависимости от формы пространства поиска может не оказаться общим решением. Условия, при которых этот алгоритм подходит, называются условиями Вольфе. Теперь, когда мы знакомы с линейным поиском, давайте посмотрим, как выполнять его на Python.

Линейный поиск на Python

Выполнить линейный поиск на Python можно вручную, с помощью функции line_search(). Она поддерживает одномерную оптимизацию, а также многомерные задачи оптимизации. Эта функция принимает имя целевой функции и имя градиента для целевой функции, а также текущее положение в пространстве поиска и направление движения.

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

...result = line_search(objective, gradient, point, direction)

Функция возвращает кортеж из шести элементов, включая коэффициент масштаба для направления, называемый альфа, и количество выполненных вычислений функций, а также другие значения. Первый элемент в результирующем кортеже содержит альфа. Если поиск не сойдётся, альфа будет иметь значение None.

...# retrieve the alpha value found as part of the line searchalpha = result[0]

Альфа, начальная точка и направление могут использоваться при построении конечной точки линейного поиска.

...# construct the end point of a line searchend = point + alpha * direction

Для задач оптимизации с более чем одной входной переменной, например многомерной оптимизации, функция line_search() вернёт одно альфа-значение для всех измерений. Это значит, функция предполагает, что оптимум равноудалён от начальной точки во всех измерениях, такое ограничение существенно. Теперь, после ознакомления с тем, как в Python выполнять линейный поиск, давайте рассмотрим работающий пример.

Как выполняется линейный поиск?

Мы можем продемонстрировать, как использовать линейный поиск с простой одномерной целевой функцией и её производной. Этот раздел, в свою очередь, разделён на несколько частей, включая определение тестовой функции, выполнение линейного поиска и обработку неудачных случаев, когда оптимум не находится.

Определение целевой функции

Во-первых, мы можем определить целевую функцию. Здесь поработаем с одномерной целевой функцией, а именно со сдвинутой на небольшую величину от нуля функцией x^2. Это выпуклая функция, она была выбрана потому, что её легко понять, а также легко вычислить первую производную.

• objective(x) = (-5 + x)^2.

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

# objective functiondef objective(x):return (-5.0 + x)**2.0

Первая производная этой функции может быть вычислена аналитически следующим образом:

• gradient(x) = 2 * (-5 + x).

Градиент для каждого входного значения просто указывает наклон к оптимумам в каждой точке. Реализация функции градиента приведена ниже:

# gradient for the objective functiondef gradient(x):return 2.0 * (-5.0 + x)

Можно определить диапазон входных данных для x от -10 до 20 и вычислить целевое значение для каждого входного значения:

...# define ranger_min, r_max = -10.0, 20.0# prepare inputsinputs = arange(r_min, r_max, 0.1)# compute targetstargets = [objective(x) for x in inputs]

Затем, чтобы получить представление о форме функции, мы можем построить график входных значений в сравнении с целевыми значениями:

...# plot inputs vs objectivepyplot.plot(inputs, targets, '-', label='objective')pyplot.legend()pyplot.show()

Связав всё это воедино, получим такой код:

# plot a convex objective functionfrom numpy import arangefrom matplotlib import pyplot # objective functiondef objective(x):return (-5.0 + x)**2.0 # gradient for the objective functiondef gradient(x):return 2.0 * (-5.0 + x) # define ranger_min, r_max = -10.0, 20.0# prepare inputsinputs = arange(r_min, r_max, 0.1)# compute targetstargets = [objective(x) for x in inputs]# plot inputs vs objectivepyplot.plot(inputs, targets, '-', label='objective')pyplot.legend()pyplot.show()

Программа вычисляет входные значения (x) в диапазоне от -10 до 20 и создаёт график, показывающий знакомую U-образную форму параболы. Оптимум функции, по-видимому, находится в точке x=5,0, целевое значение 0,0.

Выполнение линейного поиска

Затем можно выполнить линейный поиск по этой функции. Во-первых, мы должны определить отправную точку поиска и его направление. Здесь воспользуемся начальной точкой x=-5, расстояние от которой до оптимума около 10 единиц. Сделаем большой шаг вправо, в данном случае в 100 единиц (что значительно превышает оптимум), например, в положительном направлении. Напомним, что направление похоже на размер шага и поиск масштабирует размер шага, чтобы найти оптимум:

...# define the starting pointpoint = -5.0# define the direction to movedirection = 100.0# print the initial conditionsprint('start=%.1f, direction=%.1f' % (point, direction))# perform the line searchresult = line_search(objective, gradient, point, direction)

Затем поиск ищет оптимумы и возвращает альфа или расстояние, чтобы изменить направление. Из результата мы можем получить значение альфа, а также количество выполненных вычислений функций:

...# summarize the resultalpha = result[0]print('Alpha: %.3f' % alpha)print('Function evaluations: %d' % result[1])

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

...# define objective function minima end = point + alpha * direction# evaluate objective function minimaprint('f(end) = %.3f' % objective(end))

Затем, для развлечения, мы можем снова построить график функции и показать начальную точку в виде зелёного квадрата, а конечную точку в виде красного квадрата.

...# define ranger_min, r_max = -10.0, 20.0# prepare inputsinputs = arange(r_min, r_max, 0.1)# compute targetstargets = [objective(x) for x in inputs]# plot inputs vs objectivepyplot.plot(inputs, targets, '--', label='objective')# plot start and end of the searchpyplot.plot([point], [objective(point)], 's', color='g')pyplot.plot([end], [objective(end)], 's', color='r')pyplot.legend()pyplot.show()

Ниже приведён полный пример выполнения линейного поиска для выпуклой целевой функции:

# perform a line search on a convex objective functionfrom numpy import arangefrom scipy.optimize import line_searchfrom matplotlib import pyplot # objective functiondef objective(x):return (-5.0 + x)**2.0 # gradient for the objective functiondef gradient(x):return 2.0 * (-5.0 + x) # define the starting pointpoint = -5.0# define the direction to movedirection = 100.0# print the initial conditionsprint('start=%.1f, direction=%.1f' % (point, direction))# perform the line searchresult = line_search(objective, gradient, point, direction)# summarize the resultalpha = result[0]print('Alpha: %.3f' % alpha)print('Function evaluations: %d' % result[1])# define objective function minimaend = point + alpha * direction# evaluate objective function minimaprint('f(end) = f(%.3f) = %.3f' % (end, objective(end)))# define ranger_min, r_max = -10.0, 20.0# prepare inputsinputs = arange(r_min, r_max, 0.1)# compute targetstargets = [objective(x) for x in inputs]# plot inputs vs objectivepyplot.plot(inputs, targets, '--', label='objective')# plot start and end of the searchpyplot.plot([point], [objective(point)], 's', color='g')pyplot.plot([end], [objective(end)], 's', color='r')pyplot.legend()pyplot.show()

Программа-пример сначала сообщает начальную точку и направление. Поиск выполняется, и обнаруживается изменяющая направление для нахождения оптимума значение альфа, в данном случае найденное после трёх вычислений функции 0.1. Точка оптимума находится на отметке 5,0, значение y, как и ожидалось, равно 0,0:

start=-5.0, direction=100.0Alpha: 0.100Function evaluations: 3f(end) = f(5.000) = 0.000

Наконец, создаётся график функции, показывающий зелёную начальную точку и красную цель.

Работа со сбоями алгоритма

Линейный поиск не гарантирует нахождения оптимумов функции. Он может не найти оптимумы, если задано значение направления, недостаточно большое, чтобы охватить их. Например, найти оптимумы будет невозможно, когда направление имеет значение 3. Продемонстрировать это можно на полном примере ниже:

# perform a line search on a convex objective function with a direction that is too smallfrom numpy import arangefrom scipy.optimize import line_searchfrom matplotlib import pyplot # objective functiondef objective(x):return (-5.0 + x)**2.0 # gradient for the objective functiondef gradient(x):return 2.0 * (-5.0 + x) # define the starting pointpoint = -5.0# define the direction to movedirection = 3.0# print the initial conditionsprint('start=%.1f, direction=%.1f' % (point, direction))# perform the line searchresult = line_search(objective, gradient, point, direction)# summarize the resultalpha = result[0]print('Alpha: %.3f' % alpha)# define objective function minimaend = point + alpha * direction# evaluate objective function minimaprint('f(end) = f(%.3f) = %.3f' % (end, objective(end)))

При выполнении примера поиск достигает предела альфа 1,0, что даёт конечную точку от -2 до 49. При f(5) = 0,0 от оптимумов очень далеко:

start=-5.0, direction=3.0Alpha: 1.000f(end) = f(-2.000) = 49.000

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

...# define the starting pointpoint = -5.0# define the direction to movedirection = -3.0

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

# perform a line search on a convex objective function that does not convergefrom numpy import arangefrom scipy.optimize import line_searchfrom matplotlib import pyplot # objective functiondef objective(x):return (-5.0 + x)**2.0 # gradient for the objective functiondef gradient(x):return 2.0 * (-5.0 + x) # define the starting pointpoint = -5.0# define the direction to movedirection = -3.0# print the initial conditionsprint('start=%.1f, direction=%.1f' % (point, direction))# perform the line searchresult = line_search(objective, gradient, point, direction)# summarize the resultprint('Alpha: %s' % result[0])

Выполнение программы приводит к предупреждению LineSearchWarning, указывающему на то, что поиск, как и ожидалось, не может сойтись. Альфа возвращённое в результате поиска значение равно None:

start=-5.0, direction=-3.0LineSearchWarning: The line search algorithm did not convergewarn('The line search algorithm did not converge', LineSearchWarning)Alpha: None

Дальнейшее чтение

Если вы хотите глубже погрузиться в тему, смотрите этот раздел.

Книги

• Алгоритмы оптимизации, 2019.

• Численная оптимизация, 2006.

API

• Оптимизация и поиск корней (scipy.optimize).

• Оптимизация (scipy.optimize).

• scipy.optimize.line_search API.

Статьи

• Линейный поиск. Википедия.

• Условия Вольфе. Википедия.

Резюме

Из этого руководства вы узнали, как выполнить оптимизацию линейного поиска на Python. В частности, вы узнали:

• что линейный поиск это алгоритм оптимизации для одномерных и многомерных задач оптимизации;

• что библиотека SciPy предоставляет API выполнения линейного поиска, требующий знания о том, как вычисляется первая производная вашей целевой функции;

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

Применяемые в машинном обучении методы оптимизации, конечно же, не ограничиваются одним лишь линейным поиском, они многочисленны, разнообразны и у каждого есть свои недостатки и преимущества. Если вы хотите погрузиться в машинное обучение, изучить оптимизацию глубже, но не хотите ограничивать себя областью ML, вы можете обратить внимание на наш курс "Machine Learning и Deep Learning", партнёр которого, компания NVIDIA, не нуждается в представлении.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Всем известно, что классическая механика является предельным случаем квантовой с одной стороны и теории относительности с другой. Последние две наиболее точно описывают реальность, в то время как первая считается лишь удобным частным случаем. Из квантовой физики можно получить классическую, но не наоборот.

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

Таким образом, основные физические законы, необходимые для математической теории значительной части физики и всей химии, полностью известны, и трудность заключается лишь в том, что точное применение этих законов приводит к уравнениям, которые слишком сложны, чтобы быть разрешимыми. Поэтому становится желательным разработать приближенные практические методы применения квантовой механики, которые могут привести к объяснению основных особенностей сложных атомных систем без слишком больших вычислений.

П. Дирак

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

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

Знаменитое уравнение Шредингера математически близко к обычному уравнению диффузии. Главное отличие в том, что время становится мнимым, то есть происходит поворот Вика. Это означает, что классическое и квантовое частично связаны поворотом на 90 градусов в комплексной плоскости (умножением на мнимую единицу). Уравнение Шредингера задается:

(Сопутствующий философский бред можно найти в эмоциональной статье)

Ричард Фейнман в своих знаменитых лекциях писал:

Мы не хотим, чтобы вы думали, что мы вывели уравнение Шредингера, но хотим показать вам лишь способ рассуждения. Когда Шредингер впервые записал его, он дал своего рода вывод, основанный на некоторых эвристических аргументах и блестящих интуитивных догадках. Некоторые из аргументов, которые он использовал, были даже ложными, но это не имеет значения; важно только то, что конечное уравнение дает правильное описание природы. [Фейнман, Лекции по физике, II-14.1]

В литературе приводится множество эвристических способов обоснования уравнения, но в целом оно вводится как один из постулатов квантовой механики. Тем не менее недавняя статья из Nature, указывает на то, что последовательный аналитический вывод вполне осуществим.

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

Затем, крайне непринужденно просуммировав пути (а ля фейнмановские интегралы по траекториям) и подняв теорию стохастического оптимального контроля, разумеется, с оглядкой на релятивистскую инвариантность, авторы получают уравнение Гамильтона-Якоби-Беллмана

При этом они постоянно заостряют внимание, что вместо того, чтобы постулировать правила подстановки операторов, вывод происходит полностью осмысленным образом.

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

Затем шаг за шагом осуществляется переход:

уравнение Гамильтона-Якоби-Беллмана -> уравнение Штекельберга -> телеграфные уравнения -> уравнения Клейна-Гордона, Дирака и нерелятивистское Шредингера.

И это восхитительно!

Во первых, мнимая природа различных переменных в квантовой механике автоматически выходит из структурой метрики Минковского. Причем авторы надеются в дальнейшем установить волновое уравнение в общем искривленном пространстве-времени. И такое обобщение метрики "возможно, было бы способом объединить общую теорию относительности и квантовую механику".

Во вторых, можно вспомнить, что происхождение правила Борна до сих пор выглядит неоднозначным. Хотя, в многомировой, клеточно-автоматной, волно-пилотной и еще в некоторых интерпретациях оно всплывает так или иначе как побочный продукт. Здесь же правило Борна естественным образом связано с реальной частью минимального ожидаемого действия. "Процесс пространственно-временной диффузии проходит по маршруту, который сводит к минимуму ожидаемое действие; в этом суть того, как вероятность (перехода) связана с минимизацией энергии."

В третьих, подход придерживается реалистической философии квантовой механики, где реальность существует независимо от наблюдателя. Что это значит для нас?

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

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

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

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

(Методику построения траекторий см. в приложении)

В теории волны-пилота частицы подчиняются нелокальному действию квантового потенциала. А показанная выше модель предполагает, что исследуемая частица движется под действием внешней случайной силы пространства-времени. Здесь нет волн коллапсирующих в частицы. Частицы просто взаимодействуют с некоторыми скрытыми степенями свободы, по жизни двигаясь зигзагами. Волновые паттерны возникают из коллективного поведения миллионов частиц. А волновая функция лишь описывает эти паттерны.

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

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

Дальнейшее чтиво

• Здесь можно посмотреть более популярный обзор обсуждаемой статьи.

• Далее читаем рассуждения о верности уравнения Шредингера. В принципе, на него уже давно прицепляют всяческие довески: нелинейность, память, стохастичность, так что фундаментальность это больше вопрос веры.

• Стохастическая квантовая механика выделена в отдельную интерпретацию. Вообще, эта тема была популярна в 60-х. Чего стоит зашкварная статья, где уравнение Шредингера вывели из ньютоновской механики (правда там тоже было броуновское движение). По ней до сих пор плодятся трибьюты (раз, два, три, четыре, пять). Следует также отметить, что недавно было показано, что знаменитые соотношения неопределенности Гейзенберга в целом присущи стохастическим системам, и, как видится, они не являются уникальными для квантово-механических систем.

• Конечно, можно зайти и со стороны электродинамики. Вот из свеженького.

• Герард `т Хоофт (продвигающий интерпретацию клеточных автоматов) пару месяцев назад выпустил препринт, где квантовая механика эмерджентно выходит из классической. Кто знает, может его быстрые переменные и будут играть роль случайных сил. И до кучи вспоминаем, что на гравитацию тоже начинают поглядывать с эмерджентных позиций.

(Подробности см. в статье)

Дальше, в предложенных статьях расшариваем список литературы и Cited by, чтобы окончательно убедиться, что по теме идут серьезные сподвижки. То ли классическая детерминистичная механика ушла на задний план в ожидании когда подтянется матаппарат статистики и клеточных автоматов, чтобы затем вновь вернуться на периферию философской мысли. То ли научное сообщество устало бороться с контринтуитивностью и готово принять любую модель подразумевающую комфортную математику и простоту в объяснениях. Ответ узнают наши потомки на лекциях по философии науки.

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

Наши размышления о закономерностях в простых числах привели к некоторым сложнейшим проблемам, нерешенным даже величайшими математическими гениями. Сегодня мы рассмотрим 5 старейших математических задач о простых числах, которые интуитивно понятны старшекласснику, но все еще не доказаны даже после упорных попыток в течение 500-2000 лет.

1. Совершенные числа: существуют ли нечетные совершенные числа? Бесконечны ли четные совершенные числа?

Рассмотрим числа 6, 28, 496, 8128

Что в них особенного? Если вы не знаете, то я бы посоветовал сделать небольшую паузу и попытаться найти красивое свойство, которым обладают эти числа.

Двигаемся дальше....

Если посмотреть на собственные делители этих чисел, то нетрудно заметить то самое красивое свойство:

Числа, для которых сумма собственных делителей равна самому числу, называются совершенными числами. Самое раннее исследование совершенных чисел затеряно в истории. Однако, мы знаем, что пифагорейцы (525 год до н. э.) изучали идеальные числа.

Что мы знаем о таких числах?

• Евклид доказал, что для данного n, если - простое число, то - совершенное число. В качестве упражнения попробуйте доказать это самостоятельно.

Окей, краткий экскурс.

Простые числа Мерсенна: простые числа вида для некоторого n. Мерсенн предположил, что все числа вида простые, когда n простое. (Мы знаем, что это неправда. Например, ).

Открытый вопрос: существует ли бесконечно много простых чисел Мерсенна? На данный момент нам известно 47 простых чисел Мерсенна.

• В 18 веке Эйлер показал обратное: любое четное совершенное число имеет вид Другими словами, существует взаимно однозначное соответствие между четными совершенными числами и простыми числами Мерсенна.

Как видите, мы знаем о четных совершенных числах и способах их получения еще со времен Евклида (около 300 год до н. э.). Но нам неизвестно, существую ли нечетные совершенные числа!!! (на самом деле, прогресс в решении этой проблемы практически отсутствует).

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

2. Гипотеза о близнецах: простых чисел-близнецов бесконечно много

Простые числа-близнецы это пара вида (p, p + 2), где p и p + 2 являются простыми числами.

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

На протяжении 2000 лет в доказательстве этого утверждения практически не было прогресса.

Что мы знаем!

1. Существует бесконечно много простых пар вида (p, p + k), где k <= 246.

2. Если допустить истинность гипотезы Эллиота Халберстама (которая, по нашему мнению, верна), то существует бесконечно много простых пар вида (p, p + k), где k <= 6. Это означает, что множество пар простых чисел, отличающихся на 2 (twin-primes), на 4 (cousin-primes) и на 6 (sexy-primes) бесконечно.

Возможно, величайший из ныне живущих математиков, Теренс Тао, активно работает над этой проблемой. Посмотрите это видео, чтобы познакомиться с этим математическим гением и его работой над простыми числами-близнецами.

3. Какие правильные n-угольники построимы?

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

Древние греки знали, как построить правильный многоугольник с 3,4 и 5 сторонами. Также они умели строить правильные многоугольники с удвоенным числом сторон для данного правильного многоугольника.

Таким образом, они могли построить правильный n-угольник для n = {3, 6, 12, 24 4, 8, 16 5, 10, 20} и так далее.

Естественно задать вопрос, для каких значений n можно построить правильный многоугольник. Первый реальный результат в решении этой проблемы был получен спустя 2000 лет после того, как древние греки впервые начали её изучать. В 1796 году 19-летний подросток построил правильный 17-угольник. Этим ребенком был не кто иной, как Карл Фридрих Гаусс. Несколько лет спустя Гаусс дал ответ на общую проблему.

Что мы знаем!

Гаусс показал, что правильный n-угольник может быть построен с помощью циркуля и линейки тогда и только тогда, когда n является произведением степени двойки и любого количества различных простых чисел Ферма (включая ни одного).

Простое число Ферма это простое число вида:

Таким образом, проблема поиска всех построимых многоугольников сводится к нахождению всех простых чисел Ферма. Это отдельная нерешенная проблема. Несколько первых чисел Ферма: 3, 5, 17, 257, 65537, 4294967297

По состоянию на 2021 год единственными известными простыми числами Ферма являются F0=3, F1=5, F2=17, F3=257, F4=65537.

Ферма предположил, что все числа Ферма являются простыми. В 1732 году Эйлер открыл, что F5 делится на 641. С тех пор мы выяснили, что для n = 5, 6...31 числа Ферма составные. Простое число Ферма после F4 неизвестно.

Мы найдем ответ на вопрос о построимых правильных n-угольниках в тот же момент, как только найдем ответ на вопрос о существовании простых чисел Ферма.

4. Гипотеза Гольдбаха (1742)

Сильная гипотеза Гольдбаха:

Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Слабая гипотеза Гольдбаха:

Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Второе утверждение называется слабым, потому что в случае истинности сильной гипотезы вторая также будет истинной. К сожалению, после значительных усилий поколений математиков, начиная с Эйлера, мы так и не смогли доказать ее.

(Примечание В 2013 году Харальд Хельфготт опубликовал доказательство слабой гипотезы Гольдбаха. По состоянию на 2018 год доказательство широко принято в математическом сообществе, однако оно еще не было опубликовано в рецензируемом журнале).

В любом случае, все ждут доказательства сильной гипотезы.

Что мы знаем!

1. В 1930 году было доказано, что любое натуральное число больше 1 может быть записано в виде суммы не более чем C простых чисел, где C < 800 000 [Примечание мы хотим, чтобы C = 2].

2. В последнее десятилетие было показано, что каждое четное число n >= 4 на самом деле является суммой не более чем 6 простых чисел (т.е. С <= 6). Позже результат был улучшен до C <= 4.

Забавный факт гипотеза Гольдбаха является частью сюжета испанского фильма 2007 года Западня Ферма.

Отказ от ответственности: название статьи вводит в заблуждение. После рассказа о 4 нерешенных задачах я хотел бы показать одну математическую проблему (пятая проблема), которая была недавно решена (в 2004 году).

5. Тест простоты числа принадлежит классу P (2004)

Допустим, вам дано число n = 10089886811898868001. Вас спрашивают, простое ли это число. Первое, что вам приходит на ум, так это,

Алгоритм A проверить для каждого числа делится ли n на k. Вы можете оптимизировать этот алгоритм, понимая, что если n не является простым, то n будет иметь такой множитель k, что

Алгоритм B итак, вы проверяется только

Хорошо, но погодите, что такое P?

Говорят, что задача находится в P, если существует быстрый алгоритм, который может решить задачу. В нашем случае задача заключается в том, чтобы определить, является ли заданное n простым числом.

Итак, что такое быстрый алгоритм?

Для любой заданной проблемы у нас имеется размер ввода (назовем его x). Для нашей задачи размер ввода это количество цифр в числе n. Итак, x = 20 для указанного выше n. В общем случаем, при заданном n,

Алгоритм называется быстрым (алгоритм с полиномиальным временем), если он решает задачу за f(x) шагов, где f полиномиальная функция.

Если взглянуть на вышеупомянутые алгоритмы, то получим, что мы имеем n шагов в алгоритме А и шагов в алгоритме B.

Итак, размер ввода в нашем случае

Обозначим - количество шагов в алгоритме для данного размера ввода x.

Для алгоритма А,

Для алгоритма B,

В обоих случаях алгоритмы имеют экспоненциальное время. В течение 400 лет математики пытались выяснить, можно ли решить задачу определения простоты числа за полиномиальное время. Оказывается, что да. Новость об этом распространилась в математическом сообщество (особенно среди теоретиков чисел) в 2004 году, когда об этом объявили профессор и двое его студентов из IITK.

Алгоритм (известный как тест простоты AKS) был опубликован в статье под названием Primes Is In P, где показывается, что задача (независимо от того, является ли n простым или нет), может быть решена за ~ шагов. Позже были внесены некоторые улучшения, сократившие время до ~ шагов, также выдвигались предположения, что время можно уменьшить и вовсе до ~ шагов (прим. переводчика предположение оказалось ложным).

Дата-центр ITSOFT размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.

Зарабатывать продажей лекарств, которые заведомо не работают, не только аморально, но и не особо легко. Люди всё-таки обычно не хотят покупать препараты, неэффективность которых была доказана. А вот если вы сумели выдавить заветное p < 0.05 в пользу того, что акупунктура таки работает из данных, которые явно утверждают обратное, то серия публикаций, успех в карьере и вечная благодарность всех акупунктурщиков вам гарантированы.

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

Philadelphia Eagles выиграли 10 предыдущих игр, если они не были фаворитом, играли на собственном поле и в предыдущем матче прошли более 150 ярдов в наступлении.

10 игр! Это подразумевает, что вероятность поражения в аналогичных условиях 1/(2^10) = 1/1024 = 0.0009. Такая степень уверенности не каждый день встречается даже в серьёзных исследованиях. И это, разумеется, не потому что Eagles действительно так уж хороши, а потому что анализ был проведён неправильно. Иногда так получается просто потому, что авторы не умеют нормально анализировать данные, и в результате целые области науки оказываются под вопросом. А иногда так поступают откровенные мошенники (что в академической науке, что за её пределами).

Как получить p<0.05

По определению, p-значение в 0.05 это вероятность в 5%, что результат будет получен, если верна нулевая гипотеза, то есть если лекарство не работает, исследуемые феномены не взаимосвязаны и вообще ничего интересного тут нет. Так что основная идея проста: если взять два десятка гипотез, то, скорее всего, одна из них будет иметь p0.05.

Получить много гипотез для проверки можно двумя основными способами. Если изначально разбить рассматриваемую выборку на множество подгрупп, то, скорее всего, хоть в одной из них да получится статистически значимый результат. Этот метод прекрасно иллюстрирует xkcd: мармеладки вообще прыщи не вызывают (p>0.05), и красные мармеладки, в частности, тоже не вызывают (p>0.05). И жёлтые не вызывают, и сиреневые, и оранжевые, и коричневые, и ещё два десятка цветов не вызывают а вот для зелёных p<0.05.

Второй метод (он же метод Латиноамериканской Бабушки) подразумевает деление исходной выборки на любые произвольные подгруппы до тех пор, пока не найдётся комбинация условий, при которой p<0.05. Допустим, в вымышленной стране существует вымышленное заболевание, от которого сама собой излечивается ровно половина больных. Вторая половина умирает. На первый взгляд, ваше чудо-лекарство, повышающее долю выживших аж до 50%, выглядит так себе даже по меркам British Journal of General Practice. Но всегда можно взглянуть поподробнее.

Допустим, по чистой случайности удачно вылечившиеся распределены по полам слегка неравномерно: выздоровело 49% мужчин и 51% женщин. А среди женщин старше 60 лет препарат помог аж 55%. И, допустим, 13 пожилых женщин, участвовавших в исследовании, родом из Мексики. Вполне может оказаться, что препарат помог 10 из них. Это уже не 50%, а 77%, и к тому же вполне приличное p-значение в 0.046. Можно наслаждаться репутацией спасителя латиноамериканских бабушек (а если бы с ними не прокатило можно было бы проверить еврейских мальчиков, девочек-негритянок, белых среднего возраста и все остальные комбинации).

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

Но что, если бабушек было не 13, а 90, и препарат помог аж 61? Даже если всем остальным он не помог, две трети выздоровевших и p-значение в 0.0005 выглядят впечатляюще, а 90 человек это уже вполне приличная выборка. Давайте посчитаем, но для начала немного теории.

P-значения в общем-то довольно плохой инструмент. Сама идея обнаруживать то, чего нет, не чаще, чем в 1 эксперименте из 20 звучит не очень впечатляюще, а к тому же даже в теории 5%-ный порог p-значения обманывает экспериментатора в 30% случаев. Но вот что они делают хорошо так это конвертируют любое распределение в равномерное. Например, если взять несколько значений из нормального распределения, то они в основном лягут примерно по центру. А вот их p-значения равномерно распределятся между 0 и 1.

В статье вы чаще всего увидите p-значения только для лучшей гипотезы (что прыщи возникают от зелёных мармеладок, а лекарство прекрасно помогает пожилым женщинам латиноамериканского происхождения). Первый шаг к нормальному анализу это поправка Бонферрони:

Правило Бонферрони: Порог P-значения в для одной гипотезы эквивалентен порогу в /N для лучшей из N гипотез.

Обычно её интерпретируют как верхнюю границу: порог в /N для N гипотез заставляет принять нулевую гипотезу не чаще, чем порог в для единственной протестированной гипотезы. Но, на самом деле, это неплохая аппроксимация: пусть h1,,hN это N p-значений для N независимых нулевых гипотез, и все они находятся в диапазоне от 0 до 1. Тогда вероятность того, что хотя бы одно из них ниже /N = P(min(h1,,hN) < /N) = 1 (1 /N)^N 1 e^- 1 (1-) = . Последние шаги основываются на линейной аппроксимации e^x 1+x, которая работает при близких к нулю x.

Но это доказательство работает для независимых гипотез. В случае мармеладок так оно и есть, а вот для мексиканских бабушек гипотезы взаимосвязаны. Шанс выздоровления, например, белых мужчин положительно коррелирует и с шансом выздоровления белых людей вообще (т.е. более широкой категории), и с шансом выздоровления белых пожилых мужчин (подмножества белых мужчин). Чтобы проверить применимость правила Бонферрони в такой ситуации, я прогнал симуляцию (код доступен на Github).

Пусть в нашей стране живут люди трёх возрастов (молодые, среднего возраста и старые), двух полов и четырёх рас. В каждой из 2*3*4=24 подгрупп по пятьсот человек, общее население 12 000. По условиям задачи болезнь убивает 50% больных, так что в среднем ожидается 12 000/2=6 000 выживших. Для всей выборки мы получим p=0.05, если выздоровеет 50.75% (90 дополнительных выздоровевших) и p=0.0005, если вылечится 51.5%.

Правило больших выборок: при достаточно большой выборке статистическая значимость не обязательно обозначает практическую значимость. Можно получить копеечный эффект с очень низким p-значением.

P-значения не особенно помогают добраться до истины. Но они повсюду, с ними легко работать, и они неплохо отсекают откровенную чепуху. Поскольку статья именно про это, я не буду влезать в байесовскую статистику и ограничусь обсуждением возможных манипуляций с p-значениями.

Вернёмся к нашей симуляции. Я прогнал её 1 000 раз для трёх лекарств: плацебо, вылечивающее 50%; статистически значимое лекарство, вылечивающее 50.75%; и хорошее лекарство, вылечивающее 51.5% (да, вот такие вот у нас критерии хорошего). Для каждого из лекарств я искал подгруппу, в которой оно выдаст лучшее p-значение:

13 hispanic 1    0.12253041651147314 female hispanic 2    0.18079730402678315 young hispanic 2    0.2517223358154316 young female hispanic 3    0.17187517 white 1    0.046230490536462118 female white 2    0.57223222404718419 young white 2    0.2517223358154320 young female white 3   0.945312521 adult 1    0.36877715449216222 female adult 2    0.78520474607830623 asian 1    0.95376950946353824 female asian 2    0.819202695973217

Второе число это глубина выбранной подгруппы (вся выборка 0, азиаты 1, азиатские женщины среднего возраста 3). В нашем случае возможно 60 групп: 1 полная выборка, 9 групп глубины 1, 26 глубины 2, 24 - глубины 3. Так что поправка Бонферрони требует порога p-значения в 0.05/60=0.00083

В каждой из 1000 симуляций я выбрал самую удачную группу и построил график. Цветами показана глубина подгруппы, вертикальные линии соответствуют нескорректированному значению в 0.05 и скорректированному 0.00083. По горизонтальной оси логарифм p-значения, по вертикальной сколько симуляций (из 1000) имеют значение не ниже данного.

Безо всякого мошенничества плацебо получает p<0.05 в 5% случаев (что очевидно из определения), значимое лекарство в 50% случаев, а хорошее в 95. Но если мы применим поправку Бонферрони, то работающие лекарства пройдут проверку всего в 23% и 72% случаев соответственно. У плацебо дела ещё хуже, но всё-таки получается, что в таких случаях поправка оказывается чересчур агрессивной.

Как заметить подвох

Что всё это даёт на практике? Давайте соберём воедино все имеющиеся у нас советы.

1. Мощность превыше всего: если результат получен на крошечной выборке (и особенно если в исходных данных много шума) дальше можно не читать.

2. Считайте категории: если вы видите результат только для одной подгруппы, посчитайте, сколько аналогичных категорий можно выделить из тех же данных.

3. Применяйте поправку: разделите исходный порог p-значения на то, что получилось в предыдущем пункте (или, что эквивалентно, умножьте на него само p-значение). Если полученный результат вас устраивает, хорошо.

4. Сохраняйте скептицизм: даже со всеми поправками сомнительный результат есть сомнительный результат, а статистическая значимость необязательно подразумевает реальную значимость. Сколь угодно низкое p-значение ещё ничего не гарантирует.

Существует мета-анализ, подтверждающий с p=0.00000000012 способность некоторых людей предсказывать будущее. Цифра потрясающая, но она имеет смысл, только если нет ни малейших сомнений в том, что это исследование (и все предыдущие работы, на которые оно опирается) было проведено безупречно. Если есть причины считать, что это не так, то на самом деле p-значение намного выше полученного.

Можно предположить, что как минимум одна психологическая статья из тысячи выполнена некорректно, а то и вовсе написана по сфабрикованным результатам. Соответственно, любое полученное в психологии p-значение ниже 1/1000 ничем не лучше p-значения ровно в 1e-3. Вероятность получить результат в отсутствие изучаемого феномена равна собственно p-значению плюс вероятность того, что исследование в целом некорректно.

Посмотрим, что этот метод говорит нам насчёт ставки на Eagles. Во-первых, раз речь идёт о 10 выигранных играх, то 11-ю игру (в смысле 11-ю с конца, предшествующую этим 10) в аналогичных условиях они проиграли, иначе обсуждалась бы серия из 11 побед. Во-вторых, 10 игр это не так чтоб очень большая выборка, но зато нет никакой погрешности измерения. Мы знаем со стопроцентной вероятностью, выиграли ли они ту или иную игру или проиграли. К мощности эксперимента формальных претензий нет.

А вот со вторым пунктом некоторые проблемы . Даже если Eagles действительно неплохо играют как не-фаворит на своём поле после удачного наступления в предыдущем матче, тот же самый матч может быть описан как Игра сиэтлской команды после победы на выезде против команды, которая плохо пасует (прим. пер.: речь об описании матча с точки зрения их противников, Seattle Seahawks), или как Матч команды восточного дивизиона на западе против команды, выигравшей предыдущий матч, или ещё несколькими тысячами способов. Число возможных параметров сложно даже посчитать, но попробуем прикинуть:

1. Описание одной команды: дивизион, родной город, история в этом сезоне, результат предыдущей игры, качество атаки и защиты, статистика отдельных игроков итого не меньше 20 параметров.

2. Столько же для другой команды.

3. Обстоятельства игры: домашний / выездной матч, погода, время года, состояние поля, история игр между конкретными двумя командами итого не меньше 10 параметров.

Даже если выбрать в каждой категории всего по 1 параметру, получится 4000 моделей. Что это означает для Eagles? Вероятность поражения, согласно данной модели, 1/1024, но поправка Бонферрони для 4000 гипотез говорит нам, что примерно 4 гипотезы аналогичной сложности должны оказаться верными по чистому совпадению. Разумеется, Экинс не перебрал их все; он просто порылся в данных, нашёл интересное совпадение и опубликовал его. Но при таком количестве возможных гипотез единственное совпадение ничего не стоит. В обсуждаемом матче Eagles проиграли со счётом 15:26.

Тот же критерий нужно применять каждый раз, когда кто-то хвастается превосходством в неожиданно узкой категории. На этой рекламе коллектив Тринити-Университета признан лучшим в Техасе (и 6-м в стране) среди преподавателей, занимающихся исследованиями и читающих лекции. При виде этой фразы сразу нужно задуматься, сколько ещё категорий было в цитируемом исследовании, сколько вообще существует рейтингов, и в скольких из них Тринити никаких мест не занял. Университет 1 в общем рейтинге, скорее всего, действительно хорош в преподавании; про университет 1 в данной узкой категории мы знаем только то, что они умеют перебирать все возможные рейтинги и подкатегории.

Введение

Возможно ли превратить координаты на изображении в конкретные географические координаты? Несмотря на то, что это звучит несколько необычно, такая конвертация вполне возможна.

Сегодня я расскажу о том, как можно спроецировать координаты с плоского изображения на карту. Эта короткая статья будет своеобразным продолжением первой статьи, в которой я рассказывал о базовых возможностях Mask R-CNN.

Статья была написана в сотрудничестве с @avdosev за что ему большое спасибо.

Проблема

Необходимо по изображению с камеры понять, где находится объект на карте территории. Схематично это выглядит так.

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

Также условимся, что мы рассматриваем простой случай, когда камера не пересекает стены, и мы можем представить ее область видимости при виде сверху, как трапецию.

Требования к камере:

• Не должно быть рыбьего глаза.

Требование к изображению:

• На изображении с камеры должна быть видна плоскость земли.

Способ 1.

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

Достоинства:

• Алгоритм будет работать быстро, мы ограничены скоростью доступа к Map структуре данных, файлу или базе данных;

• Сложных вычислений в рантайме нет.

Недостатки:

• Если камера сдвигается даже на миллиметр, все наши данные устаревают, и будут давать уже не точный результат;

• Требуется хранить информацию о каждом пикселе для каждой камеры на территории, что нецелесообразно;

• Задавать для каждого пикселя координаты слишком долго и сложно.

Исходя из этих проблем, был отброшен первый способ и продолжен поиск других.

Способ 2.

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

1. Посмотреть на карту территории и изображения с камеры и постараться указать наиболее точные координаты углов;

2. Зная параметры камеры (высота над землей, координаты камеры, угол наклона камеры и углы обзора), получить координаты углов видимости (трапеции), либо сразу вычислить координаты объекта.

Расчет положения объекта по координатам углов видимости

Для начала стоит разобраться, как выглядит область видимости камеры на виде сверху.

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

Для простоты расчетов можно считать его трапецией.

Для расчета местоположения объекта используем следующие формулы.

Где

• l2 , l1 промежуточные переменные для вершины;

• imageHeight, imageWidth высота и ширина изображения с камеры в пикселях соответственно;

• A, B, C, D географические координаты вершин трапеции поля зрения камеры в формате {lat: float, lng: float};

• X, Y координаты пикселей на изображении в декартовой системе координат, являются целыми числами;

• M - результирующие координаты.

В случае Full HD картинки ширина и высота будут следующими: imageHeight=1080; imageWidth=1920.

После распознавания объекта на изображении, нейросеть отдаст координаты углов прямоугольника. Из него необходимо выбрать точку на изображении, для которой будут определяться координаты. Для этого есть несколько способов:

1. Брать центроид прямоугольника;

2. Брать середину нижней стороны прямоугольника. Этот способ даст более точный результат, если объект перемещается по земле, а не летает;

Всё это можно объединить:

Взять 1/N высоты и центр по горизонтали, где N может изменяться в зависимости от различных факторов, например, типа объекта или способа перемещения.

Например, для N=8 мы получим такую результирующую точку на прямоугольнике объекта.

Все эти способы имеют существенную погрешность при малой высоте камеры или/и при большом наклоне камеры.

Расчет углов видимости камеры, используя ее характеристики

Для нахождения точек A, B, C, D автоматизированным образом, нам необходимо найти центр будущей трапеции C.

Зная высоту h и угол наклона камеры , мы можем найти противоположный катет len.

Зная координаты камеры (точка О) и её направление (в какую сторону она смотрит, угол ) можно найти центр её наблюдения (точка С). Найти ее можно по формуле:

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

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

Для основного угла +/- половина угла обзора по вертикали.

Для вторичного угла +/- половина угла обзора по горизонтали.

Примем горизонтальный угол обзора за viewAngleHorizontal, а вертикальный за viewAngleVertical.

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

Далее повторно рассмотрим точки трапеции. (Не стоит путать следующую точку C с центральной).

Скомбинировав смещения по углам обзора, мы получаем координаты углов изображения - точки A, B, C, D.

Зная точки A, B, C, D можно получить географические координаты объекта. Но можно обойтись и без них. Следующий расчет потребует imageHeight, imageWidth, X, Y.

Если добавить вспомогательные оси, где координаты X, Y будут центром, то наш пиксель поделит изображение на 4 части. Определив отношения частей по горизонтали и по вертикали, мы можем определить углы, на которые должны делать смещение. Итоговая формула выглядит так:

Реализация на Python

imageWidth = 1920 # в данном примере зададим их константамиimageHeight = 1080import numpy as npdef geoToList(latlon):  return np.array((latlon['lat'], latlon['lng']))  def listToGeo(latlon):  return {'lat': latlon[0], 'lng': latlon[1] }  def getGeoCoordinates(A, B, C, D, X, Y):    A, B, C, D = list(map(geoToList, [A, B, C, D]))    vBC = (C - B) / imageHeight    vAD = (D - A) / imageHeight    latlonPixel1 = vBC * (imageHeight - Y) + B    latlonPixel2 = vAD * (imageHeight - Y) + A    vM = (latlonPixel2 - latlonPixel1) / imageWidth    M = vM * X + latlonPixel1    return listToGeo(M)

Результаты

Из этого изображения были получены координаты объекты левого верхнего и правого нижнего угла по X, Y соответственно - 613;233 1601;708.

Исходный код всегда доступен на Github.

Если найдете ошибки в алгоритме или в формулах, пожалуйста, сообщите об этом в комментариях.

Литература

• Using Calibration to Translate Video Data to the Real World

• Using panoramic videos for multi-person localization and tracking in a 3D panoramic coordinate

Лекции по курсу Управление Техническими Системами читает Козлов Олег Степанович на кафедре Ядерные реакторы и энергетические установки факультета Энергомашиностроения МГТУ им. Н.Э. Баумана. За что ему огромная благодарность!

Данные лекции готовятся к публикации в виде книги, а поскольку здесь есть специалисты по ТАУ, студенты и просто интересующиеся предметом, то любая критика приветствуется. В предыдущих сериях:

1. Введение в теорию автоматического управления.
2. Математическое описание систем автоматического управления 2.1 2.3,2.3 2.8,2.9 2.13.
3. ЧАСТОТНЕ ХАРАКТЕРИСТИКИ ЗВЕНЬЕВ И СИСТЕМ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ (РЕГУЛИРОВАНИЯ).
3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ.
3.2. Типовые звенья систем автоматического управления (регулирования). Классификация типовых звеньев. Простейшие типовые звенья.
3.3. Апериодическое звено 1го порядка (инерционное звено). На примере входной камеры ядерного реактора.
3.4. Апериодическое звено 2-го порядка.
3.5. Колебательное звено.3.3. Апериодическое звено 1го порядка (инерционное звено). На примере входной камеры ядерного реактора.
3.6. Инерционно-дифференцирующее звено.

Тем сегодняшней статьи: 3.7 Форсирующее звено (идеальное звено с введением производной)

Уравнение динамики форсирующего звена:

Уравнение динамики в изображениях Лапласа:

В общем, данное звено формально можно отнести к позиционным, т.к.или статическая характеристика имеет вид: .

Передаточная функция форсирующего звена:

АФЧХ форсирующего звена, получается путем замены

Модуль АФЧХ:

Подставляя в формулы (3.7.4) и (3.7.5) различные значениястроим соответствующие графики:

Логарифмическая амплитудная характеристика (ЛАХ):

Если звено приблизительно совпадает с идеальным усилительным звеном - .

Если - звено приблизительно совпадает с идеальным дифференцирующим звеном -

Переходная функция:

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

Построим соответствующие графики:

Примечание: Данное звено реализуется в ПД-регуляторах, обеспечивающих введение производных в закон управления. ПД-регулятор увеличивает быстродействие замкнутых САР, т.к. управление ведется по рассогласованию и по производной от рассогласования.

Пример

Мы уже запилили 10 лекций по УТС Управление в технических устройствах, но пока не рассмотрели ни одного примера, где было представлено собственно управление. Поскольку рассматриваемое в этой лекции звено используется в виде регулятора, разберем, наконец, в примере непосредственно модель управления техническим устройством, чтобы еще немного переместиться от теории к практической реализации.

Создадим комплексный в проект, в котором будут модель технического объекта (файл проектаnode_НS_2.prt) и модель системы управления (файлpd.prt), объединенные в пакет (файлnode_НS_2.pak)

В качестве технического объекта возьмём модель камеры смешения, используемую как иллюстрацию лекции Апериодическое звено первого порядка, и добавим к модели Узел регулирования температуры (см. рис. 3.7.7)

Узел регулирования температуры представляет собой дополнительный трубопровод с регулирующим клапаном (Valve_1 см. рис. 3.7.7). С одной стороны трубопровод подключён к узлу камеры смешения, с другой стороны задается граничное условие (ГУ) по давлению и температуре.Давление в ГУ больше давления в камере смешения, и температура то же больше чем на входе в камеру смешения.

Таким образом, при открытии клапана добавляется больше горячей воды, и температура в камере смешения растет. При закрытии клапана горячей воды подается меньше, и температура уменьшается. Так мы получаем возможность регулировать температуру.

В системе также установлен датчик температуры в узле камеры смешения. База сигналов проекта содержит два сигнала:

• Температура в камере смешения (берется из датчика);

• Положение клапанаValve_1.

  Модель системы управления представлена на рисунке 3.7.8

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

Настройки регуляторов взяты по умолчанию, все коэффициенты равны 1.

Модель позволяет переключаться между регуляторами с помощьюблокаключа.

Регулирующее воздействие передается c выбранного регулятора на модель привода. Это простой интегратор с ограничением диапазона0 - 100, который с заданной скоростью изменяет положения клапана, а результат предаётся в базу данных.

Для демонстрации работы П и ПД регуляторов используется один и тот же готовый блок ПИД регулятор. Тип регулятора задается в свойствах блока (см. рис. 3.7.9)

Для демонстрации режима управления в общем скрипте программы управления задается последовательное изменение требуемой температуры. (см. рис. 3.7.10)

В начальный момент времени заданная температура соответствует установившейся в системе температуре при 50% открытии клапана. На 10 секунде заданная температура меняется на 22 градуса С, на 50 секунде заданная температура меняется на 23.5 градусов С.

Чтобы можно было сравнить два варианта управления на одном графике, добавим еще один проект в пакет (файлdata.prt).

В данном файле расчетная схема содержит график, на котором выводятся текущее значение температуры (из базы данных сигналов) и значения из файла с предыдущим расчётом (temp_old.dat).

Во время расчёта мы сохраняем текущее значение в файл (temp_cur.dat). По завершению расчёта (секцияfinalizationскрипта) мы копируем данные из текущего файла в сохраненный ранее с помощью глобального скрипта программы. (см. рис. 3.7.11).

Результаты моделирования представлены на рисунке 3.7.12

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

Пример для самостоятельного изучения можно взять здесь.

Предыдущая лекция из главы 3, Частотные характеристики звеньев и систем автоматического регулирования: 3.6 Инерционно-дифференцирующее звено.

188. Гектора ж, в бегстве преследуя, гнал Ахиллес непрестанно.Словно как пёс по горам молодого гонит оленя.<>199. Словно во сне человек изловить человека не может,Сей убежать, а другой уловить напрягается тщетно, Так и герои, ни сей не догонит, ни тот не уходит.

Задача 1. Ахиллес и Смерть

В некоей альтернативной вселенной герою по имени Ахиллес предрекли, что жить ему осталось ровно m лет. Но мать Ахиллеса благодаря своему волшебству (она ж нимфа по легенде), продлевает ему жизнь таким образом, что каждые k (k > 1) лет продолжительность жизни увеличивается на 1 год. Сколько Ахиллес проживет в итоге, если считать, что увеличение происходит непрерывно?

Пусть x - это сколько осталось жить нашему герою. Ахиллес проживает первые m лет, но за эти годы получает лет прибавки к ПЖ. Он проживает эти лет, но за это время получает еще лет (прибавку разделить на k). И так далее, до бесконечности и можно подумать, что герой никогда не умрет. Но это не так: Смерть все таки догонит Ахиллеса, потому что все эти прибавки образуют бесконечную геометрическую прогрессию:

И тут стоит обратить внимание на условие: k > 1 из чего следует, что а это значит, что геометрическая прогрессия бесконечно убывающая. А бесконечно убывающая геометрическая прогрессия сходится к конечному значению:

Пусть у нас есть вот такая сумма:

И тут кому-то пришла в голову гениальная мысль: "а что если обе части равенства умножить на q?". Так чего же мы ждем! Умножаем:

А теперь вычтем из первого второе и получим красивую формулу для суммы:

Если q < 1, то при n стремящемся к бесконечности очевидно получаем:

Так как стремится к нулю

В период с 2000 по 2019 год ожидаемая продолжительность жизни голландских мужчин, например, увеличилась с 75.5 до 80.5 лет (то есть примерно на год каждые четыре года), что согласуется с данными по Европе в среднем. Таким образом, если человеку на текущий момент осталось жить 40 лет, а ожидаемая ПЖ увеличивается на год каждые четыре года, то имеем:

то есть мужчина-европеец в возрасте примерно 38 лет может прожить не 40 лет в среднем, а примерно на 13 лет дольше из-за прогресса в медицине (конечно, данные расчеты много чего не учитывают, нельзя их воспринимать как надежные предсказания).

А вот если k <= 1, то имеем уже бесконечность и это и есть та самая пресловутая longevity escape velocity о которой много говорит знаменитый борец со старением Обри Ди Грей. То есть Смерть никогда не догонит Ахиллеса.

А теперь давайте посмотрим насколько эта же задаче легче и логичнее решается при помощи дифференциальных уравнений:

dx - это насколько изменилось количество оставшихся лет до смерти за период dt. В отсутствии медицинского прогресса dx просто уменьшается на величину dt (логично, черт возьми). А прогресс добавляет определенное количество лет, такое что оно равно 1, если dt=k годам. Решается это уравнение тоже элементарно:

Совершенно очевидно, что x(0) = m, откуда C = m. А теперь подставим это в уравнение выше и выразим время t через которое Ахиллес помрет (x(t) = 0):

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

Пусть, например, k уменьшается по экспоненте с периодом полураспада в n лет. И давайте попробуем ответить на такой вопрос: какой должен быть минимальный m, чтобы человек мог достигнуть longevity escape velocity при таком k(t)?

Чтобы ответить на данный вопрос давайте составим дифференциальное уравнение:

Мы определили k(t) = k0*exp(-bt). Так как через n лет значение k(t) должно быть вдвое меньше, то имеем

откуда:

Интегрируем уравнение и получаем:

Чтобы определить C, воспользуемся начальным условием: x(0)=m:

Получаем следующую запись функции дожития:

Давайте взглянем на ее график:

Наша функция дожития имеет минимум и все, что нам нужно, это найти значение минимума как функции от m и найти значение m при котором этот минимум больше нуля. Как мы помним еще со школы, для того, чтобы найти минимум функции надо сначала найти ее производную и приравнять к нулю. Причем производную-то мы уже знаем из уравнения (1):

Мы точно знаем, что это минимум, потому что вторая производная положительна на всей области определения, а значит функция выпукла вниз и, следовательно, найденный экстремум является минимумом.

Теперь необходимо найти :

А отсюда уже выразим ограничение для m:

При и необходимо иметь в запасе примерно 9.2 года ожидаемой продолжительности жизни, чтобы достичь longevity escape velocity, то есть быть, например, мужчиной моложе 79 лет. Каждый может прикинуть свои шансы на достижение longevity escape velocity исходя из своего возраста. Но возможно ли в принципе бессмертие? Есть ли какие-то фундаментальные математические (не физические) ограничения? Об этом я расскажу в следующей статье, а пока давайте поговорим о более практических вещах.

Задача 2. Плазмаферез

Конечно, медицинская наука еще очень далека от достижения LEV (а может быть этого и вовсе никогда не случится), однако попытки отсрочить старение ведутся уже сейчас. Одной из самых интересных интервенций, возможно, способной немного продлить молодость и продолжительность жизни является терапевтическое разбавление плазмы. Известные геронтологи супруги Конбои продемонстрировали, что если мышкам заменить половину плазмы на физраствор с альбумином, то у них существенно улучшаются многие показатели жизнедеятельности. Предполагается, что это происходит за счет удаления из организма токсичных продуктов, которые образуются из-за старения организма. Более подробно все описано, например, тут. Более того, некоторые отчаянные биохакеры даже пробуют этот метод на себе и замечают улучшение ряда биомаркеров. Конечно, пройдет еще немало времени прежде чем установят эффективность (или неэффективность) этого метода на людях, но мы тем не менее постараемся ответить на вполне конкретный вопрос: а сколько раз нам необходимо сдать плазму, чтобы заменить половину, если за один раз забирается v мл?

Поскольку нам надо найти такой k при котором обновится половина плазмы, то приравняем правую часть уравнения выше к 1/2, прологарифмируем обе части равенства и воспользуемся свойствами логарифма, чтобы получить формулу для k:

Удельный объем плазмы взрослого мужчины составляет, в среднем, 46.7 мл/кг. Возьмем к примеру мужчину массой 80 кг и v=450 мл (стандартный объем плазмы при донорстве):

То есть взрослому сорокалетнему мужчине массой 80 кг необходимо за короткий срок 6 раз пожертвовать плазму, чтобы ее обновить чуть более чем наполовину.

Пусть X(t) - доля старой плазмы в момент времени t. Пусть скорость вытекания плазмы равна r мл/мин. Чему же будет равна концентрация старой плазмы в момент времени t + dt? А концентрация равна:

Давайте разберем каждое составляющее этого равенства:

X(t)V: концентрация старой плазмы помноженная на общий объем - очевидно это объем старой плазмы во всем организме в момент t

X(t)rdt: это объем старой плазмы, который вытечет за время dt (rdt - это скорость истечения, помноженная на время, что соответствует объему, а X(t) - это доля старой плазмы в этом объеме).

Затем мы делим получившийся объем старой плазмы на общий объем (который остается неизменным, потому что физраствор втекает с той же скоростью) и получим концентрацию. А теперь узнаем чему равно изменение концентрации (разница между концентрацией в моменты времени t+dt и t):

Разделяем переменные и решаем это дифференциальное уравнение:

Отсюда:

Мы знаем, что вначале концентрация старой плазмы равнялась 1:
X(0) = 1 => C = 1

Поэтому , а теперь найдем время, за которое обновится половина плазмы:

На практике это означает примерно 259 минут (4 с лишним часа!), если руководствоваться средней скоростью 10 мл/мин (обычно забирают 450 мл плазмы и уходит на это примерно 45 минут):

Конечно, это время абсолютно неприемлемо, однако процедуру можно существенно ускорить. Например, в этой статье описан метод, который позволяет изымать плазму со скоростью 24 мл/мин, что позволяет заменить половину плазмы за 108 минут. Весьма неплохо! Однако неизвестно выдержит ли организм замену половины плазмы за один раз :) Но это уже выходит за рамки математики, оставим этот вопрос врачам. Тем более, что различные клинические исследования по влиянию плазмафереза на старение людей уже начались.

Наша [Ирвинга Капланского и Пола Халмоша] общая философия в отношении линейной алгебры такова: мы думаем в безбазисных терминах, пишем в безбазисных терминах, но когда доходит до серьезного дела, мы запираемся в офисе и вовсю считаем с помощью матриц.

Ирвинг Капланский

Для многих начинающих исследователей данных линейная алгебра становится камнем преткновения на пути к достижению мастерства в выбранной ими профессии.

В этой статье я попытался собрать основы линейной алгебры, необходимые в повседневной работе специалистам по машинному обучению и анализу данных.

Произведения векторов

Для двух векторов x, y их скалярным или внутренним произведением xy

называется следующее вещественное число:

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

.

Для двух векторов x , y (не обязательно одной размерности) также можно определить внешнее произведение xy . Это матрица, значения элементов которой определяются следующим образом: (xy) = xy, то есть

След

Следом квадратной матрицы A , обозначаемым tr(A) (или просто trA), называют сумму элементов на ее главной диагонали:

След обладает следующими свойствами:

• Для любой матрицы A : trA = trA.

• Для любых матриц A,B : tr(A + B) = trA + trB.

• Для любой матрицы A и любого числа t : tr(tA) = t trA.

• Для любых матриц A,B, таких, что их произведение AB является квадратной матрицей: trAB = trBA.

• Для любых матриц A,B,C, таких, что их произведение ABC является квадратной матрицей: trABC = trBCA = trCAB (и так далее данное свойство справедливо для любого числа матриц).

Нормы

Норму x вектора x можно неформально определить как меру длины вектора. Например, часто используется евклидова норма, или норма l:

Заметим, что x=xx.

Более формальное определение таково: нормой называется любая функция f : n , удовлетворяющая четырем условиям:

1. Для всех векторов x : f(x) 0 (неотрицательность).

2. f(x) = 0 тогда и только тогда, когда x = 0 (положительная определенность).

3. Для любых вектора x и числа t : f(tx) = |t|f(x) (однородность).

4. Для любых векторов x, y : f(x + y) f(x) + f(y) (неравенство треугольника)

Другими примерами норм являются норма l

и норма l

Все три представленные выше нормы являются примерами норм семейства lp, параметризуемых вещественным числом p 1 и определяемых как

Нормы также могут быть определены для матриц, например норма Фробениуса:

Линейная независимость и ранг

Множество векторов {x,x,...,x} называют линейно независимым, если никакой из этих векторов не может быть представлен в виде линейной комбинации других векторов этого множества. Если же такое представление какого-либо из векторов множества возможно, эти векторы называют линейно зависимыми. То есть, если выполняется равенство

для некоторых скалярных значений ,, - , то мы говорим, что векторы x,...,x линейно зависимы; в противном случае они линейно независимы. Например, векторы

линейно зависимы, так как x = 2x + x.

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

Оказывается (здесь мы не будем это доказывать), что для любой матрицы A столбцовый ранг равен строчному, поэтому оба этих числа называют просто рангом A и обозначают rank(A) или rk(A); встречаются также обозначения rang(A), rg(A) и просто r(A). Вот некоторые основные свойства ранга:

• Для любой матрицы A : rank(A) min(m,n). Если rank(A) = min(m,n), то A называют матрицей полного ранга.

• Для любой матрицы A : rank(A) = rank(A).

• Для любых матриц A , B np: rank(AB) min(rank(A),rank(B)).

• Для любых матриц A,B : rank(A + B) rank(A) + rank(B).

Ортогональные матрицы

Два вектора x, y называются ортогональными, если xy = 0. Вектор x называется нормированным, если ||x|| = 1. Квадратная м

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

Непосредственно из определений ортогональности и нормированности следует, что

Другими словами, результатом транспонирования ортогональной матрицы является матрица, обратная исходной. Заметим, что если U не является квадратной матрицей (U , n < m), но ее столбцы являются ортонормированными, то UU = I, но UU I. Поэтому, говоря об ортогональных матрицах, мы будем по умолчанию подразумевать квадратные матрицы.

Еще одно удобное свойство ортогональных матриц состоит в том, что умножение вектора на ортогональную матрицу не меняет его евклидову норму, то есть

для любых вектора x и ортогональной матрицы U .

Область значений и нуль-пространство матрицы

Линейной оболочкой множества векторов {x,x,...,x} является множество всех векторов, которые могут быть представлены в виде линейной комбинации векторов {x,...,x}, то есть

Областью значений R(A) (или пространством столбцов) матрицы A называется линейная оболочка ее столбцов. Другими словами,

Нуль-пространством, или ядром матрицы A (обозначаемым N(A) или ker A), называют множество всех векторов, которые при умножении на A обращаются в нуль, то есть

Квадратичные формы и положительно полуопределенные матрицы

Для квадратной матрицы A и вектора x квадратичной формой называется скалярное значение x Ax. Распишем это выражение подробно:

Заметим, что

• Симметричная матрица A называется положительно определенной, если для всех ненулевых векторов x справедливо неравенство xAx > 0. Обычно это обозначается как

  

  (или просто A > 0), а множество всех положительно определенных матриц часто обозначают

  

  .

• Симметричная матрица A называется положительно полуопределенной, если для всех векторов справедливо неравенство x Ax 0. Это записывается как

  

  (или просто A 0), а множество всех положительно полуопределенных матриц часто обозначают

  

  .

• Аналогично симметричная матрица A называется отрицательно определенной

  

• , если для всех ненулевых векторов x справедливо неравенство xAx < 0.

• Далее, симметричная матрица A называется отрицательно полуопределенной (

  

  ), если для всех ненулевых векторов x справедливо неравенство xAx 0.

• Наконец, симметричная матрица A называется неопределенной, если она не является ни положительно полуопределенной, ни отрицательно полуопределенной, то есть если существуют векторы x, x такие, что

  

  и

  

  .

Собственные значения и собственные векторы

Для квадратной матрицы A комплексное значение и вектор x будут соответственно являться собственным значением и собственным вектором, если выполняется равенство

На интуитивном уровне это определение означает, что при умножении на матрицу A вектор x сохраняет направление, но масштабируется с коэффициентом . Заметим, что для любого собственного вектора x и скалярного значения с справедливо равенство A(cx) = cAx = cx = (cx). Таким образом, cx тоже является собственным вектором. Поэтому, говоря о собственном векторе, соответствующем собственному значению , мы обычно имеем в виду нормализованный вектор с длиной 1 (при таком определении все равно сохраняется некоторая неоднозначность, так как собственными векторами будут как x, так и x, но тут уж ничего не поделаешь).

Перевод статьи был подготовлен в преддверии старта курса "Математика для Data Science". Также приглашаем всех желающих посетить бесплатный демоурок, в рамках которого рассмотрим понятие линейного пространства на примерах, поговорим о линейных отображениях, их роли в анализе данных и порешаем задачи.

• ЗАПИСАТЬСЯ НА ДЕМОУРОК

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

Как входная последовательность попадает в модуль внимания

Модуль внимания присутствует в каждом энкодере внутри стека каждого энкодера, а также внутри стека каждого декодера. Сначала внимательно посмотрим на энкодер.

Для примера предположим, что мы работаем над задачей перевода с английского на испанский, где исходная последовательность слов The ball is blue, а целевая последовательность La bola es azul.

Исходная последовательность сначала проходит через слой векторного представления и позиционного кодирования, генерирующего векторы векторного представления для каждого слова последовательности. Векторное представление передаётся в энкодер, где вначале попадает в модуль внимания.

Внутри модуля внимания последовательность векторного представления проходит через три линейных слоя, создающих три отдельные матрицы запроса (Query), ключа (Key) и значения (Value). Именно эти три матрицы используются для вычисления оценки внимания [прим. перев. оценка определяет, сколько внимания нужно уделить другим частям входного предложения, когда мы кодируем слово в определённой позиции]. Важно помнить, что каждая "строка" этих матриц соответствует одному слову исходной последовательности.

Каждая входная строка это слово из последовательности

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

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

Каждое слово проходит серию обучаемых преобразований (трансформаций)

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

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

Оценка внимания это скалярное произведение матрицы ключа и матрицы запроса слов

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

Как видно из формулы, первый шаг в рамках модуля внимания умножение матрицы, то есть скалярное произведение между матрицей Query (Q) и транспонированием матрицы ключа Key (K). Посмотрите, что происходит с каждым словом. Итог промежуточная матрица (назовём её факторной матрицей [матрицей множителей]), где каждая ячейка это результат матричного умножения двух слов.

Например, каждый столбец в четвёртой строке соответствует скалярному произведению между четвёртым словом запроса и каждым ключевым словом.

Оценка внимания скалярное произведение между запросом-ключом и значением слов

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

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

Какова роль слов запроса, ключа и значения?

Слово запроса это слово, для которого мы рассчитываем внимание. В свою очередь слово ключа и значения это слово, на которое мы обращаем внимание, то есть определяем, насколько это слово соответствует слову запроса.

Например, для предложения The ball is blue строка для слова blue будет содержать оценку внимания для слова blue с каждым вторым словом. Здесь blue это слово запроса, а другие слова ключ/значение. Выполняются и другие операции, такие как деление и softmax, но мы можем проигнорировать их в этой статье. Они просто изменяют числовые значения в матрицах, но не влияют на положение каждой строки слов в ней. Они также не предполагают никаких взаимодействий между словами.

Скалярное произведение сообщает нам о сходстве слов

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

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

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

• Если два парных числа (например, a и d выше) оба положительны или оба отрицательны, произведение положительно. Произведение увеличит итоговую сумму.

• Если одно число положительное, а другое отрицательное, произведение будет отрицательным. Произведение уменьшит итоговую сумму.

• Если произведение положительное, то, чем больше два числа, тем больше их вклад в окончательную сумму.

Это означает, что, если знаки соответствующих чисел в двух векторах выровнены, итоговая сумма будет больше.

Как трансформер изучает релевантность между словами?

Скалярное произведение также применимо к оценке внимания. Если векторы для двух слов более выровнены, оценка внимания будет выше. Итак, какого поведения мы хотим от трансформера? Мы хотим, чтобы оценка внимания была высокой для двух релевантных друг другу слов в предложении. И мы хотим, чтобы оценка двух слов, не связанных друг с другом, была низкой.

Например, в предложении The black cat drank the milk слово milk очень релевантно к drank, возможно, немного менее релевантно для cat, и нерелевантно к black. Мы хотим, чтобы milk и drink давали высокую оценку внимания, чтобы milk и cat давали немного более низкую оценку, а для milk и black незначительную. Мы хотим, чтобы модель научилась воспроизводить этот результат. Чтобы достичь воспроизводимости, векторы слов milk и drank должны быть выровнены. Векторы milk и cat несколько разойдутся. А для milk и black они будут совершенно разными.

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

Другими словами, он будет изучать эти векторные представления и веса таким образом, что если два слова в предложении релевантны друг другу, то их векторы слов будут выровнены, следовательно, получат более высокe. оценку внимания. Для слов, которые не имеют отношения друг к другу, их векторы не будут выровнены и оценка внимания будет ниже.

Следовательно, векторные представления слов milk и drank будут очень согласованными и обеспечат высокую оценку внимания. Они будут несколько отличаться для milk и cat, производить немного более низкую оценку и будут совершенно разными в случае milk и black: оценка внимания будет низкой вот лежащий в основе модуля внимания принцип.

Итак, как же работает трансформер?

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

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

Самовнимание энкодера в трансформере

Внимание используется в трансформере в трёх местах:

• Самовнимание в энкодере исходная последовательность обращает внимание на себя.

• Самовнимание в декодере целевая последовательность обращает внимание на себя.

• Энкодер-декодер-внимание в декодере целевая последовательность обращает внимание на исходную последовательность.

В самовнимании энкодера мы вычисляем релевантность каждого слова в исходном предложении каждому другому слову в исходном предложении. Это происходит во всех энкодерах стека.

Декодер самовнимания в трансформере

Большая часть того, что мы только что видели в энкодере самовнимания, применима и к вниманию в декодере, но с некоторыми существенными отличиями.

В декодере самовнимания мы вычисляем релевантность каждого слова в целевом предложении каждому другому слову в целевом предложении.

Энкодер-декодер модуля внимания в трансформере

В энкодере-декодере запрос получается из целевого предложения, а ключ/значение из исходного предложения. Таким образом, он вычисляет релевантность каждого слова в целевом предложении каждому слову в исходном предложении.

Заключение

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

Здесь мы видим, что за сложными идеями скрываются простые решения. Более того, есть ощутимая вероятность того, что вскоре понимание внутренних механизмов глубокого обучения станет второй грамотностью, как сегодня второй грамотностью стало знание ПК в целом и если вы хотите углубиться в область глубокого и машинного обучения, получить полное представление о современном ИИ, вы можете присмотреться к нашему курсу Machine Learning иDeep Learning, партнёром которого является компания NVIDIA.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering