回転をサボるAVL木を落とす - Qiita
この記事では$N$を二分探索木中の要素数(ノード数)として以後断りなく用います。 今回はAVL木をsetのような平衡二分探索木として扱いますが、配列型(平衡二分木)として使ってもほとんど同じことがいえます。 前提知識 二分探索木について (分かってると嬉しい) : AVL木の平衡方法 正しい平衡 ノードの平衡係数は(左の子の高さ) $-$ (右の子の高さです)。 説明によっては一重回転をやるケースと二重回転をやるケースとを完全に別のものとして区別していますが、二重回転は一重回転を2回やってるだけで、かつその2回目が一重回転をやるケースの一重回転と一致するので以下のように実装することができます。 ノード$x$の平衡係数が2の場合 $x$の左の子の平衡係数が-1なら左の子を左回転 $x$を右回転 ノード$x$の平衡係数が-2の場合(上の全く左右対称) $x$の右の子の平衡係数が1なら右の子を右
深層学習VS決定木：テーブルデータ分析の未来｜PKSHA Delta
深層学習の技術が著しく進歩した結果、コンピュータビジョンや自然言語処理、音声信号処理などの分野では深層学習モデルの性能が古典的な手法のを大きく上回っており、すでにスタンダードなアプローチになっています。 しかし、テーブルデータを扱うタスクにおいては、深層学習の有効性は明らかになっていません。本記事では、AI Solution 事業部のアルゴリズムエンジニアよりテーブルデータにおける従来手法と深層学習の比較論文のご紹介をしていきます。 背景近年、テーブルデータを扱う深層学習モデルも登場し、一部の論文では決定木ベースのモデルと同等かそれ以上の性能を示しています。しかし、私が実務で試す中では決定木ベースのモデルの方が性能が高く、学習と推論が速く運用コストでも優れているため、深層学習モデル採用には至っていません。 より一般的なテーブルデータのタスクにおける、決定木ベースモデルと深層学習モデルとの性
Graph Neural Network を用いたグラフの木幅予測 - Preferred Networks Research & Development
本記事は、2019年夏のインターンシップに参加された中野裕太さんによる寄稿です。 皆様はじめまして。2019 年 PFN 夏季インターンシップに参加していた北海道大学の中野裕太です。本ブログでは、私が夏季インターンで取り組んだテーマである、「Graph Neural Network を用いたグラフの木幅予測」について説明します。 要旨 与えられた無向グラフがどれくらい木に近いかを表す値である木幅は、グラフ上の組み合わせ最適化問題に対するアルゴリズムの効率性や解そのものと深く関係しています。しかし、木幅を計算することは NP 困難なため、木幅を計算するには頂点数に対し指数時間かかってしまいます。そこで、今回 Graph Neural Network を用いた 2 つの方法でこの問題にアプローチしました。1 つ目は、よく知られた既存のアルゴリズムと組み合わせ探索木の枝刈りを行い高速化を図り計算
Santander Product RecommendationのアプローチとXGBoostの小ネタ
Jack (Japan)
BigQuery MLにAutoML Tables、XGBoost、DNN、ARIMAが来たのでおさらい - Qiita
はじめに 日本時間2020-06-17のリリースで、BigQuery MLにAutoML Tables、XGBoost、DNNが来ました。release-notes#June_16_2020 おさらいに、BigQuery MLで何ができるか再整理します。 追記: 日本時間2020-07-02のリリースで、BigQuery MLにARIMAも来ましたね。日本時間2020-06-28のリリースノートでエラーになってたのですが、リリース日がしれっと修正されてました。release-notes#July_01_2020 BigQuery MLでできること概要 BigQueryでStandard SQLを使って、機械学習モデルを訓練、推論できます。 データの移動を意識する必要がないため、開発スピードを向上と同時に、モデルの民主化を実現できます。 例えば、以下のようにして、1時間ほど待てば、AutoM
文書分散表現SCDVと他の分散表現を比較してみた
今回は、以下の論文の文章分散表現、Sparse Composite Document Vectors; SCDVについて書きます。 SCDV : Sparse Composite Document Vectors using soft clustering over distributional representations: https://arxiv.org/abs/1612.06778 実は去年に試しに実装していたのですが、他にネタがないためまだ投稿していませんでしたので、書こうと思います。 SCDVについて SCDVは、文章ベクトルを取得する方法の1つです。 文章ベクトルを取得する手法はDoc2Vecなど色々ありますが、論文において、取得した文章ベクトルを用いたマルチラベル分類では、他の方法よりも高い精度を出せているようです。 うーむ、ていうか、NTSGってのはなんだ。 すでにこ
KaggleのHousePricesで学ぶアンサンブルとパラメータチューニング - mirandora.com
本記事のコード/ご参照 ・本記事の全体のコードのnotebookを以下にアップしております。あわせてご参照くださいませ。 “Kaggle houseprices-tutorial-code” ・本記事含むKaggleやデータ分析初学者向けのチュートリアル解説本を執筆しました。あわせてご参照くださいませ。 ※本記事のコードや環境構築の詳細手順を記載した書籍となります。 『Pythonで動かして学ぶ！Kaggleデータ分析入門』 ※はじめに 本記事は2020年の上記書籍発売に合わせて内容を加筆・修正しました。そのため執筆当初と内容が異なる箇所がございます。 データサイエンティストの業務は華やかなPythonでの機械学習よりもBigQueryなどでの地道なデータ収集・データ集計に時間が割かれるのではと思います。もちろん、機械学習とデータ集計、どちらが華やかなのかには異論があり、芸術的なQuery
GitHub - nejumi/kaggle_memo
まずは、素うどんのXGBoostにかけて、plot_importance, feature_importances_を確認する。しかる後に、各特徴量をF-SCOREの高い順にExploratory Data Analysis (EDA)を行い、データに対する感覚を掴む。特徴量の数が少ないのであれば、初めからEDA。 情報を含まないcolumnsを除く。[Kaggle Kernel: R, Python] 標準偏差が0の説明変数 (constant cols) を除く。 重複した説明変数 (duplicated cols) を1つだけ残して他を除く。 相関係数が1である説明変数の組 (perfectly correlated cols) を探し、1つだけ残して他を除く。 各列について、値が0である説明変数の数を数えて、合計値を追加の説明変数として加える (count 0 per row)。逆
defragTreesがよさそう - Qiita
ちゃお……† 今回はdefragTreesという機械学習ライブラリを紹介します。 defragTreesとは RandomForestやXGBoostなどに対して、できるだけ精度やカバレッジを下げないようにしつつ、モデルをシンプルに(ルールを減らす)表現する手法を使ったライブラリです。 ルールが少ないので人間が見たときのわかりやすさがあります。 たとえば、元はシンプルなデータ(Figure 1 の a)でもアンサンブル学習すると無駄に複雑になってしまうことがあります (Figure 1 の b)。そこで、defragTreesを使うとオリジナルと同じようなシンプルさになります (Figure 1 の c)。 コード: https://github.com/sato9hara/defragTrees 論文: https://arxiv.org/abs/1606.09066 使い方 from
ゲームソフトの売行きをXGBoostで予測してみた【Amazon SageMaker ノートブック＋モデル訓練＋モデルホスティングまで】
本チュートリアルで実施する概要 Amazon SageMakerのノートブックでデータ前処理 Boto3経由でS3とSagaMakerの連携 モデルトレーニングインスタンスでSageMaker XGBoostの訓練 モデルホスティングインスタンスで訓練済みモデルをホスト テストデータをホスティングしたモデルを使って予測値を取得 結果確認 今回ですが第二回目となりますので、登録や初期設定の詳細に関しては省いています。まだSageMakerを一度も触られたことがない方は、第一弾目からどうぞ。 では、早速、やってみましょう！ SageMaker ノートブックインスタンスの立ち上げ SageMakerのメリットの一つとして、クラウドでJupyter Notebookが簡単に使えることです。機械学習で必要なライブラリやフレームワークが、すでに使える環境ですので、大きな時間短縮となります。 では、Sa
ポケモンの外見的特徴から種族値を勾配ブースティングで予測する - Qiita
しかし、このような占有面積が小さい、かつ高い種族値合計を持つポケモンはほとんどが伝説のポケモンとなっています。 そこで、例外は存在するものの、全体としては上に挙げた画像のような傾向を持っていると仮定します。 これより、特徴を適切に捉えることで、ポケモンの外見から種族値を予測することができます。 使用するアルゴリズム -Algorithm- 今回、予測したいパラメータは以下の7種類("HP"、"攻撃"、"防御"、"特攻"、"特防"、"素早さ"、"合計")となります。 予測のおおまかな手順としては次の2ステップとなります。 勾配ブースティングを用いた個別パラメータの予測 合計値を用いた個別パラメータに対する補正 以下では、それぞれの手順についてみていきます。 勾配ブースティングを用いた個別パラメータの予測 -Prediction by Gradient Boosting- まず、はじめにそれぞ
Microsoft Bingのランキングエンジンをxgboostでシミュレート - にほんごのれんしゅう
Microsoft Bingのランキングエンジンをシミュレートし、ランキングを学習します 目的 inspector(検査官、監査人、検閲官、視学、警視正、警部補) ランキングアルゴリズムは日々進化しています。Googleのサーチエンジンは200以上の特徴量を用いたり色々しています。 これらはGoogleでないと手に入らない特徴量も多数存在しており、容易に、ユーザが最適化できるものではなかったりします わかりやすいものでは、ドメイン以内にコンテンツが十分に存在し、それがある程度参照されるものであれば、以前あったようにWelqさんのようにコンテンツの内容の是非によらず、ランクアップしてしまうような問題もございました。 意図しない作用をもたらすから、狙ってはいけないなどということはなく、SEOはビジネスにおいて極めて重要な課題です。 SEOでどの要素（サイト規模？テキスト数？キーワードの作り？コ
C++/Rubyで基数木をつかって高速なHTTPルーティングを実現する - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 数年にわたり、PadrinoやGrapeといったWebアプリケーションフレームワークのルーティングを改善してきた自分が、今年の11月頃から、従来とは異なるアプローチでHTTPルーティングの高速化について検証したので、その結果について解説する。 なおこの記事では、その過程でC++で基数木を実装し、それを用いることにより、Rubyで高速なHTTPルーティングを実現した事例について、順を追って解説する。 tl;dr C++で基数木(Radix Tree)を表現するr2reeというライブラリを書いた。 r2reeのRuby向けバインデ
Segment Treeをちょっと高速化したい - komiyamの日記
Competitive Programming Advent Calendar Div2013の12月2日の分です。 ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の定番ですね）。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。 これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります。去年や今年のAdvent Calendarでも初学者向けの記事があるようです。初学者向けの詳しい解説はそちらをご覧ください。 私なりにsegment treeの動作原理を短くまとめると、「区間をたかだかO(log n)個の交わらない区
Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた - Preferred Networks Research & Development
釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。 今回はCentroid Path Decomposition（以下CPD）についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック（普通のツリーにも使えるのかな？なかなか難しそうですが…）の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。 Trieの実装によくある問題 Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うこ
ダブル配列の実装方法
Republic Act No. 11313 Safe Spaces Act (Bawal Bastos Law).pptx
最近のDoubleArrayの性能 - 射撃しつつ前転 改
DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。 まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。 Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならない
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ - EchizenBlog-Zwei
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。 そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
合成変量とアンサンブル：回帰森と加法モデルの要点
