ときどき更新されます

CS 周りのお勉強のログ

ダブルハッシュを用いたオープンアドレス法についてメモ

概要

プロコンのためのアルゴリズムとデータ構造を読んでいて，ダブルハッシュを用いたオープンアドレス法のところで， 2つ目のハッシュ関数と配列のサイズと関係のところが最初理解できず， 互いに素の性質から復習したのでメモ

疑問に思ったところ

  • 互いに素でないと生成できない添え字ができるのはなぜか
  • 逆に互いに素ならなぜすべての添え字を作れるのか

理解したことをメモ

基本的には下の記事を見て，互いに素の性質を復習すれば，すべての添え字を作れることについては理解できた． https://hibiyastudy.hatenablog.com/entry/math/naturalnumbers/02#-pq%E3%81%8C%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0%E3%81%AA%E3%81%A8%E3%81%8Dp2p3pq-1p%E3%82%92%E3%81%9D%E3%82%8C%E3%81%9E%E3%82%8Cq%E3%81%A7%E5%89%B2%E3%81%A3%E3%81%9F%E4%BD%99%E3%82%8A%E3%81%AF%E7%95%B0%E3%81%AA%E3%82%8B

上の解説を今回のものにあてはめると

ダブルハッシュを用いたオープンアドレス法では，以下の式でハッシュを計算．

\begin{align} (h_1(k) + i \times h_2(k)) \ \textrm{mod} \ m \end{align}

h_2(k) と m が互いに素のとき，すべての添え字 (0 \sim m-1) を表せることの証明

上の記事の③と④を使って考える．

(h_1(k) + h_2(k)) \textrm{mod} \ m, (h_1(k) + 2h_2(k)) \textrm{mod} \ m, \ldots とあるなかで，どこかで同じ値（つまり，添え字）が出てきたとする．
例えば，(1) h_1(k) + ah_2(k) と (2) h_1(k) + bh_2(k) の m で割ったときの余りが同じであったとする．
そして，それぞれの商を x_1, x_2 とし，同じ値である余りを y とする．

このとき，(1) と (2) の差は以下のように表せる．

\begin{align} h_1(k) + ah_2(k) - (h_1(k) + bh_2(k)) &= (a - b)h_2(k) \\ &=(x_1m + y - (x_2m + y)) \\ &=(x_1 - x_2)m \end{align}

つまり，(1) と (2) の差 (a - b)h_2(k) は， m の倍数となる．
この際， h_2(k) と m は互いに素なので，2つの差が m の倍数になるには， (a - b) が m の倍数である必要がある．（詳しくは記事の③）
しかしながら， (a - b) は (0 ～ m - 1) であり， m の倍数になり得ず，矛盾が生じることになる．

上で，互いに素であればすべての添え字を作れることがわかり，互いに素でないと上が成り立たないので，同じ添え字になることがあるのかなというくらいの理解になった．

Design It! の３章を読んだ．

３章では主に，設計をリスク駆動で進めていく方法について書かれていたので，まとめます．

設計におけるゴールとそれに向けて意識すること

ゴール：最適で合理的な設計ではなく，自分たちのニーズを満たす必要最小限の設計．

上のゴールを達成するために，設計中意識すること

  • 設計を解決策を検証する実験とみなす．設計において考えた組み合わせがあまり良くないわかるだけでも，ゴールに近づいている．
  • リスクを減らすということに専念する．
  • 利害関係者の数を減らしたり，制約を加えたり減らしたり，定型問題に落としたりして問題を単純化する．
  • ある解決策を検証する速度を上げて，素早く学べるようにする．
  • 問題を先に定義しようとするのではなく，解決策と同時に探っていく．

設計に専念する期間

アーキテクチャ設計に時間をかけることについて，将来の修正コストを減らせるということと，利害関係者に価値を届けるまでに時間がかかるということがトレードオフ．

最適な時間については，システムの大きさ，複雑さ，要求の変動性に依存．

設計の優先順位

リスクをベースに考える．リスクの大きさで優先順位をつける．

リスクは，現在ある条件と，それにより今後起こりうる結果をセットで記述する．

リスクの軽減に取り組み際はまず，以下のようなある程度の対処方針を決める．

  • 確率を下げる
  • 影響を軽減する
  • 時間的な制約を取り除く
  • 上で考えた条件を取り除けるようにする．
  • 受容して何もしない

その後，現在どこにリスクがあるかを基に，デザインマインドセットを選択し，解決のための設計を進めていく． この際，Think-Do-Check を利用して，次になにをすべきかを決めていく．

上記をアーキテクチャがシステムにおける最大のリスクでは無くなるまで続け，その後は必要になったときに都度対処するという方針に変える（対処プロセスは同じ）．

設計計画

上のような考えを基にして設計計画を立てる．その際以下を含むようにする．

  • どのような状態になるまで設計に専念すべきか（システムの大小などによる）
  • 設計としての成果物を何にするか
  • マイルストーン．各レビューなども含める．
  • 上位のリスク．定期的に見直す．
  • 初期の設計思想を伝える簡単な設計

Design It! の２章を読んだ．

2章では，デザイン思考をアーキテクチャ設計適用する方法について解説されていたので，まとめておく．

デザイン思考
影響を受ける人々の視点から問題や解決策について考えるための方法

アーキテクチャ設計でのデザイン思考
システムを利用する人，設計判断で影響を受ける人の視点に立ち，解決すべき問題を明らかにしたり，解決策を探求するための方法

原則

まずは，デザイン思考における原則について，アーキテクチャ設計の観点から説明されていたので，それについてまとめる．

  1. 人間のための設計
    エンドユーザや利害関係者のために設計し，利害関係者やチームメンバーと共に設計する．
  2. 曖昧さを保つ
    利害関係者が要求する品質特性や性質に影響する設計判断に絞る．それ以外の設計判断については遅らせ，選択肢を残しておく．
  3. 設計とは再設計である
    ある問題に対して，設計を行う際，すでに過去に検討されていることが多いため，新しく設計を行うよりも既存のものを洗練させることに時間をかける．
  4. アーキテクチャをタンジブルにする

方法

デザイン思考を基に，アーキテクチャ設計を行う際には，基本的に以下を繰り返す．

  1. Think
    何を知りたいか，何を行うべきか決めて，計画を立てる．
  2. Do
    計画を実行する．タンジブルなものを作る．
  3. Check
    Do の内容を確認し，ネクストアクションを決める．

この各繰り返しの中で，以下のデザインマインドセットを選択することで，各繰り返しで何をすべきかを決めて，それに集中できるようにする．

  • 理解
    利害関係者が要求するビジネス目標や品質特性について，それらの優先順位やトレードオフも含めて理解を深める．
  • 探求
    利害関係者が要求する品質特性や性質を促進させるアーキテクチャを見つけるため，その構造の組み合わせを色々と試す．
  • 作成
    現状のアーキテクチャを共有できるように，それを形にしたものを作る（モデル，プロトタイプ，ドキュメントなど）．
  • 評価
    現状のアーキテクチャと要求されているビジネス目標や品質特性を比較して，検査する．

例えば，今回はある品質特性の理解に焦点を当てて，その品質特性の理解を深めるための計画を立て，それを実行し，結果に応じてネクストアクションを決めるといった流れ．

Design It! の１章を読んだ．

各章ごとにまとめる予定です．

ソフトウェアアーキテクト

どんなもの？

  • 利害関係者と一緒に，ソフトウェアのビジネス目標や，ソフトウェアへの要求を定義． この要求には，機能や品質特性が含まれる． この際，今後の設計に影響を与えそうな制約などにも注意しておく．

  • システムをそれぞれが小さい責務を持つコンポーネントに分割． これにより，設計を行う上で，上で決めた要求を満たすため方法について考えやすくなる．

  • 設計判断を行う上で，その判断が影響を与える技術的および非技術的な様々な要素について考え，それらの要求におけるトレードオフを考える必要がある．そして利害関係者と一緒に最も良い妥協案を考える． 妥協案には，技術的負債を利用するというようなことも含まれる．

ソフトウェアアーキテクチャ

どんなもの？

  • 利害関係者と定義した品質特性やその他の性質について，それらがシステム中に現れるにはシステムをどのように構成すればよいか考えた際の設計判断が集まったもの

  • アーキテクチャを選択する＝システム上に現れてほしい品質特性や性質を選択する

  • システムの構造を定義する．ここでの構造とは，コードや実行中のソフトウェア上での要素の関係や，それら2つと物理要素（サーバ，チーム，人などを含む）の関係（あるモジュールはどのチームが開発するかなど）を示したもの． なお，構造には，それらがシステム上のどこに現れるかによりいくつか種類があり，考える品質特性に応じて，定義対象とする構造を変える．

考える利点

  • 全体では複雑なシステム構築について，分割した問題を示してくれる．
  • システムの構造が定義されており，そこには人やチーム間の関係も含まれていることから，開発において人・チームがどのように協働するか示してくれる．
  • 考える過程で，機能だけでなく，品質特性や制約などについて注意を向けることができる．

Beyond Personalization: Social Content Recommendation for Creator Equality and Consumer Satisfaction (KDD19) を読んだ．

目的

レコメンドシステムにおいて，コンテンツを消費する人 (ユーザ) の満足が高く，推薦対象のコンテンツを選ぶ上で，クリエイターの人気の有無や，投稿したコンテンツ数などに依存せず，クリエイター間での偏りのない推薦を行うための手法を提案．
また，推薦がクリエイター間での偏りのないものであったかを確認するための指標として，ジニ係数を利用することを提供している．

論文の手法の特徴

提案手法では，コンテンツベースの手法を採用．

パーソナライズされたコンテンツの特徴を推薦に利用し，各ユーザの好みに近いコンテンツを推薦することで，クリエイターの人気などに依存せず，クリエイター間での偏りを軽減できると主張している．

f:id:jamjam723:20200505120951j:plain
特徴算出のアーキテクチャ

具体的に，ドキュメント内の単語単位の特徴から文単位の特徴を算出する際，および文単位の特徴からドキュメントの特徴を算出する際に，ユーザ特徴を利用して算出されるアテンションを基に重みづけが行うことで， パーソナライズされたコンテンツ特徴を算出を行う．
ユーザ特徴は，Embedding をもとに算出され，推薦対象ユーザだけではなく，その友人ユーザが算出に利用される．

提案手法では，ユーザ特徴でのユーザの友人利用について，隣接する友人だけでなく，数ホップ先の友人を利用すると同時に，その選択にランダム性を持たせる． これにより，推薦により寄与する友人を利用することによる推薦精度向上につながることに加えて，最終的な推薦結果に多様性が生まれるとしている．

f:id:jamjam723:20200505121025j:plain
友人利用の概要

具体的に，友人の探索はバンディット問題として扱われる．つまり，推薦に扱った方が良い友人の探索を目的とした友人選択 (探索) と，探索により得られた結果を利用した友人選択 (利用) について，それらのトレードオフを基に算出される値が最適になるよう友人を選択する．この際，選択は友人関係を基に構築されるネットワーク上で行われる．
利用において，どの友人が推薦に寄与するかの指標として，実際に探索で利用した際のF1スコアや，ページランクのスコアなど複数の指標を利用可能．探索の際には，ネットワーク上で，今まで探索に利用されていな友人ほど選ばれやすくなる指標が利用される．

実験

データセットとして，Steemit (ブロックチェーンデータベースを利用し，ブログや SNS を提供しているサービス) 上のユーザとドキュメントを利用．

あるユーザがコメントしたドキュメントを正例，友人はコメントしているがそのユーザはコメントしていないドキュメントを負例として扱う．

評価指標として，推薦精度を見るためには F1 と AUC を利用し，クリエイター間での偏りがないことを確かめるためにジニ係数を利用している．ジニ係数では，値が低いほど，いろいろなクリエイターのコンテンツが推薦対象となっている．加えて，F1 とジニ係数の調和平均 (C&C) をそれらのバランスの良さを見るための指標として利用．
ある時点より実験のデータで学習し，各時点で算出される精度の平均を最終的な精度としている．

f:id:jamjam723:20200505121103j:plain
比較結果

上表が結果であり，SEAN が提案手法． 結果において，NCF や SAMN が協調フィルタリングベースの手法であり，LR，DKN，SEAN のコンテンツベースの手法と比較しジニ係数の値が高いことがわかる． つまり，協調フィルタリングベースの手法では，推薦対象となるクリエイターに偏りがあることがわかる． DKN は，パーソナライズされたコンテンツベースの手法であるが，各ドキュメントの特徴を算出する際にユーザ情報が利用されておらず，特徴算出において提案によのアーキテクチャが有効であるとしている．

f:id:jamjam723:20200505121139j:plain
コンポーネントの貢献度

また，上の結果は提案手法をいくつかのコンポーネントに分けた際に，各コンポーネントの貢献度合いを示すもの．w/o social は，友人の情報を利用しない手法．w/o social attention は友人関係を利用する際に，提案手法では友人の特徴に対してアテンションによる重みづけを行っているが，それを無くした手法．one-hop friends は，隣接する友人しか利用しないというもの．

データセットの組み方から友人関係がかなり重要になりそうなので，提案手法の精度が高くなるのは少し当然かもしれないが（比較中で友人関係を利用するのは SAMN），マルチホップで友人関係をうまく利用する方法を提案しているのもこの論文の貢献．友人の選び方については，ランダムなものとの比較や，推薦への寄与を図る指標の比較，パイパーパラメータによる精度変化が検証されている．

関連研究

比較手法として利用されていた手法

友人関係を利用した協調フィルタリングベースの手法
Social attentional memory network: Modeling aspect-and friend-level differences in recommendation (WSDM 19)

実験でもそれなりにいい精度が出ていそうな，コンテンツベースの手法
Dkn: Deep knowledge- aware network for news recommendation (WWW 18)