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

[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]

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