めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > 情報・数理 > 情報システムに関するメモ2

情報システムに関するメモ2

情報・数理 メモ

はじめに

書いてあること細かい部分だいぶ端折ってます、しっかりした部分は参考文献などかならず書いておくのでそちらのサイトさまを参考にしてください、内容は

  • 一部資料での用語のメモ
  • 試験とか資料で必要そうな用語のメモ

資料０

資料１

検索の尺度

{ 再現率 = \frac{見つけた正解の数}{すべての正解の数} \\ 適合率 = \frac{見つけた中での正しい正解の数}{見つけた数} }
以上が検索の性能の指標でありこれらはトレードオフの関係、実際には適合率がより大切。

質問緩和法

従来では検索キーワードをすべてAND検索で画像検索にかけていたものを、部文集合に分けていくつかのキーワードをテキスト検索のキーワードとして使用する

引用元：質問緩和法によるクロスメディア・メタサーチ 桑原昭裕,角谷和俊,田中克己 ,DEWS 2004
その仕組みと詳細は参考文献[2]を参照。

テストコレクション

ある技術の性能を評価するための実験(テスト）に使用するためのデータセット

引用元：NTCIR Project テストコレクションって何？

検索の性能に対するテストコレクションは...

  • 検索対象のドキュメント集合
  • 検索列（質問の集合）
  • 各質問に対応した解の集合

をふくむはず。

ベクトル空間モデル

ベクトル空間モデル - Wikipedia

検索対象のドキュメント（以下文書）をベクトルで表現して質問ベクトルと文書ベクトルのコサイン相関値から結果をもとめる。このベクトルの作り方でもっとも有名なものの一つがtf/idf法。

tf-idf - Wikipedia

tf-idf

{tf_{ij}}:文書iでの単語jの出現頻度の尺度
{df_{j}}:単語jの出現する文書数の尺度
上記をそれぞれ定義する（定義の仕方はいろいろある）。これらをもとに
{idf_{j} = \log \frac{検索対象の文書数}{df_j} }
{w_{ij} = 文書iベクトルでの第j要素の値 = tf_{ij} idf_j }
としてこの文書ベクトルと質問ベクトルの内積をとる。

適合フィードバック

The idea behind relevance feedback is to take the results that are initially returned from a given query and to use information about whether or not those results are relevant to perform a new query.

引用文献:Relevance feedback - Wikipedia, the free encyclopedia

結果を見てユーザが正解、不正解をえらびそれを元に結果を改善していく。

参考文献:

資料２

F値

情報検索 - Wikipedia（検索性能の評価項参照）
適合率と再現率の調和平均で、値が大きいほど性能がいい。

MAP(Mean average precision)

Information retrieval - Wikipedia, the free encyclopedia
各質問に対する適合率の平均値をその検索システムの性能とする尺度。

DCG(Discounted cumulative gain)

上記MAPの説明下に詳しい説明があります。

その他言葉の定義・索引

ハイパーテキスト

参考文献:ハイパーテキスト - Wikipedia
　ノード（主に文書）とそれをつなぐリンクからなるグラフ構造。データ間の関連づけはリンクにより行われる。

Dexterハイパーテキスト参照モデル

参考文献:Dexter Hypertext Reference Model
ハイパーテキストのシステムを以下の要素に分割してモデル化する。

  • ランタイムレイヤー:ハイパーテキストの表示とユーザー＝テキスト間のインタラクションを行う
  • ストレージレイヤー:テキストのノードとリンクのグラフ構造を保存する
  • コンポーネント内部レイヤー:ノード（主に文書）内部のコンテンツと構造を管理する

HyperCard

引用文献:HyperCard - Wikipedia

ハイパーテキストのノードとしてカードを用い、カードとカードをつなぐリンクとしてはボタンを用いる。カードの上にはボタンの他にテキストやグラフィックをおくことができた。プログラムを記述するにはHyperTalkと呼ばれるスクリプト言語を用いる。

SGML

参考文献:Standard Generalized Markup Language - Wikipedia
SGMLは「インスタンス」、「DTD」、「SGML宣言」の3つで構成されていて基本的なデータはテキストのみ。表示の整形はスタイルシートで行う。SGMLの改良形がXML。Adobeのホームページのどこかに詳しい説明があった。

構造化文書

引用文献:Adobe FrameMaker 8 ユーザガイド

各種の文書では、文書の内容がいくつかの論理的な単位から構成され、それぞれの論理的な単位が、一貫した順序と特定の構造で配置されています

文書を「論理構造」と「物理レイアウト構造」に分けて記述したもの。こうすることでレイアウトの生成方法を自動化できる。

  • 一体生成

ユーザが論理構造とレイアウトを自分ですべて指定する。

  • 半分離生成

ユーザは論理構造を示したファイルとレイアウトを示したファイルを別々に記述することで指定。

  • 分離生成

ユーザは論理構造のみを指定。（統一された文書などに有効）

SORP

参考文献:SOAP (プロトコル) - Wikipedia
クライアントからのリクエストとサーバからの応答をともにXML形式で行う。

REST

参考文献:REST - Wikipedia
リクエストの情報をすべてURIに埋め込んで記述（サーバーはクライアントの状態を保持せず...ステートレスにクライアントがサーバーに送る情報にこれらのやりとりを含める）。

Ajax

参考文献:Ajaxとは (Asynchronous JavaScript + XML) エージャックス： - IT用語辞典バイナリ
ウェブブラウザでの非同期通信を行うインタフェース構築に関係する技術の総称。もっとも普通の形がページに埋め込まれたjavascriptがユーザに対して対してサービスを提供、サーバと非同期に通信を行う。さらにサーバから陸エストの応答となるデータをxmlで受け取りそれをもとにユーザに対するページの情報を書き換える。

XLink

参考文献:XLink - Wikipedia
　HTML上のリンクと比べて違う点は

  • 一方向ではなく双方向のリンク
  • リンクの定義はリンクの場所以外に記述してもいい
  • リンクするさきは一つではなく任意個を指定できる
  • リンクするタイミングを記述できる

SMIL

参考文献:XML用語事典 [SMIL]

PageRank

参考文献:･ページランク計算方法の原理
　基本的な考え方、「よりたくさんのページからリンクされているページはより有用」で「より有用なページからリンクされているページは通常のページからリンク冴えるよりも有用」であるとする。各ページに有用度の基準となる数値を割り当ててそれを行列を用いてより有用なページは有用度を高く、そうでないページは有用度を低く評価する。

{ { \displaystyle A = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{array} \right) } }

第i列は「ページ{p_i}からリンクされているページの要素を１」にする。そのあと、はじめはすべてのページの有用度を同じだと仮定していったん「第i列の1である要素をすべて{¥frac{1}{第i列で１である要素の数}}」とする。つまりはじめはどの列も要素の和が1になっている。次に、すべてのページのはじめの有用度を1（もしくは有限の値）として上記の行列を何度も掛けていく。収束した値が最終的な有用度の値。しかしこのままでは

  • ほかのページへのリンクがないページがあるとすべてのページは有用度が0になりうる
  • 自分を参照するリンクがあるとそのサイトだけ有用度が与えられる

そのため、”tax”を与えることでこれらの問題を同時に回避する、詳細は以下のスライドを参照。
ランダムウォークとして考えるならば(i+1時刻にいる場所) = (1-tax)(i時刻にいる場所)+tax(ランダムに移動)。
この式から分かるようにtaxの値が大きすぎるとランダムに移動しがちなものと見て取れてしまうから通常はtaxは小さな値をとる。

参考文献:

Page rank

HITSアルゴリズム

参考文献:HITSアルゴリズムとは | SEO 検索エンジン最適化

ページは
http://en.wikipedia.org/wiki/HITS_algorithm

http://en.wikipedia.org/wiki/HITS_algorithm

http://en.wikipedia.org/wiki/HITS_algorithm
以下の二種類に分類される

  • ハブ　有用なページへのリンクをもつ
  • オーソリティ　有用な情報を発信するページ

a good hub represented a page that pointed to many other pages, and a good authority represented a page that was linked by many different hubs

引用文献:Wikipedia HITS algorithm

上記の基本的な考え方に基づくと、有用度の高いハブはほかのみんなが参照しているページを参照しているし、有用度の高いオーソリティは有用度の高いハブが参照していると考えて

  • オーソリティとしての有用度
    • そのページにリンクしている各ページのハブとしての有用度の合計
  • ハブとしての有用度
    • そのページにリンクしている各ページのオーソリティとしての有用度の合計

と有用度を決める。行列で計算すると

ハブとしての有用度　＝　行列を用いてリンク先のオーソリティとしての有用度を分配
オーソリティとしての有用度　＝　行列を用いてリンク元のハブとしての有用度を分配

となるように記述するのだから隣接行列をAとして

{ \vec{hub-weight} = A \vec{auth-weight} \\ \vec{auth-weight} = A^T \vec{hub-weight} }
※グラフは有向グラフだから転置しないと「リンクもとのハブ」を示せない

として計算すればいいと分かる。これらを交互に行うのだからまとめて{(A^T A)}をハブとしての有用度の初期値に掛け合わせていく。
参考文献:
HITS Algorithm - Hubs and Authorities on the Internet
※ http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/ での講義の第四回を参照します

XMLとDTD

以下のサイトに丁寧に書いてあるのでそれを参照して省略。
http://gogodiet.net/z/xml/

DOMとSAX

DOM:

XMLを読み込む別のAPIであるSAXと異なり、XMLデータをツリー構造として扱う事ができる。ただし、通常の場合対象のXML文書を全て読み込んでからの扱いを前提とするため動作速度が遅かったり、メモリーの使用量が大きくなる欠点もある。

引用文献:Document Object Model - Wikipedia
HTMLやXML文書を木構造でとらえてプログラミング言語がそのノードを指示してそこに対して操作を加えられるような環境を提供する。

SAX:

XML文書を木構造として扱うDOMと異なり、一連のイベントとして表現するイベント駆動型のAPIである。したがって、アプリケーションソフトウェアが積極的にAPIにアクセスするDOMに対し、SAXではアプリケーションソフトウェアがイベントが来るのを待ち受ける受動的な動作が大部分を占める。

引用文献:Simple API for XML - Wikipedia

DOMは解析結果を木構造で保持する必要があるため、逐次的な処理やメモリの消費量ではSAXが有意。またXMLが非常に大きいファイルの場合もSAXが有利（SAXはイベント駆動型のAPIでXML文書のあるノードなどのイベントを生成してファイル全体を解析することなくアプリケーションにイベントを送る。）

参考文献:Java 入門 | SAX (Simple API for XML)

XQueryとXSLTの違いについて。

実を言えば、変換（transform）と照会（query）は、多くのアプリケーションをカバーする汎用的な用語です。すでに述べたように、2つの言語はともにXPath 2.0を基礎としているため、同じような機能を備えています。しかし、使用パターンが異なるため、それぞれ適したタスクというものがあります。

引用文献:実用的なXML:XSLT 2.0とXQueryの比較

初めに両者の説明。
XSL Transformations: W3Cにより標準化されたXML文書の変換用言語.XPathによる選択と検索から決定した一部の文書に大して変換操作を行い表示、印刷用の文書を変換結果として生成することができる*1。XSLTはXMLの木構造である記述に基づいて再帰的に変換を行うことができる。

XQuery:XMLデータ問合せの為の問い合わせ言語。XML PathはXMLに準拠した文書の特定の部分を指定するための言語であり、XQueryはXPath2.0の拡張。「問い合わせ」の言語とあるようにCRUDと呼ばれる基本的なデータ操作（データの作成、読み出し、更新、削除）のうちでXqueryに定義されているのは検索結果を示すための「読み出し」のみ。

ついでにXMLも。
XML:

個別の目的に応じたマークアップ言語作成のため、汎用的に使うことができる仕様、および仕様により策定される言語の名称

引用文献:Extensible Markup Language - Wikipedia
以上の記述からもわかるように、XMLで使われるタグはユーザ自ら定義するものだから、HTMLのように表示と関係することなく、タグがその要素の説明をしていることを意味する。


両者の相違点:
　初めに「XSL」は検索で指示した結果に対して変換を行うが後者は行わない等。

RESTとAjaxで作ったサイトの違い

参考文献:Ajax と REST、第 1 回
RESTでは状態が異なれば異なるURLをもつ。一方でAjaxではURLは状態が変わっても同一でありソースをJavaScriptでリアルタイムで書き換えていくページになる。

※SOAP API:ユーザのリクエストとサーバからのレスポンスはともにXMLフォーマットに従う形式
※REST API:ユーザのリクエストはURLに対応していて、サーバからのレスポンスはXML
※Ajax:JavaScript の組み込みクラスである XMLHttpRequest を利用した非同期通信を利用して、ウェブブラウザ上で既存の枠組みにとらわれないインタフェースを実現するための技術(この項のみ引用文献:Ajaxとは - はてなキーワード)

Webサービスでのセッションの実現方法

  1. あたらしくユーザが追加される度にセッションIDを作成
  2. そのクライアントにデータを送る歳にHTTPヘッダにそのIDをクッキーの情報として取り込みクライアントがこれを受け取る
  3. 以降指定された期間はこのクッキーの情報を元にクライアントを判別

XLinkについて

　データ間同士のリンクづけを行うための規格であり説明のためにHTMLのリンク(a href)と比較すると、

  • XLinkは任意の数のリソース間に設定できる
  • XLinkは任意方向へのリンクができて、一方向のHTMLとは違う
  • リンクの定義をリンクの出発点にすべて記述する必要が無い(html ではa href=...と行き先をその場で定義する必要があった)
  • リンクの動作タイミングと効果をリンクそのものに記述可能

参考文献:XLink - Wikipedia

このほかのメモ


情報システムに関するメモ4（最後） - 雑なメモ

情報システムに関するメモ3 - 雑なメモ

情報システムに関するメモ2 - 雑なメモ

情報システムに関するメモ1 - 雑なメモ

*1:XSL Transformations - Wikipedia

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。