最小共通祖先を求めるアルゴリズムの形式検証 | Wantedly Engineer Blog
競技プログラミングには概念を知っておかないと解きようがない、いわゆる覚えゲーのような問題が存在します。典型的な例が 10^9+7 といった素数で割った余りを求めろといったもので、普段業務で日常的に素数で割った余りを求めている人でもなければ、割り算がしたければフェルマーの小定理や拡張ユークリッドの互除法を使えば良いと直ぐには思い付けないのではないでしょうか。 最小共通祖先も覚えゲーで必要な概念の一種と言えます。これは読んで字のごとく、与えられた根付き木の下で2頂点に共通する祖先のうち、最も根から遠い頂点を指す概念で、例えば木の2頂点が与えられて、頂点間の経路について何かを求めろといった問題で威力を発揮することが多いです。これを用いて解ける例を挙げるとすると次の問題でしょうか。 https://atcoder.jp/contests/abc014/tasks/abc014_4 最小共通祖先を求
MD5のハッシュ値オールゼロに挑戦 - わさっきhb
いきなりですが問題です． MD5のハッシュ値（チェックサム，fingerprint，メッセージダイジェスト）がすべて0となるような，入力メッセージを答えなさい． さっそくですが解答…いや，答えは知りません．もし，そんな入力メッセージを得ていたら，弱衝突耐性を破ったってことになります．そんな入力があるかどうかも，分かっていません． そこで，もっと簡単な問題にします． MD5のハッシュ値の先頭32ビット（16進出力では最初の8桁）がすべて0となるような，入力メッセージを答えなさい． これくらいだと，計算機をぶん回せば，答えが出てきそうです．情報セキュリティの試験も終わったことですし，Rubyスクリプトを書いてみました． Find all-zero hash · GitHub 少し気をつかったことが2つ，あります．一つは，入力メッセージをどのように生成するかです．乱数を使うと，周期の問題がありま
弱教師あり学習は何を見ているのか？ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 弱教師あり学習は何を見ているのか？ 機械学習で分類モデルを学習する際、通常であれば正しくラベリングされたデータを入力としますが、弱教師あり学習では誤ったラベルから学習します。 たとえば「飛行機」、「腕時計」、「ヒョウ」を分類するモデルを学習するとき、すべての「飛行機」画像に「腕時計」、「ヒョウ」のいずれかのラベルがついている（＝誤ってラベリングされている）とします。 この場合、「腕時計」画像、「ヒョウ」画像の特徴を持たない画像を「飛行機」画像と学習します。この学習を実装するには損失関数を工夫します。具体的には、学習で誤りラベルを推論する
複雑ネットワークの基本 - 名前はまだない
はじめに ネットワーク分析に興味をもち過去にこちらの書籍を読み、 ネットワーク分析 第2版 (Rで学ぶデータサイエンス) 作者:努, 鈴木発売日: 2017/05/24メディア: 単行本 以下のような記事を書いていました。 qiita.com qiita.com 複雑ネットワークについてだけ勉強していなかったので、書籍の続きを読みまとめます。 コードの詳細等は書籍を確認してください。 複雑ネットワークとは 複雑ネットワークとは、現実世界に存在する巨大で複雑なネットワークの性質について研究する学問です。 例えば、WEBサイトのリンク構造やSNSでのフォロー関係などのネットワーク構造について着目するような取り組みが挙げられます。 複雑ネットワークでは各頂点の指標について議論することは少なく、ネットワーク全体の構造を捉えるための指標はよく用いられると考えています。 ここでは代表的な指標をあげます
TensorFlowのSavedModelの便利さを紹介する - 生き抜くぜ21世紀
はじめに 今は2020年8月なのですが、コロナ禍だし、暑いし、経済状況最悪で暇だし、良いことないですね。 暇になったので、1年ぶりにkaggleをやってみました。 Landmark Retrievalという建物の画像検索コンペに出たところ、そのコンペの提出形式がTensorFlowのSavedModel形式でした。 私はTensorFlow案件をけっこうやってきたので抵抗はなかったのですが、この制約が原因となったのか、あまりこのコンペの参加者は多くなかったようです。 kaggleの提出形式としては賛否両論あると思いますが、実務ではとても便利な形式だと私は思っています。 それなのにもし実務でも敬遠されているとしたらもったいないと思い、この記事ではSavedModelの便利さについて紹介してみます。 ちゃんとした使い方は公式リファレンスを当たってもらうとして、概念やsaved_model_cl
WebAssemblyを用いてBERTモデルをフロントエンドで動かす - OPTiM TECH BLOG
はじめまして。R&Dチーム所属、20.5卒の伊藤です。 普段の業務では自然言語処理と格闘していることが多いです。 今回は自然言語処理モデルとして有名なBERTをWebAssemblyを使用してフロントエンドで動かしてみた話になります。 最近、自然言語処理ライブラリとして普段お世話になっているHugging Face社のTransformersのTokenizerがRustで実装されていることを知り、それならばWebAssemblyにコンパイルして動かせるのではないかと試したみたのがきっかけです。 Tokenizerのみ動かしても実用性に乏しいため、Tokenizerから得られた結果からBERTを用いた推論をブラウザで動作させるまでを行い、備忘録がでら手順をまとめました。 どなたかの参考になれば幸いです。 8/26追記 本記事内のコードを含むリポジトリを公開しました！Dockerを使用してブ
Pyevolveで学ぶ遺伝的アルゴリズム - mfumiの日記
Pyevolveとは、Pythonで書かれた遺伝的アルゴリズムのフレームワークです。公式サイトによれば、Pyevolveの方針は、 ・ pure python で書く ・ APIを簡単に使えるようにする ・ 進化過程をグラフ等で見れる ・ 拡張性をもたせる ・ パフォーマンスを第一にデザインする ・ 一般的な特徴を持つ ・ 全てのオプションにデフォルト値がある ・ open-source (GPL) …とのこと。遺伝的アルゴリズムは前から少し興味があったので、これを使って勉強してみたいと思います。 Pyevolveは日本語はおろか英語での情報もあまりありません。以下に参考になるサイトを挙げておきます。 公式サイト Welcome to Pyevolve documentation ! — Pyevolve v0.5 documentation 日本語でPyevolveについて書かれた唯一(
pytorch-transformersを触ってみる① - 機械学習・自然言語処理の勉強メモ
今更ながら、pytorch-transformersを触ってみます。 このライブラリはドキュメントが充実していて、とても親切です。 なので、今回はドキュメントに基づいて触ってみただけの備忘録です。 以下、有名どころのBERTで試してます。 詳しいことはここなどを参照してください。 huggingface.co はじめに 以下で、入手できます。簡単です。 pip install pytorch-transformersインストールしたら、以下でimportします。 import torch from pytorch_transformers import BertTokenizer, BertModel pytorch-transformersの基本は以下の3つのクラスで構成されます。 model classes モデル本体 configuration classes モデルのパラメータを設
DQNで自作迷路を解く - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? DQNで自作迷路を解く Deep Q Network（いわゆるDQN）で自作の迷路を解いてみました。 プログラムはこちらにあります。 https://github.com/shibuiwilliam/maze_solver 概要 DQNは強化学習の一種で、最適な戦略選択にニューラルネットワークを使っているものになります。 強化学習やニューラルネットワークの説明は以下が参考になります。 強化学習 ゼロからDeepまで学ぶ強化学習 - Qiita ニューラルネットワーク TensorFlowのチュートリアルを通して、人工知能の原理について学
VAEを用いたUNIXセッションのなりすまし検出 | NHN テコラス Tech Blog | AWS、機械学習、IoTなどの技術ブログ
こんにちは。データサイエンスチームの t2sy です。 この記事は NHN テコラス Advent Calendar 2018 の17日目の記事です。 はじめに ニューラルネットワークを用いた代表的な生成モデルとして VAE (Variational Autoencoder) と GAN (Generative Adversarial Network) の2つが知られています。生成モデルは異常検知にも適用できます。今回は、VAE を用いたUNIXセッションのなりすまし検出を試してみたのでご紹介します。 VAEと異常検知 データセット fastTextによるUNIXコマンドの分散表現 KerasでVAE 実行環境は以下です。 Amazon EC2 p2.xlarge インスタンス Ubuntu 16.04 Python 3.4.5 Keras 2.1.6 TensorFlow 1.8.0 V
Tensor2Tensorで雑談チャットボットを作ったら今度はうまくいった話 - Qiita
はじめに 前回の失敗から手法を変えてチャットボットの作成を試みました。 今度はうまくいきましたが、ほぼ公式ドキュメント通りの内容なのであまり面白味はありません。 前回の失敗はこちらから 全体のコードはこちらから 作成方法 今回はGoogle Brain チームが提供しているTensor2Tensor(t2t)を使うことにしました。 t2tは既に用意されているデータセットで学習するだけならコードを書くことなく(コマンドのみ)実行できる手軽さが特徴です。 自前のデータセットを実行する際にも、ほぼ公式ドキュメントに書かれている数行のコードと形式の整ったデータセットさえあれば実行できるので非常に楽です。 今回は前回作成した名大会話コーパスから抽出したinput_corpus.txtとoutput_corpus.txtをデータセットとして学習・推論をさせてみます。実行環境はGoogle Colabで
音楽と機械学習 前処理編 MFCC ~ メル周波数ケプストラム係数 - Qiita
# python import librosa x, fs = librosa.load('./hoge.wav', sr=44100) mfccs = librosa.feature.mfcc(x, sr=fs) print mfccs.shape # (n_mfcc, sr*duration/hop_length) # DCT したあとで取得する係数の次元(デフォルト20) , サンプリングレートxオーディオファイルの長さ（=全フレーム数）/ STFTスライドサイズ(デフォルト512) mfccs がいい感じの次元の ndarray になります。 お急ぎでない方向け 冒頭で述べたように、オーディオのデータを機械学習のロジックで扱いたいというモチベーションがあるわけですが、例えば俗に "CD音質" と呼ばれる音質で、リニアPCMという非圧縮の形式で1秒間録音した場合のデータサイズは CD
しゃくとり法のDequeを使ったバグりにくい実装 - Qiita
この記事の目的 しゃくとり法のバグりにくい実装の紹介です！ しゃくとり法(尺取り法)って？ しゃくとり法の説明自体は、とってもいいまとめがあるのでこちらをご覧ください。 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ でも、しゃくとり法ってバグりません？ しゃくとり法っていざ書いてみるとかなりの確率でバグります。 区間の端を表す添え字 $l$ と $r$ の動かし方が結構混乱します。 この記事ではdeque(両端キュー)を使った実装を紹介します。 なんとこの実装では添え字を使う必要がありません！ deque(両端キュー)によるしゃくとり法の実装 次の問題を例にとって説明します。 ABC 032 C - 列 長さ $n$ の整数列 $A = \{a_1, a_2,..., a_n\}$の連続部分列で、その要素の積が $K$ 以下となるものの長さの最大値を求める問題です。 次の
Rでポケモンスタンプラリー(3/3) {TSP}で巡回セールスマン問題 - INPUTしたらOUTPUT!
estrellita.hatenablog.comの続き。最後は{TSP}を利用して移動距離が最短となるようスタンプ設置駅を周回する順番を求める。 データ準備 路線ネットワークに必要なノードとエッジのデータを作成 {tidygraph}でスタンプ設置駅間の最短経路探索 路線ネットワークデータからスタンプ設置駅の最短距離を探索 {TSP}で巡回セールスマン問題を解く（ ← イマココ） 各スタンプ設置駅間の距離行列から移動距離が最短となるような巡回順を探索 目次 距離行列の作成 巡回セールスマン問題 結果の確認 距離行列の作成 グラフオブジェクトからノード情報を取り出し、スタンプ設置駅間の距離行列を作成する。 dist <- g %>% tidygraph::activate(nodes) %>% dplyr::as_tibble() %>% dplyr::filter(station_nam
はじめての自然言語処理 spaCy/GiNZA を用いた自然言語処理 | オブジェクトの広場
前回は BERT についてその概要と使い方を紹介しました。今回は自然言語処理ライブラリである spaCy と spaCy をフロントエンドとする日本語NLPライブラリの GiNZA について紹介します。 1. 始めに 本記事では欧米で有名な自然言語処理ライブラリである spaCy とリクルートと国立国語研究所の共同研究成果である日本語NLPライブラリ GiNZA について紹介します。記事の前半では、spaCy と GiNZA の概要と日本語を処理する際の基本的な機能／操作について説明します。後半では、spaCy で提供される文章分類機能について、前回までに紹介した手法も含めて精度を比較してみます。 2. spaCy と GiNZA の概要 spaCy は Explosion AI 社の開発する Python/Cython で実装されたオープンソースの自然言語処理ライブラリで MIT ライセ
【R / Python】UMAP でアクセスログを可視化してみた |
今回は UMAP で当ブログのアクセスログ (Nginx) を可視化してみます。実行環境は macOS 10.13, CPU 1.6GHz Intel Core i5, メモリ 8GB です。 次元削減のアルゴリズムは大きく2つのカテゴリに分類される。 データ内の距離構造を保持する手法 (e.g. PCA, MDS adn Sammon mapping) 大域的な距離の上で局所的な距離を保持する手法 (e.g. t-SNE, Isomap, LargeVis, Laplacian eigenmaps, diusion maps, NeRV and JSE) UMAP (Uniform Manifold Approximation and Projection) は多様体学習による可視化 & 次元削減手法で, t-SNE と同程度の可視化の質を持ちつつも高速に動作する。UMAP は t-SN
SentencePiece + 日本語WikipediaのBERTモデルをKeras BERTで利用する
SentencePiece + 日本語WikipediaのBERTモデルをKeras BERTで利用する TL;DR Googleが公開しているBERTの学習済みモデルは、日本語Wikipediaもデータセットに含まれていますが、Tokenizeの方法が分かち書きを前提としているため、そのまま利用しても日本語の分類問題ではあまり高い精度を得ることができません。 このため、SentencePieceでTokenizeしたデータセットで学習し直す必要があります。 BERTのトレーニングは結構な時間やマシンリソースが必要ですが、ありがたいことにSentencePiece+日本語Wikipediaで学習済みのモデルを配布してくれている方がいらっしゃるので、今回は以下を利用します。 BERT with SentencePiece を日本語 Wikipedia で学習してモデルを公開しました BERT
遺伝的アルゴリズムでナーススケジューリング問題（シフト最適化）を解く - Qiita
この記事は ナーススケジューリング問題という最適化の問題を遺伝的アルゴリズムで解いてみたらまあまあの精度が出たので記録です pythonのdeapというライブラリを使っています 前提 ナーススケジューリング問題 ナーススケジューリング問題というものがあります 病院等の医療施設に勤める看護師の勤務スケジュールを決定する問題のことであり，シフトスケジューリング問題の代表例である．日勤・夕勤・夜勤等の複雑なシフト勤務や多岐に渡る制約の考慮のため，実際にスケジュールを求めるのは人手では手間のかかる困難な作業であり・・・ 要するにシフト勤務のスケジュールを自動的に最適に組むというものです 制約が色々あって、必要人数を満たすような基本的なものから、公平性、必須な資格/役割、この２人は（仲が悪いから？）一緒に入れないなど、いくらでも複雑になりうる問題て感じで、完璧な解答を作るのは困難なので、近似解を求め
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
転置インデックスのポスティングリスト圧縮アルゴリズムをRustで実装してみる | by mocobeta | Medium
社内CV輪講資料 / PyTorch Lightning
