Shazamは一体どうやって動いているのか？
(perthirtysix.com/how-the-heck-does-shazam-work)- 音楽認識は、マイクが受け取った空気の振動を波形に変換し、それをスペクトログラムと少数の強い周波数ピークへ圧縮して曲の指紋を作ることで行われる
- 生の波形は音量や再生環境によって簡単に変わるため識別基準として使いにくく、短い区間ごとにFFTを適用して時間ごとの周波数構造を明らかにしてはじめて安定した比較が可能になる
- 残されたピークは単一点ではなく、anchorとtarget zoneのペアとして束ねられてハッシュになり、こうした組み合わせが特定の録音版を区別できるほど具体的な指紋ハッシュとして機能する
- 検索では曲を1曲ずつ照合せず、ハッシュをキーに直接探すhash-first構造を使い、最後に一致したハッシュ同士の時間間隔まで合っているかを確認して信頼度を高める
- サーバーベースの大規模データベース方式とオンデバイス方式では規模や制約は異なるが、核心は情報の大半を捨ててランドマークピークだけを残し、短くて騒がしいクリップでも素早く曲を見つけ出す点にある
音を逆に読み解くプロセス
- スマートフォンのマイクは非常に薄いダイアフラムで空気振動を測定し、それを時間ごとの空気圧を表す数列である波形に変換して保存する
- 耳の鼓膜も同じ圧力波を受け取るが、スマートフォンはそれを音そのものではなく数値シーケンスとして扱う
- 入ってきた音は1秒あたり数万回サンプリングされ、通常は44,100 Hzが使われる
- 生の波形だけでは曲の識別は難しく、同じ曲でも大きな音で再生すればまったく別の波形になり、異なる曲同士でも似た波形を作ることがある
- 再生環境が変わるだけでも同じ曲の波形は変化しうるため、波形そのものは識別基準として不向きである
- この問題を減らすには、波形を小さな断片に分けてからFFTを適用し、各時点にどの周波数が含まれているかを分解する必要がある
- 問いの形に変えるなら、「この短い音の断片をもう一度作るには、どんな純音を足し合わせればよいか」に相当する
- 各断片の結果を横に積み上げると、時間軸・周波数軸・明るさの軸からなるスペクトログラムになる
- FFTは、どれほど複雑な波形でも、異なる周波数・振幅・位相を持つ正弦波の和として表現できることを利用している
- たとえば1,024個のサンプルを入力すると、各周波数にどれだけのエネルギーがあるかを示すスペクトルが返ってくる
- 各周波数binごとに、すべてのサンプルをその周波数の正弦波と掛け合わせて足し合わせ、その周波数が実際の信号に含まれていれば合計は大きくなり、なければ打ち消し合う
- FFTの核心は速度にあり、素朴な分解では断片ごとに数百万回の演算が必要だが、FFTは数学的な対称性を利用しておおよそn log nまで減らす
- この速度だからこそ、スマートフォンでも1秒間に数百回実行できる
- デバイスはこの窓をオーディオ上で連続的にずらしながら各断片にFFTを適用し、その結果を積み重ねてスペクトログラムを作る
- 単純な例としては純粋な1つの周波数だけで構成された合成音が理解しやすいが、実際の音楽ははるかに複雑である
- 実際の音楽やハミングをマイクに入力するとスペクトログラムはずっと雑然として見えるが、FFTはその中でもリアルタイムで構造をあぶり出す
- ブラウザの例では、すべてのオーディオはブラウザ内部で処理され、録音も外部送信も行われない
少ないほど強くなる指紋
- システムはスペクトログラム全体を保存せず、最も大きなピークだけを残して疎な点集合へと圧縮する
- 弱い信号を捨てて最も強い地点だけを残せば、音響的に重要なランドマークだけが残る
- このように大半を捨てるのは、スペクトログラム全体を保存して検索する処理がコンピュータにとってもあまりに遅いからである
- しきい値を上げるほど、かすかな信号は消え、大きなピークだけが生き残る構造になる
- この方式はノイズ耐性を高めてくれる
- 背景雑音はスペクトログラム全体に低いエネルギーを加えるが、通常は特定領域の最強ピークまでは作れない
- 残るランドマークは、ノイズを突き抜けて現れた支配的な周波数である
- その一方で、この指紋方式は歌を直接歌って入力したときには性能が落ちやすい
- とても上手に歌っても、原曲とは異なるハッシュが作られる可能性が高い
- そのため、より新しい機械学習ベースのシステムは、正確な周波数ではなくメロディを基準にハミングや歌を処理する
点をつないでハッシュを作る
- 点1つだけでは識別力が足りないが、2点の組み合わせは偶然起こりにくいため、指紋ハッシュとして使うのに適している
- たとえば、ある時点の1,200 Hzだけなら何千曲にも現れうるが、1,200 Hzのあと0.3秒後に2,400 Hzが来る組み合わせははるかに具体的である
- アルゴリズムは各ピークを順にanchorとし、その右側に時間と周波数の範囲を持つtarget zoneを設定して、その中のすべてのピークと組にする
- 各ペアは2つの周波数と時間差、合計3つの数値から短いhashを作る
- ハッシュは、同じ入力からは常に同じ結果が出て、入力が少しでも変わるとまったく別の値になる短いコードとして働く
- Shazam系のシステムは小さな変動を扱う仕組みを持っているが、基本的にハッシュは正確な周波数とタイミングから作られる
- その結果、このハッシュは曲そのものというより特定の録音版の指紋として機能する
- そのため、coverやremixは一致させるのがより難しくなる
- 3分の曲1つからでも、このような指紋ハッシュを数千個作ることができ、データベースはそれをすべて保存する
- スマートフォンは5秒のクリップから得た少数のハッシュを持ち、データベースは膨大な数の曲から抽出した数百万のハッシュを持って、マッチング段階へ進む
正確なマッチを見つける
- 各ハッシュは一種のアドレスとして使われ、システムはクリップから得たハッシュごとに巨大なテーブルを直接参照して、そのハッシュを持つ曲を探す
- 曲単位で1つずつなめるのではなく、ハッシュ自体をキーとしてアクセスする
- 直感的なsong-first方式では、すべての曲を1つずつ検査してハッシュの重なりを確認しなければならず、曲数が増えるほど遅くなる
- 本文ではこれを**O(N)**時間と表現している
- 例示のデータベースと5秒クリップのハッシュ一覧で、この非効率さを視覚化している
- コンピュータはこれを逆転させてhash-first方式で処理できる
- 各ハッシュについて「どの曲がこのハッシュを含んでいるか」を直接問い合わせる
- 本の巻末索引のように、すべてのページを読み直す代わりに特定の単語の項目へすぐ飛ぶ構造にたとえられる
- このアプローチは参照をほぼ**O(1)**に近づける
- 曲が100曲でも1億曲でも、おおむね同じ時間で処理できる
- 取りうるハッシュ数が非常に多いため、数百万曲があっても各アドレスには通常少数の項目しか入らない
- 単に同じハッシュを共有しているだけでは終わらず、最後の検証は時間間隔で行われる
- たとえば、クリップ内で17403Cと19A998が1.2秒間隔なら、マッチ候補の曲でも同じ2つのハッシュが1.2秒間隔で現れなければならない
- 一致するハッシュ同士の時間差が互いにそろい、個数も十分であってはじめて信頼性の高いマッチになる
- システム全体は、コンピュータが特に得意とする処理に合わせて設計されている
- 数値比較とアドレス参照を中心に構成されている
- そのため、数百万曲を相手にしても全体の参照は1秒よりはるかに短い時間で終わる
より現代的なアプローチ
- Shazamのような多くの楽曲認識サービスは、オーディオクリップをサーバーへ送り、サーバー上の大規模な指紋データベースでマッチングを行う
- データベースが非常に大きく、常に変化し、検索にも相当な計算資源が必要になるため、この構成が採られている
- 一方、Appleのオンデバイス認識やGoogle PixelのNow Playingは、スマートフォン内ですべてをローカル実行する
- より小さく選別されたデータベースと最適化されたモデルを用いる
- 完全な網羅性より速度を優先し、ノイズやオーディオ変形により強い洗練された機械学習アプローチも含まれる
- オンデバイス方式はより高速で、インターネット接続がなくても動作するが、マッチ可能な曲データベースがはるかに小さいという制約がある
- 新曲の反映も一般に遅い
- 位置の変化が検出されると、新しいデータを再取得する必要がある場合もある
- 地域ごとの人気曲の違いも、オンデバイスのデータ構成に影響する
- 日本のヒット曲とアメリカのヒット曲は異なる場合がある
- マッチングがサーバーで行われるかデバイス内で行われるかにかかわらず、核心的な手法は同じである
- 情報の大半を捨て、少数のランドマークピークだけを残せば、騒がしいカフェで得た5秒のクリップでも、数百万曲の中の1曲を指し示せるほど精密な座標集合へと変わる
- 認識の核心は、多くを聴くことというより、無視すべきものを正確に捨てることに近い
ベースになった論文
- 本文のかなりの部分は、Avery Wangの2003年の論文An Industrial-Strength Audio Search Algorithmに基づいている
- 信号処理とシステム設計をより深く見たいなら、この論文が直接の出発点になる
- 全体の流れは、波形変換、ピーク選択、ピークペアのハッシュ化、逆引きインデックス参照、時間整列検証へと続く
- これらの段階が組み合わさることで、短くて騒がしいクリップでも高速な楽曲識別が可能になる
1件のコメント
Hacker Newsの意見
Shazam関連の資料も合わせて見るとよい https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf に元論文があり、本当に興味があるなら著者のYouTube発表も探してみる価値がある https://news.ycombinator.com/item?id=18069968 にはShazam社員の投稿があり、 https://news.ycombinator.com/item?id=38538996 には共同創業者が認めた説明があり、 https://news.ycombinator.com/item?id=41127726 にはGoで作られたアルゴリズムの再現がある 結局のところ、MLもコードそのものよりデータの価値のほうが大きい場合が多いと思う
私の最近の推測では、まったくそうではないかもしれないという方向 大衆音楽ではたいていうまく当たっていたが、アイススケート大会の休憩時間に流れたかなり良いシンセ音楽を何度もShazamしてみたところ、ひとつも正しく見つけられなかった まだ未発売の曲だったか、極端にニッチな音楽だった可能性もあるが、単にShazamが大きく失敗した可能性もありそう
これは当然、TVのACRにも使われているのと同系統の技術 それなのにShazamのほうがオンラインで評判がずっと良いのは、ユーザーの意図と同意を尊重しているからのように思える TVでも似たような実装をしつつ、データが広告販売にだけ使われないなら、消費者に実際の利益をもたらす形が可能なのではないかと思う
この記事はおそらく、2003年のShazam論文の元のオーディオフィンガープリンティングアルゴリズムを視覚的に説明した資料として最高レベル ただ、今ごろはどこかの時点でMLモデルに切り替えている気もする
DTW(dynamic time warping) というアルゴリズムがあるが、しばしば見過ごされる 私の勘では、Shazamにもこれがある程度使われていたのではないかと思う
同じ録音の認識はそれほど難しくない 同じ録音ならコード進行とタイミングが正確に再現可能なので、この種の認識技術はすでに10年以上も前からあった 一方で、カバーバージョンのように別録音で同じ曲を当てるのははるかに難しい Audible Magicは https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ で、同じ曲の複数のライブ版やパロディまで認識できると主張しているが、当然ながらAIとより多くの計算を使う方式だ
またこの話題かと思ったが、見たらSCPだった このドメインは少し怪しく見える CameronMacLeodの2022年の記事より完全な分析としては https://news.ycombinator.com/item?id=38531428 があり、 Slateの2009年の記事は https://news.ycombinator.com/item?id=893353
プロジェクト一覧に追加しないと Dinosaur gameで、ジャンプをキー入力ではなくコケコッコーの鳴き声でさせたら面白そう
Shazamのようなアプリに検出されないようにする方法があるのか気になる ノイズを混ぜるとか、別の手法が可能なのかと思う
1986年にApple ][cでこれを科学プロジェクトとしてやってみた