【論文要約】FederBoost: Private Federated Learning for GBDT - ⬜︎⬜︎⬜︎
はじめに Federated Learningに興味があり色々確認していたのですが、決定木ベースのモデルはないのかと思うようになりました。 探してみると以下の論文が出てきたので、読みました。 メモとしてここで簡単にまとめます。 arxiv.org はじめに 概要 イントロ 事前知識 GBDT Federated learning Secure aggregation Differential privacy 設定 環境の設定 FLの設定 Vertical FederBoost 学習 バスケット化 差分プライバシーノイズ付加 学習の全体像 推論 プライバシー保護について Horizontal FederBoost 分散バケット構築 学習 プライバシー保護について 実装と実験 有用性の検証 効率性の確認 LAN設定の場合の結果 WAN設定の場合の結果 概要 Federated Learning
XGBoost と LightGBM に実装されているポジションバイアス除去を試してみた
はじめに 以前も記事にしたが、ウェブ上のユーザーの行動ログを使って推薦システムを開発している自分のようなMLエンジニアにとって、ランキング学習におけるポジションバイアスの除去は重要なテーマである。サービスのログは通常様々なバイアスに塗れており、特にリストの上位に表示されたアイテムほどクリックが集まりやすくなってしまうポジションバイアスは非常に厄介だ。アカデミアではこの手のテーマはだいぶ研究が進んでいるものの、これまでは論文や書籍で手法が紹介されるだけで、手軽にパッと使えるライブラリは存在しなかった。 しかしどうやら最近になって XGBoost や LightGBM という多くの人が使う強力なGBDTライブラリにポジションバイアスを除去する機能が実装されたらしく、これが使い物になるのであれば実務で利用するハードルがグッと下がると思い、実験して性能を検証してみた。 検証に使うデータセット ここ
セグメント木を使う
競技プログラミングに慣れ親しんでいる方なら、セグメント木というデータ構造について、一度は聞いたことがあるでしょう。この記事は、セグメント木の構造を理解する必要はないが、使い方を知っておきたいという方のために書かれています。 この記事では、まずセグメント木について紹介し、それからセグメント木を実際に使う際の技法について紹介します。 セグメント木とは セグメント木は、固定長配列にいくつかの操作を加えたデータ構造です。セグメント木は、基本的には以下の操作を時間計算量 O(\log n) ですることができます。 i 番目の要素に x を代入 i 番目の要素を取得 l 番目の要素から r 番目の要素のモノイド積[1]を計算 ここで、モノイドを知らない方もいるかもしれませんので、モノイドについて紹介します。 モノイド モノイドは、実数や複素数の足し算や掛け算、文字列の連結といった、集合とその演算をまと
オイラーツアーした木に対するクエリ - Qiita
この記事に新規性はありません。maspyさんの記事、beetさんの記事がとても分かりやすいです。また、紹介しているテクニックはmaspyさんの記事で紹介されているものです。 maspyさんの記事: Euler Tour のお勉強 beetさんの記事: 2種類のEuler Tourについて オイラーツアーとは？ 根付き木を根からDFSして根に戻ってくるような経路（の探索）。競技プログラミングの文脈ではこの行きと戻りの経路について以下のような情報を記録しておくきRMQやRSQを適応することで木に対するいくつかのクエリを高速に処理できる。 各頂点のinとoutの時刻 それまでに辿った辺や頂点の重さなどの情報を記録 各頂点の深さの情報 用語 行きがけ: あるノードから子に移動する 帰りがけ: 子からその親ノードに移動する 実際の例 1を根とする以下の木があるとします。 時刻0は根である1にいてDF
プリム法ベースのシュタイナー木 - bowwowforeachの日記
AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
【論文解説】TabNetを理解する
さて今回は、最近テーブルデータの予測においてKaggleでもよく使われているTabNetの解説をしたいと思います。 このサイトでは自然言語処理分野がメインで画像認識分野を少しという感じでしたが、テーブルデータについても面白い発展があるようですね。 以下は簡単にまとめたTabNetの特徴です。 ディープラーニングをベースとしたモデル。特徴量の選択や加工などの前処理が不要で、end-to-endで学習することができる。アテンション・メカニズムを使い、各決定ステップ(decision step)において使用する特徴量を選択する。 アテンション・メカニズムにより解釈性が向上し、重要な特徴量をうまく学習することができる。全サンプル共通ではなくサンプルごとに重要な特徴量を選択する。いくつかの特徴量をマスクし、それを予測するという事前学習を行う。 特徴量の選択が不要で、自動的に、しかも全体ではなくサンプ
Facebook のオープンソース最適化ライブラリAx を使ってXGBoost のハイパラチューニングを行ってみた - Qiita
製造業出身のデータサイエンティストがお送りする記事 今回はFacebook のオープンソース最適化ライブラリAx を使ってXGBoost のハイパーパラメータをチューニングしてみました。 はじめに 勾配ブースティング木に関しては、過去に記事を書いておりますのでそちらを参照して頂けますと幸いです。 勾配ブースティング決定木（XGBoost, LightGBM, CatBoost）を実装してみた Optuna を使ったハイパラチューニングに関しても、過去に記事を書いておりますのでそちらを参照して頂けますと幸いです。 勾配ブースティング決定木（XGBoost, LightGBM, CatBoost）でOptunaを使ってみた Ax とは Ax は、Facebook のオープンソース最適化ライブラリです（公式のGitHubページ）。 Ax は、ベイズ最適化（GP-EI)を使ってハイパーパラメータを
XGBoostとtsfreshでMultivariate time series forecasting 備忘録 - Qiita
概要 feature-engineがきっかけで最近チェックしているPyDATA この動画を見ながらKaggleの株価予測をsktimeで試してみるか、ってモチベが上がって（よくある）久しぶりのsktimeを触っていたらtsfreshをラップしたapiに気づいたので、先にtsfreshの素性を調べてみるか、と回りくどい流れ。 時系列初心者にはマストな内容の講演動画で超オススメ。ハッ！と思わせるやり取りが質疑応答にあってとても良かった。 今回はおもにtsfreshを使って説明変数を増やすことが目的で、XGBoostは精度確認しSHAPでimportanceを可視化する程度のおまけ。 Daskのように独自の馴染めない世界観がありDocumentsの例もわかりにくく、少し手間取ったので残す。 実施期間: 2022年12月 環境：Colab パケージ：tsfresh, XGBoost, SHAP,
なぜCatboostの推論は速いの？ - 簡単なレポート
前回の記事｢AutoML v.s. Catboost｣に出てくるCatboostは、XGBoostやLightGBMと比べて30-60倍も推論が速いという特徴があります。 推論時間は、kaggleなどのコンペでは推論に時間をかけられるのであまり気にしませんが、実サービスとなると重要ですよね。 推論時間の比較 以下のグラフは、3大GBDTライブラリでの推論時間比較です。Catboostがずば抜けて速いことがやかります。 そして学習時間の速さに定評があるLightGBMは、なんと最遅です。 この推論時間の速さは、CatboostがGBDTのベースとなる決定木に symmetric tree と呼ばれる、特殊な形の木を使っているからです。 ここで、symmetric treeとは以下の図の右側のような木です。左側は普通の決定木です。 なぜsymmetric treeは速いか ｢同一の深さではすべ
[python] kd木を使った最近傍探索 - Qiita
おそらくちゃんと機能している kd木 仕組み とても説明しづらいがざっくりと説明したい 自分の説明はわかりづらいので以下のpdfを見ることをお勧めする。 Kd-treeと最近傍探索 https://hope.c.fun.ac.jp/mod/resource/view.php?id=15284 今回説明するkd木はあくまで自分が採用した方法であり、他にも微妙に違ったkd木の作り方とかあるらしい。 二次元データを例として使う [出典] https://medium.com/@schmidt.jerome/k-d-trees-and-nearest-neighbors-81b583860144 kd木のデータ構造は、データの軸をずらしながら、それぞれの軸の中央値を取ることで作ることができる 中央値といっても厳密な意味ではなくデータ数が偶数の時は中央らしき二つの点のうち大きい方になる 具体的には上
![[python] kd木を使った最近傍探索 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/4fc8b0e9fc12931ef25e05d42fae80a01eb144b2/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fqiita-user-contents.imgix.net%252Fhttps%25253A%25252F%25252Fcdn.qiita.com%25252Fassets%25252Fpublic%25252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%253Fixlib%253Drb-4.0.0%2526w%253D1200%2526blend64%253DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRmxoMy5nb29nbGV1c2VyY29udGVudC5jb20lMkYtQkx5Smd3TFI3eTQlMkZBQUFBQUFBQUFBSSUyRkFBQUFBQUFBQUFBJTJGQUNIaTNyY0NDdHBKaVFUNW8tZ3NEV1ZsNFFVNzZuanMwQSUyRnM1MC1tbyUyRnBob3RvLmpwZz9peGxpYj1yYi00LjAuMCZhcj0xJTNBMSZmaXQ9Y3JvcCZtYXNrPWVsbGlwc2UmYmc9RkZGRkZGJmZtPXBuZzMyJnM9YmU3YTJmY2ExZmViYzg0ZTNkNzcxMzI4MzI4ZWRiOTM%2526blend-x%253D120%2526blend-y%253D467%2526blend-w%253D82%2526blend-h%253D82%2526blend-mode%253Dnormal%2526s%253Dfe8a54dce4971f90dd8004e8eb81d352%3Fixlib%3Drb-4.0.0%26w%3D1200%26fm%3Djpg%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9JTVCcHl0aG9uJTVEJTIwa2QlRTYlOUMlQTglRTMlODIlOTIlRTQlQkQlQkYlRTMlODElQTMlRTMlODElOUYlRTYlOUMlODAlRTglQkYlOTElRTUlODIlOEQlRTYlOEUlQTIlRTclQjQlQTImdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzFFMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtcGFkPTAmcz01YjdlZjA4NjU0NTk0YTBkYzY1OTQ5NjIxODg0NzAxZg%26mark-x%3D120%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBSQUQwTiZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPTI3ZDMyODI3NmZlMzVjZDk2ZTBlODNjYTRhYTQzNTE3%26blend-x%3D242%26blend-y%3D480%26blend-w%3D838%26blend-h%3D46%26blend-fit%3Dcrop%26blend-crop%3Dleft%252Cbottom%26blend-mode%3Dnormal%26s%3D3bdc2f07a98ec501657fbabff2bf1ea1)
TabNetのアーキテクチャを詳しく解説 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに kaggleでは2020年ぐらいから当たり前のように使われるようになってきたTabNetですが使ったこともないですし、どんなアーキテクチャなのかも知りませんでした。今回は実装というよりもTabNetについて理解が深められたらと思います。 参考： TabNetとは一体何者なのか？ ：TabNetの概要についてわかりやすく解説している記事です。 TabNetを使えるようになりたい【追記①lgbmとstacking（ちょっと上がる）】 ：atmacup #10のディスカッションで上がっていたものです。恐らくコンペ参加しないと（後から
Adversarial Random ForestsによるテーブルデータのAugmentation・モックデータ生成
はじめに こんにちは。株式会社アイデミーデータサイエンティストの中沢(@shnakazawa_ja)です。 本記事ではAdversarial Random Forestsを使ったテーブルデータの生成について、RおよびPythonでの実装を紹介します。 Adversarial Random Forests (ARF) とは ARFは2023年にProceedings of The 26th International Conference on Artificial Intelligence and Statisticsに採択された論文で提案された、テーブルデータに対して密度推定と生成モデリングを行う高速な手法です[1]。 その名の通りGAN[2]とRandom Forestを組み合わせた手法で、生成と識別を交互に繰り返すことで元データの特性を学習し、元のテーブルデータと類似したデータを生成
Tree Tensor Networkを用いた画像分類器 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに テンソルネットワークは、量子多体系などの高次元なデータを効率的に扱うための手法として利用される技術ですが、近年、テンソルネットワークを機械学習に応用する研究が様々行われています。 今回は、文献[1]を参考に、Tree Tensor Network (TTN)を用いて、画像の分類を行うモデルをPyTorchで実装し、MNISTとFashion-MNISTに対して、その性能を確認してみます。 概要 今回用いるTree Tensor Network (TTN)は、その名の通り、木構造のテンソルネットワークです。 今回取り上げるTTN
ランダムフォレストをスクラッチで実装したい - Qiita
非Deepな機械学習手法としてランダムフォレスト (Random Forest) を選択する場面は多々ありますが、基本的にライブラリ任せになってあまり中身を意識することがありません。ので、今回はランダムフォレストの内部的な仕組みを確認しつつ、それを踏まえてPythonでスクラッチ実装していこうと思います。 ランダムフォレストについて ランダムフォレストの仕組みに関する分かりやすい記事は探せばいくらでもあるので、ここでは以降が読みやすくなるよう実装の視点から少し解説をつけておきます。 ランダムフォレストはたくさんの決定木から構成され、決定木はノードから構成されます。イメージとしては以下のようになります。 なので、実装の手順としては、 ノード : Node 決定木 : DecisionTree ランダムフォレスト : RandomForest の3つのクラスを実装していきます。 1. ノード
勾配ブースティング(Gradient Boosting)を理解する - Liberal Art’s diary
（↑from scikit-learn User Guide Gradient Boosting Out-of-Bag estimates — scikit-learn 0.24.1 documentation） 当記事では勾配ブースティング(Gradient Boosting)について簡単に確認を行います。 勾配ブースティングについては少々フォーマルな記載が多く理解が大変なのですが、上記の「scikit-learnとTensorFlowによる実践機械学習」の記述が比較的わかりやすいので、こちらを元に簡単に確認したのちにWikipediaの記載を簡単に確認します。 以下、今回の目次になります。 1. 概要の把握 2. Wikipediaの確認 3. まとめ 1. 概要の把握 1節では「scikit-learnとTensorFlowによる実践機械学習」の記述を主に参考にしながら簡単な確認を行
これでわかるB-treeアルゴリズム / B-tree algorithm
・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
ランキング学習を使って有馬記念を予想してみた - Qiita
本日は12/24です。何の日か、みなさんお分かりですよね？🎅 そう、みんな大好き有馬記念の日です。🐎 ボートレースファンからはグランプリの優勝戦の日だろ！という主張もありそうですが、今回は数年ぶりに競馬予想ネタを書きたいと思います。 私自身、過去に2回、競馬予想をテーマにした記事を掲載してきました。 機械学習の初心者がpythonで競馬予測モデルを作ってみた 機械学習の初心者がpythonで有馬記念を予想してみた レースは相対評価で予想したい 過去記事では、ロジスティック回帰やランダムフォレスト等を使用してましたが、実は違和感を少々感じていました。それは、データセット全体から絶対評価で、購入対象馬を予測しているからになります。 ちょっと分かりにくいかもしれませんが、例として、以下のデータセットの場合、レース番号に関係なく、賞金の高い馬が購入対象になりやすいという傾向があります。 レース
Target Encoding はなぜ有効なのか
分析コンペLT会 https://kaggle-friends.connpass.com/event/154881/
回転をサボるAVL木を落とす - Qiita
この記事では$N$を二分探索木中の要素数(ノード数)として以後断りなく用います。 今回はAVL木をsetのような平衡二分探索木として扱いますが、配列型(平衡二分木)として使ってもほとんど同じことがいえます。 前提知識 二分探索木について (分かってると嬉しい) : AVL木の平衡方法 正しい平衡 ノードの平衡係数は(左の子の高さ) $-$ (右の子の高さです)。 説明によっては一重回転をやるケースと二重回転をやるケースとを完全に別のものとして区別していますが、二重回転は一重回転を2回やってるだけで、かつその2回目が一重回転をやるケースの一重回転と一致するので以下のように実装することができます。 ノード$x$の平衡係数が2の場合 $x$の左の子の平衡係数が-1なら左の子を左回転 $x$を右回転 ノード$x$の平衡係数が-2の場合(上の全く左右対称) $x$の右の子の平衡係数が1なら右の子を右
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
NGBoost論文読んでみた
