Методы наименьших квадратов и наименьших модулей; нормальное распределение

К началу 19 века количество астрономических постов, проводящих измерения координат астрономических объектов увеличилось до полутора десятков – возникла надобность в сведении их данных воедино. Быстро выявились систематические ошибки отдельных наблюдателей, например, один был крив на один глаз и всегда выдавал левое смещение, которое было нетрудно учесть. Однако, даже и в скорректированном виде, измерения разнились, и возникла проблема согласования различных измерений одной и той же величины. Эта проблема была сформулирована следующим образом.

 

При данных М значениях х1, х2,…, хМ, найти значение а, удовлетворяющее уравнениям хм = а + ем, так чтобы минимизировать аддитивные ошибки ем. В данной – многокритериаль-ной – формулировке задача не имеет единственного решения. Возникло два подхода к скаляризации критериев. Один, принцип наименьших модулей, представлял Пьер Лаплас (1749-1827): надо минимизировать сумму абсолютных величин |е1|+|е2|+…+|еМ|. Второй, принцип наименьших квадратов, представлял Карл Гаусс (1777-1855) – надо минимизировать сумму квадратов ошибок, |е1|²+|е2|²+…+|еМ|². Решением по первому критерию является медиана – то значение из величин хм, которое стоит в середине отсортированного по величине ряда значений. Решением по второму критерию является арифметическое среднее, m =(е1+е2+…+еМ)/М. Оба хороши, медиана обладает теми преимуществами, что является одним из наблюденных значений и, кроме того, не зависит от крайних значений, которым, значит, позволительны любые сколь большие уклонения без какого-либо воздействия на медиану. Напротив, среднее, как правило, не совпадает ни с одним из наблюдений и, более того, неустойчиво относительно изменений в крайних значениях. См., например, ряд значений 1, 5, 1, 5, 3, который после сортировки становится 1, 1, 3, 5, 5, так что медиана равна 3. Среднее этого ряда тоже 3. Если второе значение 5 сильно увеличилось, скажем, до 15, так что сортированный ряд становится 1, 1, 3, 5, 15, то медиана все еще 3, а среднее увеличивается до 5.

Однако, Гаусс предложил теорию для своего критерия, которая оказалась настолько убедительной, что впоследствии легла в основание всего здания математической статистики, где и сейчас занимает центральное место. В основе теории Гаусса – два факта:

 

(1) Мелкие случайные ошибки, складываясь, приводят к тому, что распределение среднего значения наблюденных величин, в стандартных предположениях независимости и случайности наблюдений, является асимптотически Гауссовым, или нормальным, распределением с плотностью вероятности f(x, m, s)=Cexp{((x – m)/s)²}, где параметры  m и s - математическое ожидание и стандартное отклонение, соответственно.

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

 

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

 

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

Основные выводы:

(1) Измерения, даже интуитивно очевидных величин, при переходе к большим системам требуют разработки неочевидных теорий и сопряжены с ошибками;

(2) Обоснованием введения ненаблюдаемых величин является возможность объяснения поведения некоторых наблюдаемых величин;

(3) Различные эквивалентные формулировки могут оказаться полезными для различных приложений – сам факт наличия нескольких переформулировок может рассматриваться как эвристическое подтверждение осмысленности соответствующих утверждений;

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

 

Развитие оптимизации

       4.1 Точные методы – история и проблемы машинных вычислений.

       4.2 Локальные методы и эвристики – проблемы инициализации.

4.3 Нейронные сети для поиска по градиенту.

       4.4 Подход имитации природы – эволюция популяции: методы генетические, эволюционные, пчелиного роя и муравьиной кучи.

       4.1 Точные методы – история и проблемы машинных вычислений.

Оптимизация – один из самых распространенных принципов в инженерном подходе к природе (принцип наименьшего действия Мопертьюи 1746, химическое равновесие – минимум энергии Гиббс 1857), технике и обществу (Вальрас и Курно – модели, основанные на оптимизации полезности).

Систематический подход – после изобретения дифференциального исчисления на основе уточнения и обобщения свойства обнуления градиента в экстремальной точке (установленного еще Ферма 1646). Работа Лагранжа (1754) устанавливает метод множителей Лагранжа для оптимизации с ограничениями, продолженный в 20 столетии установлением теоремы Куна-Таккера (1951). Градиентный метод изобретен Коши (1847)

Вариационное исчисление Эйлера 1707-1783 (оптимальные функции), увенчавшееся в 20 веке теорией оптимального управления Л.С. Понтрягина (1957). Линейное программирова-ние и теория игр (Л.В. Канторович 1939, Дж. Фон Нейман 1948 и Дж. Данциг 1950).

 

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

 

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

Б. Ограниченная память – невозможность держать в памяти большие массивы; преодолевается тем же путем – см. Европейскую концепцию Грид – чтобы компьютерная ресурсы были доступны так же, как вода в водопроводе.

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

       4.2 Локальные методы  и эвристики – проблемы инициализации.

Типичный локальный метод оптимизации функции f(x) по x ÎX, работает следующим итеративным образом:

       Для каждого x ÎX определи его окрестность, О(x)ÌX, таким образом, чтобы она содержала относительно небольшое число элементов (например, если x – подмножество заданного множества А, то О(x) может состоять из всех подмножеств, отличающихся от x только одним элементом и принадлежашим X).

       0. Возьми начальное допустимое решение x₀ ÎX и рассмотри О(x₀).

       1. Перебери все x ÎО(x₀) и выбери из них оптимальное, x₁.

       2. Если x₁ лучше, чем x₀, то переопредели x₀ – сделай его равным x₁, и вернись к шагу 1; в противном случае выдай x₁ и f (x₁) в качестве окончательного решения.

 

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