JPH0746345B2 - 順次的判定プロセスの最適化方法 - Google Patents
順次的判定プロセスの最適化方法Info
- Publication number
- JPH0746345B2 JPH0746345B2 JP62127284A JP12728487A JPH0746345B2 JP H0746345 B2 JPH0746345 B2 JP H0746345B2 JP 62127284 A JP62127284 A JP 62127284A JP 12728487 A JP12728487 A JP 12728487A JP H0746345 B2 JPH0746345 B2 JP H0746345B2
- Authority
- JP
- Japan
- Prior art keywords
- rule
- cost
- ratio
- search
- firing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N5/00—Computing arrangements using knowledge-based models
- G06N5/04—Inference or reasoning models
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N5/00—Computing arrangements using knowledge-based models
- G06N5/01—Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S706/00—Data processing: artificial intelligence
- Y10S706/902—Application using ai with detail of the ai system
- Y10S706/903—Control
- Y10S706/908—Electronic or computer, internal or network, circuit
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S706/00—Data processing: artificial intelligence
- Y10S706/902—Application using ai with detail of the ai system
- Y10S706/919—Designing, planning, programming, CAD, CASE
- Y10S706/922—Computer program preparation
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- Physics & Mathematics (AREA)
- Computational Linguistics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Artificial Intelligence (AREA)
- Devices For Executing Special Programs (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】 A.産業上の利用分野 本発明は一般に人工知能の分野に、より具体的には順次
的な判断の実行のスピードを増加させるための適応的な
方法に関する。ここで用いる時、人工知能という用語
は、知能的な計算機システムを設計する事にかかわるコ
ンピュータ・サイエンスの分野を意味する、そのような
システムは、問題解決、論理的推論、言語理解、プログ
ラミング、学習、エキスパート・システム、ロボティッ
クス及びビジョンにおいて応用が増加しつつある。
的な判断の実行のスピードを増加させるための適応的な
方法に関する。ここで用いる時、人工知能という用語
は、知能的な計算機システムを設計する事にかかわるコ
ンピュータ・サイエンスの分野を意味する、そのような
システムは、問題解決、論理的推論、言語理解、プログ
ラミング、学習、エキスパート・システム、ロボティッ
クス及びビジョンにおいて応用が増加しつつある。
B.従来技術 人工知能における問題解決方法に関する最も重要な側面
には、（１）表現及び（２）探索がある。本発明は判断
プロセスにおける探索の効率に関する。現行の方法にお
ける探索の戦略は典型的には下記の特性を有している。
には、（１）表現及び（２）探索がある。本発明は判断
プロセスにおける探索の効率に関する。現行の方法にお
ける探索の戦略は典型的には下記の特性を有している。
1.固定的な制御を用いる； 2.経験に対して敏感でない； 3.探索プログラムの使用パターンを利用しない； 固定的な制御を用いた探索戦略は、良い実行時性能を達
成する上で固有の限界を有する。ここで、グラフ中の経
路発見の例を用いて、固定的な探索戦略を説明する。第
３図に示すような有向グラフを考える。有向グラフ中の
指定されたノードの対の間の経路を探索するために、プ
ログラムはPROLOGで書いてもよい。PROLOGはその名前が
プログラミング・イン・ロジック（PROgramming in LOG
ic）に由来するコンピュータ・プログラム言語であっ
て、主要な人工知能インプリメンテーション言語であ
る。例えば、D.H.D.Warren、L.M.Pereira及びF.Pereira
著、「PROLOG−The Language and Its Implementation
Comparecl with LISP」、Proceelings of The Symposiu
m on Artificial Intelligence and Programming Langu
age、（1977）、ACM発行、を参照されたい。そのような
プログラムの例を下記に示す。
成する上で固有の限界を有する。ここで、グラフ中の経
路発見の例を用いて、固定的な探索戦略を説明する。第
３図に示すような有向グラフを考える。有向グラフ中の
指定されたノードの対の間の経路を探索するために、プ
ログラムはPROLOGで書いてもよい。PROLOGはその名前が
プログラミング・イン・ロジック（PROgramming in LOG
ic）に由来するコンピュータ・プログラム言語であっ
て、主要な人工知能インプリメンテーション言語であ
る。例えば、D.H.D.Warren、L.M.Pereira及びF.Pereira
著、「PROLOG−The Language and Its Implementation
Comparecl with LISP」、Proceelings of The Symposiu
m on Artificial Intelligence and Programming Langu
age、（1977）、ACM発行、を参照されたい。そのような
プログラムの例を下記に示す。
adj（a,b）． adj（a,c）． adj（a,d）． adj（a,e）． adj（b,c）． adj（b,d）． adj（c,d）． adj（e,f）． conn（x,y）←ne（x,y） ＆ adj（x,y）． conn（x,y）←ne（x,y） ＆ adj（x,z） ＆ conn（z,
y）． conn（x,y）←fall. バックトラック付きのトップ・ダウン、左から右への探
索戦略（即ち深さ優先探索）がPROLOGシステムにより提
供されるものとして、使用されると仮定する。探索プロ
グラムは、「←conn（a,f）．」とタイプする事によ
り、ａがｆに接続されているか否かが照会される。次
に、ａからｆへの経路が見い出される前に、第2A図に示
す探索木を走査する事により探索の実行が行なわれる。
探索プロセス中に訪れるノードの順序は、順方向は破線
で、逆方向は点線で示されている。「←conn（a,
f）．」の形の照会は、探索プログラムに提供し得る問
題入力の組の例（インスタンス）を表わしている。問題
の例Ｉに関して、走査される探索木をＴ（Ｉ）で表わす
ものとする。固定的な探索戦略に関して観察される主な
特性は次の通りである。もし探索プログラムに次の形の
問題例の反復系列が与えられると、 Ｉ、Ｉ、Ｉ、…、Ｉ（ｎ個のＩの系列） 問題例の反復的な解において走査される探索木は、 Ｔ（Ｉ）、Ｔ（Ｉ）、…、Ｔ（Ｉ）（ｎ個のＴ（Ｉ）の
系列） となる。Ｉに関して、もし探索プログラムが開始が非効
率的であるとすると、Ｉが何回解かれるかに無関係に、
探索プログラムはそれがＩの最初の例を解く前にちょう
どそうであったように非効率的である。固定的な制御を
用いた探索プログラムは、その経験において、ある問題
例を他の問題例よりも頻繁に解いたという事実を利用し
て効率を改善するように学習しない。現実的な問題の場
合、全ての入力例が等しい確立で起きる事はないと信じ
られる。出会う問題例の組が非一様的な分布を示すと仮
定すると、これは平均的な実行時性能を最適化するため
に探索プログラムにより利用する事ができる。
y）． conn（x,y）←fall. バックトラック付きのトップ・ダウン、左から右への探
索戦略（即ち深さ優先探索）がPROLOGシステムにより提
供されるものとして、使用されると仮定する。探索プロ
グラムは、「←conn（a,f）．」とタイプする事によ
り、ａがｆに接続されているか否かが照会される。次
に、ａからｆへの経路が見い出される前に、第2A図に示
す探索木を走査する事により探索の実行が行なわれる。
探索プロセス中に訪れるノードの順序は、順方向は破線
で、逆方向は点線で示されている。「←conn（a,
f）．」の形の照会は、探索プログラムに提供し得る問
題入力の組の例（インスタンス）を表わしている。問題
の例Ｉに関して、走査される探索木をＴ（Ｉ）で表わす
ものとする。固定的な探索戦略に関して観察される主な
特性は次の通りである。もし探索プログラムに次の形の
問題例の反復系列が与えられると、 Ｉ、Ｉ、Ｉ、…、Ｉ（ｎ個のＩの系列） 問題例の反復的な解において走査される探索木は、 Ｔ（Ｉ）、Ｔ（Ｉ）、…、Ｔ（Ｉ）（ｎ個のＴ（Ｉ）の
系列） となる。Ｉに関して、もし探索プログラムが開始が非効
率的であるとすると、Ｉが何回解かれるかに無関係に、
探索プログラムはそれがＩの最初の例を解く前にちょう
どそうであったように非効率的である。固定的な制御を
用いた探索プログラムは、その経験において、ある問題
例を他の問題例よりも頻繁に解いたという事実を利用し
て効率を改善するように学習しない。現実的な問題の場
合、全ての入力例が等しい確立で起きる事はないと信じ
られる。出会う問題例の組が非一様的な分布を示すと仮
定すると、これは平均的な実行時性能を最適化するため
に探索プログラムにより利用する事ができる。
PROLOGにより提供される深さ優先探索のような固定的探
索戦略の重大な欠点は、種々の入力に関して探索が行な
われる固定的な順序にプログラムが気付いていなければ
ならない事である。もしプログラマが効率に関心を有す
るならば、彼は、解決したいと思う問題例の集合に関し
てその固定的探索戦略が効率的に解を発見するような方
法でプログラムを書く責任がある。例えば経路発見プロ
グラムが、主としてａからｆへの経路を発見するために
使用され、他のノード対の間の経路を発見するために使
われる事はまれであると仮定する。この時、性能を改善
するための良い戦略は、たとえ他のノード対の間の経路
を発見するための探索努力を増加させるという費用を払
っても、ａからｆへの経路を見い出す事に関係した探索
を可能な限り効率的にするようにプログラムを書く事で
ある。PROLOGが固定的な深さ優先探索戦略を使用する事
を知っていれば、プログラマは単に下記のように経路発
見プログラムを書き換える事により所望の目的を達成す
る事ができる。
索戦略の重大な欠点は、種々の入力に関して探索が行な
われる固定的な順序にプログラムが気付いていなければ
ならない事である。もしプログラマが効率に関心を有す
るならば、彼は、解決したいと思う問題例の集合に関し
てその固定的探索戦略が効率的に解を発見するような方
法でプログラムを書く責任がある。例えば経路発見プロ
グラムが、主としてａからｆへの経路を発見するために
使用され、他のノード対の間の経路を発見するために使
われる事はまれであると仮定する。この時、性能を改善
するための良い戦略は、たとえ他のノード対の間の経路
を発見するための探索努力を増加させるという費用を払
っても、ａからｆへの経路を見い出す事に関係した探索
を可能な限り効率的にするようにプログラムを書く事で
ある。PROLOGが固定的な深さ優先探索戦略を使用する事
を知っていれば、プログラマは単に下記のように経路発
見プログラムを書き換える事により所望の目的を達成す
る事ができる。
adj（a,e）． adj（a,c）． adj（a,d）． adj（a,b）． adj（b,c）． adj（b,d）． adj（c,d）． adj（e,f）． conn（x,y）←ne（x,y） ＆ adj（x,y）． conn（x,y）←ne（x,y） ＆ adj（x,z）．＆ conn（z,
y）． conn（x,y）←fail. ａからｆへの経路を発見する時に走査される探索木は第
2B図に示す通りであり、探索の努力は効率的である。こ
のように平均性能は改善する事ができる。
y）． conn（x,y）←fail. ａからｆへの経路を発見する時に走査される探索木は第
2B図に示す通りであり、探索の努力は効率的である。こ
のように平均性能は改善する事ができる。
一般に、固定的な探索戦略による効率的な実行のために
プログラムを構成する作業は２つの理由により複雑であ
る。第１に、中規模ないし大規模の探索プログラムの場
合、異なった問題例に関して走査される探索木の構造を
理解する事は、すぐに困難になる。第２に、より重要な
点として、プログラマは普通、作業量、即ちプログラム
の寿命のうちにプラグラムに与えられる異なった問題例
の相対的頻度について、あらかじめ知識を有していな
い。普通、プログラマは何が正しい問題入力であるかと
いう事しか知られない。これらの欠点は固定的探索戦略
に固有のものである。本発明は、固定的探索戦略の限界
を克服する方式に係る。
プログラムを構成する作業は２つの理由により複雑であ
る。第１に、中規模ないし大規模の探索プログラムの場
合、異なった問題例に関して走査される探索木の構造を
理解する事は、すぐに困難になる。第２に、より重要な
点として、プログラマは普通、作業量、即ちプログラム
の寿命のうちにプラグラムに与えられる異なった問題例
の相対的頻度について、あらかじめ知識を有していな
い。普通、プログラマは何が正しい問題入力であるかと
いう事しか知られない。これらの欠点は固定的探索戦略
に固有のものである。本発明は、固定的探索戦略の限界
を克服する方式に係る。
従来技術において、米国特許第4368509号は適応的な自
己最適化のための機構を議論している。この発明は変数
間の依存性を発見するアルゴリズムに基いている。その
アルゴリズムは依存性を適応的に発見するテストの系列
を発生する。
己最適化のための機構を議論している。この発明は変数
間の依存性を発見するアルゴリズムに基いている。その
アルゴリズムは依存性を適応的に発見するテストの系列
を発生する。
この技術は、それに対して観測が行なわれる１組のテス
ト入力をアルゴリズムが発生する事を可能にする。次
に、特定の数学的戦略に従って、新しい入力の組が生成
される。しかし、同じ入力の組が時間的に異なって与え
られた場合、システムは同じ方式で制御され、正確に同
一の性能を生じる。
ト入力をアルゴリズムが発生する事を可能にする。次
に、特定の数学的戦略に従って、新しい入力の組が生成
される。しかし、同じ入力の組が時間的に異なって与え
られた場合、システムは同じ方式で制御され、正確に同
一の性能を生じる。
下記の説明から明らかになるように、上記特許の発明は
非常に基本的な点で本発明とは異なっている。本発明の
重要な特性は、適応的学習及びシステムの効率の自己改
善の能力である。これは探索性能の以前の履歴を保持す
る事によって達成される。もし同一の問題入力の系列が
本発明の実施例のシステムに与えられると、問題例を解
く効率は、１つの問題例から次の問題例へ、問題を解く
のにかかわる探索努力を最小化するように変化し得る。
これは本発明の適応的学習方法によって達成される。こ
れと対照的に、上記特許の発明は本発明に特有の構成、
即ち、頻繁に出会う問題例のクラスはシステムが反復的
に使用されるので解く効率が改善されるような、系統的
な方式で効率を改善する適応的学習機能を有していな
い。
非常に基本的な点で本発明とは異なっている。本発明の
重要な特性は、適応的学習及びシステムの効率の自己改
善の能力である。これは探索性能の以前の履歴を保持す
る事によって達成される。もし同一の問題入力の系列が
本発明の実施例のシステムに与えられると、問題例を解
く効率は、１つの問題例から次の問題例へ、問題を解く
のにかかわる探索努力を最小化するように変化し得る。
これは本発明の適応的学習方法によって達成される。こ
れと対照的に、上記特許の発明は本発明に特有の構成、
即ち、頻繁に出会う問題例のクラスはシステムが反復的
に使用されるので解く効率が改善されるような、系統的
な方式で効率を改善する適応的学習機能を有していな
い。
米国特許第4472770号は前掲の特許よりも一般的である
が、上記のコメントはこの特許にも同様に当てはまる。
が、上記のコメントはこの特許にも同様に当てはまる。
米国特許第4210962号は、リアル・タイムの応用で使用
できる位に充分に速く、動的計画法の問題を解く事がで
きる事を実記している。そこでは動的計画法の問題の解
法をスピード・アップするために専用の並列コンピュー
タを使用している。動的計画法問題のパラメータは、動
的計画法プロセッサへ入力として供給される。この特許
の主目的は問題に対する最適解の高速の計算である。し
かし学習及び適応は全く行なわれていない。動的計画法
問題の例が解かれる効率は履歴、即ちその問題例が以前
にどの位頻繁に解かれたかに依存しない。従って、本発
明は、頻繁に出会った問題例を効率的に解く方向にシス
テムをバイアスする傾向を有する点で、上記特許の発明
とは基本的に異なっている。
できる位に充分に速く、動的計画法の問題を解く事がで
きる事を実記している。そこでは動的計画法の問題の解
法をスピード・アップするために専用の並列コンピュー
タを使用している。動的計画法問題のパラメータは、動
的計画法プロセッサへ入力として供給される。この特許
の主目的は問題に対する最適解の高速の計算である。し
かし学習及び適応は全く行なわれていない。動的計画法
問題の例が解かれる効率は履歴、即ちその問題例が以前
にどの位頻繁に解かれたかに依存しない。従って、本発
明は、頻繁に出会った問題例を効率的に解く方向にシス
テムをバイアスする傾向を有する点で、上記特許の発明
とは基本的に異なっている。
米国特許第4499596号は、システムに与えられる入力の
順序によってシステムが影響を受けるような方式でシス
テムを適応させる考えを開示している。この特許文献は
光学的文字認識システムにおいて効率的な文字の分類に
使用されているアルゴリズムの論理を説明している。分
類のプロセスは、走査された文字のコンパクトなコード
化ベクトル表現を生成するために使用される。これによ
り、ファクシミリの応用に関して必要な記憶域と伝送量
の低減をもたらす事ができる。しかし上記特許発明の目
的は、分類時間又は記憶要求の最適化を含んでいない。
その方式は、１度に１つづつ任意の順序のテキスト文字
を受け取る事ができるという意味において適応を行なっ
ている。最初に出会った文字の各々は自動的にクラス・
インデックスが割り当てられる。同じ文字にその後、出
会うと、出力のために文字のクラス・インデックスの検
索が行なわれる。従って上記特許文献における適応とい
う用語は、システムが初めて見た文字ストリングを分類
する能力を意味している。適応の目的は分類時間等の何
らかの目的機能の最適化ではない事に注意されたい。上
記特許文献に説明されている適応の方法は、新しい文字
に出会う毎に判定木ネットワーク表現を適応に成長させ
る事に基いている。それはヒューリスティックな性質を
持っている。このアルゴリズムにより生成される判定木
表現は、文字を分類するために使用し得る多くの可能な
判定木の１つである。しかし多くの可能な表現の中から
選択を行なうための何の形式的理論的基礎も提供されて
いない。また学習の概念も存在していない。異なった時
点で同一の文字系列を与えると、その分類アルゴリズム
は常に同一のステップを実行し、同じだけの時間及び記
憶域を実行に必要とする。問題例を解くためのアルゴリ
ズムの効率は、その問題例が以前に解かれたか否かに依
存しない。従って上記特許発明と本発明との間には基本
的な相違が存在する。
順序によってシステムが影響を受けるような方式でシス
テムを適応させる考えを開示している。この特許文献は
光学的文字認識システムにおいて効率的な文字の分類に
使用されているアルゴリズムの論理を説明している。分
類のプロセスは、走査された文字のコンパクトなコード
化ベクトル表現を生成するために使用される。これによ
り、ファクシミリの応用に関して必要な記憶域と伝送量
の低減をもたらす事ができる。しかし上記特許発明の目
的は、分類時間又は記憶要求の最適化を含んでいない。
その方式は、１度に１つづつ任意の順序のテキスト文字
を受け取る事ができるという意味において適応を行なっ
ている。最初に出会った文字の各々は自動的にクラス・
インデックスが割り当てられる。同じ文字にその後、出
会うと、出力のために文字のクラス・インデックスの検
索が行なわれる。従って上記特許文献における適応とい
う用語は、システムが初めて見た文字ストリングを分類
する能力を意味している。適応の目的は分類時間等の何
らかの目的機能の最適化ではない事に注意されたい。上
記特許文献に説明されている適応の方法は、新しい文字
に出会う毎に判定木ネットワーク表現を適応に成長させ
る事に基いている。それはヒューリスティックな性質を
持っている。このアルゴリズムにより生成される判定木
表現は、文字を分類するために使用し得る多くの可能な
判定木の１つである。しかし多くの可能な表現の中から
選択を行なうための何の形式的理論的基礎も提供されて
いない。また学習の概念も存在していない。異なった時
点で同一の文字系列を与えると、その分類アルゴリズム
は常に同一のステップを実行し、同じだけの時間及び記
憶域を実行に必要とする。問題例を解くためのアルゴリ
ズムの効率は、その問題例が以前に解かれたか否かに依
存しない。従って上記特許発明と本発明との間には基本
的な相違が存在する。
C.発明が解決しようとする問題点 従って、本発明の目的は、順次的判定をより速く実行す
るための適応的方法を提供する事である。
るための適応的方法を提供する事である。
本発明の他の目的は、順次的な判定を行なう必要のある
アプリケーションの性能を改善するための適応学習方法
を提供する事である。
アプリケーションの性能を改善するための適応学習方法
を提供する事である。
本発明の他の目的は、並列計算機を用いた順次的判定の
実行速度を増加させるために使用しうる適応的方法を提
供する事である。
実行速度を増加させるために使用しうる適応的方法を提
供する事である。
本発明の他の目的は、複数のプロセッサがアプリケーシ
ョンの実行をスピード・アップするのに効果的な方式で
学習し、適応し、協働する事を可能にする適応的方法を
提供する事である。
ョンの実行をスピード・アップするのに効果的な方式で
学習し、適応し、協働する事を可能にする適応的方法を
提供する事である。
D.問題点を解決するための手段 本発明によれば、実行をより速くする順序を得るために
実行中に行なわれた観測に基き判定の連鎖を再配列する
適応的方法が提供される。実際、一定期間にわたって平
均的性能は最適の性能へ向って収束する。このアルゴリ
ズムは１組の被選択物を試行するためのほぼ最適の順序
を維持するために使われる。プログラムが書かれた時に
は（成功及び失敗に関する）コスト及び異なった被選択
物の確率は知られていないものと仮定する。従ってプロ
グラマは事前に有する知識により最適の順序を決定する
事ができない。解くべき問題例の系列が探索プログラム
に与えられた時、プログラムは探索木の初期配列に従っ
て探索を行なう。それらの問題例を解く時、プログラム
は、異なった被選択物を試行する時に費した探索努力
（CPU時間又は命令数又は何らかの他の有力な尺度）も
モニタする。探索プログラムの実行を反復して観測する
事により収集した情報は、被選択物の最適に近い配列を
自動的に生成するために使用される。
実行中に行なわれた観測に基き判定の連鎖を再配列する
適応的方法が提供される。実際、一定期間にわたって平
均的性能は最適の性能へ向って収束する。このアルゴリ
ズムは１組の被選択物を試行するためのほぼ最適の順序
を維持するために使われる。プログラムが書かれた時に
は（成功及び失敗に関する）コスト及び異なった被選択
物の確率は知られていないものと仮定する。従ってプロ
グラマは事前に有する知識により最適の順序を決定する
事ができない。解くべき問題例の系列が探索プログラム
に与えられた時、プログラムは探索木の初期配列に従っ
て探索を行なう。それらの問題例を解く時、プログラム
は、異なった被選択物を試行する時に費した探索努力
（CPU時間又は命令数又は何らかの他の有力な尺度）も
モニタする。探索プログラムの実行を反復して観測する
事により収集した情報は、被選択物の最適に近い配列を
自動的に生成するために使用される。
この方法を有効に使用できるアプリケーションの典型は
ある種のエキスパート・システム及び故障診断システム
である。エキスパート・システムは、ルールのリストを
走査する必要がしばしばある。適用可能なルールが見つ
かると即座に、ルールが発火され、ルールのリストの走
査が反復される。各ルールには、そのルールが適用可能
か否かを判定するコスト（例えば命令の数又は実行時
間）及びルールが発火する確率が付随している。ある故
障診断及びアイソレーション・システムは、Ｎ個の可能
な結果（モジュールの置き換え又は特定のモジュールの
詳細なテスト等の動作を生じる）のうち１つを選択する
ための判定連鎖を実行する必要がある。診断システム
は、１つの手続きが肯定的な発見で終るまで、故障した
機械へ一連のテスト手続きを適用する。各々のテストは
ある長さの時間を要し、ある確率で肯定的な結果を生じ
る。
ある種のエキスパート・システム及び故障診断システム
である。エキスパート・システムは、ルールのリストを
走査する必要がしばしばある。適用可能なルールが見つ
かると即座に、ルールが発火され、ルールのリストの走
査が反復される。各ルールには、そのルールが適用可能
か否かを判定するコスト（例えば命令の数又は実行時
間）及びルールが発火する確率が付随している。ある故
障診断及びアイソレーション・システムは、Ｎ個の可能
な結果（モジュールの置き換え又は特定のモジュールの
詳細なテスト等の動作を生じる）のうち１つを選択する
ための判定連鎖を実行する必要がある。診断システム
は、１つの手続きが肯定的な発見で終るまで、故障した
機械へ一連のテスト手続きを適用する。各々のテストは
ある長さの時間を要し、ある確率で肯定的な結果を生じ
る。
本発明による適応方法は、エキスパート・システムのア
プリケーションの最適化に利用できる。この方法はエキ
スパート・システムにおいてルール・リストを走査する
ためのほぼ最適の順序を維持するために使用される。例
えばプログラムが順次的な判断連鎖を含み、それらが相
互に排他的又は独立的な結果を有し、連鎖中の各判断
に、ある固定したコスト及び確率が付随しているものと
仮定する。判断の最適の順序は、それらのコストに対す
るそれらの確率の比の値を減少するように配列する事が
ある。例えばW.E.Smith、“Various Qptimigers For Si
ngle−Stage Production"、Naval Research Logistics
Quarterly、３、（1956）、PP.59〜66及びH.A.Simon an
d J.B.Kadane、“Optimal Problem−Solving Search:Al
l−or Nore Solutions"、Artibicial intelligence、６
（３）、（1975）、PP.235〜247を参照されたい。
プリケーションの最適化に利用できる。この方法はエキ
スパート・システムにおいてルール・リストを走査する
ためのほぼ最適の順序を維持するために使用される。例
えばプログラムが順次的な判断連鎖を含み、それらが相
互に排他的又は独立的な結果を有し、連鎖中の各判断
に、ある固定したコスト及び確率が付随しているものと
仮定する。判断の最適の順序は、それらのコストに対す
るそれらの確率の比の値を減少するように配列する事が
ある。例えばW.E.Smith、“Various Qptimigers For Si
ngle−Stage Production"、Naval Research Logistics
Quarterly、３、（1956）、PP.59〜66及びH.A.Simon an
d J.B.Kadane、“Optimal Problem−Solving Search:Al
l−or Nore Solutions"、Artibicial intelligence、６
（３）、（1975）、PP.235〜247を参照されたい。
最も基本的な形において、本発明による適応方法は単一
プロセッサ・システムに適用される。また本発明は、エ
キスパート・システムにおいてルール・リストを走査す
るためにほぼ最適の順序を維持し協働する２プロセッサ
に関して説明を行なう。これらの基本的な方法は３以上
のプロセッサを有する並列コンピュータに拡張する事が
できる。
プロセッサ・システムに適用される。また本発明は、エ
キスパート・システムにおいてルール・リストを走査す
るためにほぼ最適の順序を維持し協働する２プロセッサ
に関して説明を行なう。これらの基本的な方法は３以上
のプロセッサを有する並列コンピュータに拡張する事が
できる。
E.実施例 単一のプロセッサ上にインプリメントされた本発明の第
１の実施例の説明をする前に、最初に、ある変数を定義
する必要がある。エキスパート・システムによって走査
されるリスト中のルールの総数をＮとする。各ルールの
発火の観測された頻度を、１次元配列FREQに記憶させ
る。ここでFREQ（ｉ）、ｉ＝１、…Ｎはルールｉが発火
した総数を含んでいる。最初にエキスパート・システム
が使用される時、FREQの値はゼロにセットされる。COST
を１次元配列とし、COST（ｉ）、ｉ＝１、…Ｎが、ルー
ルｉが適用可能かどうかをテストするコストの累積値が
含むものとする。またATTEMPTSを１次元配列とし、ATTE
MPTS（ｉ）、ｉ＝１、…Ｎが、ルールが発火に関してテ
ストされた回数を含むものとする。そこでルールｉに関
する平均コストはCOST（ｉ）/ATTEMPTS（ｉ）である。R
ATIOを１次元配列とし、RATIO（ｉ）、ｉ＝１、…Ｎが
下記の値を含むものとする。
１の実施例の説明をする前に、最初に、ある変数を定義
する必要がある。エキスパート・システムによって走査
されるリスト中のルールの総数をＮとする。各ルールの
発火の観測された頻度を、１次元配列FREQに記憶させ
る。ここでFREQ（ｉ）、ｉ＝１、…Ｎはルールｉが発火
した総数を含んでいる。最初にエキスパート・システム
が使用される時、FREQの値はゼロにセットされる。COST
を１次元配列とし、COST（ｉ）、ｉ＝１、…Ｎが、ルー
ルｉが適用可能かどうかをテストするコストの累積値が
含むものとする。またATTEMPTSを１次元配列とし、ATTE
MPTS（ｉ）、ｉ＝１、…Ｎが、ルールが発火に関してテ
ストされた回数を含むものとする。そこでルールｉに関
する平均コストはCOST（ｉ）/ATTEMPTS（ｉ）である。R
ATIOを１次元配列とし、RATIO（ｉ）、ｉ＝１、…Ｎが
下記の値を含むものとする。
これは各ルールに関する、テスト当りのコストに対する
発火の確率の比が評価値である。
発火の確率の比が評価値である。
ここで図面、特に第１図を参照すると、本発明の実施例
による適応方法は以下の手続きに従う。判定ブロック10
で行なわれる最初のテストは、エキスパート・システム
が初回に使用されているか否かを判定するためのもので
ある。もしそうであれば、機能ブロック12に示すよう
に、変数をカウントするために使用されるカウンタがゼ
ロに初期設定され、SCANLISTがルール・リストの初期順
序にセットされる。ルールのリストは順に維持され、ル
ールはRATIOの値が増加しないように配列される。この
リストはSCANLISTと呼ばれる。一方、もしエキスパート
・システムが初回に使用されているのでなければ、機能
ブロック12の初期設定はスキップされ、制御は直接、機
能ブロック14に行き、そこで走査サイクルが開始する。
ルールが発火のために選択されなければならない時には
常に、ルールはSCANLISTからの順序で選択される。従っ
てルールｉは、RATIO（ｉ）＞RATIO（ｊ）であれば、ル
ールｊの前にテストされる。ルール、例えばルールｋが
発火についてテストされる時、以下の動作が行なわれ
る。ATTEMPTS（ｋ）が１だけ増加され、COST（ｋ）がテ
ストのコスト分だけ増加される。ルールｋに関するテス
トが成功し、そのルールが発火する事を示す時、FREQ
（ｋ）は１だけ増加し、RATIO（ｋ）は更新される。こ
れは機能ブロック16に示されている。次に、その更新さ
れた値がSCANLISTの適合化を正当化する大幅な変化を示
しているか否かが判定ブロック18でテストされる。もし
テスト結果が肯定的であれば、RATIO値が増加しないよ
うな順序を維持するように機能ブロック20でSCANLIST中
でルールｋが再配列される。そうでなければ機能ブロッ
ク20はスキップされ、制御は判定ブロック22に渡る。こ
れはエキスパート・システムの実行が終了すべきか否か
を判定する。もしそうでなければ、プロセスは機能ブロ
ック14にループ・バックする。しかし、エキスパート・
システムの実行が終了すべきであれば、制御は機能ブロ
ック24に渡り、そこでSCANLIST、COST、FREQ、ATTEMPTS
及びRATIOの値が、将来エキスパート・システムが使用
するために保存される。
による適応方法は以下の手続きに従う。判定ブロック10
で行なわれる最初のテストは、エキスパート・システム
が初回に使用されているか否かを判定するためのもので
ある。もしそうであれば、機能ブロック12に示すよう
に、変数をカウントするために使用されるカウンタがゼ
ロに初期設定され、SCANLISTがルール・リストの初期順
序にセットされる。ルールのリストは順に維持され、ル
ールはRATIOの値が増加しないように配列される。この
リストはSCANLISTと呼ばれる。一方、もしエキスパート
・システムが初回に使用されているのでなければ、機能
ブロック12の初期設定はスキップされ、制御は直接、機
能ブロック14に行き、そこで走査サイクルが開始する。
ルールが発火のために選択されなければならない時には
常に、ルールはSCANLISTからの順序で選択される。従っ
てルールｉは、RATIO（ｉ）＞RATIO（ｊ）であれば、ル
ールｊの前にテストされる。ルール、例えばルールｋが
発火についてテストされる時、以下の動作が行なわれ
る。ATTEMPTS（ｋ）が１だけ増加され、COST（ｋ）がテ
ストのコスト分だけ増加される。ルールｋに関するテス
トが成功し、そのルールが発火する事を示す時、FREQ
（ｋ）は１だけ増加し、RATIO（ｋ）は更新される。こ
れは機能ブロック16に示されている。次に、その更新さ
れた値がSCANLISTの適合化を正当化する大幅な変化を示
しているか否かが判定ブロック18でテストされる。もし
テスト結果が肯定的であれば、RATIO値が増加しないよ
うな順序を維持するように機能ブロック20でSCANLIST中
でルールｋが再配列される。そうでなければ機能ブロッ
ク20はスキップされ、制御は判定ブロック22に渡る。こ
れはエキスパート・システムの実行が終了すべきか否か
を判定する。もしそうでなければ、プロセスは機能ブロ
ック14にループ・バックする。しかし、エキスパート・
システムの実行が終了すべきであれば、制御は機能ブロ
ック24に渡り、そこでSCANLIST、COST、FREQ、ATTEMPTS
及びRATIOの値が、将来エキスパート・システムが使用
するために保存される。
本発明に従う適応方法を用いてルールを発火させるコス
トの期待値は、典型的な場合、多数のルールが発火され
た後で最適に近いコストに収束する。第４図は７つの判
定を有する判定連鎖に適応方法を用いた結果を示す。上
の方のグラフは連鎖が故意に最悪の可能な初期配列に置
かれた時の収束を示す。下側のグラフは初期配置がラン
ダムに選ばれた場合の収束を示す。これらのデータの最
適のコストは62.6であり、両方の例は500回の判定以内
に最適に近い性能を達成した。ランダムな初期配列の場
合、事実上200回の判定の以内に収束した。これらの２
つの例に関してテストの平均コストは３〜４から１まで
改善された。観測された改善及び収束率は問題依存性を
有し、従って実際にどれが観測され得るかという事を必
ずしも反映しない。
トの期待値は、典型的な場合、多数のルールが発火され
た後で最適に近いコストに収束する。第４図は７つの判
定を有する判定連鎖に適応方法を用いた結果を示す。上
の方のグラフは連鎖が故意に最悪の可能な初期配列に置
かれた時の収束を示す。下側のグラフは初期配置がラン
ダムに選ばれた場合の収束を示す。これらのデータの最
適のコストは62.6であり、両方の例は500回の判定以内
に最適に近い性能を達成した。ランダムな初期配列の場
合、事実上200回の判定の以内に収束した。これらの２
つの例に関してテストの平均コストは３〜４から１まで
改善された。観測された改善及び収束率は問題依存性を
有し、従って実際にどれが観測され得るかという事を必
ずしも反映しない。
その方法に関してより低いオーバーヘッド・コストでほ
ぼ同じ性能の改善を達成する、基本的アイデアの種々の
変種が依存する。性能改善の大部分は最初の数百回の判
定で起きているので、ルールの再配列は異なった頻度
で、最初は殆んど毎回の判定毎に、そして最終的にはず
っとまれに行なう事ができる。再配列を行なう時、発火
に成功したルールのみの順序を変更する事も、又発火し
なかったものも含めた全てのルールを再配列する事もで
きる。テストが行なわれる毎にテストを行なうコストは
大幅に変化しない事もあるので、COST及びATTEMPTSの両
者を必ずしも維持しなくてもよい。その代りに、各ルー
ルには固定された一定の「テスト当りのコスト」が割り
当てられる。従って各ルールｉに関してCOST（ｉ）を持
てば充分であり、COST（ｉ）の初期値は、テスト中の命
令をカウントする事により又はテストの最初の実行から
決定される。この場合、RATIO（ｉ）の計算は値FREQ
（ｉ）/COST（ｉ）を計算する事に還元される。ルール
の再配列を考える上で他の単純化も可能である。ルール
が判定連鎖中の他の場所へ移動されるとその比が充分に
変化する時、そのルールを指定された位置へ移動させる
代りに、そのルールをルールが移動すべき方向の隣接ル
ールと交換すればより簡単である。この方式を用いると
収束はより緩やかになるかもしれないが、オーバーヘッ
ドがより低いため、より良い全体的性能が得られる可能
性がある。
ぼ同じ性能の改善を達成する、基本的アイデアの種々の
変種が依存する。性能改善の大部分は最初の数百回の判
定で起きているので、ルールの再配列は異なった頻度
で、最初は殆んど毎回の判定毎に、そして最終的にはず
っとまれに行なう事ができる。再配列を行なう時、発火
に成功したルールのみの順序を変更する事も、又発火し
なかったものも含めた全てのルールを再配列する事もで
きる。テストが行なわれる毎にテストを行なうコストは
大幅に変化しない事もあるので、COST及びATTEMPTSの両
者を必ずしも維持しなくてもよい。その代りに、各ルー
ルには固定された一定の「テスト当りのコスト」が割り
当てられる。従って各ルールｉに関してCOST（ｉ）を持
てば充分であり、COST（ｉ）の初期値は、テスト中の命
令をカウントする事により又はテストの最初の実行から
決定される。この場合、RATIO（ｉ）の計算は値FREQ
（ｉ）/COST（ｉ）を計算する事に還元される。ルール
の再配列を考える上で他の単純化も可能である。ルール
が判定連鎖中の他の場所へ移動されるとその比が充分に
変化する時、そのルールを指定された位置へ移動させる
代りに、そのルールをルールが移動すべき方向の隣接ル
ールと交換すればより簡単である。この方式を用いると
収束はより緩やかになるかもしれないが、オーバーヘッ
ドがより低いため、より良い全体的性能が得られる可能
性がある。
次に、Ｍ個のプロセッサにより代表されるようなマルチ
・プロセッサ・システムに本発明を応用する事を考え
る。再び、変数を定義する必要がある。Ｍ個のプロセッ
サが知識を共有して協働する頻度を含む変数をADAPT−I
NTERVALとする。この変数の値は、マルチプロセッサ・
アルゴリズムが初回に使用される時に１に初期設定され
る。発火したルールの数をカウントするための変数をCO
UNTとする。マルチプロセッサ・アルゴリズムが最初に
使われる時に、COUNTはゼロに初期設定される。
・プロセッサ・システムに本発明を応用する事を考え
る。再び、変数を定義する必要がある。Ｍ個のプロセッ
サが知識を共有して協働する頻度を含む変数をADAPT−I
NTERVALとする。この変数の値は、マルチプロセッサ・
アルゴリズムが初回に使用される時に１に初期設定され
る。発火したルールの数をカウントするための変数をCO
UNTとする。マルチプロセッサ・アルゴリズムが最初に
使われる時に、COUNTはゼロに初期設定される。
第５図の流れ図に示すように、マルチプロセッサ・シス
テムは次の手続きを実行する。単一プロセッサのインプ
リメンテーションにおけるように、プロセッサP1によ
り、行なわれなければならない最初の判定は、判定ブロ
ック26に示すように、これがエキスパート・システムが
使用される最初の時か否かの判定である。もしそうであ
れば機能ブロック28において、ルールのリストは、等し
い（又はほぼ等しい）大きさのＭ個のサブリストL1、L
2、…LMに分割される。一方、エキスパート・システム
が初めて使われるのでないならば、機能ブロック28はス
キップされ、制御は機能ブロック30に渡され、そこで走
査サイクルが開始する。プロセッサPi（ｉ＝１、２、３
…、Ｍ）はLi中のルールのリストを保持し、それらをRA
TIO値が増加しないように配列する。ルールが発火のた
めに選択される毎に、PiはルールがLi中に現れる順序で
ルールを考察する。ルールＫ及びｌが両方共にLi中にあ
るとすると、もしRATIO（Ｋ）＞RATIO（ｌ）であれば、
プロセッサPiはルールｌの前にルールｋが発火するかど
うかを考察する。ルール、例えばルールｋがPiにより発
火に関してテストされる時、下記の動作が行なわれる。
ATTEMPTS（ｋ）が１だけ増加され、COST（ｋ）がテスト
のコスト分だけ増加される。プロセッサの１つ、例えば
Pjが、発火しうるルール、例えばルールｋを見い出した
時、次の付加的な活動がPjにより取られる。即ち、COUN
Tが１だけ増加され、FREQ（ｋ）が１だけ増加され、RAT
IO（ｋ）が更新される。次にルールｋは、RATIO値が増
加しないような配列を維持するためにリストLj中で再配
列される。ルールｋが発火すると即座に、Pjは割込み機
構を通じて他の全てのプロセッサに、各リストのそれ以
上の処理を停止するように通知する。
テムは次の手続きを実行する。単一プロセッサのインプ
リメンテーションにおけるように、プロセッサP1によ
り、行なわれなければならない最初の判定は、判定ブロ
ック26に示すように、これがエキスパート・システムが
使用される最初の時か否かの判定である。もしそうであ
れば機能ブロック28において、ルールのリストは、等し
い（又はほぼ等しい）大きさのＭ個のサブリストL1、L
2、…LMに分割される。一方、エキスパート・システム
が初めて使われるのでないならば、機能ブロック28はス
キップされ、制御は機能ブロック30に渡され、そこで走
査サイクルが開始する。プロセッサPi（ｉ＝１、２、３
…、Ｍ）はLi中のルールのリストを保持し、それらをRA
TIO値が増加しないように配列する。ルールが発火のた
めに選択される毎に、PiはルールがLi中に現れる順序で
ルールを考察する。ルールＫ及びｌが両方共にLi中にあ
るとすると、もしRATIO（Ｋ）＞RATIO（ｌ）であれば、
プロセッサPiはルールｌの前にルールｋが発火するかど
うかを考察する。ルール、例えばルールｋがPiにより発
火に関してテストされる時、下記の動作が行なわれる。
ATTEMPTS（ｋ）が１だけ増加され、COST（ｋ）がテスト
のコスト分だけ増加される。プロセッサの１つ、例えば
Pjが、発火しうるルール、例えばルールｋを見い出した
時、次の付加的な活動がPjにより取られる。即ち、COUN
Tが１だけ増加され、FREQ（ｋ）が１だけ増加され、RAT
IO（ｋ）が更新される。次にルールｋは、RATIO値が増
加しないような配列を維持するためにリストLj中で再配
列される。ルールｋが発火すると即座に、Pjは割込み機
構を通じて他の全てのプロセッサに、各リストのそれ以
上の処理を停止するように通知する。
Ｍ個のプロセッサは、それらが観測から得た知識を共有
する時、下記のように協働する。ちょうどルールを発火
させたプロセッサPjにより、判定ブロック32で、適合化
のための時か否かを判定するテストが行なわれる。もし
もCOUNTがADAPT−INTERVALに等しければ、適合化プロセ
スを遂行するために制御がPjからP1へ移動する。プロセ
ッサP1はCOUNTを０にリセットし、機能ブロック34で下
記の動作を０にリセットし、機能ブロック34で下記の動
作を行なう。それは、L1、L2、…LM中に含まれるルール
を組み合せ、ルールの組み合せリストをRATIO値が増加
しない順序に配列する。このリストはMASTER−LISTと呼
ばれる。P1は次のようにL1、L2、…LMにルールを割り当
てる。ルールは、もしそれがMASTER−LISTの｛（ｋ−
１）Ｍ＋ｉ｝の位置にあれば、リストLiの位置ｋに置か
れる。もし、一方、それが適合化のための時でなけれ
ば、制御は機能ブロック36に渡され、そこでブロック30
においてルールを発火させたプロセッサPjは、各ルール
・リストの走査を開始させる信号を送り、制御は機能ブ
ロック30にループ・バックする。
する時、下記のように協働する。ちょうどルールを発火
させたプロセッサPjにより、判定ブロック32で、適合化
のための時か否かを判定するテストが行なわれる。もし
もCOUNTがADAPT−INTERVALに等しければ、適合化プロセ
スを遂行するために制御がPjからP1へ移動する。プロセ
ッサP1はCOUNTを０にリセットし、機能ブロック34で下
記の動作を０にリセットし、機能ブロック34で下記の動
作を行なう。それは、L1、L2、…LM中に含まれるルール
を組み合せ、ルールの組み合せリストをRATIO値が増加
しない順序に配列する。このリストはMASTER−LISTと呼
ばれる。P1は次のようにL1、L2、…LMにルールを割り当
てる。ルールは、もしそれがMASTER−LISTの｛（ｋ−
１）Ｍ＋ｉ｝の位置にあれば、リストLiの位置ｋに置か
れる。もし、一方、それが適合化のための時でなけれ
ば、制御は機能ブロック36に渡され、そこでブロック30
においてルールを発火させたプロセッサPjは、各ルール
・リストの走査を開始させる信号を送り、制御は機能ブ
ロック30にループ・バックする。
機能ブロック34の後で、プロセッサP1により判定ブロッ
ク38で、エキスパート・システムの実行を終了すべきか
否かを判定するテストが行なわれる。もし終了すべきで
なければ、制御は機能ブロック40に渡され、プロセッサ
P1がルール・リストの走査の再開を信号し、機能ブロッ
ク30へ制御が戻される。一方、もし実行が終了すべきで
あれば、制御は機能ブロック42へ戻され、そこでカウン
タの内容が、将来に使用するために、リストの現在の配
列と共に保存される。
ク38で、エキスパート・システムの実行を終了すべきか
否かを判定するテストが行なわれる。もし終了すべきで
なければ、制御は機能ブロック40に渡され、プロセッサ
P1がルール・リストの走査の再開を信号し、機能ブロッ
ク30へ制御が戻される。一方、もし実行が終了すべきで
あれば、制御は機能ブロック42へ戻され、そこでカウン
タの内容が、将来に使用するために、リストの現在の配
列と共に保存される。
２プロセッサのインプリメンテーションの場合、マルチ
マイクロプロセッサの手続きを用いてルールを発火させ
る期待されるコストは典型的な場合、単一プロセッサを
用いて達成可能な最適コストの半分よりも少し大きな値
に収束する。マルチプロセッサの手続きのシミュレーシ
ョン研究において観測されたスピード・アップは1.43と
1.85との間で変動した。第６図は13の判定を有する判定
連鎖に適用したマルチ・プロセッサ手続きを示す。この
グラフは初期配列がランダムに選ばれた場合の収束を示
す。この例におけるテストのコストの改善は2.3であっ
た。収束は、1000回の判定以内に33.7のコストにおいて
起きた。この例で使用したデータに関して、単一プロセ
ッサを用いたテストの最適のコストは48.2である。観測
されたスピード・アップは従って1.43である。初期配列
に対する性能の改善、収束率、及びスピード・アップ率
は、問題依存的であり、従って実際にどれが観測される
かを必ずしも反映しない。
マイクロプロセッサの手続きを用いてルールを発火させ
る期待されるコストは典型的な場合、単一プロセッサを
用いて達成可能な最適コストの半分よりも少し大きな値
に収束する。マルチプロセッサの手続きのシミュレーシ
ョン研究において観測されたスピード・アップは1.43と
1.85との間で変動した。第６図は13の判定を有する判定
連鎖に適用したマルチ・プロセッサ手続きを示す。この
グラフは初期配列がランダムに選ばれた場合の収束を示
す。この例におけるテストのコストの改善は2.3であっ
た。収束は、1000回の判定以内に33.7のコストにおいて
起きた。この例で使用したデータに関して、単一プロセ
ッサを用いたテストの最適のコストは48.2である。観測
されたスピード・アップは従って1.43である。初期配列
に対する性能の改善、収束率、及びスピード・アップ率
は、問題依存的であり、従って実際にどれが観測される
かを必ずしも反映しない。
より低いオーバーヘッド・コストで同じ程度の性能の改
善を達成しうる、基本的なマルチプロセッサ機構の種々
のバリエーションがある。性能の改善の大部分は最初の
数百の判定において生じるので、マルチプロセッサは最
初は非常に頻繁に協働するが、最終的には非常にまれに
協働するようになる。これは最初にADAPT−INTERVALを
１にセットし次にADAPT−INTERVALをより大きな値にリ
セットするマルチプロセッサ・アルゴリズムを実行する
事により達成し得る。さらに、ルール・リストが並行に
走査される各時にＭ個のプロセッサにより排他的に考察
されるＭ個のサブリストに判定連鎖を分割する代りに、
連鎖中の全ての判定より成る共通のリストを、RATIO値
が増加しない順序に維持する事が可能である。ルールは
共通リスト中の順序に従ってテストする事ができる。プ
ロセッサが利用可能になる毎に、それは現在の走査サイ
クル中にまだテストされていない、リスト中の次のルー
ルを選択し得る。１つのプロセッサによりルールが発火
するものと判定されると即座に、それは現在の走査サイ
クルを停止し、また他のプロセッサにそれ以上の処理を
停止するように割込みをかける事ができる。この方法は
基本的なマルチプロセッサ方式と同程度の収束性と全体
的性能を有し得る。
善を達成しうる、基本的なマルチプロセッサ機構の種々
のバリエーションがある。性能の改善の大部分は最初の
数百の判定において生じるので、マルチプロセッサは最
初は非常に頻繁に協働するが、最終的には非常にまれに
協働するようになる。これは最初にADAPT−INTERVALを
１にセットし次にADAPT−INTERVALをより大きな値にリ
セットするマルチプロセッサ・アルゴリズムを実行する
事により達成し得る。さらに、ルール・リストが並行に
走査される各時にＭ個のプロセッサにより排他的に考察
されるＭ個のサブリストに判定連鎖を分割する代りに、
連鎖中の全ての判定より成る共通のリストを、RATIO値
が増加しない順序に維持する事が可能である。ルールは
共通リスト中の順序に従ってテストする事ができる。プ
ロセッサが利用可能になる毎に、それは現在の走査サイ
クル中にまだテストされていない、リスト中の次のルー
ルを選択し得る。１つのプロセッサによりルールが発火
するものと判定されると即座に、それは現在の走査サイ
クルを停止し、また他のプロセッサにそれ以上の処理を
停止するように割込みをかける事ができる。この方法は
基本的なマルチプロセッサ方式と同程度の収束性と全体
的性能を有し得る。
F.発明の効果 本発明を用いれば、以前の探索の結果に基き、最適に近
い配列が維持されるので、探索の性能を向上させる事が
できる。
い配列が維持されるので、探索の性能を向上させる事が
できる。
第１図は、単一プロセッサにおいて実施した時の適応方
法の説明図、 第2A図及び第2B図は探索木の１例のグラフ表現の図、 第３図は有向グラフの図、 第４図は単一プロセッサの場合の改善効果を示すグラ
フ、 第5A図及び第5B図はマルチプロセッサにおいて実施した
時の適応方法の説明図、 第６図はマルチプロセッサの場合の改善効果を示すグラ
フである。
法の説明図、 第2A図及び第2B図は探索木の１例のグラフ表現の図、 第３図は有向グラフの図、 第４図は単一プロセッサの場合の改善効果を示すグラ
フ、 第5A図及び第5B図はマルチプロセッサにおいて実施した
時の適応方法の説明図、 第６図はマルチプロセッサの場合の改善効果を示すグラ
フである。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 Ｆｒｅｄｅｒｉｃｋ Ｈｏｙｅｓ−Ｒｏ ｔｈ，Ｄｏｎａｌｄ Ａ．Ｗａｔｅｒｍａ ｎ，Ｄｏｕｇｌａｓ Ｂ．Ｌｅｎａｔ編 Ｂｉｌｄｉｎｇ Ｅｘｐｅｒｔ Ｓｙｓｔ ｅｍｓ（昭60−６−27）産業図書 第268 頁
Claims (2)
- 【請求項１】走査されるべきリスト内にＮ個のルールを
有する、人工知能システムにおける順次的判定プロセス
の最適化方法であって、 配列FREQ（ｉ）（ｉ＝1,・・・・Ｎ）の値を、前記シス
テムが使用される初回にゼロにセットするステップと、 各ルールの発火の頻度を記憶するために、各ルールが発
火した回数を観測し、その回数を各々前記配列FREQ
（ｉ）に格納するステップと、 与えられたルールが適用可能かどうかをテストする累積
コストを含む配列COST（ｉ）（ｉ＝1,・・・・Ｎ）を生
成するステップと、 ルールが発火のためにテストされた回数を含む配列ATTE
MPTS（ｉ）（ｉ＝1,・・・・Ｎ）を生成するステップ
と、 各ルールに関する、テスト当りのコストに対する発火の
確率の比の評価値であるRATIO（ｉ）＝FREQ（ｉ）＊ATT
EMPTS（ｉ）/COST（ｉ）（ｉ＝1,・・・・Ｎ）を生成す
るステップと、 RATIOの値が増加しないように配列されたルールのSCANL
ISTを保持するステップと、 RATIO（ｉ）＞RATIO（ｊ）であればルールｉがルールｊ
の前にテストされるように、前記SCANLISTの順番で発火
のためにルールを選択するステップと、 ルールｉが発火のためにテストされる時、ATTEMPTS
（ｉ）を１増加させ、テストのコスト分COST（ｉ）を増
加させるステップと、 ルールｉに関するテストが成功し、そのルールが発火す
ることを示す時、FREQ（ｉ）を１増加させ、RATIO
（ｉ）を更新するステップと を含む順次的判定プロセスの最適化方法。 - 【請求項２】RATIOの値が増加しないような配列を維持
すべく前記SCANLISTを再配列するステップをさらに含む
特許請求の範囲（１）記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/885,101 US4752890A (en) | 1986-07-14 | 1986-07-14 | Adaptive mechanisms for execution of sequential decisions |
| US885101 | 1992-05-18 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6320657A JPS6320657A (ja) | 1988-01-28 |
| JPH0746345B2 true JPH0746345B2 (ja) | 1995-05-17 |
Family
ID=25386135
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62127284A Expired - Fee Related JPH0746345B2 (ja) | 1986-07-14 | 1987-05-26 | 順次的判定プロセスの最適化方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4752890A (ja) |
| EP (1) | EP0254825B1 (ja) |
| JP (1) | JPH0746345B2 (ja) |
| DE (1) | DE3788830T2 (ja) |
Families Citing this family (42)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4868743A (en) * | 1986-11-25 | 1989-09-19 | Hitachi, Ltd. | Traversal method of processing tree structure information and apparatus using the same |
| JPS647232A (en) * | 1987-06-30 | 1989-01-11 | Toshiba Corp | Inference processor |
| US5218669A (en) * | 1988-03-11 | 1993-06-08 | International Chip Corporation | VLSI hardware implemented rule-based expert system apparatus and method |
| JPH0727543B2 (ja) * | 1988-04-28 | 1995-03-29 | インターナシヨナル・ビジネス・マシーンズ・コーポレーション | 文字認識装置 |
| US4935877A (en) * | 1988-05-20 | 1990-06-19 | Koza John R | Non-linear genetic algorithms for solving problems |
| US5228116A (en) * | 1988-07-15 | 1993-07-13 | Aicorp., Inc. | Knowledge base management system |
| US4882699A (en) * | 1988-09-19 | 1989-11-21 | International Business Machines Corp. | Communications network routing and management system |
| US4979124A (en) * | 1988-10-05 | 1990-12-18 | Cornell Research Foundation | Adaptive, neural-based signal processor |
| JPH07100262B2 (ja) * | 1988-10-07 | 1995-11-01 | 三菱電機株式会社 | 放電加工終了判定方法及びその装置 |
| US5099436A (en) * | 1988-11-03 | 1992-03-24 | Allied-Signal Inc. | Methods and apparatus for performing system fault diagnosis |
| US5067099A (en) * | 1988-11-03 | 1991-11-19 | Allied-Signal Inc. | Methods and apparatus for monitoring system performance |
| US4972328A (en) * | 1988-12-16 | 1990-11-20 | Bull Hn Information Systems Inc. | Interactive knowledge base end user interface driven maintenance and acquisition system |
| US5829002A (en) * | 1989-02-15 | 1998-10-27 | Priest; W. Curtiss | System for coordinating information transfer and retrieval |
| US4975865A (en) * | 1989-05-31 | 1990-12-04 | Mitech Corporation | Method and apparatus for real-time control |
| US5241652A (en) * | 1989-06-08 | 1993-08-31 | Digital Equipment Corporation | System for performing rule partitioning in a rete network |
| US5155803A (en) * | 1989-06-08 | 1992-10-13 | Digital Equipment Corporation | Expert system for performing beta-token partitioning in a rete network |
| US5129037A (en) * | 1989-06-20 | 1992-07-07 | Digital Equipment Corporation | Neural network for performing beta-token partitioning in a RETE network |
| US5129043A (en) * | 1989-08-14 | 1992-07-07 | International Business Machines Corporation | Performance improvement tool for rule based expert systems |
| US5159685A (en) * | 1989-12-06 | 1992-10-27 | Racal Data Communications Inc. | Expert system for communications network |
| EP0453160A3 (en) * | 1990-04-20 | 1993-09-15 | Digital Equipment Corporation | A method and apparatus for analyzing the flow of data through a complex information exchange system |
| US5222197A (en) * | 1990-06-28 | 1993-06-22 | Digital Equipment Corporation | Rule invocation mechanism for inductive learning engine |
| EP0494788B1 (en) * | 1991-01-11 | 1996-10-02 | Canon Kabushiki Kaisha | Fault diagnosis using simulation |
| US5313527A (en) * | 1991-06-07 | 1994-05-17 | Paragraph International | Method and apparatus for recognizing cursive writing from sequential input information |
| US6418424B1 (en) | 1991-12-23 | 2002-07-09 | Steven M. Hoffberg | Ergonomic man-machine interface incorporating adaptive pattern recognition based control system |
| US8352400B2 (en) | 1991-12-23 | 2013-01-08 | Hoffberg Steven M | Adaptive pattern recognition based controller apparatus and method and human-factored interface therefore |
| US10361802B1 (en) | 1999-02-01 | 2019-07-23 | Blanding Hovenweep, Llc | Adaptive pattern recognition based control system and method |
| US5903454A (en) | 1991-12-23 | 1999-05-11 | Hoffberg; Linda Irene | Human-factored interface corporating adaptive pattern recognition based controller apparatus |
| US6400996B1 (en) | 1999-02-01 | 2002-06-04 | Steven M. Hoffberg | Adaptive pattern recognition based control system and method |
| US7242988B1 (en) | 1991-12-23 | 2007-07-10 | Linda Irene Hoffberg | Adaptive pattern recognition based controller apparatus and method and human-factored interface therefore |
| US6850252B1 (en) | 1999-10-05 | 2005-02-01 | Steven M. Hoffberg | Intelligent electronic appliance system and method |
| CA2124479A1 (en) * | 1993-06-30 | 1994-12-31 | Thaddeus Julius Kowalski | Methods and apparatus for optimizing decision making |
| US5867397A (en) * | 1996-02-20 | 1999-02-02 | John R. Koza | Method and apparatus for automated design of complex structures using genetic programming |
| US6112126A (en) * | 1997-02-21 | 2000-08-29 | Baker Hughes Incorporated | Adaptive object-oriented optimization software system |
| DE69811790T2 (de) | 1997-08-01 | 2003-11-20 | International Business Machines Corp., Armonk | Ableitung von Prozessmodellen aus Rechnungsprüfvorgängen für Systeme zur Verwaltung von Arbeitsflüssen |
| EP0895169B1 (en) * | 1997-08-01 | 2003-03-05 | International Business Machines Corporation | Deriving process models for workflow management systems from audit trails |
| US6157922A (en) * | 1997-10-24 | 2000-12-05 | Trilogy Development Group, Inc. | Method and apparatus for transparent backtracking |
| US6233493B1 (en) * | 1998-09-16 | 2001-05-15 | I2 Technologies, Inc. | Computer-implemented product development planning method |
| US8364136B2 (en) | 1999-02-01 | 2013-01-29 | Steven M Hoffberg | Mobile system, a method of operating mobile system and a non-transitory computer readable medium for a programmable control of a mobile system |
| US7966078B2 (en) | 1999-02-01 | 2011-06-21 | Steven Hoffberg | Network media appliance system and method |
| US6829604B1 (en) * | 1999-10-19 | 2004-12-07 | Eclipsys Corporation | Rules analyzer system and method for evaluating and ranking exact and probabilistic search rules in an enterprise database |
| US20040148178A1 (en) * | 2003-01-24 | 2004-07-29 | Brain Marshall D. | Service management system |
| CN113468047B (zh) * | 2021-06-17 | 2022-05-17 | 天津大学 | 基于启发式规则的并发式自适应随机测试方法 |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3588823A (en) * | 1968-03-28 | 1971-06-28 | Ibm | Mutual information derived tree structure in an adaptive pattern recognition system |
| US3824387A (en) * | 1972-01-03 | 1974-07-16 | Owens Corning Fiberglass Corp | Method and apparatus for control of conditions in a process |
| US3950733A (en) * | 1974-06-06 | 1976-04-13 | Nestor Associates | Information processing system |
| US4499596A (en) * | 1982-06-28 | 1985-02-12 | International Business Machines Corporation | Adaptive facsimile compression using a dynamic extendable decision network |
| US4551850A (en) * | 1983-02-07 | 1985-11-05 | Pattern Processing Technologies, Inc. | Response detector for pattern processing system |
| US4606069A (en) * | 1983-06-10 | 1986-08-12 | At&T Bell Laboratories | Apparatus and method for compression of facsimile information by pattern matching |
| US4599692A (en) * | 1984-01-16 | 1986-07-08 | Itt Corporation | Probabilistic learning element employing context drive searching |
| US4658370A (en) * | 1984-06-07 | 1987-04-14 | Teknowledge, Inc. | Knowledge engineering tool |
| US4635182A (en) * | 1984-07-03 | 1987-01-06 | The United States Of America As Represented By The Secretary Of The Navy | Apparatus for controlling multiple time-varying processes |
| US4642782A (en) * | 1984-07-31 | 1987-02-10 | Westinghouse Electric Corp. | Rule based diagnostic system with dynamic alteration capability |
-
1986
- 1986-07-14 US US06/885,101 patent/US4752890A/en not_active Expired - Lifetime
-
1987
- 1987-05-08 DE DE3788830T patent/DE3788830T2/de not_active Expired - Fee Related
- 1987-05-08 EP EP87106697A patent/EP0254825B1/en not_active Expired - Lifetime
- 1987-05-26 JP JP62127284A patent/JPH0746345B2/ja not_active Expired - Fee Related
Non-Patent Citations (1)
| Title |
|---|
| ＦｒｅｄｅｒｉｃｋＨｏｙｅｓ−Ｒｏｔｈ，ＤｏｎａｌｄＡ．Ｗａｔｅｒｍａｎ，ＤｏｕｇｌａｓＢ．Ｌｅｎａｔ編ＢｉｌｄｉｎｇＥｘｐｅｒｔＳｙｓｔｅｍｓ（昭６０−６−２７）産業図書第２６８頁 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0254825B1 (en) | 1994-01-19 |
| DE3788830D1 (de) | 1994-03-03 |
| JPS6320657A (ja) | 1988-01-28 |
| EP0254825A2 (en) | 1988-02-03 |
| EP0254825A3 (en) | 1991-03-27 |
| DE3788830T2 (de) | 1994-06-23 |
| US4752890A (en) | 1988-06-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0746345B2 (ja) | 順次的判定プロセスの最適化方法 | |
| Bischl et al. | Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges | |
| US4924408A (en) | Technique for compilation of knowledge bases | |
| EP0314650B1 (en) | Method for optimized rete pattern matching in pattern-directed, rule-based artificial intelligence production systems | |
| US4881178A (en) | Method of controlling a classifier system | |
| Schmidhuber | Discovering solutions with low Kolmogorov complexity and high generalization capability | |
| US4951225A (en) | Updating pattern-matching networks | |
| Lee et al. | From exact to anytime solutions for marginal MAP | |
| Zhang et al. | Compiler-level matrix multiplication optimization for deep learning | |
| US5263127A (en) | Method for fast rule execution of expert systems | |
| US4956791A (en) | Merging pattern-matching networks including retes | |
| De Campos et al. | An iterated local search algorithm for learning Bayesian networks with restarts based on conditional independence tests | |
| JP7127687B2 (ja) | 仮説推論装置、仮説推論方法、及びプログラム | |
| Cervone et al. | The development of the AQ20 learning system and initial experiments | |
| EP0358618A2 (en) | Caching argument values in pattern-matching networks | |
| Feser et al. | Differentiable functional program interpreters | |
| KR20220074430A (ko) | 뉴로 심볼릭 기반 릴레이션 임베딩을 통한 지식완성 방법 및 장치 | |
| Rubin et al. | Naval intelligent authentication and support through randomization and transformative search | |
| US5390286A (en) | Reticular discrimination network for specifying real-time conditions | |
| JP7322966B2 (ja) | 情報処理装置、情報処理方法及びプログラム | |
| Gasarch et al. | Learning via queries with teams and anomalies | |
| Silva et al. | Parallel asynchronous strategies for the execution of feature selection algorithms | |
| Acid et al. | The search of causal orderings: a short cut for learning belief networks | |
| Zhao et al. | Achieving Olympia-Level Geometry Large Language Model Agent via Complexity Boosting Reinforcement Learning | |
| Bu et al. | Physical synthesis of quantum circuits using Q-learning |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |