математическая проблемка

[stas]

Имеется некая переменная x - время завершения некоего процесса. Для процесса возможно "успешное" завершение, которое примерно занимает одно и то же время, но может варьироваться в некоторых пределах. Возможно также "ненормальное" завершение, при котором время или очень мало, или очень велико. Задача - по истории запусков этого процесса научиться отличать "успешные" времена от "ненормальных" - предполагая, что "ненормальные" очень редки. Тут вопрос - можно ли предположить, что распределение x - нормальное? Особая точность не нужна, главное, чтобы улавливались серьёзные отклонения от "обычного" поведения.

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

Comments

[ex-ilyavinar899.livejournal.com]

Если успешное завершение занимает от 1ms до 5ms, а неуспешное <100µs или >50ms - то очевидно, их можно отличить. Если же границы более размазаны, то ясно дело, отличить нельзя.

[stas]

Ну, это-то понятно. Проблема в том, что неизвестно, сколько в общем случае занимает и то, и другое - предполагается лишь, что они "сильно" отличаются (определение "сильно" в принципе можно варьировать). Лучшее, что я пока придумал - это предположить, что x - распределён нормально, найти его mean M и standard deviation S, и всё, что вне (M-3S, M+3S), обьявлять ненормальным. Для первого случая это может быть неплохой идеей, для второго - явно нет.
Однако задача-то такая не только у меня бывает. Явно придумали какие-то методы, как её решать.

[ex-ilyavinar899.livejournal.com]

Кроме длительности исполнения есть какие-то ещё данные об исполнениях? Одномерную задачу классификации решать несравненно труднее, чем двух-, трёх- и т. п. -мерную.

[stas]

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

[ex-ilyavinar899.livejournal.com]

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

Почитай про алгоритм EM.

[stas]

То есть вести статистику не только по успехам, но и по неудачам? Это интересная идея, да. Спасибо, обдумаю :)

[meshulash.livejournal.com]

Ах ты, враг нехороший! Я-то думал, ты по неудачам тоже статистику ведешь. Иначе - откуда ты знаешь, какие времена у неудач?

[stas]

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

[meshulash.livejournal.com]

В первом случае - распределение, вне всякого сомнения, нормальное.

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

[stas]

Считается, что времена отличаются (это, в общем-то, определение их различия для данного примера). Проблема, однако, в том, что может быть, скажем, одно успешное завершение со временем 1, а другое - со временем 100. Если их считать по формуле первого случая - то, фактически, все времена от 0 до 300 будут OK, даже если отклонение обоих результатов не превышает, скажем, 0.01 - хотелось бы, чтобы точность проверки была побольше. Хотя не уверен, что это как-то действительно можно выяснить, не имея дополнительных данных.

[mz1313.livejournal.com]

Пмсм, можно верхнюю границу отсчитывать от максимально возможного измерения, а нижнюю от минимально возможного. Я так понимаю, что каждое измерение не абсолютно, а охватывает некую небольшую область (скажем, одно от 99.8 до 100.2, другое от 0.98 до 1.02)? Тогда можно считать каждое отдельное измерение нормально распределенным и воспользоваться твоей формулой для случая одного варианта.

[meshulash.livejournal.com]

Я имею ввиду следующее. Пусть времена успешных завершений лежат в интервале 1-100, а времена неуспешных - в интервале 0-20. Это примерно так?

[stas]

Скорее, времена неуспешных могут быть в интервалах 0-1, 20-50 и 200-inf. Конечно, можно вообще отказаться от ловли в интервале 1-100, и смириться с тем, что выше 100 будет ловиться только от 300 и выше. Но хочется всё-таки быть уверенным, что я ничего не пропустил :)

[meshulash.livejournal.com]

Тогда, вероятно, имеет смысл совместить разбиение на интервалы и статистику по неудачам. Т.е. считать, что неудачи распределены в интервалах 0-1 и 20-50 нормально, а в интервале 200-inf - по Пуассону (или нормально, если все же не inf). И все, что не неудача полагать удачей.

Mozhno ukorotit' k etomu delu diskriminantnyj analiz.

[d-ohrenelli.livejournal.com]

Iskat' oblaka tochek (ili oblasti tochek) blizkie drug k drugu po udacham i neudacham i po rasstojanijam ot centra opredeljat'.
Esli faktor ne odin a 2 ( i oni ne zavsimy linejno )
budet eshe luchshe - a esli bol'she - eshe luchshe.
Esli dannye nechislovye algoritm ocifrovki mozhno pogljadet' v trehtomnike Ajvazjana.

D_Ohrenelli , s uvazheniem.

[diam.livejournal.com]

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

а вообще, если речь о конкретном наборе данных (log-файлы;)?), то надо нарисовать распределение и методом матеметического тыка все решить. :)

[meshko.livejournal.com]

bayesian network конечно! (ну не извращенец ли я?)
Хотя может ведь сработать. Есть довольно много библиотек, и, скорее всего, их как раз для такой цели можно легко прикрутить. И, если это правда сработает, оно ведь может и потом работать, когда задача изменится (сместятся какие-нибудь интервалы и т.д.).

[meshulash.livejournal.com]

"bayesian network конечно!"
П..ц котенку :)

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

[stas]

хехе :))

[krimsky.livejournal.com]

Была. Была такая фишка. :-)
В некотором царстве, в некотором государстве брал я такой курс под названием "Шитот нитур". Целый раздел в статистике, занимающийся именно описанной тобой проблемой в классическом варианте (без добавленного усложнения со случайными вариантами). Существует 5-6 основных подходов к решению этой проблемы, ни один из которых я в двух словах тебе объяснить не в состоянии по многим причинам (терминология, необходим опредённый уровень подготовки, да и я сам боюсь тебе напутать). Однако мне удалось откопать совершенно случайно сохранившийся силибус с курса со списком научных работ, поверхностно ознакомившись, с которыми ты сможешь лучше изучить тему и вытащить оттуда общепринятые способы решения таких задач.
Список книг и 19-ти публикаций, разбитых на подтемы (включая случаи, когда не предполагается определённое распределение), могу выслать те по факсу, еси очень надо. Ну и ва-апще... :-)

[heiheneikko.livejournal.com]

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

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

(муж)