Property Testing

• Property Testing Reviewという名のウェブサイト！
• Testing properties under Lp distances
• Lp-testing
• Property testingとdecision

Property Testing: Current Research and Surveys (Lecture Notes in Computer Science)

• • この本のサイト
• ごく簡単に言うと：
  • 「これって、Aかな、Aじゃないかな、どっちかだ、と決めよう」という状況で
  • 少々曖昧でもよいけれど、「Aだ、かなり自信ある」「Aなわけがない」に分けましょう
  • グレーゾーンは残ります
  • 「自信がある」「なわけがない」とは言いながら、「このくらい」の低い確率ではまちがっているかも、というレベルの決断
  • これなら「計算機」にもやらせられる(やらせられるようにできる)→このような枠組みでの計算機による「証明」のことをProbabilistically Checkable Proofsという
• このProperty testingは「距離」をベースに二分岐判断をするが、それに用いる「距離」としてハミング距離で出来上がってきた手法らしいが、そこにLp距離を使うのもよいよ〜、という流れらしく、この記事でリンクを張っている先も、そのようなLp関係のProperty testingにフォーカスを置いたうえで取ってきている
• Property testingでは、判断を下す対象(データ)を、「関数」であると見て、その「関数」が、ある特徴(property)を有する関数の全体の要素になっているのか、その集合から「離れて」いるのか、離れているとしたら、その「距離」はどれくらいなのか、ということで判断する。したがって、「距離」が不可欠であり、「距離」の定義にどんなものを使うか、と言うことを問題にする。また、「距離」を問題にすることから、「距離」を測りうる「１次元実数直線」に写像しているものとして「関数」を考えるらしい。この「距離」は何に定義されているかというと「関数と関数との間」に定義されている