競プロ
· ☕ 7 min read
貪欲 deque スタック キュー グラフ化 (Graph) BFS DFS Bit全探索 DP 累積和 二次元累積和 尺取法 二分探索 Union-Find ソート ダイクストラ ベルマンフォード ワーシャルフロイド 最小全域木 PQ セグ木 最大流 スター型グラフ 二次元座標を二部グラフにする(ABC 131 F) dpはとりあえず立式したほうがいい Dpは解けなそうで何でも解けるので、亜種dpを徹底的に試すと良い ダブリング ...
【論文メモ】TokenGT: Pure Transformers are Powerful Graph Learners
· ☕ 2 min read
グラフをそのままTransformerにブチこむ手法 GNNより帰納バイアスが少ないが, GNNよりも良い精度を達成 入力について まず, ノードとエッジをそれぞれ独立なものとして捉え, それぞれを同等にトークン $X$とする そのトークンに, ノードなのかエッジなのかを判別するType Identifiersをconcatして入力 トーク ...
Monkey saddle
· ☕ 1 min read
$z=x^3-3xy^2$をMonkey saddleと呼ぶらしい https://en.wikipedia.org/wiki/Monkey_saddle Monkey saddleは退化臨界点である (cf. Morse関数) ...
Morse関数
· ☕ 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 ...
【論文メモ】Why do tree-based models still outperform deep learning on tabular data?
· ☕ 1 min read
なぜテーブルデータではGBDTなどの決定木ベース手法がNNよりも強いのかについての論文 １つ目: NNは高周波数成分の学習に弱い なので, 飛び値的なデータに弱い 一方決定木ベース手法は領域を長方形に区切ってるだけなので飛び値的なデータに強い 詳しくは拙作→決定木をフルスクラッチで書けるようになろう (CART) NeRFやPerceiver: ...
【論文メモ】Deformable Attention Transformer
· ☕ 1 min read
詳しくは輪講スライド Deformable Conv のDeformと同じ grid上のpositionに対して, offset分positionをずらしてAttention 正式なoffsetはbilinear補完によって求める オブジェクトごとに受容野を歪めることができる ...
【論文メモ】Prototypical Contrastive Learning of Unsupervised Representations
· ☕ 1 min read
輪講スライド 背景 Instance-wiseな教師なし表現学習 : 加⼯された画像(instance)のペアが同じ元画像に由来するかを識別 MoCo SimCLR SimSiam など Instance-wiseな⼿法における２つの問題点 1- 低次元の特徴だけで識別できるため, 識別はNNにとって簡単なタスク → **⾼密度な情報をエンコードしているとは⾔い難い ** 2- ペア間 ...
【論文メモ】GSAM - Surrogate Gap Minimization Improves Sharpness-Aware Training
· ☕ 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 ...
Toronto Paper Matching System
· ☕ 0 min read
...
【論文メモ】RegionCLIP: Region-based Language-Image Pretraining
· ☕ 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
· ☕ 1 min read
Resion Proposal Network 背景なのか, 物体が写っているのかだけを識別するサブモジュール Faster-RCNNにおいては, ①RPNで領域を絞ってから, ②それぞれ個々の物体についてラベルを絞っていく Faster-RCNNの学習では, 「RPNの重み更新→モデル全体の重み更新」を繰り返して学習 RPNでは, Anchor boxが背景か物体か / 物体ならばGTとの ...
WL test
· ☕ 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}$が収束したら停止 ２つのグラフが[* 同じ $ ...
【論文メモ】When Shift Operation Meets Vision Transformer: An Extremely Simple Alternative to Attention Mechanism
· ☕ 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を提案 上図のように, 入力の ...
