Задача
Рис. 6.6. Линия наилучшего соответствия |
Эта основополагающая задача из области статистики и вычислительной ма- тематики формулируется следующим образом. Допустим, данные представляют собой множество P из n точек на плоскости, обозначаемых (xpy⅛), (x2,y2), ..., (xn,yn); предполагается, что x⅛ < x2 < ... < xn. Для линии L, определяемой уравнением у = ax + b, погрешностью L относительно P называется сумма возведенных в ква- драт «расстояний» от точек до P:
Естественной целью в такой ситуации будет нахождение линии с минималь- ной погрешностью.
Оказывается, у этой задачи существует компактное решение, которое легко вычисляется методами математического анализа. Опуская про- межуточные выкладки, приведем результат: линия минимальной погрешности определяется формулой у = ax + b, гдеНо существует проблема, для которой эти формулы не подойдут. Часто набор данных выглядит примерно так, как показано на рис. 6.7. В таком случае нам хоте- лось бы сделать утверждение вида «Точки лежат приблизительно на серии из двух линий». Как формализовать такое понятие?
Рис. 6.7. Набор точек, расположенных приблизительно вдоль двух линий |
Для любой одиночной линии погрешность у точек на рисунке будет запредель- ной; но если использовать две линии, ошибка может быть относительно невелика. Итак, новую задачу можно попытаться сформулировать следующим образом: вместо того, чтобы искать одну линию наилучшего соответствия, мы ищем набор линий, обеспечивающий минимальную погрешность. Но такая формулировка за- дачи никуда не годится, потому что у нее имеется тривиальное решение: при сколь угодно большом наборе линий можно добиться идеального соответствия, соединив линиями каждую пару последовательных точек в P.
С противоположной стороны можно жестко «запрограммировать» число 2 в задаче — искать лучшее соответствие не более чем с двумя линиями. Но и та- кая формулировка противоречит здравому смыслу: изначально не было никакой априорной информации о том, что точки лежат приблизительно на двух линиях; мы пришли к такому выводу, взглянув на иллюстрацию. Вероятно, большинство людей также скажет, что точки на рис. 6.8 лежат приблизительно на трех линиях.
Рис. 6.8. Набор точек, расположенных приблизительно вдоль трех линий |
На интуитивном уровне формулировка задачи должна обеспечивать хорошее прилегание точек с минимально возможным количеством линий. А теперь сфор- мулируем сегментированную задачу наименьших квадратов, которая достаточно четко отражает эти представления. Эта задача является конкретным воплощением более общей проблемы из области анализа данных и статистики, называемой обна- ружением изменений: в заданной последовательности точек данных требуется найти несколько точек, в которых происходят дискретные изменения (в нашем случае — переход к другой линейной аппроксимации).
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии