Щоб обробляти великі дані, скоротіть їх MIT News Массачусетський технологічний інститут
Прес-контакт:
Завантажити медіа
*Умови використання:
Зображення для завантаження на веб-сайті офісу MIT доступні некомерційним організаціям, пресі та широкій громадськості за ліцензією Creative Commons Attribution Non-Commercial No Derivatives. Ви не можете змінювати надані зображення, крім як обрізати їх за розміром. При відтворенні зображень повинна використовуватися кредитна лінія; якщо такого нижче не вказано, зарахуйте зображення в "MIT".
Попереднє зображення Наступне зображення
Як може засвідчити кожен, хто коли-небудь використовував електронну таблицю, часто зручно впорядковувати дані в таблиці. Але в епоху великих даних ці таблиці можуть бути величезними, з мільйонами або навіть сотнями мільйонів рядків.
Одним із способів зробити аналіз великих даних обчислювально практичним є зменшення розміру таблиць даних - або матриць, якщо використовувати математичний термін -, залишаючи купу рядків. Фокус у тому, що решта рядків мають бути в якомусь сенсі репрезентативними тих, які були пропущені, щоб обчислення, виконані на них, дали приблизно правильні результати.
На симпозіумі ACM з теорії обчислень у червні дослідники MIT представлять новий алгоритм, який знаходить якнайменше наближення вихідної матриці, що гарантує надійні обчислення. Для класу проблем, важливих в техніці та машинному навчанні, це суттєве покращення порівняно з попередніми техніками. І для всіх класів задач алгоритм знаходить наближення якомога швидше.
Для того, щоб визначити, наскільки даний рядок ущільненої матриці представляє рядок вихідної матриці, алгоритму потрібно виміряти «відстань» між ними. Але існують різні способи визначення “відстані”.
Одним із поширених способів є так звана "евклідова дистанція". На евклідовій відстані різниці між записами у відповідних позиціях у двох рядках квадратуються і складаються, а відстань між рядками є квадратним коренем отриманої суми. Інтуїція полягає в теоремі Піфагора: Квадратний корінь із суми квадратів довжин катетів прямокутного трикутника дає довжину гіпотенузи.
Інший показник відстані є менш поширеним, але особливо корисним для вирішення проблем машинного навчання та інших задач оптимізації. Це називається "Манхеттенська відстань", і це просто сума абсолютних різниць між відповідними записами в двох рядках.
Всередині норми
Насправді, і відстань від Манхеттена, і відстань Евкліда є прикладами того, що статистики називають "нормами". Манхеттенська відстань, або 1-норма, є першим коренем суми різниць, піднятих на першу ступінь, а евклідова відстань, або 2-норма, є квадратним коренем із суми різниць, піднятих на другу ступінь. 3-норма - це кубовий корінь із суми різниць, піднесених до третьої міри, і так далі до нескінченності.