Щоб обробляти великі дані, зменшіть їх

Прес-контакт:

Завантажити медіа

*Умови використання:

Зображення для завантаження на веб-сайті офісу MIT доступні некомерційним організаціям, пресі та широкій громадськості за ліцензією Creative Commons Attribution Non-Commercial No Derivatives. Ви не можете змінювати надані зображення, крім як обрізати їх за розміром. При відтворенні зображень повинна використовуватися кредитна лінія; якщо такого нижче не вказано, зарахуйте зображення в "MIT".

Попереднє зображення Наступне зображення

Як може засвідчити кожен, хто коли-небудь використовував електронну таблицю, часто зручно впорядковувати дані в таблиці. Але в епоху великих даних ці таблиці можуть бути величезними, з мільйонами або навіть сотнями мільйонів рядків.

Одним із способів зробити аналіз великих даних обчислювально практичним є зменшення розміру таблиць даних - або матриць, якщо використовувати математичний термін -, залишаючи купу рядків. Фокус у тому, що решта рядків мають бути в якомусь сенсі репрезентативними тих, які були пропущені, щоб обчислення, виконані на них, дали приблизно правильні результати.

На симпозіумі ACM з теорії обчислень у червні дослідники MIT представлять новий алгоритм, який знаходить якнайменше наближення вихідної матриці, що гарантує надійні обчислення. Для класу проблем, важливих в техніці та машинному навчанні, це суттєве покращення порівняно з попередніми техніками. І для всіх класів задач алгоритм знаходить наближення якомога швидше.

Для того, щоб визначити, наскільки даний рядок ущільненої матриці представляє рядок вихідної матриці, алгоритму потрібно виміряти «відстань» між ними. Але існують різні способи визначення “відстані”.

Одним із поширених способів є так звана "евклідова дистанція". На евклідовій відстані різниці між записами у відповідних позиціях у двох рядках квадратуються і складаються, а відстань між рядками є квадратним коренем отриманої суми. Інтуїція полягає в теоремі Піфагора: Квадратний корінь із суми квадратів довжин катетів прямокутного трикутника дає довжину гіпотенузи.

Інший показник відстані є менш поширеним, але особливо корисним для вирішення проблем машинного навчання та інших задач оптимізації. Це називається "Манхеттенська відстань", і це просто сума абсолютних різниць між відповідними записами в двох рядках.

Всередині норми

Насправді, і відстань від Манхеттена, і відстань Евкліда є прикладами того, що статистики називають "нормами". Манхеттенська відстань, або 1-норма, є першим коренем суми різниць, піднятих на першу ступінь, а евклідова відстань, або 2-норма, є квадратним коренем із суми різниць, піднятих на другу ступінь. 3-норма - це кубовий корінь із суми різниць, піднесених до третьої міри, і так далі до нескінченності.

У своїй роботі дослідники MIT - Річард Пен, докторант з прикладної математики, та Майкл Коен, аспірант електротехніки та інформатики - демонструють, що їх алгоритм є оптимальним для конденсації матриць за будь-якої норми. Але за словами Пенґ, "той, про кого ми справді дбали, був 1-нормою".

При конденсації матриці - за будь-якої норми - першим кроком є присвоєння кожному рядку вихідної матриці “ваги”. Вага рядка представляє кількість інших рядків, на які вона схожа, і вона визначає ймовірність того, що рядок буде включено до зведеної матриці. Якщо це так, його значення будуть помножені відповідно до ваги. Так, наприклад, якщо 10 рядків є хорошими підставками один для одного, але не для будь-яких інших рядків матриці, кожен з них матиме 10-відсотковий шанс потрапити в ущільнену матрицю. Якщо один із них це зробить, усі його записи будуть помножені на 10, так що це буде відображати внесок інших дев'яти рядків, в яких він стоїть.

Хоча відстань до Манхеттена в деякому сенсі простіша, ніж відстань Евкліда, це ускладнює обчислення ваги рядків. Раніше найкращий алгоритм конденсації матриць за 1-нормою давав би матрицю, кількість рядків якої була пропорційною кількості стовпців вихідної матриці, піднятих до рівня 2,5. Однак найкращий алгоритм конденсації матриць за 2-нормою дав би матрицю, кількість рядків якої пропорційна кількості стовпців вихідної матриці, помноженої на власний логарифм.

Це означає, що якби матриця мала 100 стовпців, за 1 нормою, найкращою можливістю конденсації до роботи Пенга та Коена була матриця з сотнями тисяч рядків. За 2-нормою це була матриця з кількома сотнями рядків. Ця невідповідність зростає із збільшенням кількості стовпців.

Приборкання рекурсії

Алгоритм Пенга і Коена конденсує матриці під 1-нормою, як і під 2-нормою; за 2-нормою він конденсує матриці так само, як і попередники. Це тому, що для 2-норми він просто використовує найкращий існуючий алгоритм. Для 1-норми він використовує той самий алгоритм, але використовує його п’ять-шість разів.

Реальний внесок статті полягає в математичному доведенні того, що алгоритм 2-норми дасть надійні результати за 1-норми. Як пояснює Пенг, рівняння для обчислення ваг 1 норми було відоме вже деякий час. Але "найцікавіше з цим визначенням полягає в тому, що воно є рекурсивним", говорить він. "Тож правильний набір ваг відображається як на лівій, так і на правій стороні". Тобто, вага для даного рядка матриці - назвемо його w - встановлюється рівним математичному виразу, який сам включає w.

"Це визначення, як відомо, існувало, але люди в статистиці не знали, що з ним робити", - каже Пен. "Вони дивляться на це і думають:" Як я коли-небудь обчислюю щось із цим? "

Те, що доводять Пен і Коен, це те, що якщо ви починаєте з того, що встановлюєте w в правій частині рівняння, рівному 1, тоді обчислюєте вираз і підключаєте відповідь назад до правого w, потім робите те саме знову і знову, ви швидко сходитесь на гарному наближенні правильного значення w.

"Це дуже елегантна математика, і вона дає значний прогрес у порівнянні з попередніми результатами", - говорить Річард Карп, професор комп'ютерних наук з Каліфорнійського університету в Берклі, лауреат Національної медалі науки та нагороди Тьюрінга, найвищої честь в інформатиці. «Це зводить початкову проблему до дуже простої для розуміння. Я захоплююся математичним розвитком, який в нього входив ".