ozonns.ruКак еще можно использовать метод наименьших квадратов?
Методом наименьших квадратов (МНК) называют метод оценки величин по результатам множества измерений, содержащим случайные ошибки.
Суть метода заключается в том, что критерием качества рассматриваемого решения является сумма квадратов ошибок, которую стремятся свести к минимуму. Для применения этого метода требует провести как можно большее число измерений неизвестной случайной величины (чем больше — тем выше точность решения) и некоторое множество предполагаемых решений, из которого требуется выбрать наилучшее. Если множество решений параметризировано, то нужно найти оптимальное значение параметров.
Почему сводятся к минимуму квадраты ошибок, а не сами ошибки? Дело в том, что в большинстве случаев ошибки бывают в обе стороны: оценка может быть больше измерения или меньше его. Если складывать ошибки с разными знаками, то они будут взаимно компенсироваться, и в итоге сумма даст нам неверное представление о качестве оценки. Часто для того, чтобы итоговая оценка имела ту же размерность, что и измеряемые величины, из суммы квадратов ошибок извлекают квадратный корень.
МНК используется в математике, в частности — в теории вероятностей и математической статистике. Наибольшее применение этот метод имеет в задачах фильтрации, когда необходимо отделить полезный сигнал от наложенного на него шума. Его применяют и в математическом анализе для приближённого представления заданной функции более простыми функциями. Ещё одна из областей применения МНК — решение систем уравнений с количеством неизвестных меньшим, чем число уравнений.
Я придумал ещё несколько весьма неожиданных областей применения МНК, о которых хотел бы рассказать в этой статье. МНК и опечатки
Бичом автоматических переводчиков и поисковых систем являются опечатки и орфографические ошибки. Действительно, если слово отличается всего на 1 букву, программа расценивает его уже как другое слово и переводит/ищет его неправильно или не переводит/не находит его вообще.
У меня возникла похожая проблема — имелось две базы данных с адресами московских домов, и надо было их объединить в одну. Но адреса были записаны в разном стиле: в одной базе был стандарт КЛАДР (всероссийский классификатор адресов), например «БАБУШКИНА ЛЕТЧИКА УЛ., Д10К3», а в другой базе был почтовый стиль, например: «Ул. Летчика Бабушкина, дом 10 корп. 3». Вроде бы ошибок нет в обоих случаях, а автоматизировать процесс невероятно сложно (в каждой базе по 40 тысяч записей!). Хотя и опечаток там тоже хватало… Как дать компьютеру понять, что 2 вышеприведённых адреса принадлежат одному и тому же дому? Тут-то мне и пригодился МНК.
Что я сделал? Найдя очередную букву в первом адресе, я искал ту же букву во втором адресе. Если они обе находились на одном и том же месте, то я полагал ошибку для этой буквы равной 0. Если они располагались на соседних позициях, то ошибка была равна 1, если имелся сдвиг на 2 позиции, ошибка равнялась 2 и т. д. Если такой буквы вообще не имелось в другом адресе, то ошибка полагалась равной n+1, где n — число букв в 1-м адресе. Таким образом, я вычислял сумму квадратов ошибок и соединял те записи, в которых эта сумма была минимальной.
Разумеется, номера домов и корпусов обрабатывались отдельно. Не знаю, изобрёл ли я очередной «велосипед», но задача была решена быстро и качественно. Интересно, применяется ли этот метод в поисковых системах? Возможно, применяется, поскольку каждый уважающий себя поисковик при встрече незнакомого слова предлагает замену из знакомых слов («возможно вы имели в виду…»). Впрочем, они могут делать этот анализ как-то по-другому. МНК и поиск по картинкам, лицам и картам
Этот метод можно применить и в поиске по картинкам, чертежам, картам и даже по лицам людей.
Сейчас все поисковики, вместо поиска по картинкам, по сути используют поиск по подписям к картинкам. Это, несомненно, полезный и удобный сервис, но я предлагаю дополнить его настоящим поиском по картинкам. Вводится картинка-образец, и для всех изображений составляется рейтинг по сумме квадратов отклонений характерных точек. Определение этих самых характерных точек есть сама по себе нетривиальная задача. Однако она вполне решаема: например, для лиц это уголки глаз, губ, кончик носа, ноздри, края и центры бровей, зрачки и т. д.
Сопоставив эти параметры, можно найти лицо, наиболее похожее на образец. Я уже видел сайты, где такой сервис работает, и вы можете найти знаменитость, наиболее похожую на предложенную вами фотографию и даже составить анимацию, превращающую вас в знаменитость и обратно. Наверняка, этот же метод работает в базах МВД, содержащих фотороботы преступников.
Да и по отпечаткам пальцев можно тем же методам делать поиск. Поиск по картам ориентируется на естественные неровности географических объектов — изгибы рек, горных хребтов, очертания берегов, лесов и полей.
Вот такой замечательный и универсальный метод МНК. Я уверен, что вы, дорогие читатели, сможете и сами найти множество необычных и неожиданных областей применения этого метода.