Empirical Prediction Algorithm

1. Universality.

V~HoPz9 /' 3H 1 ( +(<HvfJ"lq >)~H2). The sense of th1s requl~ement 1s ev1dent: the algorithm would be applicable to any possible pair "protocol-hypothesis".

2. Non-triviality.

H 1 ~ H o

Hypothesis resulting from algorithm work would be, at least, no weaker than the initial one.

Let ¢ be one-one computable transforma­ tion of possible pair <Hv,Pr., /'into po­ ssible pair < H! ,PrJ > ~= ( ~ H o ,Pro>), such that hypotheses Ho and H~ are re­ futed or confirmed on the same sets of objects (i.e. simultaneous~). In such a case .we can regard JP as effective one­ one translation of hypothesis Ho and pro­ tocol Pr0 into another equivalent langu­ age. It is natural to demand invariance of results of prediction relative to such effective one-one translations from one language into another equivalent one; i.e. if j < H ,Pro>= H1 i andf~ H! ,Pr: > =H1, then H 1 and H~ wou d be refuted or con­ firmed simultaneous~.

3. Consistanc:.

K.F. Samochvalov has proved the the­ orem 4 that the only function answering these three requirements is the function f·, constructing the decoder, i.e. func­ tion that brings into correlation pair ~H0 ,Pr0 with hypothesis H , interdic­ ting all protocols .exeept Pr correspon­ ding to training sequence. It is clear, such a function f· cannot be means of in­ ductive generalization or that of disco­ very of empirical laws. To obtain useful prediction method the requirements formu­ lated above must be changed. Very like~, we have to reduce the third requirement of invariance of prediction with respect to formal~ equivalent ways of initial data representation. For this reason at­ tempts to construct universal, non-trivi­ al, and useful method of prediction pre­ suppose acceptance of "Goodman's approach" [5] : one ought to prefer some languages to another ones if, in spite of their eq­ uivalence, they differ on such criteria as "habitualness" and "frequency of usage" of the terms.

The work [4] , very like~, may be a justification of widespread in science principle of "simplicity" [6,7] · Accor­ ding to .this principle, from two theories equal~ well-conformed to known fact one ought to use more "simple" one to predict new events.

Along with research of requirements to empirical prediction algorithms, some variants of algorithas in which the requ­ irement of "consistence" is replaced by that of "the greatest simplisity" are te­ sted. One of wuch algorithms is as follo­ ing [8] :

1. Let Pr 0 be the protocol of expe­ riment over the finite set Bo of empiri­ cal objects.

Let Ho be the initial hypothesis. Suppose we are interested in predic­ tion concerning the t new objects on the grounds of more strong hypothesis H 1 · Such prediction is equivalent to choice of one protocol Pr,, having cardinal n+t from all protocols having the same cardi­ nal, which conform to hypothesis H 2 ·

We usual~ know something about new empirical objects. We want to predict the values of some empirical relations Pj · Let subprotocol describing the set or these relations be E :

E = {Pr ·L

1. To predict subirotocol E we con­ struct (generate) all protocols {Pr 1 }ha­ ving cardinal n+ t such that:
2. each of them conforms to hypothe­ sis H o ;
3. for each of thea the set E is its own subset.
4. We shorten obtained list of protocols as follows: CiJ
5. For every protocol Pr1 from the list {Pr } we find the subprotocol pr that contains all non-isomorphic subpro­ tocols having cardinal K. (Number K is equal to the number of calling the point 3, so that, for example, in the first ti­ me K=1 in the second K=2, and so on.).
6. b~ We choose the subprotocols pr~'1 having minimum cardinal, i.e. K=·m·~
7. We eliainate from the list LPr 1 } (and from further discussion) all those protocols Pr the subprotocols pr of which have cardinal more than ·min.
8. _ 4. If in carrying out the step 2 we eliminated from the list if on~ one pro­ tocol, and if remaining list consists of more than one protocol, we pass on to re­ carrying out of step 3.
9. The remaining set of protocols together with all isomorphic to them cor­ responds to the hypothesis H sought.

Clear~, the step 3 provides the re­ quirement of non-triviality for the algo­ rithm. At the same time it is the forma­ lization of the hypothesis of "simplici­ ty" in accordance with which from two ri­ val hypotheses the one that is based on regularity, observable on the lesser num­ ber of objects, will predict more "succes­ sfully".

The examination of algorithms of such types was carried out on the tasks of di­ scovering regularities in empirical tab­ les or different kinds. The examples of such problems follow.

"The Ohm's law". Signatu;:e 6 con1 P <fJ,pt-J p<2Jp(2Jp<.JJ tains predicate symbo s v j .t, 11. , v , x , p~J · Their interpretation is as follows.

pcsJ symbolizes 2-ary relation "greater or lqual" tested on any two readings of volt­ meter, P.,' 31 :ti%es 3-ary relation ( o:t type a+b ~ c) tested on any three readings of voltmeter. Symbols P 1 and P1 aean analo­ gous relations on the readings o:t amper­ aeter and obaaeter. Test algoritba of ini­ tial hypothesis H- consideres as adaissi­ ble any finite values of current, resis­ tance, and tension.

Table 1.

1

Protocol Pr0 results :troa table 1, containiug the readings of amperaeter · (Xz), obaaeter (Xk) and voltmeter (Xv). Table with pred~cted values of omitted eleaents is protocol Pr~ · (There are re­ adings of instruments in brackets) "Mendel's law". Signature contains

S)"llbois

Pm pUJ pi4J P ':1 PcJJ P' "' ~21 p(.IJ pi'<J Hn t Hn t Hfl t p t p t p t 't t 'Z t ·t

that are interpreted as 2-ary, 3-ary, and 4-ar,y relations (of type a~ b, a+b c, a+b+c ~ d ) on the set of instrument rea­ dings which measure the nuaber of accumu­ lation (PHn ), quantity of rosy flowers · (Pp ), and quantity of blue flowers (P~), Teat algoritha of ~othesis H adaits integer values in table 2 which is the good·grounds :tor construction of protocol Pro · The predicted values are ticked ott; there are r6al values of quantities sought in brackets. ''!'able 2.

"Two-dimensional nuaeral table". The task consists in discovering regulari­ ties between nuabers of lines ( 'h ) , null­ bars of colwme (.:ri), and elements~ .. · , being at the intersection of these 1!nes and coluans in the table 3.*) Table 3.

This hypothesis describes features of ta­ ble 3 briefly enough and precisely (with not great redundance only).

Theoretical and experimental investi­ gations of empirical prediction algorithas are still in progress.

References.

1. Von roerster H., Inselberg A., Weston, Meaory and Inductive inference, in: Cy~rnetic Probleaa in Bionics, ed. by tr.: oestreiener and b. k. ioore, Gor­ don a Breach Sci. PUbl., New York-Lon­ don-Paris, 1968, pp.31.
2. Wittgenatein L., Tractatus L9sico-Phi­ losophicust ·New fork, 1963, proposi­ tion 5, 13 1.
3. 3 · .BH·.rfleB !!:.~., raBpHJlKo .s.n · .t aaropyi­ Ko H.r., CaMOXB&JlOB K.t. IpedoB&HRR K anropHTM8M 8MnMpHqeCKOro DP8ACK888Hirtfl 1 Bf!tfHCJlHT8Jl~HJ118 CMC'f8MH, 50, cTp. I -Ius, Iruy2.
4. CaMOXB&JlOB K.t. 0 TeopRH SMDBpHqecKoro DP8ACK888Hirt8l BH~~JllrtT8pjHH8 OKCT8M¥t 55, CTp. 3-3~, I .
5. Goodaan N. , racth:Jictiobap.d rore­ S!!1· see. ed., e DoSS erriii eo­ ~&Qf, Inc., Indianapolis, New York. Kansas City, 1965.
6. Zagoruiko N.G., Hypotheses of the sim­ plicity in the pattern recognition Sec. Int. Oon:t. on Artificial Inteile­ gehci, LODdon, 1972, pp. 318-321.
7. SaropyAKo H.r. leTo~ paonoaH&B&HHR · ~ npHM8H8HirtRo ., OB!TCKOe P8AH0 1 ?2.
8. raBpHJlKO .BJI., SaropyiKO H.r. AnropHTM 8MnHpMqeoKoro ttpeACK838HHRf ~if~te1 AQHMe CMCT8MM· 55 1CTp.I34- 3 1 ·