組合學習

當學生新概念或新命題與認知結構中已有的觀念不產生下位關係，也不產生上位關係時，它們之間可能存在組合關係。這種只能憑藉組合關係來理解意義的學習就是組合學習。

組合學習是指美國心理學家奧蘇伯爾提出的一種學習方式。指新知識與學習者人知結構中原有觀念的概括層次相同，二者既非上位關係，又非卜位關係時，通過並列或聯合而產生的學習。如質量與能量、冷熱與體積、需求與價格、遺傳與變異等，這些知識間即為並列結合關係。由於新舊知識間具有某種共同的特徵或一般的吻合性，故二者聞可建立一種聯合性結構。新知識可從勺原有知識的並列結合中獲得意義。

什麼是組合在線學習？大家都曾有過這樣的經歷，在我們刷微博或是閲讀新聞的時候，經常會看到一些自動推薦的內容，這些信息可以根據你對推送的點擊情況以及閲讀時間等來調整以後的推送選擇。再比如，手機導航往往會在你輸入地點時推薦一條最合適的路線，當你按照推薦走的時候，手機導航也會收集這次行程的信息，哪裏比較堵，哪裏很順暢，從而可以調整系統今後的推薦。

有人會提出質疑：這不就是推薦系統嗎？是的，但是傳統的推薦系統只能離線學習用户和對象的各種特徵，作出儘量合適的推薦，是一個相對靜態的系統。而我們這裏強調的是在線學習（online learning），即迅速利用在線反饋，不斷迭代調整推薦策略，從而儘快提高學習效果和整體收益。而組合在線學習（combinatorial online learning）的組合性則體現在學習的輸出上，它不是一個簡單結果，而是一個組合對象。比如上述情形中，手機導航輸出的路線其實是若干路段的組合或者包括不同交通工具換乘的組合，而手機助手的推薦也是不同消息渠道的組合。

傳統的推薦系統通過與組合在線學習相結合，就可以通過即時反饋調整策略達到更好的推薦效果。而組合在線學習應用範圍遠不止推薦系統，任何傳統的組合優化問題，只要問題的輸入有不確定性，需要通過在線反饋逐步學習的，都可以應用組合在線學習方法。組合在線學習也是當前大熱的強化學習（reinforcement learning）的一個組成部分，而組合在線學習的強大理論支持也會給強化學習提供很好的理論指導。所以組合在線學習就是下面圖示所表達的組合優化和在線學習不斷交互迭代更新的反饋環路。 ^[1] 

要介紹組合在線學習，我們先要介紹一類更簡單也更經典的問題，叫做多臂老虎機（multi-armed bandit或MAB）問題。賭場的老虎機有一個綽號叫單臂強盜（single-armed bandit），因為它即使只有一隻胳膊，也會把你的錢拿走。而多臂老虎機（或多臂強盜）就從這個綽號引申而來。假設你進入一個賭場，面對一排老虎機（所以有多個臂），由於不同老虎機的期望收益和期望損失不同，你採取什麼老虎機選擇策略來保證你的總收益最高呢？這就是經典的多臂老虎機問題。

這個經典問題集中體現了在線學習及更寬泛的強化學習中一個核心的權衡問題：我們是應該探索去嘗試新的可能性，還是應該守成，堅持目前已知的最好選擇?在多臂老虎機問題中，探索意味着去玩還沒玩過的老虎機，但這有可能使你花太多時間和金錢在收益不好的機器上；而守成意味着只玩目前為止給你收益最好的機器，但這又可能使你失去找到更好機器的機會。而類似抉擇在日常生活中隨處可見：去一個餐廳，你是不是也糾結於是點熟悉的菜品，還是點個新菜？去一個地方，是走熟知的老路還是選一條新路？而探索和守成的權衡就是在線學習的核心。 ^[1]