Method for classifying test subjects in knowledge and functionality states

• US 5,855,011 A
• Filed: 09/13/1996
• Issued: 12/29/1998
• Est. Priority Date: 09/13/1996
• Status: Expired due to Term

• Current Assignee: Curtis M. Tatsuoka
• Original Assignee: Curtis M. Tatsuoka
• Inventors: Tatsuoka, Curtis M.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/712,110
• Time in Patent Office: 837 Days
• Field of Search: 382/224, 382/228, 395/75, 395/76, 395/77, 395/51, 395/61, 395/927, 434/118
• US Class Current: 706/45
• CPC Class Codes: G01R 31/318371 Methodologies therefor, e.g. algorithms, procedures
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0203 Market surveys; Market polls

Abstract

A method for classifying a test subject in one of a plurality of states in a domain, a domain being a set of facts, a quality measure, or a combination of the two. The set of facts for a knowledge domain is any set of facts while the set of facts for a functionality domain is a set of facts relating to the functionality of a test subject. A state is characterized by a subset of facts, a value for a quality measure, or a combination of a subset of facts and a value for a quality measure. A first state is higher than or equal to a second state and a second state is lower than or equal to a first state if (1) the subset of facts or the quality measure value associated with the first state respectively includes the subset of facts or is greater than or equal to the quality measure value associated with the second state or (2) the subset of facts and the quality measure value associated with the first state respectively includes the subset of facts and is greater than or equal to the quality measure value associated with the second state. Decision-theoretic rules are specified for selecting the test items to be administered to a test subject, for determining when it is appropriate to stop administering test items, and for determining the classification of the test subject. A test subject is classified in the highest state of which he has the knowledge or functionality.

Claims

1. A method for classifying a test subject in one of a plurality of states in a domain, a domain being a set of facts, a quality measure having a range of values, or a combination of a set of facts and a quality measure, the set of facts for a knowledge domain being any set of facts, the set of facts for a functionality domain being a set of facts relating to the functionality of a test subject, a state being characterized by a subset of facts, a value in the range of values for a quality measure, or a combination of a subset of facts and a value for a quality measure, a first state being higher than or equal to a second state and a second state being lower than or equal to a first state if (1) the subset of facts or the quality measure value associated with the first state respectively includes the subset of facts or is greater than or equal to the quality measure value associated with the second state or (2) the subset of facts and the quality measure value associated with the first state respectively includes the subset of facts and is greater than or equal to the quality measure value associated with the second state, a test subject being classified in the highest state of which he has the knowledge or functionality, the method comprising the steps:

specifying a domain comprising a plurality of states and determining the higher-lower-neither relationships for each state, the higher-lower-neither relationships for a state being a specification of which states are higher, which states are lower, and which states are neither higher or lower, the plurality of states including a first, second, and third fact state characterized by subsets of facts wherein (1) the first and second fact states are higher than the third fact state and the first fact state is neither higher nor lower than the second fact state or (2) the first fact state is higher than the second and third fact states and the second fact state is neither higher nor lower than the third fact state;

specifying a test item pool comprising a plurality of test items, a test item engendering a response when administered to a test subject;

specifying an initial state probability set (SPS) for the test subject to be classified, each member of the initial SPS being an initial estimate of the probability density value that the test subject is associated with a particular state in the domain;

specifying a class conditional density f_i (x|s) for each test item i in the test item pool for each state s in the domain, a class conditional density being a specification of the probability of a test subject in state s providing a response x to the test item i, each item partitioning the domain of states into a plurality of partitions according to the class conditional densities associated with the item, a partition being a subset of states for which the class conditional densities are the same or the union of such subsets;

determining the classification of the test subject.

2. The method of claim 1 wherein the step of determining the classification of the test subject includes the steps:

administering one of a sequence of test items from the test item pool to the test subject;

updating the SPS after receiving a response to the administered test item.

3. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item which results in a partition for which the probability of a test subject being in the partition is nearest to 0.5.

4. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted uncertainty measure, the uncertainty measure being a measure of the uncertainty as to which of the test item'"'"'s partitions that the test subject is in, the uncertainty measure being smallest when all but one of the partition probabilities are near 0, a partition probability being the probability of the test subject being in the partition.

5. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted SPS uncertainty measure given the hypothetical administration of i.sub.(n+1), an SPS uncertainty measure being a minimum when all but one of the SPS probability density values are near 0.

6. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted SPS uncertainty measure given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, an SPS uncertainty measure being a minimum when all but one of the SPS probability density values are near 0.

7. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted distance measure between the SPS after a hypothetical administration of an (n+1)'"'"'th test item and the SPS after the actual administration of the n'"'"'th test item, the distance measure being a measure of the differences in the two SPSs.

8. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted distance measure between the SPS after a hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, and the SPS after the actual administration of the n'"'"'th test item, the distance measure being a measure of the differences in the two SPSs.

9. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item corresponding to the largest value of a weighted discrepancy measure summed over all pairs of states, a discrepancy measure for a test item given two states being a measure of the distance between the class conditional densities for the item and the two states.

10. The method of claim 9 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being selected using a two-valued function Φ

, the function Φ

being a function of (1) a test item and (2) a first state and a second state, Φ

having a first value if the test item separates the first and second states, Φ

having a second value if the test item does not separate the first and second states.

11. The method of claim 10 wherein Φ

has a first value for a plurality of the test items for a specified first state and a specified second state, the test item i.sub.(n+1) being selected randomly from the plurality of test items.

12. The method of claim 2 wherein test item i'"'"'.sub.(n+1) is tentatively selected as the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items, test item i'"'"'.sub.(n+1) being selected using a predetermined selection rule from test items in the test item pool that have not already been administered, a random decision being made either to use test item i'"'"'.sub.(n+1) as the (n+1)'"'"'th administered test item i.sub.(n+1) or to select another test item from the test item pool.

13. The method of claim 12 wherein the test items are ordered according to a goodness criterion associated with the predetermined selection rule, the test item i'"'"'.sub.(n+1) being the best test item, a plurality of the next-in-order test items being denoted as the better test items, one of the better test items being selected as the (n+1)'"'"'th administered test item i.sub.(n+1) if the decision is made to select a test item other than test item i'"'"'.sub.(n+1).

14. The method of claim 13 wherein the selection of one of the better test items is randomly made, the random selection being biased in accordance with the order of the better test items.

15. The method of claim 13 wherein the decision to select a test item other than test item i'"'"'.sub.(n+1) is made with a probability that is a function of a "temperature" parameter, the probability being a monotonic function of "temperature".

16. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i(r) being the test item that would be selected using selection rule r, the index r denoting any one of a plurality of selection rules, the test item i.sub.(n+1) being the test item i(r) that results in a condition selected from the group of conditions (1) smallest value for a weighted loss function, (2) smallest value for a weighted uncertainty measure, and (3) largest value for a weighted distance measure.

17. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i(r) being the test item that would be selected using selection rule r, the index r denoting any one of a plurality of selection rules, the test item i.sub.(n+1) being a random selection from the test items i(r).

18. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item that maximizes a weighted relative ranking measure based on a plurality of item selection rules, a weighted relative ranking measure being a weighted function of the relative rankings of attractiveness for each test item with respect to a plurality of item selection rules.

19. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item corresponding to the largest value of the sum of π

_n (j)π

_n (k)d_jk (i) over all states j and k in the domain, π

_n (j) denoting the members of the updated SPS after the test subject has responded to the n'"'"'th administered test item, d_jk (i) denoting a measure of the degree of discrimination between states j and k provided by test item i as measured by a discrepancy measure on the corresponding class conditional densities.

20. The method of claim 19 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being the absolute value of the difference in a first class conditional density and a second class conditional density, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k.

21. The method of claim 20 wherein the first function equals zero when the first and second class conditional densities are the same, the first function being equal to a positive constant when the first and second class conditional densities are different.

22. The method of claim 19 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being a third function of a difference function, the difference function being the difference between a fourth function of the first class conditional density and the fourth function of the second class conditional density, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k, the variety of functions denoted by the term "function" including the identity function wherein the function of a quantity is equal to the quantity.

23. The method of claim 19 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being a function of the ratio of a third function of a first class conditional density and the third function of a second class conditional density weighted by the first class conditional density when the first and second class conditional densities are different, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k, d_jk (i) being equal to zero when the first and second class conditional densities are the same, the variety of functions denoted by the term "function" including the identity function wherein the function of a quantity is equal to the quantity.

24. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted loss function for k=1, a loss function being a function of (1) the state in the domain, (2) a classification decision action that specifies a state, and (3) the number k of test items to be administered beginning with i.sub.(n+1).

25. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted loss function given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, a loss function being a function of (1) the state in the domain, (2) a classification decision action that specifies a state, and (3) the number k of test items to be administered beginning with i.sub.(n+1).

26. The method of claim 2 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of administering a sequence of test items is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item for which a weighted loss in administering the next k test items is the smallest, the loss in administering k test items being defined by a loss function consisting of two additive components, the first component being a measure of the loss associated with the classification of the test subject after administering the k test items, the loss associated with an incorrect classification being higher than the loss associated with a correct classification, the second component being the cost of administering the k test items.

27. The method of claim 26 wherein the first component of the loss function is (1) a constant A₁ (s) if the test subject would be classified correctly after administering k additional test items and (2) a constant A₂ (s) if the test subject would be classified incorrectly after administering k additional test items, the constants A₁ (s) and A₂ (s) having a possible dependence on the state s, the second component of the loss function being the sum of the individual costs of administering the k additional test items.

28. The method of claim 2 wherein the respective responses to test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) are x.sub.(n+1), x.sub.(n+2), . . . , x.sub.(n+k), k being an integer, and the SPS updating rule is a function of the class conditional densities evaluated at x.sub.(n+1), x.sub.(n+2), . . . , x.sub.(n+k) and a given SPS with the SPS probability density value for a state being nondecreasing in the class conditional density value for fixed SPS and fixed class conditional density values for all other states.

29. The method of claim 2 wherein the step of determining the classification of the test subject includes the steps:

applying a stopping rule, the steps of claim 2 being repeated if the stopping rule does not require that the administering of test items be terminated;

classifying the test subject as to a state in the domain in accordance with a decision rule if the stopping rule requires that the administering of test items be terminated.

30. The method of claim 29 wherein the domain is a combination model and the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if the marginal posterior value for a state in the discrete component of the domain is greater than a first predetermined value and the posterior variance of the continuous parameter in the domain is less than a second predetermined value.

31. The method of claim 29 wherein the stopping rule is to stop administering test items if a weighted uncertainty measure with respect to the SPS after administration of the n'"'"'th test item i_n is less than a predetermined value.

32. The method of claim 29 wherein the stopping rule is to stop administering test items if a weighted distance measure between the initial SPS and the SPS after administration of the n'"'"'th test item i_n exceeds a predetermined value.

33. The method of claim 29 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if a weighted loss function is less than a predetermined value.

34. The method of claim 29 wherein the stopping rule is to stop administering test items if the largest value of the SPS after administration of the n'"'"'th test item i_n exceeds a threshold.

35. The method of claim 29 wherein the stopping rule is to stop administering test items if a predetermined number of test items have been administered.

36. The method of claim 29 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of one or more test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted loss function increases in value.

37. The method of claim 29 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of one or more test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted uncertainty measure decreases by less than a predetermined value, the weighted uncertainty measure being with respect to the SPS after the administration of item i_n and after the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k).

38. The method of claim 29 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of one or more test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted distance measure increases by less than a predetermined value, the weighted distance measure being with respect to the SPS after the administration of item i_n and after the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k).

39. The method of claim 29 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if a specified condition occurs, the specified condition being defined in terms of one or more first conditions, one or more second conditions, one or more third conditions, one or more fourth conditions, one or more fifth conditions, one or more sixth conditions, or combinations thereof, a first condition being that a weighted loss function is less than a first predetermined value, a second condition being that a weighted loss function increases in value given the hypothetical administration of one or more test items, a third condition being that a weighted uncertainty measure is less than a second predetermined value, a fourth condition being that a weighted uncertainty measure decreases by less than a third predetermined value given the hypothetical administration of one or more test items, a fifth condition being that a weighted distance measure is larger than a fourth predetermined value, and a sixth condition being that a weighted distance measure increases by less than a predetermined value given the hypothetical administration of one or more test items.

40. The method of claim 29 wherein the decision rule is to select the state associated with the highest value in the SPS.

41. The method of claim 29 wherein the decision rule is to select the state associated with the smallest value for a weighted loss function.

42. The method of claim 1 further comprising the step:

specifying a strategy tree to be used in administering test items to test subjects, a strategy tree being a plurality of paths, each path beginning with the first test item to be administered, continuing through a sequence alternating between a particular response to the last test item and the specification of the next test item, and ending with a particular response to the final test item in the path, the classification of the test subject being specified for each path of the strategy tree using a decision rule.

43. The method of claim 42 further comprising the step:

determining for a test item in the test item pool the weighted frequency and/or the probability of being administered.

44. The method of claim 43 further comprising the step:

removing a test item from the test item pool if the weighted frequency and/or the probability of being administered is less than a predetermined value.

45. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item which results in a partition for which the probability of a test subject being in the partition is nearest to 0.5.

46. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted uncertainty measure, the uncertainty measure being a measure of the uncertainty as to which of the test item'"'"'s partitions that the test subject is in, the uncertainty measure being smallest when all but one of the partition probabilities are near 0, a partition probability being the probability of the test subject being in the partition.

47. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted SPS uncertainty measure, given the hypothetical administration of i.sub.(n+1), an SPS uncertainty measure being a minimum when all but one of the SPS probability density values are near 0.

48. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted SPS uncertainty measure given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, an SPS uncertainty measure being a minimum when all but one of the SPS probability density values are near 0.

49. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted distance measure between the SPS after a hypothetical administration of an (n+1)'"'"'th test item and the SPS after the actual administration of the n'"'"'th test item, the distance measure being a measure of the differences in the two SPSs.

50. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the largest value of a weighted distance measure between the SPS after a hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, and the SPS after the actual administration of the n'"'"'th test item, the distance measure being a measure of the differences in the two SPSs.

51. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item corresponding to the largest value of a weighted discrepancy measure summed over all pairs of states, a discrepancy measure for a test item given two states being a measure of the distance between the class conditional densities for the item and the two states.

52. The method of claim 51 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being selected using a two-valued function Φ

, the function Φ

being a function of (1) a test item and (2) a first state and a second state, Φ

having a first value if the test item separates the first and second states, Φ

having a second value if the test item does not separate the first and second states.

53. The method of claim 52 wherein Φ

has a first value for a plurality of the test items for a specified first state and a specified second state, the test item i.sub.(n+1) being selected randomly from the plurality of test items.

54. The method of claim 42 wherein test item i'"'"'.sub.(n+1) is tentatively selected as the (n+1)'"'"'th administered test item i.sub.(n+1) in the specifying a strategy tree, test item i'"'"'.sub.(n+1) being selected using a predetermined selection rule from test items in the test item pool that have not already been administered, a random decision being made either to use test item i'"'"'.sub.(n+1) as the (n+1)'"'"'th administered test item i.sub.(n+1) or to select another test item from the test item pool.

55. The method of claim 54 wherein the test items are ordered according to a goodness criterion associated with the predetermined selection rule, the test item i'"'"'.sub.(n+1) being the best test item, a plurality of the next-in-order test items being denoted as the better test items, one of the better test items being selected as the (n+1)'"'"'th administered test item i.sub.(n+1) if the decision is made to select a test item other than test item i'"'"'.sub.(n+1).

56. The method of claim 55 wherein the selection of one of the better test items is randomly made, the random selection being biased in accordance with the order of the better test items.

57. The method of claim 55 wherein the decision to select a test item other than test item i'"'"'.sub.(n+1) is made with a probability that is a function of a "temperature" parameter, the probability being a monotonic function of "temperature".

58. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i(r) being the test item that would be selected using selection rule r, the index r denoting any one of a plurality of selection rules, the test item i.sub.(n+1) being the test item i(r) that results in a condition selected from the group of conditions (1) smallest value for a weighted loss function, (2) smallest value for a weighted uncertainty measure, and (3) largest value for a weighted distance measure.

59. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i(r) being the test item that would be selected using selection rule r, the index r denoting any one of a plurality of selection rules, the test item i.sub.(n+1) being a random selection from the test items i(r).

60. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item that maximizes a weighted relative ranking measure based on a plurality of item selection rules, a weighted relative ranking measure being a weighted function of the relative rankings of attractiveness for each test item with respect to a plurality of item selection rules.

61. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, the test item i.sub.(n+1) being the test item corresponding to the largest value of the sum of π

_n (j)π

_n (k)d_jk (i) over all states j and k in the domain, π

_n (j) denoting the members of the updated SPS after the test subject has responded to the n'"'"'th administered test item, d_jk (i) denoting a measure of the degree of discrimination between states j and k provided by test item i as measured by a discrepancy measure on the corresponding class conditional densities.

62. The method of claim 61 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being the absolute value of the difference in a first class conditional density and a second class conditional density, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k.

63. The method of claim 62 wherein the first function equals zero when the first and second class conditional densities are the same, the first function being equal to a positive constant when the first and second class conditional densities are different.

64. The method of claim 61 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being a third function of a difference function, the difference function being the difference between a fourth function of the first class conditional density and the fourth function of the second class conditional density, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k, the variety of functions denoted by the term "function" including the identity function wherein the function of a quantity is equal to the quantity.

65. The method of claim 61 wherein d_jk (i) is a first function of an integral of a second function over all possible responses to test item i, the second function being a function of the ratio of a third function of a first class conditional density and the third function of a second class conditional density weighted by the first class conditional density when the first and second class conditional densities are different, the first class conditional density being associated with item i and state j and the second class conditional density being associated with item i and state k, d_jk (i) being equal to zero when the first and second class conditional densities are the same, the variety of functions denoted by the term "function" including the identity function wherein the function of a quantity is equal to the quantity.

66. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted loss function given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k), k being an integer, a loss function being a function of (1) the state in the domain, (2) a classification decision action that specifies a state, and (3) the number k of test items to be administered beginning with i.sub.(n+1).

67. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item that results in the smallest value of a weighted loss function for k=1, a loss function being a function of (1) the state in the domain, (2) a classification decision action that specifies a state, and (3) the number k of test items to be administered beginning with i.sub.(n+1).

68. The method of claim 42 wherein the (n+1)'"'"'th administered test item i.sub.(n+1) in the step of specifying a strategy tree is selected from test items in the test item pool that have not already been administered, i.sub.(n+1) being the test item for which the weighted loss in administering the next k test items is the smallest, the loss in administering k test items being defined by a loss function consisting of two additive components, the first component being a measure of the loss associated with the classification of the test subject after administering the k test items, the loss associated with an incorrect classification being higher than the loss associated with a correct classification, the second component being the cost of administering the k test items.

69. The method of claim 68 wherein the first component of the loss function is (1) a constant A₁ (s) if the test subject would be classified correctly after administering k additional test items and (2) a constant A₂ (s) if the test subject would be classified incorrectly after administering k additional test items, the constants A₁ (s) and A₂ (s) having a possible dependence on the state s, the second component of the loss function being the sum of the individual costs of administering the k additional test items.

70. The method of claim 42 wherein in the step of specifying a strategy tree a stopping rule is applied after each specification of a test item in the strategy tree, an additional test item being specified only if the stopping rule so specifies.

71. The method of claim 70 wherein the domain is a combination model and the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if the marginal posterior value for a state in the discrete component of the domain is greater than a first predetermined value and the posterior variance of the continuous parameter in the domain is less than a second predetermined value.

72. The method of claim 70 wherein the stopping rule is to stop specifying test items if the largest value of the SPS after administration of the n'"'"'th test item i_n exceeds a threshold.

73. The method of claim 70 wherein the stopping rule is to stop specifying test items if a predetermined number of test items have been specified.

74. The method of claim 70 wherein the stopping rule is to stop administering test items if a weighted uncertainty measure with respect to the SPS after administration of the n'"'"'th test item i_n is less than a predetermined value.

75. The method of claim 70 wherein the stopping rule is to stop administering test items if a weighted distance measure between the initial SPS and the SPS after administration of the n'"'"'th test item i_n exceeds a predetermined value.

76. The method of claim 70 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if a weighted loss function is less than a predetermined value.

77. The method of claim 70 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted loss function increases in value.

78. The method of claim 70 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted uncertainty measure decreases by less than a predetermined value, the weighted uncertainty measure being with respect to the SPS after the administration of item i_n and after the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k).

79. The method of claim 70 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, a weighted distance measure increases by less than a predetermined value, the weighted distance measure being with respect to the SPS after the administration of item i_n and after the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k).

80. The method of claim 70 wherein the stopping rule is to stop administering test items after administering the n'"'"'th test item i_n if, given the hypothetical administration of the sequence of one or more test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k) where k is an integer, if a specified criterion is satisfied, the specified criterion being defined in terms of one or more first conditions, one or more second conditions, one or more third conditions, or combinations thereof, a first condition being that a weighted loss function increases in value, a second condition being that a weighted uncertainty measure decreases by less than a specified predetermined value, and a third condition being that a weighted distance measure increases by less than a specified predetermined value, the weighted uncertainty measure and the weighted distance measure being with respect to the SPS after the administration of item i_n and after the hypothetical administration of the sequence of test items i.sub.(n+1), i.sub.(n+2), . . . , i.sub.(n+k).

81. The method of claim 42 wherein one or more test items at the ends of a specified strategy tree are removed if the weighted loss in administering test items for the resulting strategy tree is less than the weighted loss for the specified strategy tree, the weighted loss being obtained by weighting a loss function over all paths in the strategy tree and all test subject states, the loss function being a measure of the loss associated with administering the test items in a path of the strategy tree.

82. The method of claim 81 wherein the loss function is a function of (1) the state of the domain, (2) a classification decision action that specifies a state, and (3) the number of items administered.

83. The method of claim 81 wherein the loss function consists of two additive components, the first component being a measure of the loss associated with the classification of the test subject after administering the k test items, the loss associated with an incorrect classification being higher than the loss associated with a correct classification, the second component being the cost of administering the k test items.

84. The method of claim 83 wherein the first component of the loss function is (1) a constant A₁ (s) if the test subject would be classified correctly after administering k additional test items and (2) a constant A₂ (s) if the test subject would be classified incorrectly after administering k additional test items, the constants A₁ (s) and A₂ (s) having a possible dependence on the state s, the second component of the loss function being the sum of the individual costs of administering the k additional test items.

85. The method of claim 42 wherein the decision rule is to select the state associated with the highest value in the SPS.

86. The method of claim 42 wherein the decision rule is to select the state associated with the smallest value for a weighted loss function.

87. The method of claim 42 wherein the step of determining the classification of the test subject includes the step:

administering test items to a test subject in accordance with the strategy tree;

classifying the test subject in accordance with the path followed by the test subject through the strategy tree.

88. The method of claim 1 wherein the domain specifying step comprises the steps:

specifying at least one initial model of the states in the domain;

administering the test items in the test item pool to a plurality of test subjects,

classifying each test subject as to state for each initial model;

identifying superfluous states in each model and eliminating them from the model;

identifying missing states in each model and adding them to the model.

89. The method of claim 1 wherein the test-item-pool-specifying step comprises the steps:

specifying at least one initial model of the states in the domain;

administering the test items in the test item pool to a plurality of test subjects,

determining for a test item in the test item pool the weighted frequency and/or probability that the test item is administered;

removing the test item if the weighted frequency and/or probability is less than a predetermined value.

90. The method of claim 1 wherein the domain specifying step comprises the steps:

specifying at least one initial model of the states in the domain;

administering a sequence of test items from the test item pool to each of one or more test subjects, the corresponding sequence of responses obtained for each of the test subjects being called a test subject response pattern;

determining the ideal response pattern for a test subject in each of one or more domain states for each administered sequence of test items using the class conditional densities associated with each test item, an ideal response being a value or a set of values;

identifying those ideal response patterns that do not satisfy a specified criterion with respect to each test subject response pattern, the specified criterion being specified in terms of one or more distance measures, a distance measure being a measure of the differences between a test subject response pattern and an ideal response pattern.

91. The method of claim 90 wherein a state is removed from the initial model if its corresponding ideal response pattern does not satisfy the specified criterion with respect to a specified number of test subject patterns.

92. The method of claim 90 wherein one or more states is added to the initial model if a specified number of ideal response patterns do not satisfy the specified criterion with respect to one or more test subject response patterns.

93. The method of claim 1 wherein the test-item-pool specifying step comprises the steps:

determining the intersections of the partitions of states by the test items in the test item pool.

94. The method of claim 93 wherein the test-item-pool specifying step includes the step:

adding new types of test items to the test item pool to reduce multi-state intersections to single-state intersections.

95. The method of claim 1 wherein the domain-specifying step comprises the steps:

determining the intersections of the partitions of states by the test items in the test item pool;

replacing the original domain model with a new domain model with new states, the new states being the intersections of the partitions of the original states by the test items, the higher-lower-neither relationships of the new states being derived from the higher-lower-neither relationships of the original states.

96. The method of claim 1 wherein the class-conditional-density-specifying step comprises the steps:

(a) specifying prior distribution functions for the parameters of each test item and state, the class conditional densities for the test items being determinable from the item parameter distribution functions;

(b) administering a sequence of test items from the test item pool to each of a plurality of test subjects and recording the sequence of responses;

(c) updating the SPS for each response in the sequence of responses using the initial SPS and the test item class conditional densities;

(d) determining the test subject'"'"'s classification;

(e) updating the distribution functions for the parameters of each test item and state utilizing each test subject'"'"'s classification;

(f) repeating steps (c), (d), (e), and (f) until the process converges.

97. The method of claim 1 wherein the test-item-pool-specifying step comprises the steps:

determining the sharpness of a test item from the test item pool, sharpness being a measure of the capability of a test item to discriminate between test subjects in different states, sharpness being measured by use of one or more discrepancy measures;

removing the test item from the pool if its sharpness does not satisfy a predetermined criterion.

98. The method of claim 1 wherein the class-conditional-density-specifying step comprises the steps:

identifying test items having questionable class conditional densities, a questionable class conditional density being indicated by a sharpness criterion not being satisfied;

changing the class conditional probability density of one or more test items to achieve greater sharpness.

99. The method of claim 98 wherein the class-conditional-density-specifying step further comprises the steps:

removing from the test item pool any test items for which the class conditional densities were changed and the sharpness criterion was not satisfied.

100. The method of claim 1 further comprising the step:

specifying a remediation program for each state in the domain, a remediation program for state X being a compilation of facts associated with one or more other states in the domain and a procedure for teaching the facts in the compilation to a test subject, the compilation not including facts associated with state X.

101. The method of claim 1 wherein the step of determining the classification of the test subject includes the steps:

(a) administering one of a sequence of test items from the test item pool to the test subject;

(b) updating the SPS after receiving a response to the administered test item;

(c) applying a stopping rule, steps (a) and (b) being repeated if the stopping rule so specifies;

(d) classifying the test subject as to a state in the domain in accordance with a classification rule if the stopping rule so specifies;

(e) directing the test subject to a remediation program.