Як ще можна використовувати метод найменших квадратів?
Методом найменших квадратів (МНК) називають метод оцінки величин за результатами безлічі вимірів, що містить випадкові помилки.
Суть методу полягає в тому, що критерієм якості розглянутого рішення є сума квадратів помилок, яку прагнуть звести до мінімуму. Для застосування цього методу вимагає провести якомога більше число вимірювань невідомої випадкової величини (чим більше - тим вище точність рішення) і деякий безліч передбачуваних рішень, з якого потрібно вибрати найкраще. Якщо безліч рішень параметризованих, то потрібно знайти оптимальне значення параметрів.
Чому зводяться до мінімуму квадрати помилок, а не самі помилки? Справа в тому, що в більшості випадків помилки бувають в обидві сторони: оцінка може бути більше вимірювання або менше його. Якщо складати помилки з різними знаками, то вони будуть взаємно компенсуватися, і в підсумку сума дасть нам невірне уявлення про якість оцінки. Часто для того, щоб підсумкова оцінка мала ту ж розмірність, що і вимірювані величини, з суми квадратів помилок витягують квадратний корінь.
МНК використовується в математиці, зокрема - в теорії ймовірностей і математичній статистиці. Найбільше застосування цей метод має в задачах фільтрації, коли необхідно відокремити корисний сигнал від накладеного на нього шуму. Його застосовують і в математичному аналізі для наближеного представлення заданої функції більш простими функціями. Ще одна з областей застосування МНК - рішення систем рівнянь з кількістю невідомих меншим, ніж число рівнянь.
Я придумав ще кілька вельми несподіваних областей застосування МНК, про які хотів би розповісти в цій статті.
МНК і друкарські помилки
Бичем автоматичних перекладачів та пошукових систем є друкарські помилки і орфографічні помилки. Дійсно, якщо слово відрізняється всього на 1 букву, програма розцінює його вже як інше слово і переводить / шукає його неправильно чи переводить / не знаходить його взагалі.
У мене виникла схожа проблема - малося дві бази даних з адресами московських будинків, і треба було їх об'єднати в одну. Але адреси були записані в різному стилі: в одній базі був стандарт КЛАДР (всеросійський класифікатор адрес), наприклад «БАБУШКІНА ЛЬОТЧИКА ВУЛ., Д10К3», а в іншій базі був поштовий стиль, наприклад: «Вул. Льотчика Бабушкіна, будинок 10 корп.3 ». Начебто помилок немає в обох випадках, а автоматизувати процес неймовірно складно (у кожній базі по 40 тисяч записів!). Хоча і друкарських помилок там теж вистачало ... Як дати комп'ютеру зрозуміти, що 2 вищенаведених адреси належать одному і тому ж будинку? Тут-то мені і знадобився МНК.
Що я зробив? Знайшовши чергову букву в першій адресі, я шукав ту ж букву в другому адресі. Якщо вони обидві знаходилися на одному і тому ж місці, то я вважав помилку для цієї букви рівною 0. Якщо вони розташовувалися на сусідніх позиціях, то помилка була рівна 1, якщо мався зрушення на 2 позиції, помилка дорівнювала 2 і т.д. Якщо такої літери взагалі не малося на іншому адресу, то помилка покладалася рівною n + 1, де n - число букв в 1-му адресу. Таким чином, я обчислював суму квадратів помилок і з'єднував ті записи, в яких ця сума була мінімальною.
Зрозуміло, номери будинків і корпусів оброблялися окремо. Не знаю, винайшов Чи я черговий «велосипед», але завдання було вирішено швидко і якісно. Цікаво, чи застосовується цей метод в пошукових системах? Можливо, застосовується, оскільки кожен поважаючий себе пошуковик при зустрічі незнайомого слова пропонує заміну зі знайомих слів («можливо ви мали на увазі ...»). Втім, вони можуть робити цей аналіз якось по-іншому.
МНК і пошук за картинками, особам і картками
Цей метод можна застосувати і в пошуку по картинках, кресленнями, картами і навіть по особам людей.
Зараз всі пошуковики, замість пошуку по картинках, по суті використовують пошук по підписам до картинок. Це, безсумнівно, корисний і зручний сервіс, але я пропоную доповнити його справжнім пошуком по картинках. Вводиться картинка-зразок, і для всіх зображень складається рейтинг за сумою квадратів відхилень характерних точок. Визначення цих самих характерних точок є сама по собі нетривіальне завдання. Однак вона цілком вирішувана: наприклад, для осіб це куточки очей, губ, кінчик носа, ніздрі, краю і центри брів, зіниці і т.д.
Зіставивши ці параметри, можна знайти особа, найбільш схоже на зразок. Я вже бачив сайти, де такий сервіс працює, і ви можете знайти знаменитість, найбільш схожу на запропоновану вами фотографію і навіть скласти анімацію, що перетворює вас в знаменитість і назад. Напевно, цей же метод працює в базах МВС, що містять фотороботи злочинців.
Та й за відбитками пальців можна тим же методам робити пошук. Пошук по картах орієнтується на природні нерівності географічних об'єктів - вигини річок, гірських хребтів, обриси берегів, лісів і полів.
Ось такий чудовий і універсальний метод МНК. Я впевнений, що ви, дорогі читачі, зможете і самі знайти безліч незвичайних і несподіваних сфер застосування цього методу.
