コンピューターが＆＃8220;学習することは可能ですか？ユーザー提供の例による正規表現？

Question

コンピュータが「学習」することは可能ですか？ユーザー提供の例による正規表現ですか？

明確にするために：

• 正規表現を学習したくないしない。
• 「学習」するプログラムを作成したいおそらくテキストからパーツを選択するか、開始マーカーまたは終了マーカーを選択することにより、ユーザーがインタラクティブに提供する例からの正規表現。

それは可能ですか？ Googleで使用できるアルゴリズム、キーワードなどはありますか？

編集：回答ありがとうございますが、この機能を提供するツールには興味がありません。論文、チュートリアル、ソースコード、アルゴリズムの名前などの理論情報を探しているので、自分で何かを作成できます。

Answer 1

計算学習理論入門には、学習アルゴリズムが含まれています。有限オートマトン。すべての正規言語は有限オートマトンと同等であるため、プログラムによっていくつかの正規表現を学習することが可能です。 カーンとヴァリアントは、有限オートマトンを学習することはできません。関連する問題は、隠れマルコフモデルの学習です。これは、文字シーケンス。最も最近の「正規表現」プログラミング言語で使用される言語は、実際には通常の言語よりも強力であるため、学習が難しい場合があります。

Answer 2

はい、 可能です、 サンプルから正規表現を生成できます（テキスト-＆gt;必要な抽出）。 これは仕事をするオンラインツールです： http://regex.inginf.units.it/

Regex Generator ++オンラインツールは、GP検索アルゴリズムを使用して、提供された例から正規表現を生成します。 GPアルゴリズムは、より高いパフォーマンスとよりシンプルなソリューション構造（OccamのRazor）につながる多目的適応度によって駆動されます。 このツールは、トリエステ大学（Universit＆＃224; degli studi di Trieste）のMachine Lerning Labによるデモ用アプリケーションです。 ビデオチュートリアルこちらをご覧ください。

これは研究プロジェクトであるため、使用されているアルゴリズムについてはこちらをご覧ください。

見よ！：-）

例から意味のある正規表現/解決策を見つけることは、提供された例が問題をよく説明している場合にのみ可能です。 抽出タスクを説明するこれらの例を検討してください。特定のアイテムコードを探しています。例はテキスト/抽出ペアです：

"The product code il 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

例を見て、（人間の）男は言うかもしれません：＆quot;アイテムコードは\ d ++-345 [AB]＆quot;のようなものです

商品コードがより寛容であるが、他の例を提供していない場合、問題を十分に理解する証拠がありません。 人間が生成したソリューション\ d ++-345 [AB]を次のテキストに適用すると、失敗します。

"On the back of the item there is a code: 966-347Z"

一致とは何か、望ましい一致ではないものをより適切に説明するには、他の例を提供する必要があります。 --i.e：

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

電話番号は製品IDではありません。これは重要な証拠です。

Answer 3

有効な一致のリストに基づいて単独で意味のある正規表現を生成できるコンピュータープログラムはありません。理由をお見せしましょう。

コンピューターが生成する場合、例111111および999999を提供するとします。

1. これら2つの例に正確に一致する正規表現：（111111 | 999999）
2. 同一の6桁の数字に一致する正規表現（\ d）\ 1 {5}
3. 6個の1と9に一致する正規表現 [19] {6}
4. 任意の6桁の \ d {6}
に一致する正規表現
5. 上記3つのうち、単語の境界があるもの。 \ b \ d {6} \ b
6. 数字の前後にない最初の3つのいずれか。 （？＆lt;！\ d）\ d {6}（？！\ d）

ご覧のとおり、例を正規表現に一般化できる方法はたくさんあります。コンピューターが予測可能な正規表現を作成する唯一の方法は、すべての一致をリストするよう要求することです。次に、それらの一致と正確に一致する検索パターンを生成できます。

可能性のあるすべての一致を一覧表示したくない場合は、より高いレベルの説明が必要です。それはまさに正規表現が提供するように設計されているものです。 6桁の数字の長いリストを提供する代わりに、「任意の6桁」に一致するようにプログラムに指示するだけです。正規表現の構文では、これは\ d {6}になります。

正規表現と同じくらい柔軟な高レベルの記述を提供する方法は、正規表現と同じくらい複雑になります。 RegexBuddy のようなツールはすべて、高レベルの説明の作成とテストを簡単にすることです。簡潔な正規表現構文を直接使用する代わりに、RegexBuddyを使用すると、単純な英語のビルディングブロックを使用できます。しかし、サンプルを一般化すべきときとそうでないときを魔法のように知ることができないため、高レベルの説明を作成することはできません。

サンプルテキストとユーザーが提供するガイドラインを使用して正規表現を生成するツールを作成することは確かに可能です。そのようなツールを設計する際の難しい部分は、正規表現自体よりもツールを学習しにくくすることなく、またツールを一般的な正規表現ジョブまたは単純な正規表現に制限することなく、ユーザーに必要なガイド情報をどのように求めるかです。

Answer 4

はい、確かに「可能」です;擬似コードは次のとおりです。

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")<*>quot;;

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

問題は、例のリストと一致する正規表現の数が無限にあることです。このコードは、セット内で最も単純な/最も愚かな正規表現を提供し、基本的にポジティブな例のリストにあるものと一致します（ネガティブな例も含めて他には何も一致しません）。

実際の課題は、すべての例に一致する最短の正規表現を見つけることですが、それでも、ユーザーは非常に良い入力を提供して、結果の表現が「正しい表現」であることを確認する必要があります。

Answer 5

この用語は「誘導」だと思います。通常の文法を誘導したい。

有限の例のセット（正または負）でそれが可能であるとは思わない。しかし、正しく思い出せば、相談できるOracleがあればそれを行うことができます。 （基本的には、コンテンツになるまでプログラムにユーザーにyes / noの質問をさせる必要があります。）

Answer 6

このサイトで少し遊びたいかもしれませんが、とてもクールで、あなたが話していることと似たようなことをしているように聞こえます： http://txt2re.com

Answer 7

プロローグに基づいた、このような問題専用の言語があります。 progol と呼ばれます。

他の人が言及したように、基本的な考え方は帰納的学習であり、ILP（帰納的論理プログラミング）AIサークル。

2番目のリンクはILPに関するwiki記事です。トピックに関する詳細を知りたい場合は、多くの有用なソース資料が含まれています。

Answer 8

@Yuvalは正しいです。あなたは計算学習理論、または「帰納的推論」を見ています。 ＆quot;

「学習」の定義として、質問はあなたが考えるよりも複雑です。自明ではありません。一般的な定義の1つは、学習者が必要に応じていつでも回答を吐き出すことができるが、最終的には、回答の吐き出しを停止するか、常に同じ回答を吐き出す必要があるということです。これは、入力の数が無限であることを想定しており、プログラムがいつその決定に達するかについての保証をまったく与えません。また、後で何か異なるものを出力する可能性があるため、いつ決定に達したのかわかりません。

この定義により、通常の言語は学習可能であると確信しています。他の定義では、それほどではありません...

Answer 9

Googleと CiteSeer でいくつかの調査を行ったところ、次のテクニック/論文が見つかりました：

• 制限内の言語識別
• おそらくほぼ正しい学習

また、Dana Angluinの「クエリと反例からの正規セットの学習」有望に思えますが、PSまたはPDFバージョンを見つけることができませんでした。引用とセミナーの論文のみです。

これは理論的なレベルでさえ難しい問題のようです。

Answer 10

人が正規表現を学ぶことが可能であれば、プログラムは基本的に可能です。ただし、学習できるようにするには、そのプログラムを正しくプログラムする必要があります。幸いなことに、これはかなり有限の論理空間なので、オブジェクトやそのようなものを見ることができるようにプログラムを教えるほど複雑ではありません。