Foto oleh DeepMind on Unsplash
Perkalian matriks adalah operasi dasar yang digunakan di banyak sistem, mulai dari jaringan saraf hingga rutinitas komputasi ilmiah. Menemukan algoritme yang efisien dan terbukti benar untuk perkalian matriks dapat berdampak besar dalam membuat perhitungan lebih cepat dan lebih efisien, tetapi merupakan tugas yang sangat menantang. Ruang untuk kemungkinan algoritme sangat besar, dan metode tradisional untuk menemukan algoritme, seperti heuristik rancangan manusia atau pencarian kombinatorial, seringkali tidak optimal.
DeepMindSolusi berbasis AI yang baru-baru ini diusulkan untuk pencarian otomatis jauh melampaui intuisi manusia. Solusinya terdiri dari agen pembelajaran penguatan mendalam yang disebut AlphaTensor, yang dibangun di atasnya AlfaZero. Agen ini dilatih untuk memainkan game pemain tunggal, TensorGame, yang tujuannya adalah untuk menemukan algoritme yang efisien secara komputasi untuk perkalian matriks.
AlphaTensor sangat baik dalam menangani matriks besar dengan mendekomposisi perkalian matriks besar menjadi perkalian yang lebih kecil. Selain itu, AlphaTensor dapat digunakan untuk mencapai kinerja tercanggih untuk perkalian matriks setelah disetel dengan baik pada perangkat keras tertentu.
AlphaTensor memiliki potensi besar untuk mempercepat komputasi deep learning. Dalam pembelajaran mendalam, banyak operasi yang memakan waktu dapat dipetakan ke perkalian matriks. Dengan menggunakan AlphaTensor untuk mengoptimalkan operasi ini, kinerja keseluruhan model pembelajaran mendalam dapat ditingkatkan secara signifikan.
Baru-baru ini, OpenAlphaTensor, the implementasi open source pertama dari AlphaTensor, dirilis, yang dapat merevolusi kekuatan komputasi model deep learning.
Tensor Perkalian Matriks
Untuk non-ahli dalam pengoptimalan perkalian matriks, mungkin tidak mudah untuk memahami bagaimana operasi seperti perkalian matriks dapat dipetakan dalam tensor tiga dimensi. Saya akan mencoba menjelaskannya dengan kata-kata sederhana dan dengan contoh.
Mari pertimbangkan produk C = A*B, di mana untuk kesederhanaan A dan B adalah matriks persegi berukuran N. Operasi perkalian dapat dipetakan dalam bentuk tensor 3D (N^2, N^2, N^2). Dimensi tensor pertama mewakili matriks pipih A, dimensi kedua matriks pipih B, dan dimensi ketiga matriks pipih C.
Tensor hanya memiliki nilai biner (baik 1 atau 0) untuk setiap entri. Perhatikan bahwa tensor mewakili operasi perkalian, sehingga tidak bergantung pada nilai matriks A dan B.
Setiap entri tensor sesuai dengan koefisien operasi. Misalnya, untuk menghitung C[1,1], perlu mengalikan A[1,1] dan B[1,1]. Oleh karena itu, entri tensor [0,0,0], yang sesuai dengan A[1,1], B[1,1] dan C[1,1], akan memiliki nilai 1. Sebaliknya, untuk menghitung C[1,1 ,2,1], A[1] tidak diperlukan. Jadi, baris tensor T[N+0, :, XNUMX] hanya akan berisi nol.
Gambar di bawah menunjukkan contoh tensor untuk N=2.
Gambar dari DeepMind kertas diterbitkan dalam Alam
Seperti yang ditunjukkan pada (b) dan (c) pada gambar di atas, dimungkinkan untuk mengimplementasikan algoritme untuk menghitung produk menggunakan dekomposisi tensor 3D. Lebih khusus lagi, algoritma di bawah ini dapat digunakan untuk mengubah dekomposisi tensor (matriks U, V, W) menjadi algoritma perkalian matriks.
Algoritma meta yang diparameterisasi untuk menghitung produk matriks C=AB yang diperkenalkan di DeepMind kertas
Permainan Tensor
Masalah menemukan algoritme yang efisien untuk perkalian matriks sangat menantang karena jumlah kemungkinan algoritme yang dipertimbangkan jauh lebih besar daripada jumlah atom di alam semesta, bahkan untuk kasus kecil perkalian matriks.
DeepMind mengubah masalah ini menjadi permainan pemain tunggal, dan menyebutnya TensorGame. Dalam permainan ini, pemain memilih cara menggabungkan entri matriks yang berbeda untuk mengalikannya. Skor diberikan berdasarkan jumlah operasi yang diperlukan untuk mencapai hasil perkalian yang benar. Permainan berakhir saat tensor nol tercapai atau saat jumlah gerakan maksimum telah dilakukan. Faktorisasi akhir dievaluasi berdasarkan estimasi peringkat residu dan kriteria pengoptimalan tertentu, seperti kompleksitas waktu asimtotik atau runtime praktis.
Posisi awal dalam TensorGame sesuai dengan Tensor Perkalian Matriks yang diekspresikan secara acak.
Di setiap langkah t permainan, pemain menuliskan tiga vektor
, yang menentukan tensor peringkat-1 . Keadaan permainan diperbarui dengan mengurangi vektor yang dipilih oleh pemain:
dimana
adalah Tensor Perkalian Matriks.Jika permainan berakhir pada langkah p, ini berarti Tensor Perkalian Matriks
dapat didekomposisi menjadi tensor peringkat-1 p , yaitu setidaknya memiliki peringkat p.TensorGame kemudian dapat diartikan sebagai algoritme dekomposisi peringkat dan AlphaTensor dapat dilihat sebagai algoritme untuk memperkirakan peringkat tensor.
Arsitektur AlphaTensor
Sejauh ini kita telah mempelajari TensorGame dan mengklarifikasi bagaimana solusinya dapat dilihat sebagai algoritme perkalian matriks. Sekarang mari jelajahi konsep utama AlphaTensor, algoritme yang digunakan untuk game.
Arsitektur AlphaTensor pada dasarnya adalah arsitektur Transformer encoder-decoder di mana:
- pembuat enkode mengambil status permainan sebagai masukan , n tindakan sebelumnya yang diambil oleh model (biasanya n=7), dan indeks waktu t dari tindakan saat ini. Informasi ditumpuk bersama dalam tensor dengan bentuk (n+1, N^2, N^2, N^2). Tensor ini kemudian dibentuk ulang dan diubah (menggunakan tiga lapisan linier) dalam bentuk tensor (N^2, N^2, c) di mana c adalah dimensi bagian dalam model.
- dekoder menghasilkan tindakan n_steps dari vektor tersemat yang diberikan oleh pembuat enkode dengan cara auto-regresif. Setiap tindakan sesuai dengan token dari kembar tiga mewakili salah satu triplet yang menguraikan tensor game (yaitu mengurangi peringkatnya)
Model dilatih dengan bergantian propagasi balik dan akting model. Akting model digunakan untuk menghasilkan data yang kemudian digunakan untuk melatih model. Dalam praktiknya, model dilatih dengan campuran data yang dihasilkan secara sintetik dan data yang dihasilkan oleh model selama akting. Langkah akting dilakukan dengan mengambil tensor 3D yang sesuai dengan operasi matriks dan memainkan game n_actors di dalamnya. Setiap aktor memainkan sebuah permainan baik atas dasar standar atau atas dasar alternatif (perubahan dasar diterapkan dengan probabilitas tertentu). Hasilnya kemudian dikumpulkan dan dapat digunakan pada langkah pelatihan dengan data sintetik.
Langkah akting didasarkan pada Monte Carlo Tree Search (MCTS) AlphaZero, yang dimodifikasi untuk mendukung ruang aksi yang besar. Singkatnya, sebelum memilih tindakan, jalur n_sims dieksplorasi dari keluaran model dengan eksplorasi maksimum di masa depan sebanyak 5 langkah. Probabilitas yang dihasilkan oleh model kemudian disesuaikan dengan jalur yang dihasilkan. Kemudian tindakan dengan jalur masa depan yang paling menjanjikan dipilih untuk melanjutkan permainan.
Saat melatih model, hadiah sebenarnya adalah hadiah negatif (penalti). Nilai absolutnya meningkat dengan setiap langkah tambahan yang diperlukan untuk menyelesaikan permainan. Jika model mengambil m langkah untuk menyelesaikan TensorGame, hadiah yang terkait dengan game tersebut adalah r=-m. Jika model tidak dapat menyelesaikan TensorGame dalam langkah max_rank, hadiah dihitung dengan memperkirakan peringkat tensor yang tersisa. Rank diperkirakan sebagai jumlah dari rank matriks yang menyusun tensor. Estimasi adalah batas atas pada peringkat sebenarnya dari tensor.
Saat menyempurnakan model, imbalan penalti pada status terminal juga harus memperhitungkan latensi algoritme yang dihasilkan oleh model. Rumus imbalannya menjadi rt'=rt+λbt, dengan rt adalah skema imbalan yang dijelaskan sebelumnya, bt adalah imbalan acuan (hanya bukan nol pada keadaan terminal), dan λ adalah koefisien yang ditentukan pengguna.
Percepatan (%) algoritme yang ditemukan AlphaTensor yang disesuaikan untuk GPU dan TPU, diekstraksi dari makalah DeepMind. Percepatan diukur relatif terhadap perkalian matriks standar (misalnya cuBLAS untuk GPU) pada perangkat keras yang sama dan dibandingkan dengan Algoritma Strassen-square. Sumber: DeepMind.
Saya baru saja dirilis BukaAlphaTensor, implementasi sumber terbuka pertama dari AlphaTensor. Pada bagian ini saya akan berjalan melalui implementasi. Seperti yang telah kita bahas sebelumnya, arsitektur AlphaTensor cukup mudah, berdasarkan trafo standar dengan arsitektur encoder-decoder. Komponen paling menarik dari AlphaTensor adalah lapisan pertama di bagian pembuat enkode dan cara pengambilan sampel tindakan.
Mari kita mulai dengan lapisan penyandian pertama.
# x.size = (N, T, S, S, S)
# scalars.size = (N, s)
batch_size = x.shape[0]
S = x.shape[-1]
T = x.shape[1]
x1 = x.permute(0, 2, 3, 4, 1).reshape(batch_size, S, S, S * T)
x2 = x.permute(0, 4, 2, 3, 1).reshape(batch_size, S, S, S * T)
x3 = x.permute(0, 3, 4, 2, 1).reshape(batch_size, S, S, S * T)
input_list = [x1, x2, x3]
for i in range(3): temp = self.linears_1[i](scalars).reshape(batch_size, S, S, 1) input_list[i] = torch.cat([input_list[i], temp], dim=-1) input_list[i] = self.linears_2[i](input_list[i])
x1, x2, x3 = input_list
Dalam cuplikan di atas, kami menunjukkan bagaimana tensor input didekomposisi menjadi tiga tensor, yang kemudian digunakan sebagai input kueri, kunci, dan nilai dari lapisan transformator.
- Di tiga dimensi tensor yang mewakili matriks rata (A, B, C), tensor input diratakan sepanjang setiap dimensi bersama dengan dimensi yang mewakili tindakan sebelumnya. Dengan cara ini, di setiap salinan tensor input yang diratakan, dimensi yang dipilih adalah agregasi dari nilai T-1 terakhir dan nilai sebenarnya, untuk semua nilai S dari dimensi yang dipilih, dengan S=N^2. Secara filosofis, seolah-olah, untuk setiap dimensi, kita fokus pada apa yang terjadi pada tindakan sebelumnya di dimensi itu.
- Skalar dipetakan dalam tiga ruang berdimensi S^2 yang berbeda, kemudian dibentuk ulang untuk digabungkan dengan tensor yang diperoleh pada titik sebelumnya. Secara konseptual, skalar dipetakan ke ruang penyematan berdimensi S^2, dan kemudian informasi yang disematkan dipotong-potong menjadi vektor S dan ditumpuk bersama, mirip dengan apa yang terjadi pada teks saat diberi token.
- Token skalar digabungkan dengan tensor input yang direstrukturisasi, lalu diberikan sebagai input ke lapisan linear untuk memetakan informasi fokus skalar+sejarah saluran dalam dimensi internal model.
Ketiga langkah ini dapat diartikan sebagai cara memberikan model baik informasi tentang skalar (seperti dalam langkah waktu TensorGame) dan fokus pada tindakan sebelumnya untuk setiap saluran.
Mengenai cara tindakan dihasilkan, menarik untuk dicatat bahwa AlphaTensor menghasilkan sebagai keluaran triplet u, v, w, yang bertujuan untuk mengurangi peringkat tensor. Ketiga vektor berukuran S dan karena digabungkan, model harus menghasilkan vektor berukuran 3*S. AlphaTensor dilatih dengan algoritme RL, jadi semua tindakan yang mungkin harus dinyatakan dalam probabilitas dalam ruang yang disebutkan, yaitu model menghasilkan probabilitas atas tindakan yang berbeda. Ini berarti bahwa setiap vektor dalam ruang 3S harus dipetakan ke tindakan yang berbeda. Ini menghasilkan ruang tindakan dengan ukuran |F|^(3S), di mana |F| adalah banyaknya nilai berbeda yang dapat diambil oleh elemen u, v, w. Biasanya, nilai dibatasi ke (-2, -1, 0, 1, 2), menghasilkan kardinalitas 5 elemen.
Inilah tantangan besar: untuk menghasilkan probabilitas aksi untuk produk matriks dari matriks ukuran 5 kita memerlukan memori 5^75 * 4 byte, yang berarti ~10^44 GB memori. Jelas, kami tidak dapat mengelola ruang aksi sebesar itu.
Bagaimana kita memecahkan masalah? Untuk mengurangi jejak memori dari probabilitas tindakan, kita dapat membagi triplet menjadi potongan yang lebih kecil, "membuat token", dan memperlakukan potongan tersebut sebagai token yang dihasilkan dalam arsitektur transformator, yaitu token diberikan sebagai input ke dekoder dalam regresi otomatis. jalan. Pada contoh di atas kita dapat membagi triplet menjadi 15 bagian, mengurangi konsumsi memori menjadi 15 * 5^(75/15) * 4, yaitu 187.5 KB.
def _eval_forward(self, e: torch.Tensor): bs = e.shape[0] future_g = ( torch.zeros((bs, self.n_samples, self.n_steps)).long().to(e.device) ) ps = torch.ones((bs, self.n_samples)).to(e.device) e = e.unsqueeze(1).repeat(1, self.n_samples, 1, 1) future_g = future_g.view(-1, self.n_steps) ps = ps.view(-1) e = e.view(-1, e.shape[-2], e.shape[-1]) for i in range(self.n_steps): o_s, z_s = self.core(future_g[:, : i + 1], e) future_g[:, i], p_i = sample_from_logits(o_s[:, i]) ps *= p_i future_g = future_g.view(bs, self.n_samples, self.n_steps) ps = ps.view(bs, self.n_samples) return ( future_g, ps, z_s[:, 0].view(bs, self.n_samples, *z_s.shape[2:]).mean(1), )
Di atas kami menampilkan cuplikan kode untuk menghasilkan tindakan penuh. Dalam kode, self.core berisi lapisan decoder dan tensor e mewakili output dari lapisan encoder. Nol dapat dianggap sebagai token dalam model NLP dan tindakan n_steps yang mewakili potongan n_steps dihasilkan secara progresif.
Model mengembalikan tiga kuantitas:
- Tindakan yang dihasilkan
- Probabilitas yang terkait dengan tindakan penuh
- Logits dihasilkan untuk menghasilkan tindakan pertama (potongan pertama) yang akan digunakan untuk menghitung nilai model.
Perlu menghabiskan beberapa kata pada parameter n_samples. Parameter tersebut digunakan untuk langkah akting dan memungkinkan model untuk menghasilkan versi yang berbeda dari triplet yang kemudian akan digunakan untuk menjelajahi ruang aksi dalam algoritma Monte Carlo Tree Search yang digunakan dalam proses Acting. Tindakan berbeda n_samples diambil sampelnya sesuai dengan kebijakan yang dihasilkan oleh model.
Langkah Akting
Bagian paling rumit dari keseluruhan algoritme mungkin adalah langkah Akting yang digunakan untuk menyelesaikan TensorGame. Algoritme tidak dijelaskan secara mendalam dalam makalah AlphaTensor, karena didasarkan pada beberapa makalah DeepMind sebelumnya yang baru saja dikutip dan diberikan sebagaimana diketahui. Di sini, saya akan merekonstruksi semua bagian yang hilang dan menjelaskan langkah demi langkah implementasi kami.
Kami dapat mengatur langkah-langkah akting dalam tiga komponen berbeda:
- Pencarian Pohon Monte-Carlo
- Simulasi permainan
- Komputasi kebijakan yang ditingkatkan
Mari kita analisa satu per satu.
Pencarian Pohon Monte-Carlo (MCTS)
Monte Carlo Tree Search (MCTS) adalah teknik kecerdasan buatan yang banyak digunakan untuk bermain game, khususnya dalam permainan papan dan video game. Algoritme membuat pohon permainan yang mensimulasikan potensi gerakan dan hasil serta menggunakan pengambilan sampel acak untuk mengevaluasi hadiah yang diharapkan untuk setiap gerakan. Algoritme kemudian secara iteratif memilih langkah dengan imbalan tertinggi yang diharapkan dan mensimulasikan hasil hingga mencapai status terminal atau kondisi berhenti yang ditentukan. Simulasi digunakan untuk memperkirakan kemungkinan menang untuk setiap gerakan dan memandu proses pengambilan keputusan. MCTS telah terbukti efektif dalam permainan yang kompleks di mana jumlah kemungkinan gerakan dan hasil yang besar, dan telah digunakan dalam sistem AI permainan yang sukses, seperti AlphaGo.
Di AlphaTensor, versi modifikasi dari MCTS asli digunakan. Secara khusus, alih-alih memilih tindakan secara acak dari seluruh ruang tindakan, tindakan dipilih di antara subset yang dihasilkan langsung oleh model (melalui n_samples yang disajikan sebelumnya). Koreksi terhadap pemutakhiran kebijakan kemudian diterapkan dalam langkah perhitungan Kebijakan yang Disempurnakan.
Dalam implementasi kami, kami memutuskan untuk menyimpan semua informasi tentang pohon Monte-Carlo dalam kamus yang memiliki kunci versi hash dari status TensorGame dan sebagai nilai informasi yang terkait dengan status itu sendiri. Setiap langkah Monte-Carlo dimulai dari sebuah node dan mensimulasikan mini-game n_sim, menjelajahi masa depan dengan cakrawala 5 gerakan. Jika node sudah dieksplorasi pada simulasi sebelumnya, n_sim disesuaikan dengan jumlah eksplorasi sebelumnya. Untuk setiap node, jumlah kunjungan disimpan dalam tensor N_s_a, karena tensor ini berisi jumlah kunjungan per tindakan anak node (di antara yang diambil sampelnya oleh model).
def monte_carlo_tree_search( model: torch.nn.Module, state: torch.Tensor, n_sim: int, t_time: int, n_steps: int, game_tree: Dict, state_dict: Dict,
): """Runs the monte carlo tree search algorithm. Args: model (torch.nn.Module): The model to use for the simulation. state (torch.Tensor): The initial state. n_sim (int): The number of simulations to run. t_time (int): The current time step. n_steps (int): The maximum number of steps to simulate. game_tree (Dict): The game tree. state_dict (Dict): The dictionary containing the states. """ state_hash = to_hash(extract_present_state(state)) if state_hash in state_dict: with torch.no_grad(): N_s_a = state_dict[state_hash][3] n_sim -= int(N_s_a.sum()) n_sim = max(n_sim, 0) for _ in range(n_sim): simulate_game(model, state, t_time, n_steps, game_tree, state_dict) # return next state possible_states_dict, _, repetitions, N_s_a, q_values, _ = state_dict[ state_hash ] possible_states = _recompose_possible_states(possible_states_dict) next_state_idx = select_future_state( possible_states, q_values, N_s_a, repetitions, return_idx=True ) next_state = possible_states[next_state_idx] return next_state
Kode di atas menunjukkan penerapan algoritme kami. Untuk masalah penyederhanaan kode, koreksi kebijakan dilakukan dalam fungsi simulation_game.
Simulasi Permainan
Fungsi simulation_game bertanggung jawab untuk menjelajahi pohon yang terdiri dari node yang mewakili status TensorGame tertentu. Itu juga menjalankan model setiap kali node daun ditemui dan menyimpan semua informasi node dalam kamus state_dict. Mari kita lihat lebih dalam implementasinya:
@torch.no_grad()
def simulate_game( model, state: torch.Tensor, t_time: int, max_steps: int, game_tree: Dict, states_dict: Dict, horizon: int = 5,
): """Simulates a game from a given state. Args: model: The model to use for the simulation. state (torch.Tensor): The initial state. t_time (int): The current time step. max_steps (int): The maximum number of steps to simulate. game_tree (Dict): The game tree. states_dict (Dict): The states dictionary. horizon (int): The horizon to use for the simulation. """ idx = t_time max_steps = min(max_steps, t_time + horizon) state_hash = to_hash(extract_present_state(state)) trajectory = [] # selection while state_hash in game_tree: ( possible_states_dict, old_idx_to_new_idx, repetition_map, N_s_a, q_values, actions, ) = states_dict[state_hash] possible_states = _recompose_possible_states(possible_states_dict) state_idx = select_future_state( possible_states, q_values, N_s_a, repetition_map, return_idx=True ) trajectory.append((state_hash, state_idx)) # state_hash, action_idx future_state = extract_present_state(possible_states[state_idx]) state = possible_states[state_idx] state_hash = to_hash(future_state) idx += 1 # expansion if idx = max_steps: trajectory.append((state_hash, None)) if not game_is_finished(extract_present_state(state)): state = state.to(model.device) scalars = get_scalars(state, idx).to(state.device) actions, probs, q_values = model(state, scalars) ( possible_states, cloned_idx_to_idx, repetitions, not_dupl_indexes, ) = extract_children_states_from_actions( state, actions, ) not_dupl_actions = actions[:, not_dupl_indexes].to("cpu") not_dupl_q_values = torch.zeros(not_dupl_actions.shape[:-1]).to( "cpu" ) N_s_a = torch.zeros_like(not_dupl_q_values).to("cpu") present_state = extract_present_state(state) states_dict[to_hash(present_state)] = ( _reduce_memory_consumption_before_storing(possible_states), cloned_idx_to_idx, repetitions, N_s_a, not_dupl_q_values, not_dupl_actions, ) game_tree[to_hash(present_state)] = [ to_hash(extract_present_state(fut_state)) for fut_state in possible_states ] leaf_q_value = q_values else: leaf_q_value = -int(torch.linalg.matrix_rank(state).sum()) # backup backward_pass(trajectory, states_dict, leaf_q_value=leaf_q_value)
Setiap simulasi dibagi menjadi tiga bagian:
- Seleksi
- Perluasan
- backup
Di bagian pemilihan, simulasi dijalankan pada simpul pohon yang sudah dibuat, dan simpul berikut dipilih menggunakan fungsi berikut:
def select_future_state( possible_states: List[torch.Tensor], q_values: torch.Tensor, N_s_a: torch.Tensor, repetitions: Dict[int, list], c_1: float = 1.25, c_2: float = 19652, return_idx: bool = False,
) -> torch.Tensor: """Select the future state maximizing the upper confidence bound."""
# q_values (1, K, 1) pi = torch.tensor( [ len(repetitions[i]) for i in range(len(possible_states)) if i in repetitions ] ).to(q_values.device) ucb = q_values.reshape(-1) + pi * torch.sqrt( torch.sum(N_s_a) / (1 + N_s_a) ) * (c_1 + torch.log((torch.sum(N_s_a) + c_2 + 1) / c_2)) if return_idx: return ucb.argmax() return possible_states[ucb.argmax()]
Dalam praktiknya, tindakan memaksimalkan fungsi ucb:
untuk keadaan tertentu dipilih. Di sini Q mewakili nilai Q yang dihasilkan oleh model dan π mewakili distribusi acak atas tindakan yang diambil sampelnya menggunakan kebijakan model. N(s, a) merepresentasikan jumlah kunjungan node ke aksi a dari node s.
Setelah fase pemilihan mencapai simpul daun, jika simulasi belum mencapai kondisi terminal (dalam hal eksplorasi maksimum, yaitu cakrawala masa depan, atau akhir permainan), model ini kemudian digunakan untuk memilih simpul alternatif n_samples (mereka akan menjadi simpul daun). node dalam iterasi berturut-turut). Ini disebut fase ekspansi, karena node baru ditambahkan ke pohon. Kemudian, tidak ada lagi node yang dieksplorasi dalam simulasi saat ini, tetapi nilai q_leaf dikirim ke langkah simulasi berikut: cadangan.
Backup adalah tahap akhir dari setiap simulasi. Selama pencadangan, jika simpul daun adalah status terminal, hadiah akhir dihitung; jika tidak, nilai q daun digunakan sebagai perkiraan hadiah. Kemudian hadiah disebarkan kembali pada lintasan simulasi dengan memperbarui status q_values dan memperbarui penghitung kunjungan N(s, a). Dalam cuplikan di bawah ini kami menampilkan kode untuk propagasi balik hadiah.
def backward_pass(trajectory, states_dict, leaf_q_value: torch.Tensor): """Backward pass of the montecarlo algorithm"""
reward = 0 for idx, (state, action_idx) in enumerate(reversed(trajectory)): if action_idx is None: # leaf node reward += leaf_q_value else: ( _, old_idx_to_new_idx, _, N_s_a, q_values, _, ) = states_dict[state] if isinstance(reward, torch.Tensor): reward = reward.to(q_values.device) action_idx = int(action_idx) if action_idx in old_idx_to_new_idx: not_dupl_index = old_idx_to_new_idx[int(action_idx)] else: not_dupl_index = action_idx reward -= 1 q_values[:, not_dupl_index] = ( N_s_a[:, not_dupl_index] * q_values[:, not_dupl_index] + reward ) / (N_s_a[:, not_dupl_index] + 1) N_s_a[:, not_dupl_index] += 1
Komputasi Kebijakan yang Ditingkatkan
Setelah semua simulasi dijalankan dan MCTS menawarkan snapshot yang menarik dalam waktu dekat, saatnya memperbarui kebijakan yang terkait dengan node yang diprediksi dan mengembalikannya, sehingga dapat digunakan selama pelatihan. Kebijakan yang ditingkatkan, mengikuti metode yang dijelaskan dalam Hubert dkk, digunakan untuk mengelola ruang tindakan yang besar. Bahkan, untuk ruang pencarian kecil, dimungkinkan selama MCTS mengambil sampel tindakan secara acak dari ruang tindakan dan mengevaluasi dampaknya. Pendekatan serupa dalam ruang tindakan yang jauh lebih besar akan menyebabkan semua lintasan menyimpang di jalur yang berbeda dan akan membutuhkan jumlah lintasan yang tak terbatas untuk mendapatkan statistik yang bermakna dan kemudian memperbarui kebijakan. Karena di sini kita menggunakan sample-MCTS untuk menghindari dispersi, yaitu tindakan n_samples diambil sampelnya sesuai dengan kebijakan model dan kemudian MCTS hanya memilih salah satu tindakan sampel sambil menjelajahi pohon, kita perlu memperhitungkan koreksi sampel saat menghitung kebijakan terakhir yang diperbarui yang akan digunakan saat melatih model.
Dalam praktiknya, kebijakan yang ditingkatkan dihitung sebagai
dimana
def compute_improved_policy( state_dict: Dict, states: List[str], model_n_steps: int, model_n_logits: int, N_bar: int,
): """Compute the improved policy given the state_dict, the list of states. The improved policy is computed as (N_s_a / N_s_a.sum())^(1/tau) where tau is (log(N_s_a.sum()) / log(N_bar)) if N_s_a.sum() > N_bar else 1. """ policies = torch.zeros(len(states), model_n_steps, model_n_logits) N_bar = torch.tensor(N_bar) for idx, state in enumerate(states): N_s_a = state_dict[state][3] actions = state_dict[state][5] if N_s_a.sum() > N_bar: tau = (torch.log(N_s_a.sum()) / torch.log(N_bar)).item() else: tau = 1 N_s_a = N_s_a ** (1 / tau) improved_policy = N_s_a / N_s_a.sum() for sample_id in range(actions.shape[1]): action_ids = actions[0, sample_id] for step_id, action_id in enumerate(action_ids): policies[idx, step_id, action_id] += improved_policy[ 0, sample_id ] return policies
Perhatikan bahwa dalam implementasi kami setelah menghitung kebijakan dari tensor N_s_a, kami harus memetakannya kembali ke tensor aksi asli. Faktanya, N_s_a hanya mempertimbangkan tindakan yang diambil sampelnya oleh model, sedangkan kebijakan akhir harus mengandung probabilitas juga untuk tindakan yang tidak dieksplorasi.
Perbedaan sehubungan dengan algoritma pelatihan ChatGPT
AlphaTensor adalah anggota terbaru dari keluarga metode kecerdasan buatan AlphaGo/AlphaZero oleh DeepMind. Metode ini didasarkan pada algoritma Monte Carlo Tree Search (MCTS), yang telah disempurnakan dan ditingkatkan oleh DeepMind untuk menangani tugas-tugas yang semakin kompleks. Sistem AI lainnya, ChatGPT OpenAI, yang telah menimbulkan banyak perhatian karena kinerjanya yang luar biasa, dilatih dengan pendekatan berbeda, yang disebut Pembelajaran Penguatan dengan Umpan Balik Manusia (RLHF).
RLHF adalah teknik penyempurnaan yang digunakan untuk menyetel model bahasa agar mengikuti serangkaian instruksi tertulis. Ini menggunakan preferensi manusia sebagai sinyal hadiah untuk menyempurnakan model, sehingga menyelaraskan perilaku model bahasa dengan preferensi yang dinyatakan dari sekelompok orang tertentu, daripada beberapa gagasan yang lebih luas tentang 'nilai-nilai kemanusiaan'.
Sebaliknya, MCTS adalah algoritma pencarian berbasis pohon yang digunakan untuk menentukan gerakan optimal dalam permainan. Ini mensimulasikan gerakan potensial dan memperbarui nilai setiap gerakan berdasarkan hasil mereka, memandu pemilihan gerakan terbaik.
RLHF mengumpulkan data dari demonstrasi yang ditulis manusia dan perbandingan berlabel manusia antara model AI, dan melatih model hadiah untuk memprediksi preferensi sekelompok orang tertentu. Model hadiah kemudian digunakan untuk menyempurnakan model AI. MCTS, di sisi lain, menggunakan simulasi dan evaluasi untuk menentukan keputusan terbaik.
Meskipun berbeda pendekatan, RLHF dan MCTS juga memiliki kesamaan. Kedua teknik kecerdasan buatan menggunakan metode pengambilan keputusan dan pemecahan masalah, dan keduanya menggunakan pendekatan trial-and-error untuk mengeksplorasi pilihan yang berbeda dan membuat keputusan berdasarkan informasi yang tersedia. Keduanya juga merupakan proses berulang yang meningkat dari waktu ke waktu karena lebih banyak informasi dan pengalaman dikumpulkan.
Pilihan antara RLHF dan MCTS bergantung pada tugas yang dihadapi. RLHF sangat ideal ketika tidak ada metrik yang jelas untuk mengevaluasi kinerja model, sementara MCTS telah terbukti efektif dalam tugas-tugas seperti permainan di mana pengetahuan dan eksplorasi masa depan memberi model keuntungan yang signifikan.
Pengoptimalan Kode untuk pelatihan AlphaTensor
Menerapkan algoritme pelatihan AlphaTensor memerlukan menemukan kompromi yang sempurna antara kecepatan pelatihan dan konsumsi memori. Seperti yang terlihat di bagian Model, hanya dengan mempertimbangkan tokenisasi tindakan dapat menghemat banyak memori, tetapi pengurangan ruang tindakan yang terlalu agresif dapat menyebabkan penurunan akurasi dan kinerja yang lebih lambat. Yang terakhir terjadi karena semua token dihasilkan secara berurutan dengan cara autoregresif oleh dekoder model. Oleh karena itu, waktu inferensi bertambah secara linier dengan jumlah token per tindakan setelah softmax pada ruang tindakan tidak lagi menjadi penghambat.
Saat menyiapkan pelatihan AlphaTensor, ditemukan kesulitan utama dalam menangani proses akting. Jika tensor tidak disimpan dalam format yang benar, MCTS dapat dengan mudah menyebabkan pertumbuhan penggunaan memori yang tidak terkendali. Di sisi lain, jika jumlah tensor yang disimpan selama setiap simulasi berkurang terlalu banyak, MCTS dapat menghabiskan banyak waktu untuk menghitung ulang status yang diperlukan.
Mari kita ambil contoh langkah simulasi game, di mana game dieksplorasi dengan melihat kemungkinan skenario masa depan. Untuk setiap negara bagian, jika kita tidak menyimpan tindakan yang dihasilkan oleh model dan kita memutuskan untuk hanya menyimpan benih acak yang digunakan untuk mengambil sampel tindakan dari kebijakan, maka setiap kali kita menjelajahi simpul pohon kita harus menghitung ulang kebijakan tersebut dan lalu ambil contoh tindakannya. Jelasnya, kami memutuskan untuk menyimpan tindakan sampel untuk menghemat waktu dan menghindari keharusan mengelola pembagian model antara proses yang berbeda dalam kasus paralelisasi eksplorasi MCTS. Namun, menyimpan tindakan saja tidak cukup untuk mendapatkan langkah tindakan yang cukup efisien. Faktanya, waktu untuk mengubah tindakan n_steps menjadi triplet (u, v, w), mengurangi status tensor game, dan membuat tensor 3D baru dari tindakan n_samples akan dengan mudah menjadi hambatan bagi keseluruhan pelatihan. Kedua, kami tidak ingin menyimpan semua kemungkinan status masa depan untuk setiap tindakan yang diambil sampelnya, karena hal ini akan berdampak besar pada memori yang digunakan oleh algoritme. Misalkan kita menetapkan n_samples=32, n=7 dan N=5, dan ingat bahwa N adalah ukuran hasil kali matriks persegi yang ingin kita kurangi dan n adalah jumlah tindakan sebelumnya yang diingat oleh model. Dalam situasi ini, setiap tensor keadaan akan berbentuk (8, 25, 25, 25), yang dikalikan dengan 32 akan menghasilkan 3282525254 byte untuk setiap node dalam grafik. Sekarang, mengingat setiap simulasi dalam fase ekspansi menghasilkan node baru (dan n_sim=200), kita akan memiliki konsumsi memori akhir sebesar 200328252525*4 = 3.2 GB untuk node MCTS pertama saja. Dalam skenario terburuk, saat menjelajahi node max_rank aktif (di mana max_rank=150), ini akan menghasilkan konsumsi memori total 150 * 3.2 GB = 480 GB dalam memori RAM (atau memori GPU jika semua tensor disimpan di GPU) . Kami menjalankan pelatihan di workstation kami dengan RAM 128 GB dan memori GPU 48 GB, jadi kami harus mengurangi konsumsi memori.
Karena kami tidak ingin menambah waktu eksekusi, kami mengadopsi pengoptimalan yang memanfaatkan redundansi keadaan tensor yang dihasilkan. Faktanya, tensor memiliki n-1 tindakan yang sama sebelumnya, yang kemudian dapat disimpan satu kali dan tidak diulangi untuk setiap tensor yang disimpan. Hal ini mengakibatkan pengurangan memori sebesar 2/7~28%, yang berarti dalam kasus terburuk, 137GB dapat disimpan. Pada titik ini, hanya dengan memangkas bagian pohon yang tidak digunakan (seperti lintasan yang tidak dipilih) dan menyimpan tensor di memori CPU, kami dapat menghindari kesalahan memori apa pun selama pelatihan.
Dengan OpenAlphaTensor sekarang menjadi open source, beberapa jalan menarik untuk pengembangan lebih lanjut terbuka.
Kemajuan alami adalah penyempurnaan OpenAlphaTensor pada perangkat perangkat keras target. Hal ini diharapkan dapat menghasilkan kinerja komputasi yang sangat kompetitif. Saya akan mempublikasikan lebih banyak tentang kinerja OpenAlphaTensor pada berbagai perangkat keras GitHub. Pada saat artikel ini ditulis, OpenAlphaTensor sedang menjalani pelatihan.
Kemajuan penting lainnya adalah dukungan untuk kompilasi jarak jauh, yang memungkinkan pengguna membuat algoritme yang dioptimalkan untuk perangkat edge. Ini dapat dicapai dengan menyimpan model OpenAlphaTensor di server, sedangkan algoritma perkalian matriks dievaluasi pada perangkat keras yang berbeda.
Penting juga untuk memperluas dukungan bagi kompiler yang berbeda untuk menghitung koreksi hadiah berbasis latensi. Kompiler yang berbeda dapat menghasilkan algoritme optimal yang berbeda pada perangkat keras tertentu. Misalnya, makalah DeepMind menunjukkan hasil yang menjanjikan menggunakan JAX dan kompiler XLA pada TPU dan GPU Nvidia. Akan menarik untuk mengevaluasi ini menggunakan NCCL di Nvidia atau LLVM di CPU.
Terakhir, memperluas model dan algoritme pelatihan untuk mendukung ukuran matriks yang lebih besar tetap menjadi tantangan besar. Saat ini, OpenAlphaTensor mendukung ukuran matriks maksimum 5, tetapi dapat diterapkan dengan membagi perkalian matriks yang lebih besar menjadi kelompok MM kecil dengan ukuran lebih kecil dari 5. Pendekatan ini kurang optimal, dan melakukan pengurangan langsung pada tensor besar yang sesuai dengan MM penuh secara teoritis dapat menghasilkan hasil yang lebih baik.
Diego Fiori adalah CTO Nebuly AI, sebuah perusahaan yang berkomitmen untuk menjadikan pengoptimalan AI sebagai bagian dari perangkat setiap pengembang.
- Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
- Platoblockchain. Intelijen Metaverse Web3. Pengetahuan Diperkuat. Akses Di Sini.
- Sumber: https://www.kdnuggets.com/2023/03/first-open-source-implementation-deepmind-alphatensor.html?utm_source=rss&utm_medium=rss&utm_campaign=first-open-source-implementation-of-deepminds-alphatensor
- :adalah
- ][P
- $NAIK
- 1
- 3d
- 8
- a
- Sanggup
- Tentang Kami
- atas
- Mutlak
- mempercepat
- Menurut
- demikian
- Akun
- ketepatan
- Mencapai
- dicapai
- Tindakan
- tindakan
- sebenarnya
- menambahkan
- Tambahan
- Disesuaikan
- diadopsi
- memajukan
- Keuntungan
- Setelah
- Agen
- pengumpulan
- agresif
- AI
- Sistem AI
- bertujuan
- algoritma
- algoritma
- Semua
- Membiarkan
- memungkinkan
- sendirian
- sudah
- alternatif
- antara
- jumlah
- menganalisa
- dan
- Lain
- terapan
- pendekatan
- pendekatan
- arsitektur
- ADALAH
- artikel
- buatan
- kecerdasan buatan
- AS
- ditugaskan
- terkait
- At
- Otomatis
- tersedia
- menghindari
- kembali
- backup
- berdasarkan
- Pada dasarnya
- dasar
- BE
- karena
- menjadi
- sebelum
- makhluk
- di bawah
- patokan
- TERBAIK
- Lebih baik
- antara
- Luar
- papan
- Permainan papan
- terikat
- lebih luas
- BT
- membangun
- dibangun di
- by
- bernama
- CAN
- tidak bisa
- kasus
- Menyebabkan
- disebabkan
- tertentu
- menantang
- menantang
- perubahan
- Saluran
- ChatGPT
- anak
- pilihan
- memilih
- terpilih
- dikutip
- jelas
- Jelas
- kode
- mengumpulkan
- menggabungkan
- berkomitmen
- Umum
- perusahaan
- dibandingkan
- kompetitif
- kompleks
- kompleksitas
- komponen
- tersusun
- kompromi
- komputasi
- kekuatan komputasi
- menghitung
- komputasi
- konsep
- Secara konseptual
- kondisi
- kepercayaan
- Mempertimbangkan
- dianggap
- mengingat
- menganggap
- konsumsi
- mengandung
- terus
- kontras
- dikonversi
- Core
- Sesuai
- berkorespondensi
- bisa
- Melawan
- CPU
- menciptakan
- membuat
- kriteria
- CTO
- terbaru
- Sekarang
- data
- berurusan
- memutuskan
- memutuskan
- keputusan
- Pengambilan Keputusan
- keputusan
- mendalam
- belajar mendalam
- DeepMind
- tergantung
- dijelaskan
- Menentukan
- Pengembang
- Pengembangan
- alat
- Devices
- DICT
- berbeda
- kesulitan
- Dimensi
- ukuran
- langsung
- menemukan
- menemukan
- dibahas
- distribusi
- Terbagi
- turun
- Menjatuhkan
- selama
- e
- setiap
- Terdahulu
- mudah
- Tepi
- Efektif
- efisien
- antara
- elemen
- elemen
- tertanam
- berakhir
- ditingkatkan
- besar sekali
- cukup
- masuk
- kesalahan
- memperkirakan
- diperkirakan
- Eter (ETH)
- mengevaluasi
- dievaluasi
- mengevaluasi
- evaluasi
- Bahkan
- Setiap
- contoh
- contoh
- menarik
- eksekusi
- perluasan
- diharapkan
- pengalaman
- Menjelaskan
- menjelaskan
- eksploitasi
- eksplorasi
- menyelidiki
- Dieksplorasi
- Menjelajahi
- menyatakan
- memperpanjang
- memperpanjang
- sangat
- hampir
- keluarga
- lebih cepat
- umpan balik
- beberapa
- Angka
- terakhir
- temuan
- Pertama
- Mengapung
- Fokus
- mengikuti
- berikut
- Tapak
- Untuk
- bentuk
- format
- rumus
- ditemukan
- dari
- penuh
- fungsi
- mendasar
- lebih lanjut
- pengembangan lebih lanjut
- masa depan
- permainan
- Games
- menghasilkan
- dihasilkan
- menghasilkan
- menghasilkan
- mendapatkan
- mendapatkan
- Memberikan
- diberikan
- Pemberian
- tujuan
- Pergi
- baik
- GPU
- GPU
- grafik
- besar
- Kelompok
- Grup
- tumbuh
- Pertumbuhan
- membimbing
- tangan
- Penanganan
- terjadi
- Terjadi
- Perangkat keras
- perangkat perangkat keras
- perangkat keras
- Memiliki
- memiliki
- di sini
- paling tinggi
- horison
- Seterpercayaapakah Olymp Trade? Kesimpulan
- How To
- Namun
- HTTPS
- besar
- manusia
- i
- SAYA AKAN
- ideal
- BEI
- gambar
- Dampak
- melaksanakan
- implementasi
- penting
- memperbaiki
- ditingkatkan
- in
- Meningkatkan
- Meningkatkan
- makin
- independen
- indeks
- informasi
- mulanya
- memasukkan
- sebagai gantinya
- instruksi
- Intelijen
- menarik
- intern
- diperkenalkan
- intuisi
- IT
- perulangan
- NYA
- Diri
- jpg
- KDnugget
- Menjaga
- kunci
- pengetahuan
- dikenal
- bahasa
- besar
- lebih besar
- Terakhir
- Latensi
- Terbaru
- lapisan
- lapisan
- memimpin
- belajar
- pengetahuan
- Daftar
- melihat
- mencari
- Lot
- terbuat
- Utama
- utama
- membuat
- Membuat
- mengelola
- pelaksana
- banyak
- peta
- pemetaan
- Matriks
- hal
- maksimum
- makna
- berarti
- cara
- anggota
- Memori
- metode
- metode
- metrik
- hilang
- campuran
- model
- model
- dimodifikasi
- modul
- lebih
- lebih efisien
- Selain itu
- paling
- pindah
- bergerak
- dikalikan
- Alam
- Alam
- Dekat
- perlu
- Perlu
- dibutuhkan
- negatif
- jaringan
- saraf
- jaringan saraf
- New
- berikutnya
- nLP
- simpul
- node
- non-ahli
- Gagasan
- jumlah
- Nvidia
- diperoleh
- of
- Penawaran
- on
- ONE
- Buka
- open source
- OpenAI
- operasi
- Operasi
- optimal
- optimasi
- Optimize
- dioptimalkan
- Opsi
- asli
- Lainnya
- jika tidak
- keluaran
- secara keseluruhan
- kertas
- dokumen
- parameter
- bagian
- tertentu
- khususnya
- bagian
- Konsultan Ahli
- sempurna
- prestasi
- melakukan
- tahap
- potongan-potongan
- plato
- Kecerdasan Data Plato
- Data Plato
- Bermain
- pemain
- bermain
- Titik
- Kebijakan
- kebijaksanaan
- posisi
- mungkin
- potensi
- kekuasaan
- Praktis
- praktek
- meramalkan
- diprediksi
- preferensi
- disajikan
- sebelumnya
- probabilitas
- mungkin
- Masalah
- proses
- proses
- menghasilkan
- Diproduksi
- Produk
- deret
- progresif
- menjanjikan
- diusulkan
- terbukti
- terbukti
- menerbitkan
- diterbitkan
- RAM
- acak
- jajaran
- agak
- tercapai
- Mencapai
- baru-baru ini
- menurunkan
- mengurangi
- mengurangi
- halus
- penguatan pembelajaran
- dirilis
- yang tersisa
- sisa
- luar biasa
- ingat
- terpencil
- ulang
- mewakili
- merupakan
- wajib
- membutuhkan
- tanggung jawab
- terbatas
- mengakibatkan
- dihasilkan
- Hasil
- kembali
- Pengembalian
- merevolusionerkan
- Pahala
- BARIS
- rt
- Run
- s
- sama
- Save
- penghematan
- skenario
- skenario
- skema
- Pencarian
- Kedua
- Bagian
- benih
- terpilih
- memilih
- seleksi
- DIRI
- set
- pengaturan
- beberapa
- Bentuknya
- berbagi
- Pendek
- harus
- Menunjukkan
- ditunjukkan
- Pertunjukkan
- Sinyal
- penting
- signifikan
- mirip
- kesamaan
- Sederhana
- kesederhanaan
- hanya
- simulasi
- sejak
- situasi
- Ukuran
- ukuran
- kecil
- lebih kecil
- Potret
- So
- larutan
- MEMECAHKAN
- Memecahkan
- beberapa
- sumber
- Space
- spasi
- tertentu
- Secara khusus
- ditentukan
- kecepatan
- menghabiskan
- Pengeluaran
- membagi
- kotak
- ditumpuk
- Tahap
- standar
- awal
- dimulai
- Negara
- state-of-the-art
- menyatakan
- Negara
- statistika
- Langkah
- Tangga
- henti
- menyimpan
- tersimpan
- toko
- mudah
- sukses
- seperti itu
- mendukung
- Mendukung
- sintetis
- data sintetis
- secara sintetis
- sistem
- sistem
- disesuaikan
- Mengambil
- Dibutuhkan
- pengambilan
- target
- tugas
- tugas
- teknik
- terminal
- istilah
- bahwa
- Grafik
- Masa depan
- Grafik
- informasi
- Negara
- mereka
- Mereka
- dengan demikian
- karena itu
- Ini
- Ketiga
- tiga
- tiga dimensi
- Melalui
- waktu
- membuang-buang waktu
- untuk
- bersama
- token
- Tokenisasi
- dipatok
- Token
- terlalu
- toolkit
- puncak
- obor
- Total
- tradisional
- Pelatihan VE
- terlatih
- Pelatihan
- kereta
- lintasan
- berubah
- mengobati
- benar
- memahami
- Alam semesta
- terpakai
- Memperbarui
- diperbarui
- Pembaruan
- memperbarui
- meningkatkan
- us
- penggunaan
- menggunakan
- Pengguna
- biasanya
- nilai
- Nilai - Nilai
- berbagai
- versi
- Video
- Video game
- Mengunjungi
- Kunjungan
- W
- Cara..
- Apa
- yang
- sementara
- sangat
- Wikipedia
- akan
- kemenangan
- dengan
- kata
- workstation
- bernilai
- akan
- penulisan
- tertulis
- X
- zephyrnet.dll
- nol