EP0254825A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Adaptive mechanisms for execution of sequential decisions
Assignee: International Business Machines Corp
•
Filing: 1987-05-08
•
Granted: —
•
Expires: 2007-05-08
Abstract
Abstract An adaptive mechanism is presented in the context of optimization of expert system applications. Both single and multiple processor implementations are disclosed, The mechanism is used to maintain a near-optimal sequence for scanning rule lists in expert systems. For a program containing a sequential-decision chain with many independent or mutually exclusive outcomes with each decision having associated with it some fixed cost and probability, the adaptive mechanism tends to produce the optimal ordering automatically from repeated observations of the execution of the decision chain.
Inventors
- 👤 Kadathur Subramanya Natarajan
- 👤 Harold Stuart Stone
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 18:32
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/04; G06N5/01; Y; Y10; Y10S; Y10S706/00; Y10S706/902; Y10S706/903; Y10S706/908; Y10S706/919; Y10S706/922
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
207 words
An adaptive mechanism for the optimization of sequential decision making in an artificial intelligence system having N rules in a list to be scanned comprising the steps of: storing the observed frequencies of firing of different rules in a one-dimensional array FREQ, with FPEQ(i), i=1,...,N, containing the number of times each rule has fired; setting the FREQ values to zero the first time said system is used; generating a one-dimensional array COST(i), i=l,...,N, containing the accumulated cost of testing if a given rule is applicable; generating a one-dimensional array ATTMEPTS (i), i=l,...,N, containing the number of times a rule has been tested for firing; generating a one-dimensional array RATIO(i), i=l,...,N, containing the value FREQ (i) ATTEMPTS (i) COST(i) which is the estimate of the ratio of probability of firing to cost per test for each rule; maintaining a SCANLIST of rules in a sequence ordered by nonincreasing RATIO values; selecting a rule for firing in order from SCANLIST so that Rule i is tested before Rule j if RATIO(I) >RATIO(j); incrementing ATTEMPTS(i) and increasing COST(i) by the cost of testing when RULE(i) is tested for firing; and increasing FREQ(i) by one when a test for RULE(i) is successful indicating that a rule will fire and updating RATIO(i).
Claim 2
Dependent Claim
207 words
An adaptive mechanism for the optimization of sequential decision making in an artificial intelligence system having N rules in a list to be scanned comprising the steps of: storing the observed frequencies of firing of different rules in a one-dimensional array FREQ, with FPEQ(i), i=1,...,N, containing the number of times each rule has fired; setting the FREQ values to zero the first time said system is used; generating a one-dimensional array COST(i), i=l,...,N, containing the accumulated cost of testing if a given rule is applicable; generating a one-dimensional array ATTMEPTS (i), i=l,...,N, containing the number of times a rule has been tested for firing; generating a one-dimensional array RATIO(i), i=l,...,N, containing the value FREQ (i) ATTEMPTS (i) COST(i) which is the estimate of the ratio of probability of firing to cost per test for each rule; maintaining a SCANLIST of rules in a sequence ordered by nonincreasing RATIO values; selecting a rule for firing in order from SCANLIST so that Rule i is tested before Rule j if RATIO(I) >RATIO(j); incrementing ATTEMPTS(i) and increasing COST(i) by the cost of testing when RULE(i) is tested for firing; and increasing FREQ(i) by one when a test for RULE(i) is successful indicating that a rule will fire and updating RATIO(i).
Claim 3
Dependent Claim
25 words
The adaptive mechanism as recited in claim 1 further including the step of reordering SCANLIST to maintain the ordering to be in nonincreasing RATIO values.
Claim 4
Dependent Claim
26 words
The adaptive mechanism as recited in claim 2 further including the step of saving SCANLIST, FREQ, COST, ATTEMPTS and RATIO for future use by the system.
Claim 5
Dependent Claim
87 words
In an artificial intelligence system, a method of optimization of sequential decision making process comprising the steps of: monitoring quantifiable performance parameters including probability or equivalent relative frequency of occurrence of different outcomes of a search; developing a prior history of the monitored quantifiable performance parameters including the cost of the search, where cost is any dominant performance measure of the system; and automatically adapting and converging to an optimum average cost of search based on the prior history developed of the monitored quantifiable performance performance parameters.
Claim 6
Dependent Claim
87 words
In an artificial intelligence system, a method of optimization of sequential decision making process comprising the steps of: monitoring quantifiable performance parameters including probability or equivalent relative frequency of occurrence of different outcomes of a search; developing a prior history of the monitored quantifiable performance parameters including the cost of the search, where cost is any dominant performance measure of the system; and automatically adapting and converging to an optimum average cost of search based on the prior history developed of the monitored quantifiable performance performance parameters.
Claim 7
Dependent Claim
65 words
The method of optimization recited in claim 4 wherein the step of automatically adapting and converging to an optimum average cost of search comprises the steps of: computing ratios of probability or equivalent relative frequency of occurrence to cost for search rules in said sequential decision making process; and ordering a search list of rules in a nonincreasing order of ratios computed for the rules.
Claim 8
Independent Claim
114 words
The method of reducing the overhead of an adaptive algorithm of a sequential decision making process for an artificial intelligence system wherein quantifiable performance parameters are monitored and measured the sequential decision making process is automatically adapted and converged to an optimum average search cost comprising the steps of: varying the frequency of the adaptation process to be relatively more frequent initially and less frequent or not at all after the search process reaches near optimal or optimal behavior; and controlling the measurement of the quantifiable performance parameters to be very accurate initially during the adaptation process and less accurate or not at all as the adaptation operations are done less frequently or discontinued.
Claim 9
Independent Claim
114 words
The method of reducing the overhead of an adaptive algorithm of a sequential decision making process for an artificial intelligence system wherein quantifiable performance parameters are monitored and measured the sequential decision making process is automatically adapted and converged to an optimum average search cost comprising the steps of: varying the frequency of the adaptation process to be relatively more frequent initially and less frequent or not at all after the search process reaches near optimal or optimal behavior; and controlling the measurement of the quantifiable performance parameters to be very accurate initially during the adaptation process and less accurate or not at all as the adaptation operations are done less frequently or discontinued.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.