2011 Борис Григорьевич Миркин Профессор, Кафедра анализа данных и искусственного интеллекта опми ниу вшэ, Москва, РФ (стр. 6 из 13)
А. Последовательный, не параллельный, характер вычислений – слишком большие вычисления невозможны по ресурсам времени и среды (например, перебор всех подмножеств миллион-элементного множества, что породило забавную дисциплину теории не полиномиальных задач, таких как задача нахождения общего метода для отыскания всех нулей произвольной булевой функции большого числа переменных (для монотонных функций – задача полиномиальная, применялась академиком О.И. Ларичевым в алгоритмах принятия решений)) – в настоящий момент появились первые архитектуры, так называемые кластеры, с большим количеством определенным образом соединенных машин, на которых можно вести параллельные вычисления;
Б. Ограниченная память – невозможность держать в памяти большие массивы; преодолевается тем же путем – см. Европейскую концепцию Грид – чтобы компьютерная ресурсы были доступны так же, как вода в водопроводе.
В. Фиксированная разрядная сетка для представления чисел – неадекватность, например, отсутствие гарантии сходимости сходящихся рядов. Накладывает требование более глубокой проработки методов, например, для изучения числа обусловленности при обращении матриц (точная задача в условном мире арифметики вещественных чисел).
4.2 Локальные методы и эвристики – проблемы инициализации.
Типичный локальный метод оптимизации функции f(x) по x ÎX, работает следующим итеративным образом:
Для каждого x ÎX определи его окрестность, О(x)ÌX, таким образом, чтобы она содержала относительно небольшое число элементов (например, если x – подмножество заданного множества А, то О(x) может состоять из всех подмножеств, отличающихся от x только одним элементом и принадлежашим X).
0. Возьми начальное допустимое решение x0 ÎX и рассмотри О(x0).
1. Перебери все x ÎО(x0) и выбери из них оптимальное, x1.
2. Если x1 лучше, чем x0, то переопредели x0 – сделай его равным x1, и вернись к шагу 1; в противном случае выдай x1 и f (x1) в качестве окончательного решения.
Работает быстро, да вот решение может быть далеко от оптимального. Возникло направление по выведению оценок близости локальных решений к оптимуму, пока, увы, только по функционалу. На мой взгляд, более перспективно направление отыскания «хороших» инициализаций.
4.3 Нейронные сети для поиска по градиенту.
Нейрон (искусственный) это преобразование входных сигналов в выходной сигнал с помощью их суммирования с весами; выход появляется когда сумма выше порога:
 |
 |
Figure 2. A scheme of artificial neuron, on the left. The same neuron with the firing threshold shown as a wiring weight on the fictitious input always equal to 1, on the right.
Возможность аппроксимировать сложную функцию «квазилинейными» функциями, а для поиска решения использовать локальный метод с выбором не лучшего решения в окресности, а лучшего направления движения. Оказалось, градиентный метод в этой ситуации можно представить как метод взаимодействия между нейронами, составляюшими сеть, при которой каждый нейрон оперирует только с поступающей с предыдущих уровней информацией об ошибке и своими собственными передаточными возможностями, ничего не зная о структуре соседей.
Богатые структурные возможности обеспечившие небывалую популярность в 90-е; но – ограничения: невозможность разумной интерпретации (не в нейрофизике, где, впрочем пока этот аппарат не смог помочь в имитации нейроритмов) и локальность получаемого решения.
4.4 Подход имитации природы – эволюция популяции: методы генетические,
эволюционные, пчелиного роя и муравьиной кучи (genetic algorithms, evolutionary algorithms, particle swarm optimization and ant colony optimization).
Во всех этих методах главное то, что моделируется эволюция популяции решений, тогда как в классической оптимизации речь идет только об одном решении и его последовательном улучшении. Это – основа современного развития вычислительного интеллекта. Здесь всё еще только начинается.
Генетические алгоритмы – представляют возможные решения последовательностями – «хромосомами», которые от итерации к итерации «скрещиваются», подвергаются «кроссинговеру» и «мутируют». При этом лучшие решения запоминаются и определенным образом используются. После определенного числа итераций (поколений) наилучшее достигнутое решение выдается в качестве результата.
Эволюционные алгоритмы – так же осуществляют переход от поколения к поколению, но без использования «хромосом». Решения здесь обычно представляют, как обычно, через числовые значения, векторы и матрицы, а мутации и скрещивания заменяют изменениями в случайных направлениях.
Оптимизация роя частиц – еще дальше отходит от генетической интерпретации. Здесь популяция – это частиц рой, движущихся в случайном направлении со случайными скоростями, модифицируемыми в направлении достигнутых наилучших решений. На удивление, подобные методы довольно легко «раскалывают» задачи оптимизации сложных нелинейных функций с нелинейными же ограничениями.
В применении же к большим данным обнаруживается общий недостаток методов, инспирированных природой – долгое время вычислений.
5. Некоторые идеи вероятности и статистики.
В настоящее время, когда многие математики подходят к статистике как части теории вероятностей, трудно представить, что в начале статистика не имела ничего общего с вероятностью, хотя обе возникли в государствах Северной Италии в период зарождения капитализма, 17 век. Статистика – от слова «стата» (государство) – для отражения показателей народного хозяйства и населения, теория вероятности из потребности анализа карточных игр – карточная игра там была тогда средой для формирования отношений и заключения договоров. Можно сказать, что теория вероятностей зародилась в переписке П.Ферма (1601-1665) и Б. Паскаля (1623-1662).
Вероятность - это мера случайности. Что такое случайность? Вот четыре довольно разных подхода:
(а) Выбор из хорошо перемешанной колоды – классический взгляд. Вера в существование механизма, устойчиво перемешивающего колоду.
(б) Вероятность события сопряжена с частотой его появления в «вероятностном эксперименте» (по сути – та же хорошо перемешанная колода).
(в) Степень нашей уверенности в появлении события – это понимание отсеялось недавно в так называемые нечеткие множества.
(г) Подход А.Н. Колмогорова: случайность это отсутствие закономерности; тогда степень случайности данной последовательности – сложность или даже длина программы, ее порождающей. Этот взгляд объединяет случайность со сложностью и информативностью. Он связан с развитием вычислительной техники и необходимостью разработки алгоритмов для генерации «случайных» - математики говорят, псевдослучайных – чисел.
Первоначально статистика не имела ничего общего с вероятностью; она развивалась - сначала в Англии как политическая арифметика (родоначальник – Уильям Петти (1623-1687))– для демографических и народнохозяйственных оценок. Связь с вероятностью, равно как и обоснование идеологии статистического вывода, а также и практики статистического наблюдения – в трудах одного из основателей статистики как науки, включая переписи населения – бельгийца Адольфа Кетле (1796-1874) при исследовании частот различных социальных явлений таких как самоубийство. Серьезную роль сыграли российские ученые П.Л. Чебышев (1821-1894), А.А. Марков (1856-1922), А.И. Чупров (1842-1908), А.М. Ляпунов (1857-1918) и А.Н. Колмогоров (1903-1987).
5.1 Вероятностная статистическая модель как средство анализа данных.
Рассмотрим множество N наблюденных значений какого-либо показателя X={x1,…,xN}. Хотя рассматривается одномерная характеристика, все дальнейшее верно и для многомерных наблюдений.
Вероятностник будет считать, что эти числа – независимая случайная выборка из распределения с плотностью f(u/a), где a – параметры распределения, как например, в случае нормального распределения
f(u/(m, s))= Cexp{-(u - m)2 / 2s2},
где a=(m, s) - математическое ожидание и дисперсия.
Вероятностный статистик будет склонен рассматривать математическую модель наблюдений, например, в форме уравнения
xi = a + ei, для всех i=1,2,…, N
где ei - аддитивные ошибки, подчиняющиеся определенному закону распределения.
И в том, и в другом случае данные используются для оценки параметров соответствующих моделей. Основные проблемы – насколько точно оценены параметры? Как сделать оценки поточнее? Нельзя ли уменьшить зависимость от вида функции распределения? Как убедиться, что распределения соответствуют предположениям?
5.2 Смысл коэффициента корреляции.
Рассмотрим множество N наблюденных пар значений показателей (x,y)={(x1, y1), …,(xN, yN)}. Вопрос – можно ли что-нибудь сказать о связи y с x? На этот вопрос Ф. Галтон – а его интересовала связь способностей родителей и их детей, - предложил свою теорию регрессионного анализа (1896), смысл которой состоял в том, что надо построить линейную зависимость y=ax+b с оценкой постоянных коэффициентов a и b исходя из идеи минимизации суммарной квадратичной погрешности оцененных через х значений y с наблюденными. Согласно этой теории, характеристикой связи x и y является коэффициент корреляции
r = [Si (xi – mx)(yi-my)] ⁄[Ns(x) s(y)]
А именно, оптимальные значения коэффициентов регрессионного уравнения определяются формулами
a = r s(y) /s(x)
b = my –a*mx
где mx, my – средние значения, а s(y), s(x) – среднеквадратичные (стандартные) отклонения переменных величин xi и yi, соответственно. При этом минимальное значение суммы квадратов погрешностей в значениях yi , получаемых если принять линейную зависимость yi = axi+b, равно