VC dimension
Sep. 30th, 2014 12:03 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ile_eliПамяти Червоненкиса
Machine learning (по-нашему למידת מכונה, не знаю как по-русски) - это то, что осталось (по моим наблюдениям) от красивого слова "искусственный интеллект". Как научить машину делать что-то очень умное, что только специалист умеет (в более интересных случаях - то, чего и специалист не умеет).
Самая старая задача machine learning - обучение по размеченным примерам (тоже как-то не очень по-русски).
Пример: допустим, по анализу крови можно как-то узнать, болен человек некоторой болезнью или нет. Анализ крови - это, скажем, 10 чисел (показатели 10 заранее заданных параметров). Можно попробовать допросить врача, как он по этим параметрам что-то определяет. В лучшем случае, сможем написать программу, которая делает то же, что врач, в более реальном случае - не выйдет. Врач, глядя на анализ может вспомнить, что 10 лет назад видел что-то подобное, и тогда оказалось... - а вот рассказать заранее все, что он может вспомнить - вряд ли получится. Подход machine learning такой:
Представим каждый анализ как точку в 10-мерном пространстве (если бы параметров было всего 2, это была бы точка на плоскости: по одной оси откладываем значение первого параметра, по другой - второго). Допустим (абсолютно реальное предположение), есть база данных с миллионом анализов больных людей и миллионом - здоровых. Отметим точки, соответствующие больным красным цветом, здоровым - синим. Утверждение о том, что по анализу крови можно узнать, болен человек или нет эквивалентно тому, что существует в нашем 10-мерном пространстве (а если бы параметров было 2 - в плоскости) поверхность (линия), отделяющая все возможные красные точки от всех синих. Как только мы найдем такую поверхность (линию), компьютер сможет узнать, находится ли какая-то новая точка в красной области или в синей. Вполне вероятно, что результат будет гораздо лучше, чем у самого лучшего врача: он же не помнит миллион случаев, а поверхность наша их все учитывает.
Проблема в том, что провести такую поверхность очень сложно: у нас же есть не все возможные красные и синие точки, а только миллион, как же мы можем быть уверены, что она и остальные отделяет правильно?
Если мы ограничиваемся только очень простыми поверхностями (например, показатель номер 3 больше 18), то только в очень простых случаях сможем отделить все известные красные точки от синих. Если мы берем сколь угодно сложные поверхности, то отделить известные красные точки от известных синих очень просто, но абсолютно бессмысленно. Пример: обводим все известные красные точки маленьким кружочком (10-мерным, если параметров 10, обычным - если их 2), говорим, что все, что внутри кружочков - красное, все остальное - синее. На размеченных точках мы ни разу не ошибемся, но когда появится новая точка, мы, конечно, решим, что она синяя, что не обязательно верно.
Чтобы разумно отделить одни точки от других, нужно найти поверхность не слишком сложную, с одной стороны, и хорошо отделяющую красные от синих на размеченных примерах, с другой стороны. Вопрос в том, как определить сложность поверхности.
Так вот, оказывается, что все обычные определения (типа количества параметров, которые ее определяют) не работают. То есть, не получается как-то ограничить ожидаемую ошибку на неизвестных точках, используя обычную размерность функции, задающей поверхность и ошибку на размеченных точках (а также их количество).
Так вот, отвечает на этот вопрос VC dimension - размерность Вапника-Червоненкиса. Семейство поверхностех имеет размерность N если любые N точек (но не любые N+1) можно разделить какой-то поверхностью из этого семейства. Что значит разделить? Что как бы мы не раскрасили эти N точек на красные и синие, всегда найдется такая поверхность из этого семейства, что красные будут с одной стороны, а синие - с другой.
Оказывается, что если определить размерность таким способом, и если размеченные точки случайно выбраны из всех возможных, то есть довольно простая связь между количеством размеченных точек, количеством ошибок на них, размерностью, и вероятностью, что новая точка будет помечена правильно.
Некоторые говорят, что сам подход machine learning порочный, потому что вместо того, чтобы разбираться в природе вещей мы выискиваем способы как-то решить проблему, не разобравшись. Это, конечно, верно, что не разобравшись, но во-первых, так было всегда: наблюдения показали, что частота колебаний маятника почти не зависит от амплитуды. Черт его знает, почему она не зависит, но часы делать можно. Просто сейчас поиски этих "оказалось" поставлены на промышленную основу. Во-вторых, лучше хоть как-то решить проблему сейчас, а лет через 100, глядишь, разберемся, почему оно работает. В-третьих, эти "оказалось" часто как раз и помогают докопаться до причины.
Machine learning (по-нашему למידת מכונה, не знаю как по-русски) - это то, что осталось (по моим наблюдениям) от красивого слова "искусственный интеллект". Как научить машину делать что-то очень умное, что только специалист умеет (в более интересных случаях - то, чего и специалист не умеет).
Самая старая задача machine learning - обучение по размеченным примерам (тоже как-то не очень по-русски).
Пример: допустим, по анализу крови можно как-то узнать, болен человек некоторой болезнью или нет. Анализ крови - это, скажем, 10 чисел (показатели 10 заранее заданных параметров). Можно попробовать допросить врача, как он по этим параметрам что-то определяет. В лучшем случае, сможем написать программу, которая делает то же, что врач, в более реальном случае - не выйдет. Врач, глядя на анализ может вспомнить, что 10 лет назад видел что-то подобное, и тогда оказалось... - а вот рассказать заранее все, что он может вспомнить - вряд ли получится. Подход machine learning такой:
Представим каждый анализ как точку в 10-мерном пространстве (если бы параметров было всего 2, это была бы точка на плоскости: по одной оси откладываем значение первого параметра, по другой - второго). Допустим (абсолютно реальное предположение), есть база данных с миллионом анализов больных людей и миллионом - здоровых. Отметим точки, соответствующие больным красным цветом, здоровым - синим. Утверждение о том, что по анализу крови можно узнать, болен человек или нет эквивалентно тому, что существует в нашем 10-мерном пространстве (а если бы параметров было 2 - в плоскости) поверхность (линия), отделяющая все возможные красные точки от всех синих. Как только мы найдем такую поверхность (линию), компьютер сможет узнать, находится ли какая-то новая точка в красной области или в синей. Вполне вероятно, что результат будет гораздо лучше, чем у самого лучшего врача: он же не помнит миллион случаев, а поверхность наша их все учитывает.
Проблема в том, что провести такую поверхность очень сложно: у нас же есть не все возможные красные и синие точки, а только миллион, как же мы можем быть уверены, что она и остальные отделяет правильно?
Если мы ограничиваемся только очень простыми поверхностями (например, показатель номер 3 больше 18), то только в очень простых случаях сможем отделить все известные красные точки от синих. Если мы берем сколь угодно сложные поверхности, то отделить известные красные точки от известных синих очень просто, но абсолютно бессмысленно. Пример: обводим все известные красные точки маленьким кружочком (10-мерным, если параметров 10, обычным - если их 2), говорим, что все, что внутри кружочков - красное, все остальное - синее. На размеченных точках мы ни разу не ошибемся, но когда появится новая точка, мы, конечно, решим, что она синяя, что не обязательно верно.
Чтобы разумно отделить одни точки от других, нужно найти поверхность не слишком сложную, с одной стороны, и хорошо отделяющую красные от синих на размеченных примерах, с другой стороны. Вопрос в том, как определить сложность поверхности.
Так вот, оказывается, что все обычные определения (типа количества параметров, которые ее определяют) не работают. То есть, не получается как-то ограничить ожидаемую ошибку на неизвестных точках, используя обычную размерность функции, задающей поверхность и ошибку на размеченных точках (а также их количество).
Так вот, отвечает на этот вопрос VC dimension - размерность Вапника-Червоненкиса. Семейство поверхностех имеет размерность N если любые N точек (но не любые N+1) можно разделить какой-то поверхностью из этого семейства. Что значит разделить? Что как бы мы не раскрасили эти N точек на красные и синие, всегда найдется такая поверхность из этого семейства, что красные будут с одной стороны, а синие - с другой.
Оказывается, что если определить размерность таким способом, и если размеченные точки случайно выбраны из всех возможных, то есть довольно простая связь между количеством размеченных точек, количеством ошибок на них, размерностью, и вероятностью, что новая точка будет помечена правильно.
Некоторые говорят, что сам подход machine learning порочный, потому что вместо того, чтобы разбираться в природе вещей мы выискиваем способы как-то решить проблему, не разобравшись. Это, конечно, верно, что не разобравшись, но во-первых, так было всегда: наблюдения показали, что частота колебаний маятника почти не зависит от амплитуды. Черт его знает, почему она не зависит, но часы делать можно. Просто сейчас поиски этих "оказалось" поставлены на промышленную основу. Во-вторых, лучше хоть как-то решить проблему сейчас, а лет через 100, глядишь, разберемся, почему оно работает. В-третьих, эти "оказалось" часто как раз и помогают докопаться до причины.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-09-30 04:41 am (UTC)no subject
Date: 2014-09-30 04:57 am (UTC)no subject
Date: 2014-09-30 03:35 pm (UTC)"по анализу крови узнать болен человек или нет"
вообще-то, врач не должен просто дать ответ на вопрос: "болен или не болен", а хорошо бы узнать чем человек болен и как его лечить, если он таки болен :)
одни и те же результаты анализов могут сигнализировать о болезни или быть нормальными (для разных людей);
а еще человек (гад такой) может быть болен несколькими болезнями :(
а еще на результаты анализов кроме болезней могут влиять и принимаемые лекарства, и питание и многое другое
да и анализы не у всех пациентов одинаковые, а по симптомам и рез-там первичных анализов даются дополнительные анализы (позволяющие подтвердить, уточнить или опровергнуть предварительный диагноз)
когда врач вспоминает случай 10 лет назад, то он его вспоминает не только потому, что были похожие анализы, но потому, что есть сходство между случаями
а теперь мой вопрос: "а какая цель у данного использования ИИ?"
no subject
Date: 2014-09-30 05:53 pm (UTC)