競プロ 📅 2022/8/2 · ☕ 7 min read 貪欲 deque スタック キュー グラフ化 (Graph) BFS DFS Bit全探索 DP 累積和 二次元累積和 尺取法 二分探索 Union-Find ソート ダイクストラ ベルマンフォード ワーシャルフロイド 最小全域木 PQ セグ木 最大流 スター型グラフ 二次元座標を二部グラフにする(ABC 131 F) dpはとりあえず立式したほうがいい Dpは解けなそうで何でも解けるので、亜種dpを徹底的に試すと良い ダブリング ... #競プロ #アルゴリズム #post
【論文メモ】TokenGT: Pure Transformers are Powerful Graph Learners 📅 2022/8/2 · ☕ 2 min read グラフをそのままTransformerにブチこむ手法 GNNより帰納バイアスが少ないが, GNNよりも良い精度を達成 入力について まず, ノードとエッジをそれぞれ独立なものとして捉え, それぞれを同等にトークン $X$とする そのトークンに, ノードなのかエッジなのかを判別するType Identifiersをconcatして入力 トーク ... #論文 #Graph
Monkey saddle 📅 2022/8/2 · ☕ 1 min read $z=x^3-3xy^2$をMonkey saddleと呼ぶらしい https://en.wikipedia.org/wiki/Monkey_saddle Monkey saddleは退化臨界点である (cf. Morse関数) ... #数学 #post
Morse関数 📅 2022/8/2 · ☕ 1 min read M を n 次元可微分多様体とする. M 上の $C^∞$ 関数 $f : M → R$の臨界点 $p$が非退化であるとは, $f$ の $p$における Hessian $H_p(f)$ が正則行列となることである.すべての臨界点が非退化であるような関数を Morse 関数とよぶ. https://www.ms.u-tokyo.ac.jp/~kohno/lectures/g1-7.pdf ... #数学 #post
【論文メモ】Why do tree-based models still outperform deep learning on tabular data? 📅 2022/8/1 · ☕ 1 min read なぜテーブルデータではGBDTなどの決定木ベース手法がNNよりも強いのかについての論文 1つ目: NNは高周波数成分の学習に弱い なので, 飛び値的なデータに弱い 一方決定木ベース手法は領域を長方形に区切ってるだけなので飛び値的なデータに強い 詳しくは拙作→決定木をフルスクラッチで書けるようになろう (CART) NeRFやPerceiver: ... #論文
【論文メモ】Deformable Attention Transformer 📅 2022/8/1 · ☕ 1 min read 詳しくは輪講スライド Deformable Conv のDeformと同じ grid上のpositionに対して, offset分positionをずらしてAttention 正式なoffsetはbilinear補完によって求める オブジェクトごとに受容野を歪めることができる ... #論文
【論文メモ】Prototypical Contrastive Learning of Unsupervised Representations 📅 2022/8/1 · ☕ 1 min read 輪講スライド 背景 Instance-wiseな教師なし表現学習 : 加⼯された画像(instance)のペアが同じ元画像に由来するかを識別 MoCo SimCLR SimSiam など Instance-wiseな⼿法における2つの問題点 1- 低次元の特徴だけで識別できるため, 識別はNNにとって簡単なタスク → **⾼密度な情報をエンコードしているとは⾔い難い ** 2- ペア間 ... #論文 #対照学習 #自己教師あり学習 #EMアルゴリズム
【論文メモ】GSAM - Surrogate Gap Minimization Improves Sharpness-Aware Training 📅 2022/8/1 · ☕ 2 min read はじめに SAMの改良 (SAM : Sharpness-Aware Minimization) Surrogate Gap Minimization Improves Sharpness-Aware Training 論文メモ 問題提起 SAMの計算式では, 本当にフラットな損失点を見つけているとは言えない $$L_\mathcal{S}^\text{SAM}(\mathbf{w}) \triangleq \max_{|\mathbf{\epsilon}|_p\leq\rho} L_\mathcal{S}(\mathbf{w}+\mathbf{\epsilon})$$ 例えば下の図では, 近傍 $f_p$について最適化すると, SAMの場合, 青に収束してしまう危険がある 本当に見るべきは以下に定義するsurrogate gap $h(x)$ $$h(x) := f_p(x) - f(x)$$ surrogate gap $h(x)$については, H ... #論文 #Optimizer
【論文メモ】RegionCLIP: Region-based Language-Image Pretraining 📅 2022/7/30 · ☕ 1 min read 問題点: CLIPは画像全体を用いるため, 物体検出には向かない そこで, 本論文ではCLIPをRegion-text matchingへと拡張した CLIPを用いた open-vocabularyな物体検出タスクが行える open-vocabulary object detection 関連研究としてViLDを挙げている ViLD: Open-vocabulary Object Detection via Vision and Language Knowledge Distillation CVPR22 流れ [RPN](Resion Proposal Network)を用いて候補領域を探す RP ... #論文
RPN 📅 2022/7/30 · ☕ 1 min read Resion Proposal Network 背景なのか, 物体が写っているのかだけを識別するサブモジュール Faster-RCNNにおいては, ①RPNで領域を絞ってから, ②それぞれ個々の物体についてラベルを絞っていく Faster-RCNNの学習では, 「RPNの重み更新→モデル全体の重み更新」を繰り返して学習 RPNでは, Anchor boxが背景か物体か / 物体ならばGTとの ... #機械学習 #post
WL test 📅 2022/7/28 · ☕ 1 min read 引用: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/ 正式名称: The Weisfeiler-Lehman Isomorphism Test グラフが同型であるかチェックするアルゴリズム 各ノード $i$に適当なラベル $C_i = 1$を割り当てる 隣接するノードの多重集合 $L_i$をノードに記録する 多重集合 $L_i$をハッシュに通して新たな $C_i$を得る ( $C_i \leftarrow hash(L_i)$) 以上を繰り返して, ノードの分割 ${C_i}$が収束したら停止 2つのグラフが[* 同じ $ ... #Graph #数学 #post
【論文メモ】When Shift Operation Meets Vision Transformer: An Extremely Simple Alternative to Attention Mechanism 📅 2022/7/28 · ☕ 1 min read Attentionはglobalでdynamic dynamicについては On the Connection between Local Attention and Dynamic Depth-wise Convolution しかし global→SwinTransformerを見るとそこまでViTの精度に関係なさそう dynamic→MLP-Mixerを見ると, MLPはstaticなので精度に関係なさそう そこでShiftViTを提案 上図のように, 入力の ... #論文