ゼロから始める勾配ブースティング決定木の理論
はじめに はじめまして。データアナリティクスラボの力岡です。 私は日頃、テーブルデータの分析業務において、LightGBMをはじめとする勾配ブースティング系アルゴリズムを活用しています。ただし、その仕組みを十分に理解したうえで使いこなせているかというと、まだ自信が持てない部分もあります。そこで本記事では、自分自身の理解を深めるとともに、これから学ぶ方々にも役立つよう、勾配ブースティング決定木（GBDT）について体系的に解説していきます。 1. 勾配ブースティング決定木 勾配ブースティング決定木（Gradient Boosting Decision Trees、GBDT） は、複数の決定木（弱学習器）を組み合わせて高い予測精度を実現する、アンサンブル学習の一手法です。その名の通り、「勾配降下法」「ブースティング」「決定木」という3つの要素を組み合わせて構成されており、実務やKaggleなどの
世界一わかりやすいゼロ知識証明 Vol.2: Zero-Knowledge Proofs in the Context of Modern Cryptography
このブログシリーズをグラントプロジェクトとしてサポートしてくださっているイーサリアム財団、また執筆に際してフィードバックとレビューをしてくださった末神奏宙さんに感謝します。 Special thanks to Ethereum Foundation for awarding grants to this blog post series, and Sora Suegami for feedback and review. このブログシリーズは、ソフトウェアエンジニアに限らず、あらゆる日本の読者のみなさんに向けて、最先端の暗号技術とその重要性をわかりやすく説明するという趣旨で書かれています。それぞれ単体の記事としてもお読みいただけますが、順番に読み進めていくことでより理解が深まります。まだお読みでない方は、ブロックチェーンやコンセンサスアルゴリズムの仕組みについて解説しているVol.1を先に
memcached proxyで使うハッシュアルゴリズムを比較した話 - Mirrativ Tech Blog
memcached proxyのハッシュアルゴリズム比較 はじめまして！hibikiです(@add_bakkers) 現在大学3年生で、最近はネットワークに興味があり勉強中です。2023年8月からインフラチームにインターンとして参加しました。 本記事ではmemcached proxyのハッシュアルゴリズム比較の結果を紹介します。 memcached proxyのハッシュアルゴリズム比較 1. 背景と目的 ミラティブでのmemcachedの利用 課題: クライアントサイドでサーバ決定をしている memcached proxyの検討 2. memcached proxyに求められるアルゴリズム キーの分散 移動率の抑制 パフォーマンス ハッシュアルゴリズムの比較 3. 今回行うベンチマークの概要 計測対象とシナリオ 分散と移動率のベンチ 処理性能のベンチ 4. ベンチマークの結果と比較 移動率
Secrets from the Algorithm: Google Search’s Internal Engineering Documentation Has Leaked
Watch Our Google Algorithm Leak Webinar Replay Google, if you’re reading this, it’s too late. Ok. Cracks knuckles. Let’s get right to the Google algorithm leak. Internal documentation for Google Search’s Content Warehouse API has been discovered. Google’s internal microservices appear to mirror what Google Cloud Platform offers and the internal version of documentation for the deprecated Document
「アルゴリズム」という言葉の由来は？
アルゴリズムという言葉はGoogle検索やSNSでの分析や、特定のタスクを実行して処理するプログラム、人工知能の開発などで私たちの生活に不可欠です。だれもが聞いたことある「アルゴリズム(Algorithm)」というワードがどこから来たのかという由来と歴史について、メルボルン大学でデジタルヘルスの研究員を務めるデビー・パッシー氏が解説しています。 Why are algorithms called algorithms? A brief history of the Persian polymath you’ve likely never heard of https://theconversation.com/why-are-algorithms-called-algorithms-a-brief-history-of-the-persian-polymath-youve-likely-n
拡散モデルと最適輸送 - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ
『最適輸送の理論とアルゴリズム』が重版して第 5 刷となりました。皆さまありがとうございます！ 漫画家さんやイラストレーターさんが重版したときに重版感謝の描き下ろしイラストを投稿しているのを見ていいなと思ったので、僕も専門書が重版したときに重版感謝の書き下ろし専門記事を投稿します。 本稿では、最近話題の拡散モデルと最適輸送の関係を直観的に解説します。 拡散モデルは画像の生成によく用いられる生成モデルです。モデルはノイズ入りの画像を受け取り、ノイズを除去することを目指します。生成時には、完全なノイズ画像からはじめて、モデルによりノイズを除去することと、微小なノイズを加えることを繰り返して洗練させていき、自然画像を得ます。 拡散モデルの動作の図示 このように、ノイズ から自然画像 までゆらぎながら変化する過程をブラウン橋 (Brownian bridge) と言います。ブラウン運動 (Brow
ARIES のすごさがいまいち理解できないでいるのですが、本質的なところとしてはどういったところがすごいのでしょうか。 ARIES/IM、ARIES/KVLといった、リカバリ用途以外のアルゴリズムでも名前が入ったものがあったりするので、周辺用途でも応用が利くようなアイデアを包含するものなのではないかと思っているのですが、いかんせんそこが掴めないでおります。 | mond
ARIES のすごさがいまいち理解できないでいるのですが、本質的なところとしてはどういったところがすごいのでしょうか。 ARIES/IM、ARIES/KVLといった、リカバリ用途以外のアルゴリズムでも名前が入ったものがあったりするので、周辺用途でも応用が利くようなアイデアを包含するものなのではないかと思っているのですが、いかんせんそこが掴めないでおります。 ARIESの本質、これは僕も疑問でした。Algorithms for Recovery and Isolation Exploiting Semanticsの頭文字を取ってのARIESですが何がSemanticsをExploitしているのかという点について考えるたびに別の答えが思いつくのでまるでわかりませんでした。 そこで去年、大阪に訪問していたC. Mohan先生（ARIESの著者）に直接聞いてみました。（Mohan先生の右後ろで目を
Othello is Solved
The game of Othello is one of the world's most complex and popular games that has yet to be computationally solved. Othello has roughly ten octodecillion (10 to the 58th power) possible game records and ten octillion (10 to the 28th power) possible game positions. The challenge of solving Othello, determining the outcome of a game with no mistake made by either player, has long been a grand challe
入門 B-link tree
概要 DBMS で広く利用されている B+ tree には様々な variant が存在するが、B-link tree もその1つ。 シンプルなラッチプロトコルで並行アクセスをさばけるよう、リーフノード以外のノードにも右の隣接ノードへのポインタを持たせた構造となっており、PostgreSQL で使われていることでも有名。 この記事では主にこの B-link tree に焦点を当てる。 B+ tree 全般やその他インデックス技術自体に興味がある場合は「最強DB講義 #10 いまどきのデータベース索引技術（石川佳治 教授）」の講義資料を読むのがおすすめ。 B-link tree 理解する上で必須な知識「ラッチ」 「ラッチ」というのはいわゆるロックのことだが、DB においては「ロック」というとトランザクション分離のための高価な(数千CPUサイクルを要する)処理を指すことが多く、「ラッチ」という
何故パスワードをハッシュ化して保存するだけでは駄目なのか？ - NRIネットコムBlog
不正アクセスによるIDとパスワードの漏洩を受けて、MD5によるハッシュ化について話題になっていました。システムを作る上で、パスワードの管理や認証はどう設計すべきかを考えるために、少し整理をしてみます。もし事実誤認があれば、どしどしご指摘ください。 == 2023/8/21追記 == この記事は、ハッシュの保存の仕方一つとっても、沢山の対策方法が必要であるということをお伝えするために記載しています。そして、これから紹介する手法を取れば安全とお勧めしている訳ではないので、その点をご留意いただければと思います。攻撃手法に応じての対応策の変遷を知っていただくことで、セキュリティ対策は一度行えば安全というものではないことを知って頂くキッカケになれば幸いです。 == 追記終わり == パスワードのハッシュ化 まず最初にパスワードの保存方法です。何も加工しないで平文で保存するのは駄目というのは、だいぶ認
PNGファイル爆発しろ！
まえがき Web上で広く利用されるPNG(Portable Network Graphics)フォーマットは、デジタル画像を変化させずに小さいデータサイズへ変換する圧縮技術の一種です。PNGフォーマットはオリジナル画像を完全復元可能な可逆(lossless)圧縮ですから、JPEGフォーマットのように画像を歪めてしまう非可逆(lossy)圧縮ほどは小さくできません。それでもオリジナルのデジタル画像データの半分程度まではサイズ削減可能な画像圧縮アルゴリズムと言われています。[1] そげぶ いいぜ てめえが何でも思い通りに圧縮出来るってなら まずはそのふざけた幻想をぶち壊す!! （スペース都合によりAA省略） 本記事では、PNGフォーマットを画像データ圧縮(compress)用途で利用するのではなく、オリジナル画像データよりも遥かに巨大なPNGファイル を生成します。 PNGフォーマットでは任意
暗号の歴史と現代暗号の基礎理論（RSA, 楕円曲線）-後半- - ABEJA Tech Blog
はじめに このブログに書かれていること 自己紹介 注意 Part3 現代の暗号 共通鍵暗号方式と鍵配送問題 鍵配送問題とは？ 共通鍵暗号方式と公開鍵暗号方式の違いとメリット・デメリット RSA暗号 RSAで使われる鍵 処理手順 暗号化の手順 復号の手順 RSA暗号の数学的背景 一次不定式が自然数解を持つ理由 eとLの関係性 そもそもなぜこの式で元の平文に戻るのか？の数学的根拠 証明パート１ フェルマーの小定理 中国剰余定理 RSA暗号をPythonで 楕円曲線暗号 楕円曲線とは？ 楕円曲線の式 楕円曲線における足し算の定義 楕円曲線における引き算の定義 無限遠点 楕円曲線における分配法則と交換法則 楕円曲線の加法を式で表現 点Pと点Qが異なる場合 点Pと点P 同じ点を足し合わせる場合 有限体 有限体とは？ 有限体上の楕円曲線 楕円曲線暗号における鍵 ECDH鍵共有 数式ベースでの手順説明
暗号の歴史と現代暗号の基礎理論（RSA, 楕円曲線）-前半- - ABEJA Tech Blog
はじめに このブログに書かれていること 自己紹介 注意 Part1 古典暗号 2つの暗号方式 スキュタレー暗号 アルゴリズムと鍵 シーザー暗号 原理 頻度分析 アルベルティ暗号 ヴィジュネル暗号 如何にしてヴィジュネル暗号は破られたか Part2 近代暗号 エニグマ エニグマの登場 エニグマの基本構造 如何にしてエニグマは突破されたか 前提条件 必ず異なる文字に変換される性質を利用 ループを利用 まとめ 参考文献 採用情報 はじめに このブログに書かれていること 前半 古代暗号から始まる暗号の歴史 エニグマの構造と解読法について 後半（後半ブログは こちら） RSA暗号の基本 楕円曲線暗号の基本 自己紹介 こんにちは！株式会社ABEJAの @Takayoshi_ma です。今回のテックブログですが、ネタに5時間程度悩んだ挙句、暗号を取り上げることにしました！暗号化手法の解説にとどまらず、そ
この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - ヴァルの開発記
概要 この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。 この記事を読むために必要な知識は以下です。 ・モンテカルロ木探索＋UCB1 ・MiniMax探索 ・ボンバーマンの基本的なルール 名のある木々 名もなき木々を紹介する前に、まずは名のある木々を紹介します。 MCTS モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。 有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。 一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。 →A Survey of Monte Carlo Tree Search Methods 最良優先MiniMax 最良優先MiniMax探索についてはこちらの論文が
「競プロ典型 90問」Smallest Subsequence (最小部分列問題)
最小部分列問題 「 競プロ典型 90 問」の 006 - Smallest Subsequence（★5） (最少部分列問題) という問題を解いてみたのですが、最初は解説をみてもさっぱり分からず打ちひしがれていました･･･。 が、けんちょんの競プロ精進記録 を見るに、どうもこの問題を解く途中で出てくる nex という配列が「極めて汎用性が高いので、実にさまざまな問題で活用できます！！！」ということらしく、ちゃんと理解しといた方が良さそうだ･･･ということで気を取り直して取り組んでみたところなんとか理解できました。 せっかくなので忘れないうちに解説記事を作って記憶を定着させたいと思います。なお後半の実装パートは、Haskell で実装します。 けんちょんさんの解説記事にあるとおり、この問題 (を全探索で解く場合) の解法のキーになるのは事前に「任意の文字が i 番目以降に出現する位置」を二次
キャッシュアルゴリズムの比較 - falsandtruのメモ帳
アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri
Knuth: The Art of Computer Programming の話 | IIJ Engineers Blog
2002年から約10年 IIJ技術研究所長. 年を取ってからは古い計算機や昔の計算法に興味が増し, シミュレーターを作ってそのプログラムを書いたり. 近頃はKnuthのTAOCPにあった問題のプログラムなどに挑戦したりしている. 【IIJ 2022 TECHアドベントカレンダー 12/5（月）の記事です】 クリスマスといえば, 英国王立研究所が1825年から続けている「クリスマス講演」が有名で, 岩波文庫にあるFaradayの「ロウソクの科学」はその1860年の講演だ. それに比べればまだ20年くらいだが, スタンフォード大学のKnuth教授も毎年「クリスマス講義」を続けている. しかし今回のブログはそのKnuthによる大著, The Art of Computer Programming(以後TAOCP)が話題である. 上段の左の横積みは, 英語版TAOCPの, 上から第1, 2, 3,
分かると、実に、おもしろい！ QRコードの仕組み
少しマニアックな知識、QRコードの仕組みを紹介します。 QRコード決済、リンクをQRコードで提供するなど、日常的に使用されているQRコードにあるそれぞれのパターンがどのように機能しているか、どういう役割をしているのか、なぜ上下逆さにしても読み取れるのか、なぜ一部が隠されても読み取れるのかなどが分かります。 QR codes by Dan Hollick (@DanHollick) 下記は各ポイントを意訳したものです。 ※当ブログでの翻訳記事は、元サイト様にライセンスを得て翻訳しています。 はじめに QRコードの仕組み 終わりに はじめに QRコードがどのように機能しているのか、疑問に思ったことはありませんか？ 控えめに言って、実に、おもしろい！ 注意: この記事⬇では非常にマニアックな内容が含まれています。 QRコードの仕組み QRコード（Quick Response code）は自動車部
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
Why React Re-Renders • Josh W. Comeau
Filed underReactoninAugust 16th, 2022.Aug 2022.Last updatedoninJanuary 28th, 2025.Jan 2025. IntroductionSo, I'll be honest. I had been working professionally with React for years without really understanding how React's re-rendering process worked. 😅 I think this is true for lots of React developers. We understand enough to get by, but if you ask a group of React developers a question like “What
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
