Алгоритм агрегування для прогнозування пакетів SpringerLink
Анотація
У цій роботі сформульовано протокол прогнозування пакетів, що є приватним випадком онлайн-прогнозування із затримкою зворотного зв'язку. Згідно з протоколом прогнозування пакетів, той, хто навчається, повинен зробити кілька прогнозів, не бачачи відповідних результатів, і тоді результати виявляються за один раз. Стаття розробляє теорію прогнозування з порадами експертів щодо зграй шляхом узагальнення поняття змішуваності. Ми пропонуємо ряд алгоритмів злиття для прогнозування пакетів з жорсткими найгіршими випадками втрат, подібних до тих, що використовуються для агреговального алгоритму Вовка. На відміну від існуючих алгоритмів налаштувань зворотного зв'язку із зволіканням, наші алгоритми не залежать від порядку результатів у наборі. Емпіричні експерименти на наборах даних про спорт та ціни на будинки проводяться для вивчення ефективності нових алгоритмів та порівняння їх із існуючим методом.
Вступ
Ця стаття стосується он-лайн протоколу прогнозування, де учень повинен передбачити результати \ (\ omega _1, \ omega _2 \ ldots \), що відбуваються послідовно. Учень отримує зворотний зв'язок по ходу.
У базовому он-лайн протоколі прогнозування, на кроці т навчається видає прогноз \ (\ gamma _t \), а потім відразу бачить справжній результат \ (\ omega _t \), який є зворотним зв'язком. Якість прогнозування оцінюється функцією втрат \ (\ лямбда (\ гамма, \ омега) \), вимірюючи невідповідність між прогнозом і результатом або, загалом кажучи, кількісно визначаючи (несприятливий) ефект при прогнозуванні \ (\ гамма \) конфронтує результат \ (\ omega \). Результативність учня оцінюється сукупною втратою Т випробування \ (\ sum _ ^ T \ лямбда (\ gamma _t, \ omega _t) \) .
У цій роботі ми стурбовані проблемою прогнозування за порадами фахівців. Припустимо, що учень має доступ до прогнозів ряду експертів. Перш ніж учень зробить прогноз, він може побачити прогнози експертів, і його мета - зазнати втрат, близьких до втрат найкращого ретроспективно.
У протоколі із затримкою зворотного зв'язку може бути затримка з отриманням справжніх результатів \ (\ omega _t \). Можливо, учню доведеться зробити кілька прогнозів, перш ніж фактично побачити результати минулих випробувань. Ми розглянемо особливий випадок цього протоколу, коли з’являться результати пачки: учень повинен зробити кілька прогнозів, ніж виявляються всі результати, і знову потрібно зробити кілька прогнозів.
Проблема, яка природно вкладається в ці рамки, полягає в сукупності прогнозів букмекерів. Вовк та Жданов (2009) прогнозують результати спортивних матчів на основі ймовірностей, розрахованих на основі шансів, наведених букмекерами. Якщо збіги відбуваються один за одним, проблема, природно, відповідає базовому прогнозуванню за допомогою рекомендацій експертів. Однак загальноприйнято (наприклад, в англійській Прем'єр-лізі), що кілька матчів відбуваються в той же день. Було б природно спробувати спрогнозувати всі результати заздалегідь. Усі матчі того самого дня можна розглядати як зграю в наших рамках.
Ми розробляємо теорію прогнозування з експертними порадами щодо пакетів, розширюючи алгоритм агрегування (AA), представлений Вовком (1990, 1998). У розд. 2.2 та Додаток А, ми досліджуємо існуючу теорію АА для прогнозування одиничних результатів (за нашою термінологією, пакети розміром один). Теорія базується на концепції змішуваність середовищ прогнозування, які називаються іграми. У розд. 3, ми розробляємо теорію змішуваності для ігор з пакетами результатів. Теорема 1 показує, що гра з участю пачок К Результати мають той самий профіль констант змішуваності, що і оригінальна гра з одиночними результатами, але швидкість навчання ділиться на К. Це спостереження дозволяє нам обробляти пачки постійного розміру. Однак, як обговорювалося вище, у справді цікавих випадках розмір упаковки змінюється з часом, і, таким чином, змішуваність середовища змінюється від кроку до кроку. До цієї проблеми можна підходити по-різному, що призводить до різних алгоритмів з різними межами продуктивності. У розд. 4, ми вводимо три Алгоритми агрегування для прогнозування пакетів, AAP-max, AAP-інкрементальний та AAP-струм і отримують найгірші верхні межі їх сукупних втрат.
Загальна теорія АА (Вовк, 1998) дозволяє нам показати у розділі. 5, що в якомусь сенсі наші межі є оптимальними. У розд. 5.1, ми пропонуємо автономне виведення нижньої межі для системи змішаних втрат Адамського та ін. (2016). Однак питання оптимальності упаковки ще далеко не повністю вирішене і вимагає подальшого дослідження.
Як вже згадувалося раніше, проблему прогнозування пакетів можна розглядати як окремий випадок проблеми із зволіканням із зворотним зв’язком. Ця проблема вивчалась здебільшого в рамках он-лайн опуклої оптимізації (Zinkevich 2003; Joulani et al. 2013; Quanrud and Khashabi 2015). Термінологія та підхід до он-лайн опуклої оптимізації відрізняється від нашої, яка сягає Літлстоуна та Уормута (1994) та була обстежена Цеза-Б'янкі та Лугосі (2006).
Проблему прогнозування за допомогою поради фахівців щодо зволікання із зворотним зв’язком можна вирішити, запустивши паралельні копії алгоритмів, що передбачають одиничні результати. У розд. 2.3, ми описуємо алгоритм Паралельні копії, який, по суті, СМІЛИЙ від Joulani et al. (2013) з використанням алгоритму агрегування як базового алгоритму для окремих результатів. Теорія агреговуючого алгоритму передбачає найгірший верхній випадок втрати паралельних копій. Ми бачимо, що термін жаління множиться на максимальну затримку або розмір упаковки, як у існуючій літературі (Joulani et al. 2013; Weinberger and Ordentlich 2002).
Межі, які ми отримуємо для наших нових алгоритмів, однакові (AAP-max та AAP-інкрементальні) або несумісні (AAP-струм) з обмеженнями для паралельних копій. Ми обговорюємо межі в секті. 5, а потім у розд. 6 проводять емпіричне порівняння продуктивності алгоритмів.
Для експериментів ми прогнозуємо результати спортивних матчів на основі шансів букмекерів і визначаємо ціни на будинки на основі описів будинків. Спортивні набори даних включають футбольні матчі, які, природно, містять пакети, та тенісні матчі, де ми представляємо пакети штучно двома різними способами. Набори даних про ціни на житло містять записи про майнові операції в Еймісі в США та районі Лондона. Набори даних фіксують лише місяць транзакції, тому вони природно організовані в пакети. Експерименти з цінами на житло дотримуються підходу Kalnishkan et al. (2015): передбачення за порадами експертів можна використовувати для пошуку відповідної минулої інформації. Передбачувачі, навчені різним розділам минулих даних, можна комбінувати в режимі он-лайн, щоб відповідні минулі дані використовувались для прогнозування.
Ефективність алгоритму паралельних копій залежить від порядку результатів у пакетах, тоді як наші алгоритми не залежать від порядку. Ми порівнюємо сукупну втрату наших алгоритмів із втратою паралельних копій, усередненою за випадковими перестановками в пакетах. Ми прийшли до висновку, що хоча паралельні копії можуть працювати дуже добре, особливо якщо порядок результатів у пакетах містить корисну інформацію, втрата наших алгоритмів завжди близька до середньої втрати паралельних копій, а деякі алгоритми перевершують середнє.
Потім ми порівнюємо наші алгоритми між собою, роблячи висновок, що AAP-max є найгіршим, і AAP-струм перевершує AAP-інкремент, якщо відношення максимуму до мінімального розміру упаковки невелике.