使用多臂吃角子老虎機進行可驗證性強化之主動式學習

Verifiability Enhanced Active Learning Using Multi-armed Bandit

張晏誠(Yen-Cheng Chang)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202003579

摘要

在監督的機器學習中，主動學習是一項重要的技術，可減輕標註訓練資料所需的工作量。主動學習中的大多數詢問策略都是基於訓練過後的分類器。但是，在許多實際應用中，經過訓練的分類器直到查詢、標記和訓練才發現許多實例根本不准確。在本文中，我考慮了來自資料空間和訓練過後的分類器的信息，目的是減少在主動學習中達到預定的準確性所需的詢問數量。

可驗證性強化之主動式學習（VEAL）是一種基於池的技術，它使用可驗證性的概念來詢問資料，可驗證性的概念定義為被版本空間中所有分類器正確分類的實例的比例。我進一步將VEAL與不確定性指標以及一些隨機程序結合起來，使用多臂吃角子老虎技術來實現總體上更穩定的性能。

實驗結果表明，對於在二元分類中進行20個詢問（池中的800個查詢）之後，VEAL和其他最新技術之間的平均準確度差異個別為0.25\%(對uncertainty)、 -0.048 \% (對ALBL)、 1.01\% (對QUIRE)。在相同的實驗設置下，與MAB結合使用時，MAB-VEAL的準確率高於uncertainty 0.85\%、高於ALBL 0.29\%、高於QUIR 1.62\%。

對於多類分類中，VEAL和其他最新技術（選擇最佳的嵌入空間）之間的準確性差異在MNIST上為-0.04 \%、在CIFAR-10上為-0.08 \%、在STL-10上為-0.22 \%、在SVHN上為0.18 \%。同樣地，MAB-VEAL和其他最新技術的準確性差異在MNIST上為-0.09\%、在CIFAR-10上為0.8\%、在STL-10上為-0.16\%、在SVHN上為0.31\%。儘管對多類分類器沒有明確定義驗證性，但與其他最新技術方法相比，VEAL和MAB-VEAL仍產生了有競爭性的結果。

關鍵字

機器學習 ； 主動式學習 ； 可驗證性 ； 不確定性 ； 多臂吃角子老虎機 ； 置信度上限

並列摘要

In supervised machine learning, active learning is an important technique which alleviates the effort needed for labeling training data. Most of the query strategies in active learning are based on the trained classifier; however, in many real-world applications, the trained classifier is not at all accurate until many instances have been queried, labeled, and trained. In this thesis, I consider the information from both instance space and the trained classifier, aiming to reduce the number of queries needed to achieve a predefined level of accuracy in active learning.

The proposed verifiability enhanced active learning (VEAL) is a pool-based technique which queries instances using the concept of verifiability, which is defined as the proportion of instances that are correctly classified by all classifiers in the version space. I further combine VEAL with the uncertainty indicator as well as some stochastic behaviors by the multi-armed bandit techniques to achieve a more stable performance in general.

Empirically, for binary classification, after 20 queries (out of 800 in the pool), the average accuracy differences between VEAL and other state-of-the-art (SOTA) methods are 0.25\% vs. uncertainty; -0.048\% vs. ALBL; 1.01\% vs. QUIRE. Combined with MAB, under the same experiment setup, MAB-VEAL outperformed uncertainty by 0.85\% on average, and outperformed ALBL by 0.29\% on average, and outperformed QUIRE by 1.62\% on average.

For multi-class classification, the accuracy differences between VEAL and other SOTA methods (with their most preferable embeddings) are -0.04\% on MNIST, -0.08\% on CIFAR-10, -0.22\% on STL-10 and 0.18\% on SVHN. Similarly, that for MAB-VEAL are -0.09\% on MNIST, 0.8\% on CIFAR-10, -0.16\% on STL-10 and 0.31\% on SVHN. Although verifiabilty was not specifically defined for multi-class cases, VEAL and MAB-VEAL still yielded competitive results compared with other SOTA methods.

並列關鍵字

machine learning ； active learning ； verifiability ； uncertainty ； multi-armed bandit ； upper confidence bounds

參考文獻

[1] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armedbandit problem. InConference on Learning Theory, pages 39–1, 2012.

[2] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmedbandit problem.Machine Learning, 47(2):235–256, 2002.

[3] A. Beygelzimer, S. Dasgupta, and J. Langford. Importance weighted activelearning.ACM International Conference Proceeding Series, 382, 12 2009.

[4] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines.ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011.

[5] W. Chu, M. Zinkevich, L. Li, A. Thomas, and B. Tseng.Unbiased onlineactive learning in data streams.In Proceedings of the 17th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, 195–203.,2011.