higepon blog |
|---|
| 2022年振り返り 2022-12-31 08:27:09 プライベートなことは Notion に書いた。 Kaggle コンペ参加は1回のみ。 バレエを始めた。 週2-3回の筋トレはよく続いた。 8月にコロナに罹った。熱を出して寝込んだ。家族はほぼ無症状。後遺症はなし。 息子は中学生になり、子育ての負荷がぐっと下がった。 仕事は新しいプロジェクト。比較的忙しい1年だった。 ロシアがウクライナと戦争を始めた。 肋骨を骨折した。 帯状疱疹になった。 Mosh の M1 対応。Rust で書き直す実験など。 ダッシュして膝を痛めた。老後に膝が痛いというのはこのような感じなんだろうか。確かに出不精になりそう。 ELSA Speak 始めた。 新しい習い事を始める勇気がなかった。 |
| How GC in unsafe loxido works 2022-12-03 16:08:01 ceronman/loxido: Rust implementation of the Lox programming language. How to allocate object let bar = gc.alloc(LoxString::from_string("bar".to_owned())); LoxString::from_string and GcObject implementation. They are staraightforward. pub struct LoxString { pub header: GcObject, pub s: String, pub hash: usize, } impl LoxString { pub fn from_string(s: String) -> Self { let hash = LoxString::hash_string(&s); LoxString { header: GcObject::new(ObjectType::LoxString), s, hash, } __snip__ pub struct GcObject { marked: bool, next: Option<NonNull<GcObject>>, obj_type: ObjectType, } Gc::alloc should be doing the trick. I added a comment for each line. pub fn alloc<T: Display + 'static>(&mut self, object: T) -> GcRef<T> { unsafe { // Alloc object in heap. let boxed = Box::new(object); // Get raw pointer from Box::into_raw. // pointer is NonNull<T>. let pointer = NonNull::new_unchecked(Box::into_raw(boxed)); // This assumes &T has GcObject as the first field with the exact sae alignhment. let mut header: NonNull<GcObject> = mem::transmute(pointer.as_ref()); // Gc.first is linked list of GcObject(=header). header.as_mut().next = self.first.take(); // The newly allocated one becomes head of the linked list. self.first = Some(header); // GcRef is a struct with one field pointer: NonNull<T>. GcRef { pointer } } } Mark Adding my comments inline. fn mark_roots(&mut self) { // Mark VM stack. for &value in &self.stack[0..self.stack_len()] { self.gc.mark_value(value); } // Mark call frames. for frame in &self.frames[..self.frame_count] { self.gc.mark_object(frame.closure) } for &upvalue in &self.open_upvalues { self.gc.mark_object(upvalue); } self.gc.mark_table(&self.globals); self.gc.mark_object(self.init_string); } Trace mark_object pushes in-use objects to grey_stack. blacken_object marks recursively in objects. Unlike Rust GC this doesn't have Trace trait. So in blacken_object it should enum all GcRef field. fn trace_references(&mut self) { while let Some(pointer) = self.grey_stack.pop() { self.blacken_object(pointer); } } Sweep if the object is not marked release the object from heap. fn sweep(&mut self) { let mut previous: Option<NonNull<GcObject>> = None; let mut current: Option<NonNull<GcObject>> = self.first; while let Some(mut object) = current { unsafe { let object_ptr = object.as_mut(); current = object_ptr.next; if object_ptr.marked { object_ptr.marked = false; previous = Some(object); } else { if let Some(mut previous) = previous { previous.as_mut().next = object_ptr.next } else { self.first = object_ptr.next } Box::from_raw(object_ptr); } } } } |
| Finalize, Sweep and Rooting - Understanding Rust GC 2022-12-02 04:58:04 Finalize Trait Previously we explored Trace in Trace - Understanding Rust GC - higepon blog. Let's look into Finalize trait. This is really simple. Every GC-ed object should implement this finalize. pub trait Finalize { fn finalize(&self) {} } Let's look at finalize implementation for array and Option<T>. They are empty. Hmm. I'm not quite sure why. Let me start from collect_garbage and come back here later. ;; Array impl<T: Trace, const N: usize> Finalize for [T; N] {} ;; Option<T> impl<T: Trace> Finalize for Option<T> {} collect_garbage In collect_garbage after the mark returns unmarked objects (= not used objects) and it will call finalize_glue() for each GC<T> object. let unmarked = mark(&mut st.boxes_start); if unmarked.is_empty() { return; } for node in &unmarked { Trace::finalize_glue(&(*node.this.as_ptr()).data); } finalize_glue calls finalize in the Trait. So say an array is unmarked, the gc eventually calls empty trace of the array. Now I remember that finalize give the object a chance to any necessary work before it's deallocated. For example an object may want to close a file associated with it. Sweep Now we know that the gc collects unmarked objects and calls finalize for the unmarked objects. It's time to sweep them. unsafe fn sweep(finalized: Vec<Unmarked>, bytes_allocated: &mut usize) { let _guard = DropGuard::new(); for node in finalized.into_iter().rev() { if (*node.this.as_ptr()).header.marked.get() { continue; } let incoming = node.incoming; let mut node = Box::from_raw(node.this.as_ptr()); *bytes_allocated -= mem::size_of_val::<GcBox<_>>(&*node); *incoming = node.header.next.take(); } } This is actually very interesting. It recreates Box from returning raw pointer using from_raw which makes sense! Rooting Let's get back to root and unroot. A Tour of Safe Tracing GC Designs in Rust - In Pursuit of Laziness has a good summary and examples of what is rooting and why we need it. In one word: Rooting. In a garbage collector, the objects “directly” in use on the stack are the “roots”, and you need to be able to identify them. struct Foo { bar: Option<Gc<Bar>> } // this is a root let bar = Gc::new(Bar::new()); // this is also a root let foo = Gc::new(Foo::new()); // bar should no longer be a root (but we can't detect that!) foo.bar = Some(bar); // but foo should still be a root here since it's not inside // another GC'd object let v = vec![foo]; To track root objects, the GC maintains root counts in GC_BOX. In short GC_BOX with root count > 0 is a root object. Rooting - Designing a GC in Rust explains it very well. Note that the count is incremented or decremented when GC<T> object is moved. Summary Finalize gives an object an opportunity to do some clean up work before it's free-ed. Sweep returns unmarked objects using Box. To track objects directly use in stack the gc maintains root count. |
| Trace - Understanding Rust GC 2022-12-02 04:55:53 Goal I want to understand how Rust GC work to see if I can use it in my Scheme VM interpreter to be written in Rust. How to use GC-ed objects should implement Trace and Finalize. You should use Gc::new instead of Box::new to allocate objects in heap. Here is an example from the official document. let x = Gc::new(1_u8); let y = Gc::new(Box::new(Gc::new(1_u8))); #[derive(Trace, Finalize)] struct Foo { a: Gc<u8>, b: u8 } let z = Gc::new(Foo {a: x.clone(), b: 1}) What is Gc<Foo>? z variable above is Gc<Foo> type. You can access fields of Foo like z.a. But why? It doesn't have z field in it. Because it implements Deref Trait Rust compiler can take care of it. impl<T: Trace + ?Sized> Deref for Gc<T> { type Target = T; #[inline] fn deref(&self) -> &T { &self.inner().value() } } The definition of the struct GC<T> as follows. It has only 2 fields. pub struct Gc<T: Trace + ?Sized + 'static> { ptr_root: Cell<NonNull<GcBox<T>>>, marker: PhantomData<Rc<T>>, } Trace Trait Per Designing a GC in Rust - In Pursuit of Laziness the purpose of trace is a way of walking the fields of a given object and finding inner Gc<T> fields. For example if you have one GC<T> object, you should be able to find all GC<T> fields or inner fields by the tracing. Let's look into the Trace trait. I'm not sure what root and unroot are doing yet. We'll get back to here later. /// The Trace trait, which needs to be implemented on garbage-collected objects. pub unsafe trait Trace: Finalize { /// Marks all contained `Gc`s. unsafe fn trace(&self); /// Increments the root-count of all contained `Gc`s. unsafe fn root(&self); /// Decrements the root-count of all contained `Gc`s. unsafe fn unroot(&self); /// Runs Finalize::finalize() on this object and all /// contained subobjects fn finalize_glue(&self); } Here is one Trace implementation of for 'static lifetime struct. unsafe impl<T: ?Sized> Trace for &'static T { unsafe_empty_trace!(); } unsafe_empty_trace! is a macro which has no-op trace, root and unroot method. This makes sense because 'static lifetime indicates that the data pointed to by the reference lives for the entire lifetime of the running program. So we don't event need to track or sweep. Let's look at one more example. This is the trace for an array. I would guess this is marking all elements in the array. Let's confirm. unsafe impl<T: Trace, const N: usize> Trace for [T; N] { custom_trace!(this, { for v in this { mark(v); } }); } custom_trace! is implemented as follows. It defines inline mark method and call it in the $body. /// This rule implements the trace method. /// /// You define a `this` parameter name and pass in a body, which should call `mark` on every /// traceable element inside the body. The mark implementation will automatically delegate to the /// correct method on the argument. #[macro_export] macro_rules! custom_trace { ($this:ident, $body:expr) => { #[inline] unsafe fn trace(&self) { #[inline] unsafe fn mark<T: $crate::Trace + ?Sized>(it: &T) { $crate::Trace::trace(it); } let $this = self; $body } I think $crate::Trace::trace(it); is calling trace() for Gc<T> but not 100% sure. unsafe impl<T: Trace + ?Sized> Trace for Gc<T> { #[inline] unsafe fn trace(&self) { self.inner().trace_inner(); } Then it calls trace_inner() for GcBox. /// Marks this `GcBox` and marks through its data. pub(crate) unsafe fn trace_inner(&self) { let marked = self.header.marked.get(); if !marked { self.header.marked.set(true); self.data.trace(); } } Remember that GcBox is the raw pointer allocated in Gc::new and stored in ptr_root. pub fn new(value: T) -> Self { assert!(mem::align_of::<GcBox<T>>() > 1); unsafe { // Allocate the memory for the object let ptr = GcBox::new(value); // When we create a Gc<T>, all pointers which have been moved to the // heap no longer need to be rooted, so we unroot them. (*ptr.as_ptr()).value().unroot(); let gc = Gc { ptr_root: Cell::new(NonNull::new_unchecked(ptr.as_ptr())), marker: PhantomData, }; Let's quickly look at GcBox definition. pub(crate) struct GcBoxHeader { // XXX This is horribly space inefficient - not sure if we care // We are using a word word bool - there is a full 63 bits of unused data :( // XXX: Should be able to store marked in the high bit of roots? roots: Cell<usize>, next: Option<NonNull<GcBox<dyn Trace>>>, marked: Cell<bool>, } #[repr(C)] // to justify the layout computation in Gc::from_raw pub(crate) struct GcBox<T: Trace + ?Sized + 'static> { header: GcBoxHeader, data: T, } Okay. Now I have better understanding. The trace method just set marked=true which means the ptr is in use. By the way who is calling the trace method and when? The answer is collect_garbage => GcBox::trace_inner() => trace. This is exciting! We're so close to the core of the gc. Let's look at collect_garbage. /// Collects garbage. fn collect_garbage(st: &mut GcState) { __snip__ unsafe fn mark(head: &mut Option<NonNull<GcBox<dyn Trace>>>) -> Vec<Unmarked> { // Walk the tree, tracing and marking the nodes let mut mark_head = *head; while let Some(node) = mark_head { __snip__ unsafe { let unmarked = mark(&mut st.boxes_start); if unmarked.is_empty() { return; } Now we know GcState.boxes_start is the actual starting point of mark and it recursively marks GC<T> objects. My next question is who's setting up boxes_start? The answer is it is done in GcBox::new whenever it allocates new GcBox, it maintains a link list of GcBox and set it to boxes_start. let gcbox = Box::into_raw(Box::new(GcBox { header: GcBoxHeader { roots: Cell::new(1), marked: Cell::new(false), next: st.boxes_start.take(), }, data: value, })); st.boxes_start = Some(unsafe { NonNull::new_unchecked(gcbox) }); And finally GcState is a thread local object as follows. So GcState is a kind of global variable which is local to a thread. // The garbage collector's internal state. thread_local!(static GC_STATE: RefCell<GcState> = RefCell::new(GcState { bytes_allocated: 0, threshold: INITIAL_THRESHOLD, boxes_start: None, })); Summary of Trace (Mark) GC-ed object should implement Trace trait. The trace method should recursively call trace method for inner objects. In mark phase the gc calls trace for GcBox::newed objects. Next: Finalize, Sweep, root and unroot - Understanding Rust GC - higepon blog. |
| Mosh compiler/VM のデバッグを1週間続けた話 2022-10-30 15:08:03 Mosh は R7RS に対応しつつあるので ecraven/r7rs-benchmarks というベンチマークを走らせてみた。今回は速度は気にせずにR7RS Scheme 処理系としてコードを間違いなく正しく実行できるかに注力。結局57個中で3つのベンチマークで実行に失敗することが分かった。うち2つは比較的簡単に修正できた。最後の1つが手強かったので記録を残す。 スタート 失敗するのは conform というベンチマーク。期待される結果とは違うものを Mosh が返してしまう。そして実行時間がやけに短い。conform ベンチマークのスクリプト（ r7rs-benchmarks/conform.scm）を見てみるとグラフ構造を作って何かやっているらしい。正直コードを理解しようとするのは3秒で諦めた。 この時点ではデバッグが難航する事は知る由もないのでデバッグ print を入れてなぜ期待と違うかを調べようとするがすぐに挫折。なぜならば A) グラフ構造を扱っているので自分の中で自分を参照していてデバッグ print と相性が悪いこと。write/ss で shared structure を print できるがそれでも視認性が悪い。 B) データ構造が大きく print しきれない C) そもそも何をやっているのかコードから読み取れない。 この状態で2-3時間無駄に使った。 心理的安全性 これは難航しそうだとようやく気付いたので少し落ち着くことにした。正しい状態がよく分からないのが問題なので Gauche で実行して比べることとした。次に処理内容が分からないのは良いとして、メインの処理を何となく名前から特定した。ここでようやくメインの処理にデバッグ print を入れて Gauche と比較できるようになり、ある関数で一瞬で間違った値が返っていることが分かった。 間違うポイントが分かったので勝利を確信。その関数への入力を維持したまま再現コードを小さくしていくことにした。ところがこれがかなり難しい。入力も出力もグラフなので文字列や数字を扱うのとは別の難しさがある。色々やっているうちにぐちゃぐちゃになってしまった。元に戻らなくなってしまい大反省。debug という git branch を作り少しずつ進むようにしたら急に捗ったし壊すことも無くなった。チェックポイントあるし壊しても大丈夫という心理的安全性大事。1日かけて小さなコードに絞ることができた。 (define (foo) (define (bar n) (cond ((= n 1) #t) (else (let loop ((lst '(1))) (if (null? lst) #t (and (display "=> recusive1\n") (bar 1) (display "=> loop\n") (loop (cdr lst)))))))) (bar 0) ) (foo) このコードの (bar 1) の呼び出しの後に (display "=> loop\n") が呼ばれないことが分かった。これは明らかにおかしいなぜならば (bar 1) は #t を返すから。 それで誰が悪いのか？ Scheme 処理系を書いたことのある人なら分かると思うが、これは色々怪しい。define の中に define があり named let があり末尾再帰があり。どこでバグっていてもおかしくない。 この時点でバグの原因候補は実行順に コンパイラ手前の S 式の変換。例）and を if に変換 コンパイラの S式 => iform への変換 コンパイラの iform に対する最適化 コンパイラのコード生成部 コンパイラの merge instructions 部 VM R6RS -> バックエンド変換部 R7RS -> R6RS 変換部 というのを切り替えないといけない。その上この辺りを触るのは10年以上ぶりである！ コンパイラと VM を調べる 最適化を OFF にすると再現しなくなったので 最適化そのものが間違っている 最適化で出てくるコードを正しく実行できないパスがある あたりが怪しい。 pass2 の最適化の途中。1週間のデバッグを終えた今の目で見ればおかしいところは明らか。 ($if ($asm NUMBER_EQUAL ($lref n[1;0]) ($const 1)) ($const #t) ($letrec ((loop[0;0] ($lambda[loop;2] (lst[2;0]) ($label #0 ($if ($asm NULL_P ($lref lst[2;0])) ($const #t) ($if ($call ($gref display) ($const "=> recusive1\n")) ($if ($call[tail-rec] ($lref bar[2;0]) ($const 1)) ($if ($call ($gref display) ($const "=> loop\n")) ($call[jump] ($call[embed] ($lambda[loop;2] (lst[2;0]) label#0) ($const (1))) ($asm CDR ($lref lst[2;0]))) ($it)) ($it)) ($it)))))) ) ($call[embed] ($lambda[loop;2] (lst[2;0]) label#0) ($const (1))))) pass2 の最適化後の iform は以下の通り。ここで時間を使いすぎた。 ($define () foo ($lambda[foo;0] () ($call[embed 4 0] ($lambda[bar;2] (n[1;0]) ($label #0 ($if ($asm NUMBER_EQUAL ($lref n[1;0]) ($const 1)) ($const #t) ($call[embed 7 0] ($lambda[loop;2] (lst[2;0]) ($label #1 ($if ($asm NULL_P ($lref lst[2;0])) ($const #t) ($if ($call ($gref display) ($const "=> recusive1\n")) ($if ($call[jump 0 0] ($call[embed 4 0] ($lambda[bar;2] (n[1;0]) label#0) ($const 0)) ($const 1)) ($if ($call ($gref display) ($const "=> loop\n")) ($call[jump 0 0] ($call[embed 7 0] ($lambda[loop;2] (lst[2;0]) label#1) ($const (1))) ($asm CDR ($lref lst[2;0]))) ($it)) ($it)) ($it))))) ($const (1)))))) ($const 0)))) 結局 pass2 の最適化で local call を埋め込む処理あたりで何かがおかしい事は分かるのだが。この iform がおかしいのか。後続の処理がおかしいのか分からないので後続も見る。 実際の VM instruction 列を表示してみると。ますます分からない。 CLOSURE 81 0 #f 0 11 ((reproduce.scm 1) foo) LET_FRAME 7 CONSTANT_PUSH 0 ENTER ;; Label #0 1 REFER_LOCAL_PUSH_CONSTANT 0 1 BRANCH_NOT_NUMBER_EQUAL ;; if (= n 1) 5 CONSTANT #t LOCAL_JMP ;; goto label #1 57 LET_FRAME 5 REFER_LOCAL_PUSH 0 DISPLAY 1 CONSTANT_PUSH (1) ENTER 1 REFER_LOCAL_BRANCH_NOT_NULL 0 5 CONSTANT #t LOCAL_JMP 38 FRAME 6 CONSTANT_PUSH => recusive1 REFER_GLOBAL_CALL display ;; (display "=> recusive1\n") 1 ;; # of args TEST ;; (display ...) return value is true. So we skip the +1 next line and go to +2 line. 29 CONSTANT_PUSH ;; Come here after (display ...) call 1 SHIFTJ ;; adjust SP and FP 1 ;; depth 4 ;; diff 0 ;; How many closure to go up? LOCAL_JMP ;; Jump to label #0 -42 TEST 19 FRAME 6 CONSTANT_PUSH => loop REFER_GLOBAL_CALL display 1 TEST 10 REFER_LOCAL 0 CDR_PUSH SHIFTJ 1 1 0 LOCAL_JMP -43 LEAVE 1 LEAVE ;; label #2 1 ;; adjust stack RETURN ;; return to the code (the code is taken from the top of stack). ** But we don't have the code in the stack?*** 0 DEFINE_GLOBAL foo HALT NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP NOP) 動的に VM で実行される様子を stack と共に。 ======================== FRAME FP|0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" ======================== REFER_GLOBAL FP|0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" ======================== CALL |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" ======================== LET_FRAME # LET_FRAME for lambda[foo] |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" FP|4: 4 # Save fp |5: "#(#(CLOSURE ...))" # Closure ======================== CONSTANT |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" FP|4: 4 |5: "#(#(CLOSURE ...))" ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" FP|4: 4 |5: "#(#(CLOSURE ...))" |6: 0 # Constant 0 ======================== ENTER # Adjust fp |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 ======================== REFER_LOCAL # a=(Constant 0) |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 # Constant 0 |7: 0 # Constant 0 ======================== CONSTANT # a=(Constant 1) |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 0 ======================== BRANCH_NOT_NUMBER_EQUAL # a != stack-bottom(Constant 0) |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 # Discarded stack top. ======================== LET_FRAME # LET_FRAME for loop. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 # Save fp |8: "#(#(CLOSURE ...))" # Push closure ======================== REFER_LOCAL # a=(Constant 0) REALLY??? |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 |8: "#(#(CLOSURE ...))" ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 0 # push (Constant 0) ======================== DISPLAY # Create a display and set it to closure. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 |8: "#(#(CLOSURE ...))"# Note stack is popped. ======================== CONSTANT # a=(1) |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 |8: "#(#(CLOSURE ...))" ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 # (1) ======================== ENTER |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 # New FP. ======================== REFER_LOCAL # a=(1) |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 ======================== BRANCH_NOT_NULL # Go to else. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 ======================== FRAME # Push stuff. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 |10: "(#(#f ...)" # closure |11: 9 # fp |12: 54 # pc + n |13: "(#(CLOSURE ...)" # Current codes ======================== CONSTANT # a="=> recursive1" |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" |14: "=> recusive1\n" ======================== REFER_GLOBAL # a=<display> |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" |14: "=> recusive1\n" ======================== CALL # call a=<display>. Note codes is now body of display. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () # display has optional-arg '() ======================== REFER_LOCAL # a="=> recursive1\n" |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () ======================== BRANCH_NOT_NULL # a is not null so we go to Else. But this is really weird. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () ======================== REFER_LOCAL # a="=> recursive1" |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () |16: "=> recusive1\n" ======================== REFER_FREE 0 # Point codes + 6 |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" |15: () |16: "=> recusive1\n" ======================== TAIL_CALL # call <display> and jump to #(RETURN 1 ...) => recusive1 |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" |9: 1 |10: "(#(#f ...)" |11: 9 |12: 54 |13: "(#(CLOSURE ...)" FP|14: "=> recusive1\n" ======================== RETURN |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 # this is () ======================== TEST # Return value of display is #t |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 ======================== CONSTANT |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" |6: 0 |7: 6 |8: "#(#(CLOSURE ...))" FP|9: 1 # (1) |10: 1 # 1 ======================== SHIFTJ 1 4 0 # Adjust frame for jump. Stack is now for bar call. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== LOCAL_JMP |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== REFER_LOCAL # a=1 |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== PUSH |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 |7: 1 ======================== CONSTANT |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 |7: 1 ======================== BRANCH_NOT_NUMBER_EQUAL # Now 1=1. Jump to else. |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== CONSTANT #t |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== LOCAL_JMP 66 |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" |4: 4 |5: "#(#(CLOSURE ...))" FP|6: 1 ======================== LEAVE |0: "#(#(FRAME ...))" |1: 0 |2: 6 |3: "(#(FRAME ...)" ======================== RETURN ======================== HALT これを脳内で何回も再生し iform と行ったり来たりして実行していくと (bar 1) を実行した後に local_jump したら戻ってこれないのは自明であることに気づく。この lambda 埋め込みは間違いである。それに気づけばあとは簡単で (and の途中で埋め込まれてしまったのは (bar 1) 呼び出しが末尾再帰と誤認されたのが原因。 この1行の修正でお仕事完了。 |
| Scheme で MNIST 続き 2022-10-18 08:23:18 Scheme で MNIST からの学び - higepon blog の続き。 f64array 前回のプロトタイプをもとに Mosh のシステムライブラリとして f64array というものを導入した。double 型の2次元の行列を表現したもの。追加した手続きは最低限のもの。 make-f64array f64array-ref f64array-set! f64array-shape f64array-dot-product) f64array の構築、setter/getter、dot product 。プロファイラで見てみると行列の shape を返す手続きも無視できない回数呼ばれている。おそらく行列同士の計算での broadcast で呼ばれているのだろう。 Portable なコードを書く R7RS では処理系ごとの違いをうまく扱える仕組みが用意されているので Gauche と Mosh 両方で動くように整えてみよう。 行列の初期化で make-normal-generator を使うのだが Gauche には SRFI-194 がないようなので data.random ライブラリから似たような手続きを持ってきて rename している。ところで SRFI-194 の author は Shiro さんなのであった。 (cond-expand [gauche (import (rename (data random) (reals-normal$ make-normal-generator)))] [(library (srfi 194)) (import (only (srfi 194) make-normal-generator))]) また Mosh では .mosh.sld という拡張子のライブラリを優先して読み込むという機能があるので以下のように Mosh が読み込むライブラリ、Mosh 以外が読み込むライブラリを分けることができる。ここで行列の実装を分岐している。 そしてどちらの行列ライブラリにも共通なコードは (include "matrix-common.scm") のように直接ファイルを include する。 というわけでめでたく Mosh と Gauche の両方で動く MNIST デモができました。他のR7RS 処理系でも少しの手直しで動くのではないかと期待している。PR 待ってます。コードは mosh/tests/mnist at master · higepon/mosh · GitHub。 |
| Scheme で MNIST からの学び 2022-10-09 14:05:28 久しぶりに Mosh Scheme に触っている。良い機会なので ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装 を参考に Scheme で動く MNIST デモを実装しようと思い立つ。MNIST は 0 から 9 までの手書き数字の認識デモ。Neural Network フレームワークのデモやチュートリアルでよく使われるあれだ。なお Scheme には Python でいうところの numpy は存在しないので必要な行列演算はすべて Scheme で実装することとする。 データサイズ train data 画像(28 x 28 x 1) と正解ラベル（0-9） train data: 60000件 test data: 10000件 実装前の期待と予想 他の言語・フレームワークでデモ可能だったのだから CPU 上で十分速く動作する。 比較的小さなモデル・train data なので pure Scheme 実装で大丈夫だろう。 matrix-mul がボトルネックになるかもしれない。 技術的な選択 Matrix は Vector の Vector として表現する。Uniform Vector （格納する型が決まっているもの）もありだが Mosh では未実装なので見送り。 行列演算の高速実装は特に目指さない。ナイーブな実装で良い。 matrix-mul の実装 特に工夫のないナイーブな実装。３重ループ。 (define (matrix-mul a b) (unless (= (matrix-shape a 1) (matrix-shape b 0)) (error "matrix-mul shapes don't match" (matrix-shape a) (matrix-shape b))) (let* ([nrows (matrix-shape a 0)] [ncols (matrix-shape b 1)] [m (matrix-shape a 1)] [mat (matrix nrows ncols)]) (define (mul row col) (let loop ([k 0] [ret 0]) (if (= k m) ret (loop (+ k 1) (+ ret (* (mat-at a row k) (mat-at b k col))))))) (do ((i 0 (+ i 1))) ((= i nrows) mat) (do ((j 0 (+ j 1))) ((= j ncols)) (mat-at mat i j (mul i j)))))) 結果1 2層の NN を hidden_size = 10 batch_size=3 で動かしてみたが 1 batch 回したプロファイラの結果。matrix-mul は 32165 回呼ばれ 95%（98 秒）を占めている。 Time% msec calls name location 95 98500 32165 (matrix-mul a b) <transcoded-textual-input-port <binary-input-port tests/mnist.scm>>:175 1 1140 64344 (matrix-map proc a) <transcoded-textual-input-port <binary-input-port tests/mnist.scm>>:96 結果2 1 は明らかに遅いので C++ 側で実装してみる。98秒->75秒だが思ったよりも速くない。逆に言えば VM ループは思ったよりも速い。 92 74590 32165 matrix-mul 1 680 64543 (matrix-element-wise op a...) <transcoded-textual-input-port <binary-input-port tests/mnist.scm>>:186 ここで C++ 側の実装を注意して見る必要がある。途中の計算結果の保持に Scheme Object を使っていること。行列に Fixnum もしくは Flonum が存在するので型チェックをしてくれる Arithmetic::add と mul を利用して計算していること。これだと most inner loop で heap allocation が発生してしまう。 Object ret = Object::makeVector(numRowsA); for (size_t i = 0; i < numRowsA; i++) { ret.toVector()->set(i, Object::makeVector(numColsB)); } for (size_t i = 0; i < numRowsA; i++) { for (size_t j = 0; j < numColsB; j++) { Object value = Object::makeFlonum(0.0); for (size_t k = 0; k < numColsA; k++) { Object aik = a->ref(i).toVector()->ref(k); Object bkj = b->ref(k).toVector()->ref(j); value = Arithmetic::add(value, Arithmetic::mul(aik, bkj)); } ret.toVector()->ref(i).toVector()->set(j, value); } } 結果3 もしも Uniform Vector なら内部データの型チェックは不要になり、すべての計算を double のまま行うことが可能なはず。これを模した適当な実装をやってみる。不正なデータを入力されたらインタプリタが落ちてしまうがデモなのでよしとする。 98秒が60m秒になり実用的な速度に落ち着いた。heap allocation は避けたいと思わせる結果。 1 60 32165 matrix-mul double value = 0.0; for (size_t k = 0; k < numColsA; k++) { Object aa = a->ref(i).toVector()->ref(k); Object bb = b->ref(k).toVector()->ref(j); double aik = aa.isFixnum() ? aa.toFixnum() : aa.toFlonum()->value(); double bkj = bb.isFixnum() ? bb.toFixnum() : bb.toFlonum()->value(); value += aik * bkj; } ret.toVec 学びと改善のアイデア Matrix を Vector で表現すると型チェックのオーバーヘッドがある Matrix の内部表現は double/int の2次元配列とし C++ でアクセサと mul を実装すれば良い。 matrix-mul 以外の行列操作は Scheme 側で書いてもほぼ問題なさそう。多少遅くても呼ばれる回数が matrix-mul と比べて極端に少ない。例）add, element-wise multiply, transpose, shape。 matrix-mul は SIMD などでもっと速くなるだろう。 余談 numpy は歴史が長いだけあってよく出来ている。 オブジェクト指向の操作の方がコードが読みやすい場合がある a.t は a の転置。(t a) だと若干意味合いが違うし広すぎる。 numpy の broadcasting の仕組みは便利だし必須部品であることがよく分かった。スカラ lr と 行列A の掛け算とか。 numpy の subset が SRFI で提案されたら面白いと思う。ただ上記の理由により Scheme だけで実装すると遅いと思うので悩ましい。各処理系が独自に実装することを期待はできなそうな。 現実的には Tensorflow フロントエンドで Scheme が使えれば良いのかもしれないが、それなら Python で十分。 Scheme で気軽に機械学習が楽しめるという Path は意外と遠い。Python 1強である理由も分かった。 |
| Mosh + clang-tidy 2022-09-02 20:10:10 伝説のプログラマのポッドキャストJohn Carmack: Doom, Quake, VR, AGI, Programming, Video Games, and Rockets | Lex Fridman Podcast #309 - YouTubeを聴いていたらデバッガと static analyzer がいかに素晴らしいかを説いていたので clang-tidy を使ってみることにした。 Ubuntu 20.04 aarch64 上で $ apt install bear clang-tidy $ cd mosh.git # clang-tidy が必要とする mosh.git/compile_commands.json を make コマンドの結果から生成 $ bear make # とりあえずチェックする $ run-clang-tidy -checks="-*,bugprone-macro-parentheses" # 修正も実行 $ run-clang-tidy -checks="-*,bugprone-macro-parentheses" -fix |
| Mosh + GitHub Actions 2022-09-02 19:28:28 okuoku@ さんの助けもあり GitHub Actions で Mosh を Ubuntu / macOS でビルド・テストするようにできた。これが可能になったのは夏休みに Docker で複数の環境構築・テストをすることにより 64bit Ubuntu で動くようになったから。 |
| CS25: Transformers United を受講した 2022-08-28 07:01:04 Stanford CS 25 Transformers Unitedを受講した。猫も杓子も Transformer という時代なので基礎の復習とキャッチアップを兼ねて。 良かった点 Transformer の基礎の復習がきちんとできた self attention について「分かったような分からないような」という理解から「ぎりぎり他人に説明できるかも」くらいの理解になった。 LSTM は近くがよく見える。Transformer は遠くまでよく見える。という以前の学びも。そうだよねと腹落ちした。 言語以外の応用エリア（Vision・音声）などが学べた Transformer の登場に関わった人の話が面白かった イマイチな点 一部の講師・ゲストスピーカーは準備不足 or 説明が退屈だった。オンラインでの講義に慣れていないのもあると思う。 自分が学生で単位を取ろうとしていたら大変だったかも。前提知識もかなり必要だし。話題の幅も広い。 |
| The Rust Programming Language を読んだ - 2022夏休み 2022-08-16 10:51:43 〇〇言語の後継XYZ言語がリリース。とニュースがあるたびに「少し触っとくか？まあいいか」を繰り返し。最後に「新しい」言語を学んだのは Swift という状態だったのでRust の本をオンラインで読みできる限りコードを写経した。以下感想。 メインで学びたかった Ownership 。コンパイラによる強制部分は「これがコンパイルエラーになるのか面白い」と楽しかった。 String と str は分かるけど分からない。String の内部表現が UTF-8 みたいな話は UTF-32 にすればいいの（誰にも支持されない） OOP の話がほんのかなり終盤に出てくるのは言語の思想なんだろうか？ cargo は便利。 VS Code のサポートが貧弱な気がする。ちゃんと拡張を調べられてないだけかも。 VM Loop とかどう書くのだろうか。VM 命令の Pattern Match で十分速度出るのかな？ |
| データ解釈学入門を読んだ - 2022 夏休み 2022-08-08 14:55:51 統計検定2級や Kaggle で学んだものたちの隙間を埋めてくれる良い本だった。どことは言わないが、読んでいる途中に仕事のことを思い出す記述があり背筋がピンと伸びた。以下雑多なメモ。 分析者のためのデータ解釈学入門 データの本質をとらえる技術作者:江崎貴裕ソシムAmazon 測りやすいデータが選ばれがち。 データを歪めるモチベーション（犯罪件数、いじめ件数は少なくレポートしたい） (大きな声で何度でも）データの前処理は一番時間がかかる。手を抜かない。1つ1つの処理前後で正しいか必ず確認する。決してまとめて処理しない。 多重検定に注意。過去にこれやってたな。 HARKing, p-hacking これは・・・ 数々の認知バイアス |
| Bitcoin and Cryptocurrency Technologies を履修した - 2022 夏休み 2022-08-05 10:23:27 Coursera の Bitcoin and Cryptocurrency Technologies | Coursera というクラスを履修した。Princeton University が提供している仮想通貨のオンライクラス。 自分は仮想通貨を所有していない。仮想通貨やそれらにまつわる技術については、どこかのまとめ記事で読んだ程度という状態だったのだがこれを脱するべく受講。最近は Web3やらDAOやらNFTというワードが飛び交っており、数週間前にもとある書籍が炎上していた。これらを感覚ではなく知識に基づく理解ができるようになるのが目標。もし仮に否定的な立場だとしても「自分が理解できないから否定する」だけは避けたい。 良かった点 ごまかしのない大学の授業。講師陣が深い理解をしていることが分かる。 基礎技術（Cryptographic Hash, Digital Signatures, Public key as identitiesなど）の詳細を丁寧に教えてくれる。 シンプルな仮想通貨を紹介し Double Spending を防ぐ方法など段階を追って説明してくれる。 Bitcoin に関しても多くの時間を割いてる。Bitcoin のトランザクションの生データまで追っているのはとても良かった。 イマイチな点 Andrew Ng の Machine Learning のようなコースを想像すると期待はずれかも。Andrew Ng は抜群に教えるのがうまい。本コースは大学の授業を録画しましたというレベルのもの。 コードを書く宿題がスパルタで万人向けではない。ユーザーレビューでもこれが一番の不満として挙げられている 宿題の意図は仮想通貨トランザクションの一部を実装することでドメイン知識の理解と定着を狙っていると思われる。そこは大変よい。授業の動画を見ただけではスルーしていたようなユーザー間で何をやりとりしているかなどがよくわかる。 Java が分からないと終わる。 Jupyter notebook とかではなくて zip ファイルでソースコードをダウンロードしてコードを書き、コードをフォームから submit する方式。テストやビルドファイルもない。 ノーヒントすぎる。 Java のクラスインターフェースの設計がイマイチ（これは僕の主観） 感想 本質が理解できた（と思わせられた）のは本当に良かった。 hot/cold ストレージ、ウォレット、マイニング、ブロックチェーンの詳細、合意形成、soft/hard folk など技術要素が理解できた。 Bitcoin Scripts 全く知らなかったのだが面白かった。 匿名性についてもかなり深く突っ込んでおり面白かった。2ch, reddit, Bitcoin がどのような意味での匿名性を提供しているのか分かった。 政府の関与とか BitLicense なども。まあそうなるよねという感想。 夢のような技術というよりは、ブロックチェーンという基礎技術の上にかなり苦労して複雑なアプリケーションを構築している感じなのね。このアングルで見ていくと Web3 の見え方も違うかも。 |
| Mosh の Apple Silicon 対応 - 2022夏休み 2022-08-04 17:13:19 scheme.org の方から mosh.scheme.org の利用について声をかけていただいた。せっかくなので Mosh の Apple Silicon 対応をしようと思いたった。なお最後のリリースは 0.2.7 で 2011/6/14 に okuoku さんによって行われている。10年以上前である。 C/C++ で書かれたソフトウェアなので新しいアーキテクチャ(=Apple Silicon)でちょいちょいとコンパイルし直せば良い。という話ではない。なぜならば Mosh のコンパイルには安定して動く Mosh が必要だから。これは gcc のビルドに gcc が必要なのと同じ問題で、bootstrap 問題と呼ばれる。さらにややこしいのが Mosh のコンパイラは Scheme で書かれており、これを VM で実行可能なコードにコンパイルするために Gauche で書かれた VM を使っていたりするので厄介である。 Step1: 0.2.7 リリースを雑にビルドする まずは安定して動く Mosh のバイナリが欲しいのでリリースビルドをビルドする。リリースビルドのビルドには Mosh は必要ない。ビルドするとすぐに GC 周りのエラーになった。10年前の Boehm GC は Apple Silicon に対応していないので以下のエラーになる。 "The collector has not been ported to this machine/OS combination." # error "The collector has not been ported to this machine/OS combination." ^ そこでまず最新の Boehm GC を入手してビルドを試みる。10年の間に Boehm GC のディレクトリ構造などが変更になっており Mosh 側の Makefile に変更が必要である。行儀悪いが直接 Makefile を編集してことなきを得た。 続いて奇妙な以下のテストエラー。 (let ((b (make-bytevector 4 0))) (bytevector-sint-set! b 0 -1 'little 4) (bytevector-uint-ref b 0 'little 4)) : expected 4294967295 but got -1. 詳しく調べてみると Fixnum の 乗算内部で行われているオーバーフローチェックが意図通りうまく動いていないっぽい。 static Object mul(int n1, int n2) { const fixedint ret = (fixedint)n1 * n2; /* Overflow check from Gauche */ if ((n2 != 0 && ret / n2 != n1) || !Fixnum::canFit(ret)) { Return const fixedint ret = (fixedint)n1 * n2; この部分の fixedint は int の alias なのだが Apple のドキュメントによると乗算がオーバーフローしたときの動作は不定のようだ。なのでここは int よりも大きなサイズで判断しなければならず。const long ret = (fixedint)n1 * n2; とするのが良さそう。 これを直してめでたく M1 上で動く Mosh がビルドできた。 Step2: macOS 上で bootstrap してみる さて M1 mac 上で動く安定 Mosh バイナリができたので./gen-git-build.shを実行してみるがエラー。Scheme で書かれたコンパイラを gosh を利用して変換している処理。詳細を調べたり Gauche のバージョンを当時のものに合わせてみたがダメだった。不安定な土台な上で何かをやるのは筋が悪いと気づいた。 Step3: Ubuntu on Docker を試す Linux 上で Mosh をビルドして動かす方が枯れていて良いだろうということで Docker で。i386 Ubuntu image ではうまくいかなかったので i686 Ubuntu image でやってみたら動いた。依存ライブラリの大半は apt install で取得できるのだが、正規表現ライブラリの oniguruma は特定のバージョンをソースコードからビルド。 ./gen-git-build.sh では autoconf も利用しているのだが正直なところエラーが出たとしても対処できそうにない。 無事 bootstrap できたので tar.gz にまとめてドキュメントを書き。 Release mosh-0.2.8-rc1 · higepon/mosh · GitHub にリリースしておいた。 所感 10年以上前に書かれたコードを新しいアーキテクチャで動かすのは思ったよりも面倒。記憶を頼りにいくつものツール・デバッグを繰り返してやりたいことができたが、最近ではそういう面倒にはほとんど遭遇しない。Tensorflow のバージョン違いで問題が起きるとか、cuda のインストールとか平和なものばかりである。懐かしい気持ちだが、ツールの試行錯誤より本質に時間を使える今の方が良いね。 詳細なログはNotes: Mosh 0.2.7 on M1 mac · Issue #14 · higepon/mosh · GitHubに。 |
| Machine Learning Design Patterns 2021-12-11 09:42:55 Scaling Min-max & clipping は一様分布に良い Z-score は正規分布に良い。 input data によっては non-linear な変換の方が適切。例えば Wikipedia page views。これは正直意識してなかった。 この視点で圧力コンペのデータでやってみた（02-01-scaling.ipynb) Categorical 入力が array of categorical である場合は考えたこともなかった。dummy と one hot encoding の違いを理解した。 Design Pattern 1: Hashed Feature Kaggle では経験のないパターン。新しい ID や cold start にも対応できるのが良い。学習データにはない空港が建設された場合どうするか。というのはわかりやすい例だった。感覚的には hash が衝突して全く関係のない入力同士が同じ bucket に入るとうれしくないような。categorical_column_with_hash_bucket の使用例がなかったので書いてみた。 (https://github.com/higepon/Machine-Learning-Design-Patterns/blob/main/pattern-1-hashed-feature.ipynb Design Pattern 2: Embeddings Embeddings は散々使い倒してきたので実装はしない。Embedding size の目安の指標は知らなかったのでメモ。Image の auto encoder による dimension reduction は使ったことないので今度やる。 one rule of thumb is to use the fourth root of the total number of unique categorical elements while another is that the embedding dimension should be approximately 1.6 times the square root of the number of unique elements in the category, and no less than 600 Design Pattern 3: Feature Cross Kaggle で行われている feature engineering の中で最もシンプルなもの。モデルには見えないものを作って見せる。もしくはモデルには見えるかもしれないが学習に時間がかかるものを直接見せる意味合いがある。Crossed feature の見つけ方を書いてくれたらもっと良かった。 Design Pattern 4: Multimodal Input 種々の feature を concatenate して feed するやつ。きちんとした名前がついているのは知らなかった。Kaggle でも多用されてる。別種の embeddings を concatenate するとか。 Design Pattern 5: Reframing Reframing とは Machine Learning Model の Output の種類を変えること。例）Regression が自然なのに Classification にする（またはその逆）。 例：降水量予測問題 問題 Output は降水"量" なので実数を予測する regression タスクだろうか？ 実際にやってみると同じ feature に対して降水量が 0.3 cm のときも 0.5 cm の時もある。 解法 そもそも降水は確率的な振る舞いをするので 1 つの実数値を予測する Regression モデルは合っていないのかも。 Classification model として Reframe する。 Classification 例: 離散確率分布として考える。 Single real value を予測するのではなく。ある範囲の降水量のどのクラスに属するかをそれぞれのクラスの確率を予測する。 この Classification model では異なる降水量の分布を得ることができるのが single value prediction の Regression model と大きく違う。Regression model だと分布のmeanをとってしまうことになる。 なぜ良いか？ bucketing により precision をある程度犠牲にしてしまうが離散化した classification の方が複雑な target を学習するのがうまいらしい。 赤ちゃんの体重の確率分布の話はとても面白かった。best root mean square error が stddev に一致するのも納得。 逆の例：ユーザーの過去見た video id とその raring (1-5) を入力に次に見る video を1つ recommend する classification problem。 Regression problem として video の user space での characteristics を output する Design Pattern 6: Multilabel 画像の中にいる複数の動物名を特定する。文章からふさわしい複数の tag を生成する。 単純な classification なら softmax + argmax で選ぶ。dog, cat, rabbit から1つ選ぶなら [.89, .02, .09] で argmax。足すと1になることに注意。 解法 sigmoid で [.92, .85, .11] のように各要素で 0-1 の確率を出す。 各種 classification まとめ binary classification softmax は冗長なので sigmoid + binary cross entropy loss。 multilabel sigmoid + binary cross entropy loss。 sigmoid 結果の parse 方法 softmax + argmax のようには行かない。各クラス label を採用するか threshold が必要。 Design Pattern 7: Ensembles Model の Prediction に誤差がある。なぜか？ (1) 減らせない誤差：dataset にある noise、問題の framing、よくない訓練データなどに由来する誤差。 (2) bias=Underfit. (3) vairiance=overfit. Ensemble 手法 Bagging: high variance を解決する。k個のモデルに対して k 個の subsample された学習データを用意。各モデルの出力を aggregate する(mean / majority vote) Boosting: Ensemble Model は各サブモデルよりも capacity を上げるので bias を減らす方向に動く。Gradient Boosting の boosting。 Dropout は bagging の一種と考えることもできるというのは目から鱗だった。 Design Pattern 8: Cascade 問題 usual（よく起きる）とunusual（滅多に起きない）の両方に対して値を予測したい。モデルは滅多に起きないことを無視する方向で学習してしまう。 unusualの方をoverweightする方法もあるがusualの方が精度が落ちてしまう 直感的には以下のCascade Design Patternを思いつくだろう usualかunusualかを予測するモデルを作る usualケースを予測するモデルを作る unusualケースを予測するモデルを作る 本番時のpredictionでは1つ目のモデルの出力に応じて1つ目もしくは2つ目のモデルを呼び出して予測 上記の問題は。1つ目のモデルのtrue labelがないこと。1つ目のモデルが間違った場合、2つ目3つ目のモデルは今まで見たことのないような入力で予測をする羽目になる。 解法 usualかunusualかを予測するモデルを作る usualケースを予測するモデルを作る unusualケースを予測するモデルを作る 2つ目と3つ目のモデルの出力を入力にするモデルを作る（これが最終出力） 注意点：他のパターンと違いこのパターンはベストプラクティスとは限らない。複雑である。パフォーマンス悪くなるかも。MLの問題を分割するのは一般的に良くない。なぜならばMLは複数の要素が絡んだものを学習する能力が備わっているから。 Design Pattern 9: Neutral Class 薬処方でイブプロフェンかアセトアミノフェンどちらを処方するか？というbinary classificationではなく。どちらでも良いというneutralなクラスを追加するという話。全然関係ないけど null object pattern を思い出した。 Design Pattern 10: Rebalancing 問題: 特定のクラスのデータが少ないとモデルがそのクラスの分類を学習してくれない。 解法 適切なevaluation metricを選ぶ F-measureとか。test set はオリジナルデータセットと同じバランスでなければいけない。 Downsampling majority class のデータ数を学習時に減らす。 ensembleと組み合わせることが多い。その場合はmedianをとる。減らす majority クラスをその度にランダムに変えてモデルを学習すれば良い。 Weighted classes Kerasならclass_weight で特定のクラスが重要だよとモデルに教えることができる。=> よく効いた Output Layer Bias class weightに追加してモデルのoutput layerのbiasをimbalanceを加味してセットする。=> 効いた Upsampling 特定のクラスのデータを複製して増やしたり、生成する。down samplingと合わせて行われる。 SMOTE は生成を自動でやってくれるアルゴリズム。 Cascade パターンも使える down sampling と class weightを組み合わせることもできる。down sampling 後のバランスに合わせてclass weightを設定する。 SMOTE を利用したover sampling も試して効いた。 Design Pattern 11: Useful Overfitting 意図的に training data に overfit して利益を得る。 以下のような場合には overfitting が望ましい input が物理ベースのもので数式で precise state が計算できる場合など。それを模倣するように model に学習させる場合は overfitting させるべき。 Distilling bigger model の場合も。小さなモデルは bigger モデルが生成した training data に overfit すべき。 Design Pattern 12: Checkpoints 学習時間が伸びるにつれてエラーで止まった時のコストが高い。checkpoint を保存しておけば途中からトレーニングを再開できる。 作者も書いていたがこれは実は簡単ではなくて、learning rate とか optimizer なども復元しないといけない。Colab がもっと弱かった頃はかなり頑張って resume できるようにしていたが最近はサボってる。 Design Pattern 13: Transfer Learning pretrained model の final output layer を取り除き(正確には flatten 以降）モデルを nontrainable にする。final layer をすげ替えて学習すれば完成。以前 Kaggle のコンペの public notebook でこの方法を学んだが。なぜうまくいくのか？を直感的に理解していなかったので良い学びがあった。著者らが公開しているnotebookは必ず実行してみるべき。驚くほど短い training でそれなりの精度が出る。 fine-tuning は完全に nontrainable にするのではなくて一部のlayersをtrainable にする。 その分学習に時間がかかる train data が多く。元のモデルと同じ種類のデータの場合はこちらの方が効くかも。 Transfer learning は text & image がメインだが TabNet は tabular data で良い結果を残しつつある。 Design Pattern 14: Distribution Strategy データ量とモデルのサイズは大きくなるばかり。シングルGPUだと学習時間が14 daysとかも。 方法は2つ data parallelism 各ワーカーが training data のサブセットに対して処理をする synchronous training 各ワーカーはモデルのコピーを持っていて forward 後 gradient を計算。各ワーカーの gradient を集約して中央サーバーが gradient step してモデルパラメータを更新。最新のモデルを各ワーカーに渡す。 待ち合わせやワーカー同士のコミュニケーションで overhead がある。 1つのマシン+ multiple GPUs だと速くできる。 overhead があるので batch size を可能な限り大きくするべき。ただし val_loss が急激に大きくなる場合があるので注意。 asynchronous training 各ワーカーの gradient を集約せず、asynchronous でパラメータを更新するのでスループットが高い。 model parallelism model が分割され各ワーカーはモデルの一部を担当する Design Pattern 15: Hyperparameter Tuning 全ての組み合わせを試すのは無理。 keras-tuner library (Baysian optimization) Design Pattern 16: Stateless Serving Function 問題 train したモデルをそのまま production に deploy するといくつか問題がある (1) Model をメモリにロードしなければならないがとても大きい（embedding layers, deep なモデルなど） (2) train 時は Python で書かれていたが、Serving 時は違う言語でという要求がある (3) Model の input/output の形式は training に最適化されているが user friendly とは言えない。例えば serialized binary より JSON の方がうれしいとか。 解法 Model export: learning rate, drop-out など不要なものを取り除いて model の数学的なコアのみを export する Inference: serving_fn として取り出して実行する Web endpoint: Cloud function などで stateless に export する 仕事でMLしたことがないので。production deployment の話は面白い。Web フレームワークという成熟した技術基盤に乗せてしまい。監視・スケーラビリティなどを任せようというすっきりした解法であった。 Design Pattern 17: Batch Serving 問題: 1つのリクエストで全ユーザーのプレイリストを作るようなユースケースではどうすれば良いか？ 解法 Distributed Data Processing (BiqQueryなど） で簡単にできるよ。 Design Pattern 18: Continued Model Evaluation 問題: Model を deploy して終わりではない。production でも意図通り動いているか？もし動かなくなったら検出できる？ 解法 モデル性能悪化をモニタリングする。そのためには raw_data, ground truth, prediction が必要。 Serving 時にサンプリングして raw_data, prediction を保存。ground truth は通常遅れて入手されることが多い。 これも Kaggle では学べないもの。継続的にモニタリングして性能が意図通りか確認することは予想できていたが、ground truth の入手は serving 時よりかなり遅れることがある。などの課題には気づいてなかった。counterfactual も考えると難しいね。 Design Pattern 19: Two-Phase Predictions 問題: ユーザーの device で prediction したい時がある（フィットネスアプリとか）。その場合はモデルのサイズなどトレードオフがある。 解法: 問題を2つに分ける。シンプルで edge で実行するもの。それを引き継いでクラウド側でやるもの。例: Google Home。 Design Pattern 20: Keyed Predictions 問題: 大量の入力に対する出力は分散して predict される。分割された output を元の input に対応する形で整える必要あり。 解法: client に入力とともに key を指定させる。 Design Pattern 21: Transform 問題: Model への input は実際に model が計算に使う形式とは限らない。入力は text だが計算に使うのは embedding vectorとか。training 時とprediction時の何らかの入力の違いによるミスは大問題。 解法: input を feature にする部分をきちんと認識して分ける（Transform） 驚くべきはBigQuery がTransform句をサポートしていること。こういう間違いが起きない強制力は素晴らしいと思う。prediction 時だけ特定の feature engineering 忘れるとかなくなる。 Tensorflow は feature engineering をグラフに含める方法をサポートしている。tf.keras.layers.Lambda でやるやつ。 cons: feature engineering とモデルを分けられないので、別モデルを試しづらい。feature engineering のキャッシュが難しい。feature engineering の結果のデータ分析が難しい。 Design Pattern 22: Repeatable Splitting test, train, valid のデータ分割の話。Kaggle で実地で学んだので略。 Design Pattern 23: Bridged Schema 問題: デリバリーのチップ額を予測するモデル。支払いタイプが現金とカードで予測するモデルがある。データ元の改善によりカードの詳細が取れるようになった（gift, debit, credit) 。今すぐにでもこの有用なデータでモデルと学習し直したいがまだデータが少ない。どうするか？ 解法 古いデータの schema を新しいデータにマッチするようにブリッジする。新しいデータは可能な限り全て、古いデータは augment してモデルを学習する。 スキーマをブリッジするとは？古いデータの支払いタイプカードは本当は新しいデータタイプの gift, debit, credit のどれかだったはずだがそれは記録されていない。これを probalistically or statically にブリッジできる。 Probabilistic method: 新しいデータではカード種別の割合が分かっているので（例: 10%, 30%, 60%）古いデータをロードするたびに一様分布から0-100数値を取り出す。それに応じて古いデータのカード種別を設定する。 おすすめStatic method: カテゴリカル変数は one-hot encodingされることが多いので。古いデータの支払いタイプは [0, .1, .3, .6] とする。新しいデータの方はそのまま [0, 0, 1, 0] などとする。 他にやること まず新しいデータから十分な evaluation データをとっておく。件数は evaluation metrics が安定するくらいに。 bridge する古いデータの件数を決める。 Design Pattern 24: Windowed Inference 問題: 空港の発着の遅れについて。「通常より遅れているか？」を判定したい。時間帯によって遅れの傾向は違うので2時間のタイムウィンドウの中で異常値加判定する。prediction 時にはどうすれば良いのか？ 解法 モデルの state を時間に沿って保存する stream processing を実行する フライト到着時間のスライディングウインドウを作る。ウィンドウは2時間で終わるが10分ごとに閉じる。つまり10分毎に過去2時間の集約値を計算する。 モデルの内部stateは新しいフライト情報が入り次第更新される。 ウィンドウが閉じるたび（この例では10分毎）に time series ML モデルが2時間のフライトリスト情報で学習を行う。そしてこのモデルはこれから未来のpredictionに使われる。 time series モデルパラメータは状態変数として外に保存される。LSTMの場合model weightがこれに当たる。 このシンプルな例ではモデルパラーメタは2時間ウィンドウの平均遅延時間と偏差になる。 Design Pattern 25: Workflow Pipeline end to end の model deploy運用をコンテナ化で行うという。もっともな内容。まあそうですよね。 Design Pattern 26: Feature Store 問題: Feature engineering はad hocかつone offになりがちなのでプロジェクトや組織をまたいだ共有が難しい。 解法: 一箇所にコードとドキュメントをまとめてそこを使うようにする。オープンソースの実装もいくつかある。 Design Pattern 27: Model Versioning 問題: モデルを更新したいが後方互換性も維持したい 解法: 新しいモデルは別のRest API endpointにデプロイする Design Pattern 28: Heuristic Benchmark 問題: 自転車レンタル使用時間の予測モデルのtest set に対する MAE が 1200 秒である。これはビジネスの観点から良いか悪いのか？特にこれが初めて作ったモデルだと比較対象がない 解法: 直感的に理解でき、比較的簡単に計算できるmetricsを定義する。 Table 7-1の例がとても良い。 Design Pattern 29: Explainable Predictions 問題: test set に対する MAE などの指標が分かってもそれだけではユーザーからの信頼は得られない。なぜその結果になったのか説明してほしい。もしかしたら意図しないbiasをもとに判断しているかも。 解法: feature attributions。各々のfeatureがどの程度出力に寄与したかを求める。 Instance level attributions: 各予測に対して attribution を求める。例）特定の決済がなぜ承認されたか？ Global attributions: モデル全体として attribution を求める。instance level の平均と言っても良い。例）飛行機の遅延時間予測では天候が一番原因となっている。 ここで SHAP 登場。 Design Pattern 30: Fairness Lens 問題: 学習データやパイプラインのどこかで問題のあるバイアスが入り込むことがある。 解法: 学習前にバイアスを特定し、学習したモデルを Fairness Lens を通して評価する。モデルとデータで全てのユーザーグループを平等に扱う。 Training 前 Data Analysis をして Data bias を見つける。例) race, gender などが balanced かどうか。classification problem なら label が balanced かどうか？data label をする人の主観 bias はないか？ 上記 balance を維持したまま train, test, valid のデータ分割を行う。 What if tool が便利そう Training 後 model に bias が入り込むことがある。原因はデータにあった未発見のbias、モデルアーキテクチャ、optimization metrics など。 training 後の model を What if tool に渡して test set に対する prediction を見てみる |
| MATHEMATICS FOR MACHINE LEARNING の読書記録 2021-08-06 09:34:24 いくつかの Kaggle competitions を経験し数学の復習が必要だと気づいたので Mathematics for Machine Learning を読む。まずはトライアルで2章を読み切る。新・数学の学び方 を参考に以下のルールで読みすすめる。 数式を完全に分かるまで追う。 実際に手を動かして同じ式変形をする。分からない場合は覚えるまで式変形を繰り返す。 記録をここに残す。 どうしても分からないところは誰かに質問する。 これがうまくいくようであれば仲間を募る？ https://mml-book.com 読後の感想など 数字 355 ページ 12章 70日 GoodNotes の手書きノート407ページ なぜ読んだか 冒頭にも書いたが Kaggle Indoor コンペでチームメイトの Saito さんのやっていることが分からなかったのが直接の動機。それ以外にも Discussions で線形代数の基礎が分かっていれば深い理解が得られそうな場面もあった。 なので機械学習をからめて線形代数を網羅的に勉強したかった（正確には復習）。 何を得たか 以下の2つが大きい。 70日間ほぼ毎日、数式を書く・追うことを繰り返して勘を取り戻していった（助けて下さった Twitter の皆さんには感謝しかない） 網羅的に勉強したのだから大丈夫。という謎の安心感。（これはCSを網羅的に学習したときも感じた。） Twitter での記録 (上が最新） すべてのノート 12章 11章 10章 9章 8章 7章 6章 5章 4章 3章 2章 2021/6/16 朝。Exercis 2.20 終わった。 e と f の答えが合わず悔しい。どこで間違った。これにて2章読了。合計20日・ノート117ページ。サポートしてくださった。@Ak141J, @kengohirachi, @__garzon, @NeXTSTEP2OSX, @TwShotaro , @melonsode (敬称略)本当にありがとうございました。3章も挫折禁止でいきます。 2021/6/15 夜。Exercise 2.20 d まで。もう少し 2021/6/15 朝。Exercis 2.15 G={(a-b, a+b, a-3b)|a,b∈R} の basis の求め方が分からない。(a-b, a+b, a-3b) が basis かとも思ったが a,b∈R なので定まっていないから違う。(a-b, a+b, a-3b) = (a-b)[1 0 0]T + (a+b)[0 1 0]T + (a-3b)[0 0 1]Tと書けるから the canonical basis でよいのだろうか 良くない。詳細は__garzon@さんのコメント。 2021/6/14 Kengo Hirachi (@kengohirachi) さんによるヒント で Exercise 2.12 光が見えた。本当に感謝。 2021/6/13 Exercise 2.12 で突然 basis of U1 ∩ U2 を求めろと言われお手上げ。そもそも intersection について言及なかったはず。 2021/6/12 Exercise 2.5 まで。2.2 はぱっと見の難しさがすごい。読み解くとギリギリ分かる範囲。 2021/6/11 (1) Rank Nullity Theorem の唐突感。何がうれしいのか分からず戸惑う。(2) Affine subspaces のところで間違いを見つけて errata 見たら修正されてた。(3) というわけで2章は Excercises を残すのみ！ 2021/6/10 Image and Kernel の Definition 2.23 まで。Basis Change は数式が多かった。おかげで飛躍が少なく理解しやすかった。Kernel/null space と書いている割に文脈によっては null space を多用しているけど ker(φ) と。面白い。 2021/6/9 Theorem 2.20 (Basis Change) の途中。やりたいことの背景は分かるのであとは式を丁寧に追うだけのはず。 2021/6/8 (2.94) は https://twitter.com/Ak141J/status/1401922706858135554 において @Ak141J さんが教えてくださった。方法で完全に納得しました。 2021/6/10 更新。Nyoho@NeXTSTEP2OSX さんに間違いをご指摘いただいたので修正。このスレッドから追える。 2021/6/5 式 (2.94) がやはり分からない。あいまいな理解を減らすために 2.7.1 を全体的に見直して 2.94 直前までは理解できたのだが分からない。明日もうすこしネットで同じ内容のものを探そう。 2021/6/3 (2.94) まで。Example 2.21 がが理解出来ないので明日も続ける。任意のx∈V, y∈Wのlinear mapping について話していたのにいつの間にか basis の変換の話に。 2021/6/2 (2.84)まで。generating set, basis, rank 。新しい概念がたくさん。rankは分かったような分からないような。 2021/6/1 (2.76)まで。Linear Independence をクリア。定義、例、直感的な説明、手を動かしてようやく理解できた気がする。 2021/5/31 Example 2.12 まで。Example 2.12 内の The intersection of arbitrarily many subspaces is a subspace itself. がしっくりこない。 Kengo Hirachi (@kengohirachi) さんによるコメント 参照。いつもコメントくださってありがたい。 2021/5/30 事情により時間を取れず 2021/5/29 式(2.64)まで。Gaussian Elimination の計算に苦労した。Group を学んでからの Vector Spaces の定義は分かったような分からないような。 2021/5/28 式(2.53)まで。きちんと追えたと思う。 2021/5/27 式(2.45)まで。式(2-40)から(2-43)が最初全然分からなかった。Ax=b の解 x=x' 。Ax=0 の解 x=x'' はA(x'+x'')=b を満たすので x'+x'' は Ax=b の解であることは分かる。だがなぜそれが一般解なのか。Ax=0 を満たす解を2種類求めているのはなぜなのか？が分からなかった。 2021/5/26 式(2.37)まで。さすがに覚えている内容だが式をきちんと追った。 1章 2021/5/26 本書の読み方的な章。 |
| Indoor Location & Navigation コンペ振り返り 2021-05-18 17:28:09 Indoor Location & Navigation というコンペで9位入賞。目標だった Kaggle Master になったので振り返り。これはチームメイトである @KaggleSaito さんとの成果である。 どういうコンペか？ 与えられたスマホセンサーデータ(Wifiなど)からショッピングモールでのフロアと位置を推定する。これがうまくいけば、例えばイオンモールの無印の近くにいるときに適切なクーポンをユーザーに届けられるかもしれない。 評価指標 大まかに言うと真の (x, y) との距離が小さければよい。何階か？を外すと大きなペナルティ。 自分のモデル 他のチーム同様 Wifi データをメインに LSTM/GRU のモデルで位置を推定し、post processing で精度を高めた（大きな画像へのリンク） 他のチームとの差別化要因は Training Data を水増しできたこと。コンペの host が提供する utility 関数に ``compute_step_postion``` という関数がありセンサーデータを人間の歩み(step) に変換できる。これを以下で述べるアプローチと組み合わせると精度が上がった。 Kouki さんが Shareししてくれた Wifi データを LSTMにに入力する方法の視点を変えて、より自然な waypoint ベースの training set を生成した。 Saito さんの提案ではじめた Pseudo Labeling がよく効いた。 LSTM/GRU の Stacking。 Saitoさん主導の Post Processing。 floor image を利用しての hallway map を作成。 hand labeling ではない waypoint の生成 試したがうまく行かなかったもの Transformer hallwayからハズレた場合に大きなペネルティを与える custom loss（実装大変だった） 作業環境・実験管理 Colab Pro のハイメモリをメインで使った。データのサイズが大きくメモリに載せるのが大変だった。ML力よりもエンジニアリング力がある自分としてはとても有利だったと思う。 Colab Pro は notebook 機能はほぼ使わず。安価に GPU が使える実行環境として利用した。 実行環境の入出力（データセット）は API を利用して Kaggle Datasetを使う 以前は Google Drive だったが圧倒的に Kaggle datasetののほうが良かった。 実行ボタンを押すと、Kaggle dataset からデータダウンロード、実行 scriptを git からチェックアウト。学習が終わったら結果を Kaggle dataset にアップロード。 各実験ごとに番号を振り、その notebookで実行ボタンを押せばすべてが再現するようにした。 コーディングは Localの Visual Studio Code on Macで。 Docker は非力なローカルマシンでは足枷にしかならなかったので今回はやめた。 自分が伸び悩んでいたところがわかった 自分は長らく金メダルが取れずに伸び悩んでいたのだが。どうすればよかったのかがようやく分かった。 データをよく見ること EDA しよう。データを良く見ようとはよく言われることだ。本にも書いてある。分からないなりに EDA notebook を作り visualize したことは何度でもあるか正直ピンときてなかった。今回うまく行った方法は、他人が書いたデータプロセスコードを行レベルで完全に理解し数倍に高速化すること。その過程で「分かった」と思っていたが全然肌感覚で理解していなかったデータの関係が見えてきた。そして高速化・自分のコードに書き直したことでその先のステップに進みやすかった。 ツールや API への習熟 これも当たり前すぎるかもしれない。有名な Grand Master Abhishekさん のYouTube 動画を見たときに衝撃を受けたのを覚えている。pandas の各種機能 keyward 引数など調べずにスラスラ書いていた。一方自分はすべて検索しながらコピペしながらである。 このコンペでは上記の高速化があったので、たくさんコードを書いた。今なら何も見ずに pandas の groupby や LSTM モデル・データセットのコードを書く自信がある。 |
| Visual Studio Code キーバインディング微調整 2021-04-28 09:53:52 Command Palette にアクセスするキーバインドが動いていない気がする ctrl + ; に割り当てた when expression を空にしないと動かなかった Go to Definition cmd + t Go Back cmd + r Ctrl x b が効かない。 Karabiner-Elements がバッティングしてた。Karabiner-Elements の設定から Ctrl-x as prefix を消した。 |
| Riiid コンペ復習 - maskingなど 2021-01-11 13:19:21 これは Riiid! Answer Correctness Prediction | Kaggle において自分が理解できていなかった部分をまとめるもの。間違いを含む可能性がある。間違いを見つけたら @higeponja にお知らせください。 Riiid はいわゆる time series コンペ。きちんと masking をしないとleakage が発生する。このあたりの自分の理解をまとめる。 未来の情報を使ってはいけない train/infer 時のマスク 未来の情報を train/infer 時に使ってはいけない。これを厳密にやらないと leakage になる Transformer の attention で未来を見てはいけない。例）問題番号 102 の正解・不正解が分かれば、以前の問題101の予測は簡単になるかもしれない。いわゆる triu マスク。 task_container_id を共有する問題は、すべての問題を解き終わらないと答えを知ることができない。これは Riiid 固有の話。そのため未来を参照しないマスクとあわせてもう1つマスクが必要。下記 task mask 参照。src_mask, tgt_mask, memory_mask すべてに同じマスクが必要。 train & validation split 厳密には train/valid を split するときに task_container_id を分断してしまうと leakage が発生する。これの影響は軽微であるというコメントもあった。なぜならそれは分断面のみで起こるからデータが大きければ影響が少ないからだと思われる。 pad を参照しない loss 計算時に pad 部分を mask する。 auc 計算 今回の Transformer 系の解法ではデータを右側に寄せる解法が多かった。これは長さの異なる input でも必ず seq[-1] が求める prediction になるから。このことから auc 計算時にはseq[-1] のみを計算対象とするべきだったようだ。 間違い、新発見があれば追記するかも。 |
| Google Football コンペ 2020-12-12 09:20:35 銅メダルでした。 以前のRLコンペから学んでやらなかったこと DQN などの自前実装：自分の学習のためなら良いが、自前実装はバグりやすくたくさんの罠がある。すでに動いているベースラインが運営から提供されているのでそれを使う。そうすれば reward / observation の調整などの本質に集中できる。本コンペの場合は seed_rl ベースの notebook が提供されていた。 初挑戦したこと seed_rl を利用することで GCP の AI Platform に詳しくなった。間違った configuration で高額課金になってしまうことを恐れていたが、きちんと document を読んでいけば怖くないよ。 やってよかったこと 論文と関連研究の読み物。これにより成功しそうな施策のリストができた（例：difficulty を徐々に上げる adaptive learning) GCP フリークレジットへの申込み。コンペの途中でわかったことだが football は GPU ではなく CPU heavy な training プロセスだった。GPU P100 1つにつき n1-standard_96 * 4 の構成で学習させる。これはクラウド以外ではほぼ不可能だった。 失敗したこと 失敗ではないが GCP クレジット(or お金)がもっとあれば training で試行錯誤できた。 seed_rl を TPU で動かすことが競争優位性となると思いがんばったが、実質不可能だった。早めに運営に質問すれば良かった。 大まかな試行錯誤の流れ 初期段階では自分のベースラインを作ろうと思い pfrl で簡単にデモを書いた。discussion で質問するにつれて seed_rl に勝てる部分がないことに気づき捨てた。 observation については以前の RL コンペから直接画像を入力するのは問題外だとわかっていたので SMM を time series で 4 つ stack したものをそのまま利用。結局 observation を変更することはなく最終日までこのままだった。ちなみに stacking することを submission コードで考慮していなかったので序盤に score が伸びず悩んだ。 reward はこれも score,checkpoint の両方がすでに用意されていてそれらがベースになった。kyohei さんが中盤から checkpoint reward を減衰させるコードを書いてくれた。agent が点数を入れられるようなってからは checkpoint は逆に足かせになるから。 最初から hard 相手に training するよりも徐々に対戦相手を強くしていくほうが学習効率と最終的にもっと強くなるらしいので試してみた。アイデアは簡単だが実装は gym env の理解が必須だったので真面目に取り組んだ。がんばれば difficulty を動的に変更できたので良かった。 GCP + seed_rl でのトレーニング seed_rl は強化学習フレームワークで learner (GPU) と複数の actor からなる。actor は episode を play するわけだが自分の action を決める場合の inference を自分自身では行わず GRPC で learnerで行うことで学習を scalable にするところが肝であった。 learner の GPU を使い切るには actors の数が物を言った。vcpu を 96 個つんだ instance を 4つかうという富豪構成。フリークレジット $1000 をもらえたとはいえかなりの制約だった。 team のメリット kyohei さんに声をかけていただいてチームを組ませていただいた。ほぼ毎日 slack で議論して試行錯誤した。進捗の共有には dynalist を使った。チームを組むと自分に足りないものがよく見えてとても勉強になった。自分はもっと深くものを考えないといけない。つい浅はかな考えを元に手を動かしてます。 もう一つのメリットはやはり心が折れないこと。仲間がいるとがんばれる。 |
| Visual Studio Code + Docker for Kaggle 2020-12-04 15:51:30 Kaggle 用の docker image が公開されているのでそれを Mac 上の Visual Studio Code 使う。 やったこと Remote-Containers という拡張を入れて拡張経由で docker を使う。これは host と container 内の両方で Visual Studio Code を起動するので開発環境=実行環境になりうれしい。 devcontainer.json に Container で起動する Visual Studio Code にインストールしたい拡張の記述 諦めたこと Container 内で GitHub に push などをやろうとした。.git_config の共有、credential を環境変数で渡すなど。どれもうまく行かなかったのでやめた。よく考えれば host 側のファイルシステムを mount させてhost 側で commit すれば良い 非 root ユーザーでの実行。tutorial に従ったが home directory が permission error で作れなかった。深堀りはしなかった。 想定する開発フロー Visual Studio Code で Container 起動。 そのまま編集。 Visual Studio Code の console で実行 GitHub へのコミットは上記の通り |
| Karabiner-Elements 2020-11-09 14:03:19 Karabiner-Elements を使っていたのだが Visual Studio Code で有効になり困っていたので入れ直す。 それでしたら frontmost_application_unless でできます!オフにしたい機能ごとにこういう条件をmanipulatorsに付けるとできます。bundle_identifiersは https://t.co/jNVsPKVqdq.VSCode なので com\\.microsoft\\.VSCode にされるといいと思います。 https://t.co/xZDdfmev0s— Nyoho (@NeXTSTEP2OSX) 2020年11月7日 で教えていただいたことを元にきれいにインストールした時のメモ。 現状の問題点 macOS 上で Emacs キーバインドが使えるのは良いが、Visual Studio Code で有効になると困る。なぜならば VS Code では別途 Emacs キーバインドが用意されておりそちらを優先したい。 クリーンインストール ~/.config/karabiner を別の場所に退避 Karabiner-Elements 設定 - Misc - Uninstall Karabiner-Eelements mac 再起動 macOS の素の状態を確認 Ctrl-W は効かない。 Ctrl-F や Ctrl-B などは効く。これは macOS の機能？ Visual Studio Code で Ctrl-X Ctrl-F や Ctrl-X B などが効くことを確認。 Karabiner-Elements を公式サイトからインストール 設定 起動 Version 13.1.0 Complex Modifications - Add Rule - Import more rules from the Internet Emacs key bindings (rev 12) の上4つを有効にする。 追記 number1cruncher.com にある mark region とか ctrl-y を取り込む。 https://github.com/higepon/dotfiles/commit/c912fdd6624354d373426c8dc3d3920658fc4f2e#diff-0dc7a7cc6b2e4051d7e9ecd928e8af90f31115dc774b182451abf6b496ba3762 |
| Kaggle Halite コンペ + 強化学習 2020-09-17 10:39:18 Halite by Two Sigma | Kaggle に参加していた。今回はお誘いいただいて @threecourse さん と @Seed57_cash さんとチームで挑んた。 コンペの目的 4人プレイの岩塩(halite)集めゲーム 1プレイヤーが複数の shipyards and ships を操作することが可能 盤面サイズ 21 x 21 のボードゲーム 詳細はここ 前半: チーム結成前 強化学習で解くことを決意。以前学んだ強化学習は記憶から飛んでいるので1から勉強し直すことに。決めた方針は 強化学習は難しいので、とにかくシンプルスタート 時間がたっぷりあるので DQN を自前で実装して理解を深める halite コンペではなく、もっとシンプルな connectx コンペで練習する Colab Pro 結果としてこの方針は良い面も悪い面もあった 良かった点 DQN の実装にとても苦労したので強化学習のデバッグに強くなった。動いていないのはなぜか？に対して仮説が立てられるように connectx は十分にシンプルな題材で、他にも強化学習で解いている人がいたので参考情報が多かった Colab Pro はすばらしい :) 悪かった点 DQN は不安定だったのでかなりの時間を溶かしてしまった。理想的には理論を理解し、サンプルを実行しあとはライブラリを使うのが正解な気がする 時間はたっぷりなかった。強化学習はデバッグ・トレーニングに時間がかかる 後半: チーム結成後 @threecourse さんに pfrl を教えてもらい自分の実装を移植した。ライブラリを使うと責任の分担がはっきりするので observation, reward そして model に集中できる。さらに DQN が動くようになると数行の修正でより安定した PPO が動くようになりコストパフォマンスが大変良かった。チームメイトと slack で議論・情報共有しながらできたのはとても良かった。他にも @threecourse さん と @Seed57_cash さんがモデルについて話しているときに、「ああ。このくらいやらないとだめなんだ」というベースラインをしれたのは大変ありがたかった。 実装の詳細 ship の convert はハードコーディング 1 ship が 1 agent self play (自己強化学習） 上記2つから 4人対戦の場合 4 * ship の数の agent がいることになるので training 負荷が高かった reward 衝突回避が難しかった。結局大きな goal (= 最終的にゲームに勝つ）では衝突回避は学習できなかった。衝突を事後検知して失われたスコアに応じて負のrewardを与えた ship は4方向の移動と動かないという選択肢があるのだが、compound 命令として deposit を定義した。これのおかげで deposit という行動を取ると reward を貰えることを学んでくれた observation 6チャンネルの 2D array (自分の位置、味方の船、shipyard の位置、時間経過、halite の位置、spawn予定地) どこまで行けたか 1人プレイ & 1 ship で halite をあつめて deposit => OK 2人プレイ& 1 ship for each で haliteをあつめて deposit => OK 2人プレイ & 2 ship for each => カオス 結局複数プレイヤー複数 ship は正しく動くところまで持っていけなかった。pfrl を正しくない方法で使っているのでそれが原因かもしれない。 所感 強化学習は安定させるのが難しい。ただしデバッグ方法を理解すれば、かなりましになる。 チームでやるほうが学びがある。本当にありがたい。 実世界で役に立つ強化学習もやってみたい。 |
| DQN デバッグメモ 2020-08-25 18:21:34 デバッグの過程をまとめる。ほぼ自分用。 自分用のまとめ PyTorch でも tensoarboard を使ってたくさんログをとる。ログをとればおかしいところはみつかる。 ログすべきもの observation を tensorboard で visualize する。 次の最善手が分かっている observation を手動で作る。policy network が出力する action values を tensorboard に出力する。その action value が最善手に converge するか見守る loss benchmark agent との対戦結果。win rate ではなくて win/draw/lost 数をプロットする。 1 episode の長さをプロットする。self play では徐々に長くなることが想定される self play でなければ average reward。 eps decay curve 。これをプロットして学習が進む前に random move をやめてしまうのを防ぐ。 特に注意すべき点 agent に渡されている observation を人の目で観察する。与えられた情報で自分が勝てるようになるか考える。 observation を neural network 用に加工するときにミスをしていないか確認する。 reward が clipping されているか。 Target network の更新頻度を調節せよ policy network の更新式を理解してデバッグする 同様の試みの learning rate / モデルサイズ / learning が始まるまでの steps などを参考にする 以下は自分がデバッグしていたときの生ログで未整理です。 可能な限りログを取る reward, action, observation, average_reward などを logger でログを取る。 Visualize Observation を人の目で見られるように visualize した。もともとの DQN 実装が current_state - prev_state = observation としていたが、これではどうやっても Connect X では勝てない。差分だと置かれた１つのコマとそのポジションしかわからない。 epsilon decay DQN では agent に exploration させるために一定の確率で action を random sample する。この確率は episode が進むにつれて小さくなるように設計されている（＝学習が後半で進むと仮定しているから）。この確率をログしてみると。どうも学習が全然進んでない段階で小さくなりすぎているように見えたので調整した。 loss reward ばかりに気を取られて loss をグラフに描いてみたら様子がおかしい。初期にガクッと下がって、その後ぐんぐん上がっていく。これはおかしいのだろうか。まずは loss の定義から見直そう。 To minimise this error, we will use the Huber loss. The Huber loss acts like the mean squared error when the error is small, but like the mean absolute error when the error is large - this makes it more robust to outliers when the estimates of Q are very noisy. とある。そもそも error は以下ののものを比べている。 state=s, action=a に対する Q value. Q(s, a)。 memory から取り出した s と a に一致する Q value をNN から取り出したもの 次の time step における最大の Q value * γ + r。 memory から取り出した next_state に対して最大のQ value とそれを与える action を特定 このエラーが徐々に大きくなるのはいくつかのシナリオが考えられるが、まずは詳細なログを取ってみよう。 100 episodes ごとに Q value の絶対値が大きくなっていることが観察された。それにともない loss が相対的に大きくなっているように見える。Q value が大きくなっているのはなぜか。ある state に対する報酬全体が上がるとは、初期状態に Q function が見積もっていたよりも実際の報酬が高いということ？reward をログしてみた。reward は 1, -1, 0 のどれかである。reward を non_final_mask で絞るとすべて 0 だ。あれこれでは学習進まない？ と思ったけど正しそう。他のDQN実装とも見比べた。あと loss が increase するのはありっぽい。 python - Cartpole-v0 loss increasing using DQN - Stack Overflow 状況を整理 観察されていること loss が下がってそのうち上がる 同時に random agent との対決での勝率が下がる 仮説またはアイデア そもそもどれくらいで Converge するのかを調べる 他の実装を動かしてみて観察する loss が下がりきったときの勝率を見てみる。Eearly stopping するの？ episode 200 あたりで下がりきって勝率もそこから下がる 普通の NN なら下がり続けるので上がる理由が理解できない。 learning rate が大きすぎるのでは learning rate 1e-3 にして実験中 qvalues が stable で値も爆発していない。良いかも！ 50000 episodes は少なかったかも。 Pytorch DQN - ConnectX | Kaggle だと 5e-4 200000 episodes, average reward も print しよう eps が急激に小さくなっていた。 うまく動き出したような気がする eps をグラフに描いたら明らかにおかしかった。学習の初期に一気に最小値まで下がってしまっていた。EPS_DECAY = 200000 ほどにするとゆっくり下がってよい。この変更により明らかに avg reward が変わった。 うまく行っていると思う理由 - avg reward が徐々に上がって正の数になっていること。つまり勝ちが多い。 - 同様の指標だが実際の戦闘で勝率 0.5 を超えていること - とある state に対する qvalue が converge している など。loss は必ずしも下がるのが正解とは言えないということらしい。 うまく動いたものを保存するために別ディレクトリにグラフと script を隔離。 問題点 reward stats の計算に間違いがある 最大限 debug しているので遅い。1 episode の時間を計測しよう。 loss の振れ幅が大きいので learning rate を小さくしてみよう Colab でうごかしてみよう Colab で動かしてみた lr=1e-2 qvalues と loss は全然収束してないのに Avg reward と Win rate は上がっている。 Colab で動かしてみた lr=1e-3 qvalues と loss は収束しているが Avg reward は下がっている。 速度改善・クラッシュ修正 pyplot がメモリを使いすぎてクラッシュ。描画点が増えるにつれて pyplot が急激に遅くなり学習時間よりも長くかかってしまう。Tensorboard in Pytorch の乗り換えてすべて解決。ちなみにグラフだけではなく observation を画像として Tensorboard に表示することも可能。こうやって苦労すると Tensorboard のすばらしさが分かる。 lr=1e-2 9万エピソード loss, qvalue ともに収束してないように見える 勝率は 0.5 をほぼつねに超えている 勝率は高めだが分散が大きい 以上の観察から lr が大きすぎてうまい local optimal を見つけられないのではと推測。 lr=1e-3 7万エピソード loss, qvalue ともにどこかに収束しつつあるように見える。自信なし。 avg reward > 0 である 1e-3 よりはまともにみえる。しかしやはり他の記事を見ると loss の大きさが気になる。 DQN debug ブログを読み解く Solving Open AI gym Cartpole using DDQN - The intersection of energy and machine learning batch size model parameter 可視化 target copy 頻度 10 episode ごとではなくて 10000 steps ごとにした target copy うごいてる？？？ next q も表示してみる target net の update の更新頻度 上記ブログを読んでみると target net の更新頻度の目安が書いてあり 10K - 100K step ごとらしい。頻繁すぎたかも。 lr=1e-3 10000 steps で更新 loss の scale が自分が思っていた範囲に収まっている。qvalue もしかり。 ところで以下も visualize してみたが policy net と target net の weights がおかしくない？5000 step 離れるとこんなに変わるものか？いや変わるか。5000 steps ごとのはずなのに全然表示されない部分がある。値がゼロに集中するわけではないし。これはなんだろうか。その後 debug したが target update は正常に行われていることを確認した。全然表示されないのは頻度が少なすぎるのかもしれない。 lr=1e-2 10000 steps で更新 submission lr=1e-2 10000 steps で流して reward を観察する。まずうまく動いているかを確認する。 うまく動いているならば early stopping が stability を試みる。local で random agent に対して 0.81 ののものを submit した。Score は 580.7。弱いが。最初の1歩。 negamax との対戦 random 相手に学習しても強くならないのは明らかなので、もう少し強い negamax と戦わせてみる。途中で時間切れになったが少しずつ reward が上がっているのが見える。ただし negamax はアルゴリズムとして遅いのであまり学習に向かないのでそこまで。 self play self play を試みているが、まだコードが正しいか自信が持てない。気づいた点を片っ端から直していく。 episode time が定期的におそくなっている これはかなり怪しい。学習速度の足を引っ張っている可能性も。play 自体にかかっている時間かどうかを切り分けよう。結論 negamax との対戦が遅い。これはどうしようか。とりあえず頻度を下げた。 かかる時間 10000 episodes にかかる時間は ~4000 secs。 観察1 negamax との win rate がとてもゆるやかに上がっている qvalue が収束していない eps decay が速く下がりすぎている 次のステップ この学習をそのまま走らせておく eps decay を緩やかにしたものも走らせる 結果：同様に win rate が下降気味。ただし qvalue は収束しつつある。 eps decay を緩やかかつ lr=1e-3 にしてみる。 結果：同様に win rate が下降気味。ただし qvalue は収束しつつある。 仮説：常に自分自身と戦うと成長しないのではないか？過去の自分のスナップショットと戦わせよう。 過去の自分と対決するコードを書き始める 過去の自分と対決 self play を実装した。 時間をかけても強くなっていない。一方で他のグラフは特に矛盾がない。このことから agent が本当に強くなる前に世代交代しているのではないかという仮説を立てた。そのため Alpha Zero の論文のようにパラメータを改める。 - 100 episode ごとに世代評価を 1000 に。 - 対戦数を 11 -> 100 に。11 だと偶然6勝してしまうことがありそう。 あと気になるのは avg_reward が 0 以下なのに世代交代が起きていること。これは episode の reward の平均をとっていたからだ。勝負がつかないのは -0.05 が積まれるから。avg_reward は勝負がついたときの reward の平均としよう。 self play negamax, random を evaluation として使う reward が上がっているのは良い。 level は右肩上がりで良い random 相手でも勝率 0.5 はだめすぎる。 仮説1: random 相手に勝てるようになるにも時間がかかる 検証する方法。 ConnectX の DQN 実装他に探す。収束までの episodes 調べる。 Pytorch DQN - ConnectX | Kaggle これによると negamax に勝つのは難しいっぽいが 14K episodes で random には勝ててる。 仮説2: 実装に間違いがある Pytorch DQN - ConnectX | Kaggle これ読む。 もう一度コード読み直す。 グラフを見て怪しいものを探す 仮説3: 1000 steps あたりでは vs random で勝率 0.85 だった。そのあと忘れた？ 試すこと Observation mean 0 std 1 に scaling する 20200815_experiment_standardize_pixels.ipynb で試している 特に変化なし。 大きい replay buffer 100000 20200815_exp_buffer_100000.ipynb loss の order が小さいままなのはよいのか？右肩下がりに random との戦績が下がっている。 1000000 20200815_exp_buffer_1000000.ipynb 上記とあまり変わらず Look at sensitivity of EVERY hyper parameter lr 1e-3 をためそう 100000 と比較すること random 相手に 0.5に収束。 eps length 11 あたりに収束 勝率0.55 ではなくて 0.60/0.70 でせだいこうたいはどうか？ Look at episode length (sometimes more informative than episode reward). episode length がきれいに長くなっている。これは良い傾向か？勝負がながびく reward は -0.05 にしているけども。あとやっぱり長引くにつれて random に負けるのはなぜ。もっとよく考えろ。多分良い傾向。お互い強くなってミスをしなくなっている。でもなぜ random 相手に勝てないのか？ You might need a huge buffer, so adapt code accordingly 仮説: 勝率が 0.5 に近づく = random に近づくということから model が学びをリセットし続けている。モデルサイズが小さいという仮説。 他の実装をみる - https://github.com/kirarpit/connect4 を見ると 6x7 の board size だと死ぬほど時間がかかると書いてある。4x5だとすぐに収束するようだ。 - 試してみたが全然だめ。 - - board_size 変えられるかな？ https://codebox.net/pages/connect4 ここはネットワークサイズが分かる。 debug Q-Learning 復習。今回は完全に理解した！ だめな点 先手後手どちらも学ばせないといけない。next_state があるから。 先手・後手の色は変えてはいけない。=> これはまちがい。OKです。 盤面にある数で自分の手番はわかる。 scaling で色は変えてはいけない。 loss が 1000 steps を超えたら急激に上がる target update 頻度を上げたら loss のけたがあがりすぎた？ そう。target に近づいて loss 下げる前にまた自分で更新されたら辛い。 よくよくself play reward を log してみたら 0 と 1 しかなかった。self play だと自分の手番で負けることがないから！！ reward を 0 -> -1 にしたら全て動くようになった。 |
| Reinforcement Learning の self play についてのまとめ 2020-07-27 19:57:54 強化学習の self play について知りたいことがあるので、ざっくりと有名な論文を読んでいく。熟読はしない。 知りたいこと self play は同一インスタンス、別インスタンスどちらか？ 直感的にはどこかで stuck しそうな感じがするけど？ 学習が進んでいることをどのように評価するか？ 論文 Mastering the game of Go without human knowledge + AlphaGo Zeroの論文を読む その4(自己対局) - TadaoYamaokaの日記 性能指標 Elo rating for each Training time 最良の model インスタンスを更新していく checkpoint で evaluate して 55% 以上で勝てたら入れ替え 同一インスタンスかはわからなかったが明記されてないということは同一？ stuck しないらしい Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm) 上記と同じっぽい Beating the World’s Best at Super Smash Bros. Melee with Deep Reinforcement 6種類の違うモデルを戦わせた。過去の自分と戦わせたとの記述がある。 game 内に内蔵されている別AIとの対戦で評価？ |
| Jupyter/Colab における pyplot リアルタイム描画 2020-07-24 13:09:57 強化学習の様子を visualize するために pyplot でグラフをリアルタイム描画していたが遅くて筋が悪いのでやめた。inline で表示すると plot 数が増えると極端に遅くなりボトルネックになる。inline リアルタイム描画をやめて、画像ファイルとして出力して inline 表示も試したが同様。もともと気軽に見られるようにとの意図だったが完全に裏目に出ているのでやめる。tensorboard のように log からグラフ描画のほうが筋が良さそう。 |
| 強化学習/RL/Reinforcement Learning のデバッグ方法 2020-07-13 19:36:20 RL のデバッグは難しい。RLアルゴリズムの選択、適切な reward の設定、Deep RLの場合モデルの選定、実装の正しさ、適切なパラメータ、そもそも学習できる問題なのか。切り分けが難しい。世の中には同じように思っている人がたくさんいるようだ。情報元から適当にまとめる。 情報元 What are your best tips for debugging RL problems? : reinforcementlearning Deep Reinforcement Learning practical tips : reinforcementlearning williamFalcon/DeepRLHacks: Hacks for training RL systems from John Schulman's lecture at Deep RL Bootcamp (Aug 2017) DQN debugging using Open AI gym Cartpole - The intersection of energy and machine learning チェックリスト 低次元の state をもつシンプルな environment で問題をかんたんにする reward を simple にしてみる。すぐに効く形の feedback も良い。 random policy に解かせてみる。random でも時々問題を解けそうなら有望。 自分の目で observation を見て、自分でも解けるか確認 Observation mean 0 std 1 に scaling する Reward も可能なら scale する Observation/Reward に outlier がいないことを確認する 動くかな。やってみよう。はうまくいかない。たくさんのことを正しくやらないと学習は進まない。 agent を正しく実装することがとても重要。他のコードよりもテストが大事。 可能な限り unit tests を書く ありとあらゆる場所に asserts を。matrix dimension, input, output, action の range 長い時間実行する前に、1行1行目を皿にしてコードを読む。 可能な限り見える化、すべてを log する いくつかの states をピックアップして q-value を見てみる。徐々に変わって stablize されるはず。 すべての input/output/state を記録する Neural Net がからむと 10 倍難しくなる。最初は Neural Net でやらず。うまく動いたら swap する seed を固定する optimizer の選択にsensitiveなので注意 すべてを normalize せよ 良い結果が出ているものは100-1000 の reward 使ってる 参照実装が使っている hyper parameters 使う 大きい replay buffer, bigger batch size 常に simple version から試して動くことを確認 そもそも agent はときどき正しいことをやっているの？ DQN は収束がおそいよ |
| RL での batch size 2020-07-05 12:37:19 Reinforcement Learning を Welcome to Spinning Up in Deep RL! — Spinning Up documentation で勉強しながら実装している。とある実装で batch size = 5000 となっていて「値が大きすぎる」と思い、何気なく小さな値に変更した。それをすっかり忘れて試行錯誤しているうちに policy gradient (logprob) が 0.0 になってしまい学習が進まない減少に悩まされた。ログを見て、よくよく考えてみたら logprob が 0 ってことは選択された action の確率が 1 ってことだ。つまり policy はどんな状態でも1つのアクションしか取りようがない状態をモデルが学習してしまっていた。さらに観察すると、これはある episode で agent が右に移動し続けただけで大きな報酬を得てしまったのを学習したのだとわかった。batch size が小さかったせいでこれが大きく聞きすぎてしまったようだ。 |
| OpenAI Gym の MountainCar が難しいという話 2020-06-30 15:59:51 Vanilla Policy Gradient を勉強・実装している。CartPole はうまく学習できるのに MountainCar の学習が進まない reward -200 であり続けるという減少にハマった。RL のデバッグは本当に難しく、観察してもよくわからなかった。検索してみるとまさに同じ減少で困っている人が解決方法を紹介していてくれた。結論だけ書くと official env の reward が厳しすぎるので独自の reward を定義しようというものであった。納得。あとから見返してみれば明白なのだが気づけなかった。 Solving Curious case of MountainCar reward problem using OpenAI Gym, Keras, TensorFlow in Python – A Software Engineer's Journal |
| Colab + PyTorch Lightning + Comet ML + Bert 2020-03-10 09:20:47 Colab + PyTorch Lightning + Comet ML - higepon blog の続き。 目標 Tensorflow 2.0 コンペで自分が書いた training のコードを Colab + PyTorch Lightning + CometML に移植する。移植したことでメリットがあるかを検証する。 Google Drive の利用とその失敗 Colab を利用すると 12時間毎にマシンがリセットされる。つまり巨大な kaggle の dataset や生成物が全て消えてしまう。生成物の例としては train/valid split したものとか modelを save したものとか。これらを毎回生成するのは無駄なので Google Drive 上に置いておく。これをダウンロードすれば良い。というコードを書いたのだがうまく行かなかった。生成にかかる時間はほほゼロになったが Google Drive から生成物をダウンロードする時間が支配的になってしまった。ボツ。 移植 transformers Bert のモデルを TF2.0 で使ったモデルにする。 import torch from transformers import ( BertModel, BertTokenizer ) bert_model_name = 'bert-large-uncased-whole-word-masking-finetuned-squad' tokenizer = BertTokenizer.from_pretrained(bert_model_name) bert = BertModel.from_pretrained(bert_model_name) 次に LightningModule の Optional な callback をコメントアウトする。validation_step, validation_end, test_step, test_end は Optional である。 forward と training_step を埋めてこんな感じになった。batch が dataloader の返すものかな。 def training_step(self, batch, batch_nb): # batch input_ids, attention_mask, token_type_ids, no_answers, y_batch = batch # fwd y_hat = self.forward(input_ids, attention_mask, token_type_ids) # loss loss = loss_fn(y_hat, y_batch, no_answers) # logs tensorboard_logs = {'train_loss': loss} experiment.log_metric('train_loss', loss.detach().cpu().numpy(), step=self.global_step, epoch=self.current_epoch, include_context=True) return {'loss': loss, 'log': tensorboard_logs} 謎の CUDA エラー データローダーの実装が終わり end to end で動かしてみると以下のエラー。 RuntimeError: CUDA error: device-side assert triggered 付加情報がない。普通の PyTorch NN なら同じモデルを CPU で動かすと詳細なエラーが分かるのだが transformer Bert はどこかで GPU 前提っぽい。と思ったが CPU 上で動かせた。num_classes が 5 であるべきところが別の config file が使われて 2 になっていた。これが cross entropy loss を計算するところでこけてた。 |