Dokumen Asli PENGEMBANGAN ALGORITMA HYBRID QUANTUM ANNEALING UNTUK OPTIMASI ENSEMBLE LEARNING DISERTASI Karya tulis sebagai salah satu syarat untuk memperoleh gelar Doktor dari Institut Teknologi Bandung Oleh LENNY PUTRI YULIANTI NIM: 33221007 (Program Studi Doktor Teknik Elektro dan Informatika) INSTITUT TEKNOLOGI BANDUNG Juli 2024 Dokumen Asli PENGEMBANGAN ALGORITMA HYBRID QUANTUM ANNEALING UNTUK OPTIMASI ENSEMBLE LEARNING Oleh Lenny Putri Yulianti Anggota (Program Studi Doktor Teknik Elektro dan Informatika) NIM: 33221007 Institut Teknologi Bandung (Dr. Judhi Santoso, M.Sc.) Menyetujui Tim Pembimbing Tanggal 22 April 2024 (Prof. Ir. Kridanto Surendro, M.Sc., Ph.D.) Ketua Anggota (Agung Trisetyarso, Ph.D.) 27 Mei 20245 Juli 2024 Dokumen Asli ABSTRAK PENGEMBANGAN ALGORITMA HYBRID QUANTUM ANNEALING UNTUK OPTIMASI ENSEMBLE LEARNING Oleh Lenny Putri Yulianti NIM: 33221007 (Program Studi Doktor Teknik Elektro dan Informatika) Quantum annealing (QA) adalah pendekatan komputasi kuantum yang banyak digunakan untuk menangani persoalan optimasi dan probabilistic sampling. Meskipun QA masih tergolong baru, pendekatan ini telah banyak diterapkan untuk optimasi persoalan machine learning, seperti clustering, support vector machines, dan lain-lain. Sebagian besar penelitian yang telah mengimplementasikan QA pada domain machine learning menunjukkan bahwa QA memberikan kinerja prediksi yang lebih baik dibandingkan metode state-of-the-art klasik. Akan tetapi, persoalan machine learning yang dioptimasi dengan QA umumnya hanya persoalan yang menggunakan satu learner. QA memiliki peluang yang menjanjikan untuk menangani persoalan machine learning yang terdiri atas banyak learner, yaitu ensemble learning. Fundamental dari pembuatan model ensemble adalah menggunakan strategi “perturb and combine” di mana model ensemble yang baik harus memperhatikan trade-off optimal antara akurasi dan diversity dari trained learners. Salah satu metode state-of-the-art yang banyak digunakan untuk meningkatkan diversity dari trained learners pada model ensemble adalah metode clustering balancing dengan over-sampling. Akan tetapi, terdapat kelemahan dari metode clustering balancing yang sudah ada, yaitu 1) hasil cluster yang tidak selalu strong dan balanced, 2) adanya persentase similarity clusters yang lebih tinggi, serta 3) adanya persentase korelasi trained learners yang lebih tinggi karena metode ini melakukan penambahan data pada kelas minor dengan menduplikasi beberapa sampel yang memengaruhi proses training. Seluruh trained learners yang dihasilkan untuk membentuk ensemble juga belum tentu memberikan kontribusi positif pada peningkatan akurasi. Pemilihan sekumpulan trained learners yang optimal perlu dilakukan agar kinerja ensemble semakin meningkat. Hal ini berpeluang untuk dioptimasi menggunakan QA karena QA ditemukan berpotensi untuk memberikan kinerja akurasi dan efisiensi yang lebih baik pada persoalan optimasi dibandingkan metode state-of-the-art klasik. Akan tetapi, implementasi QA juga memiliki beberapa kelemahan, yaitu: 1) adanya kemungkinan tetap terjebak pada minimum lokal, 2) adanya kemungkinan overfitting pada solusi awal, serta 3) sensitivitas terhadap parameter. Oleh karena itu, diperlukan juga peningkatan kualitas dari implementasi QA. Dokumen Asli Berdasarkan persoalan dan peluang yang telah dianalisis, penelitian ini mengusulkan pengembangan algoritma hybrid QA yang berfokus untuk menangani tiga persoalan ensemble learning, yaitu: 1) pembuatan strong dan balanced clusters menggunakan algoritma hybrid QA yang mengombinasikan pendekatan clustering balancing dan QA; 2) pemilihan clusters optimal menggunakan algoritma QA; serta 3) pemilihan trained learners optimal menggunakan algoritma QA. Ketiga usulan metode ini merupakan satu kesatuan proses untuk menghasilkan model ensemble yang optimal. Selain itu, pada proses pemilihan clusters dan trained learners, diterapkan juga proses re-sampling pada algoritma QA yang diusulkan untuk menangani tiga kelemahan dari implementasi QA dan meningkatkan kualitas ensemble. Algoritma usulan dievaluasi menggunakan empat dataset dari UCI repository, satu dataset dari Airbus – BMW Group, serta satu dataset real. Evaluasi dilakukan berdasarkan empat aspek utama: ukuran, akurasi, diversity, dan waktu komputasi ensemble. Algoritma usulan dibandingkan dengan beberapa metode ensemble benchmark, yaitu bagging, AdaBoost, clustering, clustering balancing, dan metode ensemble yang menggunakan particle swarm optimization. Selain itu, hasil eksperimen juga dievaluasi dengan enam single learner yang menjadi base classifiers, yaitu artificial neural network, support vector machines, linear discriminant analysis, decision trees, K-nearest neighbors, dan Naïve Bayes. Hasil evaluasi menunjukkan bahwa algoritma usulan memiliki rata-rata akurasi tertinggi, yaitu 72.40%, dengan confidence interval 95%. Penelitian ini pun menganalisis adanya tiga faktor yang memengaruhi dan dipengaruhi oleh peningkatan akurasi ini, yaitu ukuran ensemble, nilai diversity, dan waktu komputasi. Algoritma usulan ditemukan dapat mereduksi ukuran ensemble awal meskipun persentase penurunannya tidak sebesar metode benchmark particle swarm optimization. Selain itu, algoritma usulan juga memiliki rata-rata nilai diversity paling tinggi dibandingkan seluruh metode benchmark di mana nilai diversity yang tinggi dan diiringi dengan pengurangan bias dapat mendorong peningkatan akurasi. Algoritma usulan juga ditemukan memiliki waktu komputasi yang lebih cepat dibandingkan metode benchmark yang melakukan pruning dengan algoritma metaheuristik klasik particle swarm optimization. Kata kunci: hybrid, quantum annealing, optimasi, ensemble learning Dokumen Asli ABSTRACT THE DEVELOPMENT OF HYBRID QUANTUM ANNEALING ALGORITHM FOR OPTIMIZING ENSEMBLE LEARNING By Lenny Putri Yulianti NIM: 33221007 (Doctoral Program in Electrical Engineering and Informatics) Quantum annealing (QA) is a quantum computing approach widely used to address optimization problems and probabilistic sampling. Despite being relatively new, this approach has been extensively applied to optimize machine learning problems such as clustering, support vector machines, and others. Most studies implementing QA in the machine learning domain indicate that QA provides better predictive performance compared to classical state-of-the-art methods. However, QA optimization in machine learning typically focuses on problems involving a single learner. QA holds promising potential for addressing machine learning problems with multiple learners, namely ensemble learning. The fundamental concept behind ensemble model creation involves the "perturb and combine" strategy, where a good ensemble model must carefully consider the optimal trade-off between accuracy and diversity of trained learners. One widely used state-of-the-art method to enhance the diversity of trained learners in ensemble models is the clustering balancing method with over-sampling. However, there are drawbacks to the existing clustering balancing method, such as 1) clusters that are not always strong and balanced, 2) higher similarity cluster percentages, and 3) higher correlation percentages among trained learners due to the addition of data in the minor class by duplicating some samples, affecting the training process. Not all trained learners generated to form the ensemble necessarily contribute positively to accuracy improvement. The selection of an optimal set of trained learners is crucial for enhancing ensemble performance. This presents an opportunity for optimization using QA because QA has the potential to offer better accuracy and efficiency in optimization problems compared to classical state-of- the-art methods. However, QA implementation also has some drawbacks, including 1) the possibility of getting stuck in local minima, 2) potential overfitting in initial solutions, and 3) sensitivity to parameters. Therefore, there is a need for quality improvement in QA implementation. Based on the analyzed challenges and opportunities, this research proposes the development of a hybrid QA algorithm focusing on addressing three ensemble learning problems: 1) creating strong and balanced clusters using a hybrid QA algorithm that combines clustering balancing and QA approaches; 2) selecting optimal clusters using a QA algorithm; and 3) choosing optimal trained learners Dokumen Asli using a QA algorithm. These three proposed methods form a unified process to produce an optimal ensemble model. Additionally, in the process of selecting clusters and trained learners, a re-sampling process is applied to the proposed QA algorithm to address three weaknesses in QA implementation and improve ensemble quality. The proposed algorithm was evaluated using four datasets from the UCI repository, one dataset from the Airbus – BMW Group, and one real-world dataset. The evaluation focused on four main aspects: size, accuracy, diversity, and ensemble computation time. The proposed algorithm was compared with several benchmark ensemble methods, including bagging, AdaBoost, clustering, clustering balancing, and ensemble methods using particle swarm optimization. Additionally, the experimental results were evaluated using six single learners as base classifiers: artificial neural network, support vector machines, linear discriminant analysis, decision trees, k-nearest neighbors, and Naïve Bayes. The evaluation results showed that the proposed algorithm achieved the highest average accuracy, at 72.40%, with a 95% confidence interval. This study also analyzed three factors that influence and are influenced by this accuracy improvement: ensemble size, diversity value, and computation time. The proposed algorithm was found to reduce the initial ensemble size, although the reduction percentage was not as significant as that of the particle swarm optimization benchmark method. Moreover, the proposed algorithm achieved the highest average diversity value compared to all benchmark methods, where high diversity values accompanied by reduced bias can lead to increased accuracy. The proposed algorithm also demonstrated faster computation times compared to benchmark methods that use classical particle swarm optimization for pruning. Keywords: hybrid, quantum annealing, optimization, ensemble learning.