понеделник, 17 септември 2018 г.

Minimal and Maximal Models in Reinforcement Learning


Each test gives us one property which we will denote as test result. The extension of that property we will denote as the test property. This raises the question about the nature of that property. Can it be a property of the state of the world? The answer is both yes and no. For a random model of the world the answer is negative, but if we look at the maximal model of the world the answer would flip to positive. There can be various models of the world. The minimal model knows about the past and the future the indispensable minimum. Conversely, in the maximal model the world knows everything about the past and the future. If you threw a dice the maximal model would know which side will fall up and would even know what you will do. For example, it would know whether you will throw the dice at all.
Keywords: Artificial Intelligence, Reinforcement Learning, Partial Observability, Event-Driven Model, Double-State Model, Test Property, Test State.

Introduction


We try to understand the world (the environment) and for this purpose will use tests. One example of a test is the following:

If I press the door handle Þ the door will open.

Each test contains a condition (prerequisite). The condition in this case is that I must press the door handle. When the condition is met, the test is done and we get the test result, which can be true or false. In our example the door will open or will not open.

Each test gives us one property (the test result). The property in our example is “the door is locked”. We cannot know the value of that property at each and every point in time. We only know that value at the time points when the test is done.

We will assume that the property is meaningful at any time point and will thus try to extend the characteristic function of that property beyond the subset of time points at which the test is done. The property may not necessarily be total or defined at each and every time point. Say, if somebody stole the door, the question of whether it is locked becomes meaningless. In other words, while we will do our best to extend the characteristic function of the property, we may not always end up with a total function.

What is the idea behind extending the test result to a test property? If I gave you a slice from a cucumber, would you be able to reconstruct the whole cucumber out of that slice?  We certainly mean a mental reconstruction of the cucumber, not a physical one. That reconstruction however is not unique as it may generate various objects. E.g. from a cucumber slice we may conceive a rhinoceros if we imagine that the slice comes from its tusks. Certainly, we will try to find extensions which are as simple, natural and credible as possible.

Bear in mind that the cucumber slice is real, while the cucumber as such is imaginary or conjured up. If I let you see the full cucumber it would be easier for you to imagine it; however, you are more likely to imagine a healthy cucumber, whilst the actual one may turn out to be rotten inside. That is, you never get the full information. You always receive a fraction (a slice of information) from which you have to conjure up the whole thing.

Now let us discuss the question of what is this property (the test result and its extension). At different moments its value can be true or false. However, it is not a property of time because it depends on the developments playing out around the time point rather than on the time point proper. Maybe this is a property of the state of the world (the subset of states in which the property is TRUE).

Does this property depend on the past and on the future? Typically, the test takes place within a certain period of time rather that at a single moment. The test result depends therefore on the temporal context (the near past and the near future within the test period). If we take the test property it depends on a wider temporal context and may tell us something about the distant past and the distant future of the world.

Let us have the property “This letter brings good news”. The test for this property is “Open the envelope and check what the letter says”. The property tells us something about the future. To put it more precisely, it tells us what we will read in the letter after we open the envelope. Is it a property of the world? Does the world know what the letter says before we open it? We tend to think that yes, the world knows, but it can afford not to know, as well. For example, the majority of computer games do not bother to calculate the whole world, but take care only of the fraction of the world the gamer sees now. If the world were such a game, it would decide what the content of the letter is only when you open it. In a similar example, let us imagine life as a TV serial. In series 1354 you receive a letter, but open it 10 series later. When will the scriptwriter decide what is in the letter? When he or she writes the script of series 1354 or the script of series 1354+10? So we see that the world may or may not know in advance how the future will unfold.

Similar is the situation with the past. The property “I am back from a vacation” provides some clues about the past. The test to verify this property is: “I check whether I am on a vacation or on a business trip and then come back”. We assume that if you are back from a vacation and are still at home (have not gone elsewhere), then you are still back from a vacation. That is, we extended the property to time points at which it is not tested.

Let us assume that the future of the world does not depend howsoever on whether you are back from a vacation or from a business trip. Then why should the world remember that fact at all? The question which keeps historians awake at night is whether the world remembers the past. Did a historical event leave any documents or other traces of its occurrence? The answer is that the past can be remembered but it is perfectly possible some facts to be totally discarded.

This article will discuss two models of the world – minimal and maximal. In the minimal model the world remembers the indispensable minimum from the past and knows the indispensable minimum about the future. Conversely, in the maximal model the world remembers everything from the past and knows everything about the future. In the maximal model the world knows exactly what is going to happen and even what you (the agent) would do or not do.

What are we looking for?


What is given and what are we trying to find out? In this article we will try to find an explanation of the world. With Reinforcement Learning [1] we have an agent who lives in a certain world. The world is an oriented graph similar to Figure 1. The agent follows the arrows, moves from one state to another and collects certain rewards. It is vital for the agent to explore the world and understand it well, otherwise he would not get to the rewards. Many articles assume that the world is a given entity and what we look for is a policy which would be successful in that world (e.g. [­3]). In this article we will assume that the world is unknown.

Figure 1

In Figure 1, the possible moves of the agent are represented by arrows and the possible observations are denoted with various numbers and colours. Each arrow should be tagged with a label indicating the action corresponding to that arrow. Although we have not shown these labels, the figure clearly demonstrates that sometimes there is a single arrow (possibility) and at other times there are more possibilities (at states 2 and 3). We will assume that not all actions are possible and that the transitions are nondeterministic. In other words, for a particular state/action there may not be even a single arrow with right label departing from that state, or there may well be more than one arrow with the right label.

By allowing for nondeterministic transitions we have in fact embraced randomness. In [5] we demonstrated that there are two types of randomness, predictable and unpredictable. Here we will work with unpredictable randomness (with a probability in the interval [0, 1]). This kind of randomness is also used in Nondeterministic Finite Automaton (NFA). With NFA something may or may not occur, and we do not know the probability of its occurrence. The Partially Observable Markov Decision Process (POMDP) uses predictable randomness (something occurs with a precisely determined probability). In [5] we demonstrated the equivalence of the four types of models (the deterministic one, the models with the two types of randomness, and the model which combines the two types of randomness). So we can use whichever model suits us best and have thus opted for the model with unpredictable randomness used here.

Full Observability means that we can tell which is the state just by the observation. The opposite is referred to as Partial Observability. Going back to Figure 1, when we are able see the number of the state, we enjoy Full Observability. Seeing the colour only does not tell us the full story. If all we see is a red circle we cannot not know whether it is state 4 or 5.

If we had the world’s model, we would be able to foretell the future. Thus, if we find ourselves in state 4 we will predict that the next state will be 6. In a red state we will know that the next state will be either green or blue. Likewise, we can back-tell the past. Suffice it to turn the arrows in opposite direction and the past will become the future. The only problem is that turning the arrows may force a deterministic graph become nondeterministic, but we have chosen to use nondeterministic graph models anyway.

What is given? The given body of facts is the history until the present time point, that is the sequence of actions (outputs) and observations (inputs or views).

a1, v2, a3, v4, … , at-1, vt

The numbering notation here identifies the number of the moment and not the number of the step. There are two moments in each step. At the first moment we produce information (this is our action) and in the second moment we enter what we see. That is, the step number will be the moment number divided by two.

Why do we choose to divide time in moments and not in steps? Because of the event-driven models, where the states will change at certain moments. At each step the state may change twice because the step has two moments.

There will be two types of moments: input and output moments. They will also be referred to as even and odd moments.

Note that the inputs and outputs will be vectors of scalars. We will assume that these scalars are finite. We could have stayed with Boolean vectors, but have not done so in order to avoid redundant coding (cf. [4]).

The history will also include all the incorrect (bad) moves we have tried before we play our next move.

bad1, a1, v2, bad3, a3, v4, … , badt-1, at-1, vt

Here we can imagine the bad element as a list or as a set of incorrect moves (because the order in which we have tried the incorrect moves is not essential). We will assume that the incorrect moves were tried at the same moment when the correct move was played (that is why the set of moves bad and the next correct move a have the same index).

Definition: For our purposes, life is a history which cannot be continued.

A history cannot be continued when it is either infinite or terminates in a state which does not have any arrows coming out of it. The term we used for these states in [6] was “sudden death”.

The Double-State Model


Figure 1 depicts the standard model, which is based on steps. We will use a double-state model, which is based on moments.

Figure 2

Figure 2 explains the difference between the standard model and the double-state model. The latter is obtained from the first by replacing each state with two states connected with an arrow. All arrows which previously entered the one state now enter the first one of the two states. The arrows which previously departed from the one state now depart from the second one of the two states. The former label of the state now goes to the arrow which connects the new states. In the double-state model, only arrows have labels and states have none. We have used smaller circles for odd-number states in order to stress that there are two types of states.

Note: Here we will deem that a state relates to a time period while an arrow relates to a time point which is the onset of the text time period. In event-driven models however, we will deem that states relate to longer time periods and arrows relate to very brief periods (lasting one moment or bit more).

Although it appears that the double-state model includes twice as many states, this is not actually the case, because when two states are equivalent from a future perspective they can be merged in a single state. The standard model allows the merging of only those states which are equivalent from both present and future perspective. I.e. in the standard model each state must remember the present, but need not do so in the double-state model. This is one of the reasons why we introduce that model. In the present article we attach paramount importance to the information we can derive from the state – what can the state tell about the past and the future. The present is part of the past because it has already occurred.

As the name suggests, the double-state model deals with two types of states: post-input and post-
output. We will call them evens and odds, meaning even-number and odd-number states. Evens are more important because they are the states in which we think. In odd states we do not think, but just wait to see what information the world will give us. (It may be assumed that the world does the thinking in the odd states. So we take turns – at one time point we put the thinking hat on and at the next time point we pass the thinking hat over to the world.)

Let use as an example the world in which we play chess against an imaginary opponent. Our actions (outputs) will be vectors in the form of (x1, y1, x2, y2). These vectors describe our move. We will be able to see the opponent’s move and the reward. That is, the input will be a (x1, y1, x2, y2, R) vector. The states in the double-state model will be the positions on the chessboard. Even-number states will be those in which it is the white’s (ours) turn to make a move. If our move terminates the game (e.g. checkmate) the opponent must play some idle move and return to us only the reward of the game. The idle move is a vector in the form of (0, 0, 0, 0, R) and must lead to the initial position so that the game can be restarted.

Things with the standard model will be more complicated. The states will only be the positions when it is white’s turn to move, but the model must also remember the opponent’s move which produced that position. Hence there will be more states because “white ahead” positions will be twice less, but if there are averagely 100 ways to produce a position (from 100 different positions with 100 different moves of the opponent) the standard model will end up with 50x more states.

As mentioned already, the standard model needs to remember the present while the double-state model does not. How about the future? When we play chess against a deterministic opponent, then both models produce deterministic graphs. Let us assume that the opponent is nondeterministic and enjoys the liberty to choose among several possible moves at each position. In that case, the standard model would produce a nondeterministic graph (a single move from us triggers several different responses/counter-moves and their respective positions). The double-state model will remain deterministic, because our move creates a single, determinate position. Two or more arrows, which correspond to the possible moves of the opponent, will depart from that position (if the opponent were deterministic, there would be just one arrow).

Does the double-state model always produce a deterministic graph? Not always, but we can always transform the graph to a deterministic one. Now we will go back to our chess game example, but will slightly change the rules: we will not be able to see the opponent’s move, but only the piece moved by the opponent. So we will not see (x2, y2). Now that we know the piece, but not the place to which it was moved, we will have several possible positions. While the obvious graph representing this kind of game is nondeterministic, we can perfectly apply a deterministic graph. If the state of the world is not a specific position on the chessboard, but a set of possible positions, then each move will trigger a single arrow which points to a set of possible positions. That is, in the first (nondeterministic) scenario the world knows more about the future than in the second scenario. In the deterministic scenario, the world does not know the exact position. What the world knows is the set of possible positions. When will the world get to know the exact position, however? Not until a later time point, when the exact position will transpire from the input (observations). Same as the letter in our TV serial. In the first case the world knows what is in the letter, while in the second case it will not decide what the letter says until you open the letter.

The Minimal Model


In our concept, a double-state model of the world will be minimal when the world’s knowledge about the past and the future is limited to the indispensable minimum. In the minimal model, if two states are equivalent vis-à-vis the future, they coincide. In other words, the model does not remember anything about the past unless it is necessary in order to determine the future.

Furthermore, the minimal model is a deterministic graph. This means that the branches are pushed forward (to the future) as much as possible. Hence, nothing of the future will be known in advance (the thing will become known only when it has left its imprint on the observation, not earlier).

A minimal model is not tantamount to a least-state model. Minimalism does reduce the number of states with regards to the past, but tends to increase them with regards to the future (because we have replaced the specific possibilities with sets of specific possibilities).

The determinization procedure can always be applied so we can always obtain a deterministic graph. A deterministic graph does not necessarily mean a deterministic agent or world. For the agent to be deterministic there must not be any branches from the even states. (Here by saying that an agent is deterministic we meant that the agent is forced to play a deterministic game, because the agent has only one possible move. Generally speaking, however, a deterministic agent is understood as an agent who plays deterministically without being forced to do so.) For the world to be deterministic there must not be branches from the odd states. A deterministic graph means that the states know only the indispensable minimum about the future. (If two states are different, their past has been different, too. Therefore, the differentiating factor is their different past, not their different knowledge about the future).

The Total Model


An incorrect move is one which has not any arrow for it, i.e. this move simply cannot be made. However, we would like to enable the agent try incorrect moves without further implications. That is, the agent will only receive information that the move is not correct, but will remain in the same state.

For this purpose, to each even state (at which incorrect moves exist) we will add an odd state (see Figure 3). All incorrect moves from the even state will point to the new odd state. From the new odd state we will go back to the even state with an arrow labeled “bad”. That label will be a special new vector, which we have added for our purpose and which will be received as an input only when we try an incorrect move.

Figure 3

In Figure 3, the possible moves are represented by red, blue and green arrows. There are two incorrect moves at state s0 and only one incorrect move at s4. State s2 has not an additional odd state due to the absence of incorrect moves at s2.

This gives us a total model, where all moves can be tried, but only the correct ones change the state of the world, while the incorrect ones only return information which confirms that they are not correct. Thus we obtain a whole new total model, which describes the same world as the previous model, but has an added value in that it lets us try the incorrect moves.



The Maximal Model


Now that we saw the minimal model well and alive, we might think there is a maximal model, too. That should be the model where the state knows everything about the past, everything about which moves are correct and everything about the future.

Knowing everything about the past is easy as long as we do not stumble into branches when we walk back (in the direction opposite to that of the arrows). In other words, if the model is tree-shaped then the state will know everything about the past (we will able to reconstruct the entire history by going back from that state).

We can easily add also the information about which moves are incorrect, because this information is finite.

If we were to know everything about the future, we must dispense with any nondeterminism. We want to know which side will fall up before we throw the dice. We will thus construct a model where all nondeterminism is precipitated in the initial state. Once we select the initial state (in a nondeterministic way), the way ahead will only be deterministic.

Let us take the tree of all reachable states. (This is a true tree, because equivalent states are not merged into one.) We will make determinization on that tree, although this is not strictly necessary. From that tree we will obtain all policies of the world. These are sub-trees, which have no branches at observation points, but keep their branches at action points. These trees are many (cardinality of the continuum). We will take all those trees and make a model where the initial states will be the roots of all these trees.

“Policy” is maybe not the most appropriate word to use here, because a policy implies a certain objective. Here we assume that only the agent has an objective, and the world has none. If we claim that the entire world tries to help us or disrupt us, that would be far too egocentric. Nevertheless, we will imagine that in the world there are agents who are up to something (have their objectives). So, the world has not an objective as such, but we will still use “policies” to denote the various behaviours of the world.

We have thus made a model which consists of all policies of the world. Yet before life begins, the world randomly chooses one of its policies and follows it to the end of the agent’s life. The idea is to preconceive how to play the game before the games begins. We may decide that if the opponent plays a rook, we will respond with a bishop and so forth. This preconception is a policy and is depicted with an infinite tree. These trees are uncountable. We may decide to play using a certain deterministic program, but in this way we can preconceive only a computable policy. The number of computable policies is smaller (they are countable).

The so-obtained model is equivalent to the one we began with, because any history which is possible in one of these models is also possible in the other model. With the new model however the world behaves in a deterministic pattern except for the initial time point when the initial state is selected.

In that world, any randomly selected state knows almost everything about the future. The only thing it does not know is what action will the agent choose. We would like to construct a model which makes sure that the state of the world knows even this missing piece.

There is one hurdle, however. We tend to assume that the world is given and the agent is random. Therefore, the world cannot know what the agent will do because it does not have any idea which agent will come by. Now let us assume that the agent is fixed and the world may know something about the agent. The world may know, for example, that in a certain situation the agent will not play a certain move, although the move is correct and doable. In the model graph, the move not to be played by the agent will be shown with a missing arrow.

We will further imply that before life begins both the world and the agent have figured out how to play. They have selected their policies and will stick to them right to the end of the agent’s life. This can be described by a tuple of two infinite trees or by one life (an infinite path in the tree). This is because the result from the application of two fixed policies is a fixed path.

Thus we arrived at the maximal model of the world. It consists of all possible lives (paths in the tree of reachable states). The only missing piece is information about the incorrect moves. To bridge this gap, we will add loops similar to those in the total model. But, this will not be a total model, because loops will be added only for incorrect moves, and not for all missing arrows. This gives the model depicted on Figure 4. (No loop at s2 because there are no incorrect moves from that state.)

Figure 4

Figure 4 depicts only one life rather than all possible lives which form the maximal model. We care only about one life and this is the life we live in. This lets us assume that the maximal model has only one life, namely the life we are interested in. So we will lose the equivalence with the initial model, but the so-obtained model is what we need, because all other possible lives are not relevant.

Any state in our maximal model can be used to reconstruct the full history or even the full life. The forward and backward paths are branchless. Our added loops will not count as branches, because the bad symbol does not occur at observations after correct moves. Here the state knows which moves are incorrect, but does not know which of those moves have been tried by the agent. This information is not important to the world, because it has not any implications for the past or for the future. The information is certainly essential to the agent, because he may not know which moves are incorrect and will obviously benefit from knowing which moves he has already tried.

Conclusion


We try to understand the world, i.e. to find its model. The problem however is that there is not a single model but a raft of models. There may be unreachable and equivalent states, but this is not much of a problem. There may be parts of the world which we have not visited and will never visit. Let us take the following example: Is there life on planet Mars? We have never been there and will never go there, so the matter is irrelevant (will not howsoever affect our life).

The most serious problem is that there are models in which the world knows more and models in which the world knows less. Which model are we looking for? The answer is that we need the maximal model so that we can obtain maximum insight of the past and maximum foresight of the future. We will even venture to predict our own behaviour, because we are part of the world and trying to understand the world means that we should also try to predict our own behaviour in that world.

In order to describe the maximal model, we will use the so called extended model. That model will present the state of the world as a vector with a huge number of coordinates (variables). They will be thousands or even countless. In theory they are countless, but for practical purposes we will select only the most interesting ones. Probably this is the model referred to by Sutton in [2] (state representation which contains many state variables).

The first coordinates (variables) to be applied in the vector which describes the extended state will represent what we see at the moment. With the double-state model, an observation is not a function of the state of the world, because if the state is even-numbered there may be many arrows with different observations pointing to it. Accordingly, an odd state may have many arrows departing from it. But, here we discuss the maximal model, which always has one incoming and one outgoing arrow. In the maximal model, therefore, it is the state of the world which determines what we see at the moment.

To what we see at the moment we will add the test properties of various tests. These are not the real-world cucumber slices. These are imaginary cucumbers which we have conjured up from the real slices. Thus, the extended model will be an imaginary rather than a real thing.

Question: If we have Full Observability, do we need to add test properties to the state vector in the extended model? Answer: Yes, we need to do so, because in Full Observability case we know the state of the world, but this state comes from another model, not from the maximal one. Having Full Observability with a maximal model would make the world so simple that it will be not interesting at all.

How can we design a test property? Consider the property “Is the door locked”. We test this property and sometimes get “locked”, sometimes “unlocked”. It would be fairly difficult to create a model which tells us when exactly the door is locked or unlocked. We would be much more successful if we imagine that the doors are more than one (especially if the doors are actually  more than one). In the new model we should have an idea about which door we are standing in front of now. Some doors in that new model can be always locked, others would be always unlocked, and a third group of doors would change their state according to certain rules. In this case, we will not add to the extended model just one variable which reflects the test property. We will add many variables – one for each door (which reflects the state of the door) and one variable which indicates the exact door we are standing in front of now. In [5] this presentation was termed test state.

Which door are we standing in front of right now? This is determined by event-driven models which will be discussed in the next article.

References


[1] Richard Sutton, Andrew Barto (1998). Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA (1998).

[2] Richard Sutton (2008). Fourteen Declarative Principles of Experience-Oriented Intelligence. www.incompleteideas.net/RLAIcourse2009/principles2.pdf

[3] Johan Åström. (1965). Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications. 10: 174–205.

[4] Dimiter Dobrev (2013). Giving the AI definition a form suitable for engineers. April, 2013. arXiv:1312.5713.

[5] Dimiter Dobrev (2017). How does the AI understand what’s going on. International Journal “Information Theories and Applications”, Vol. 24, Number 4, 2017, pp.345-369.

[6] Dimiter Dobrev (2018). The IQ of Artificial Intelligence. Jun 2018. arXiv:1806.04915.

събота, 25 август 2018 г.

Минимален и максимален модел при Reinforcement Learning



Всеки тест ни дава едно свойство, което ще наречем резултата на теста. Продължението на това свойство ще наречем тестовото свойство. Въпросът е, какво представлява това свойство? Дали това не е свойство на състоянието на света? Отговорът е и да и не. Ако вземем произволен модел на света, то отговорът е не, но ако изберем максималния модел на света, то тогава отговорът е да. Имаме различни модели. Минималният модел е този, при който света знае за миналото и за бъдещето минималното, което му е нужно. При максималния модел света знае всичко за миналото и за бъдещето. При този модел, ако хвърлите зар света знае какво ще се падне и дори знае вие какво ще направите. Например, знае дали ще хвърлите зара.

Keywords: Artificial Intelligence, Reinforcement Learning, Partial Observability, Event Model, Double Model, Test Property, Test State.

Въведение


Ние се опитваме да разберем света. За да го разберем, ще използваме тестове. Пример за тест е:

Ако натисна дръжката на врата Þ вратата ще се отвори.

Тестовете съдържат някакво условие (предпоставка). В случая условието е, че съм натиснал дръжката на вратата. Когато условието е изпълнено, тогава теста е проведен и тогава получаваме резултата на теста, който е истина или лъжа. В случая врата се отваря или не се отваря.

Всеки тест ни дава едно свойство (резултата на теста). В случая свойството е „врата е заключена“. Ние не знаем каква е стойността на това свойство във всеки един момент, а само в моментите когато теста е проведен.

Ние ще предполагаме, че това свойство има смисъл във всеки един момент и ще се опитаме да продължим характеристичната функция на това свойство извън множество на моментите когато сме провели теста. Възможно е това свойство да не е тотално и да не е дефинирано във всеки един момент. Например, ако някой открадне врата, то въпросът дали тя е заключена губи своя смисъл. Тоест, ще се опитаме да продължим характеристичната функция на свойството, но не е задължително да получим тотална функция.

Каква е идеята в продължаването на резултата на теста до тестово свойство? Ако ви дам едно резенче (slice) от краставица, дали бихте могли от резенчето да възстановите цялата краставица? Разбира се, става дума за мислено възстановяване, а не за физическо.
Това възстановяване не е единствено и при него може да се получат различни обекти. Например, от резенчето от краставица можете да получите носорог, като си представяте, че това е резен от рога му. Разбира се, ние ще търсим продължения на резултата, които са максимално прости, естествени и достоверни.

Имайте предвид, че резенчето от краставица е нещо реално, докато самата краставица е нещо въображаемо и измислено. Ако ви дам да видите цялата краставица, то на вас ще е ви е по-лесно да си я представите, но вие може да си представите здрава краставица, а тя да се окаже изгнила отвътре. Тоест, никога вие не получавате цялата информация. Винаги получавате само една част (един резен информация), по който трябва да си представите целия обект.

Нека си зададем въпроса какво представлява това свойство (резултата на теста и неговото продължение). В различни моменти от времето свойството е истина или лъжа. Въпреки всичко, това не е свойство на времето, защото свойството не зависи толкова от конкретния момент, колкото от развитието на историята около този момент. Може би това е свойство характеризиращо състоянието на света (т.е. това е множеството от състоянията на света, при които свойството е истина).

Дали зависи свойството от миналото и от бъдещето? Обикновено тестът не се провежда в един конкретен момент, а продължение на известно време. Тоест, резултата от теста зависи от времевия контекст (близкото минало и бъдеще в рамките на провеждането на теста). Ако вземем тестовото свойство, то то зависи от по-широк времеви контекст и може да ни казва нещо за далечното минало и бъдеще на света.

Например свойството: „В писмото има добра новина“. Съответния тест е: „Отварям писмото и проверявам какво пише в него“. Това свойство ни казва нещо за бъдещето. По точно, казва ни какво ще прочетем в писмото, когато го отворим. Дали това е свойство на света? Дали света знае какво пише в писмото още преди да сме го отворили. Обикновено си мислим, че знае, но би могъл е да не знае. Например, повечето компютърни игри не си дават труда да изчисляват целия свят, а се грижат само за тази част от света, която играчът вижда в момента. Ако света е такава игра, то той ще реши какво пише в писмото чак когато го отворите. Друг пример, нека живота е телевизионен сериал. Ако в 1354 серия вие получите писмо и десет серии по-късно го отворите, то кога сценариста ще реши какво пише в писмото? Когато пише сценария на серията когато получавате писмото или когато пише серията когато го отваряте? Тоест, виждате, че света може предварително да знае, а може и да не знае предварително какво ще се случи в бъдеще.

Подобен е и въпросът с миналото. Например свойството: „Върнал съм се от почивка“ ни дава информация за миналото. Съответния тест е: Проверявам дали съм на почивка или в командировка и след това се връщам. Предполагаме, че ако сте се върнали от почивка и още сте си в къщи (никъде другаде не сте ходили), то продължавате да сте се върнали от почивка. Тоест, продължихме свойството за моменти, в които то не е тествано.

Нека предположим, че за бъдещето на света няма никакво значение дали сте се върнали от почивка или от командировка. Тогава има ли смисъл света да помни този факт? Въпросът, който вълнува историците е дали света помни миналото? Дали едно историческо събитие е оставило някакви документи или други следи за това, че се е случило? Отговорът е, че миналото може да се помни, а може и да не се помни.

В тази статия ще разгледаме два модела на света – минимален и максимален. При минималния светът помни минималното от миналото и знае минималното за бъдещето. При максималния е обратното, там светът помни всичко от миналото и знае всичко за бъдещето. Там светът знае точно какво ще се случи и дори знае вие (агента) какво ще направите.

Какво търсим?


Какво е дадено и какво се търси? В тази статия ще търсим обяснение на света. При Reinforcement Learning имаме един агент, който живее в някакъв свят. Света е един ориентиран граф подобен на този на фигура 1. Агентът се движи от състояние на състояние по стрелките и събира някакви награди (rewards). За него ще е много важно да разбере света, за да може да намери наградите. Има много статии, където се предполага, че света е даден и се търси стратегия, която би била успешна в този свят (например []). В тази статия ще предполагаме, че света е неизвестен.

Figure 1

На фигура 1 възможните действия на агента са отбелязани със стрелки, а възможните наблюдения са отбелязани с различни номера и цветове. На всяка стрелка би трябвало да има етикет (label), който да казва на кое действие съответства тази стрелка. На тази фигура етикетите са изпуснати, но се вижда, че понякога има една възможна стрелка, а понякога възможностите са няколко (при състояния 2 и 3). Ще предполагаме, че не всички действия са възможни, както и че имаме недетерминирани преходи. Тоест, ще предполагаме, че при конкретно състояние и конкретно действие може и да няма стрелка с този етикет излизаща от това състояние, както и че може такива стрелки да има повече от една.

Това, че допускаме недетерминирани преходи означава, че допускаме случайност. В [3] показахме, че има два вида случайност – прогнозируема и непрогнозируема. Тук използваме непрогнозируемата случайност (нещо се случва с вероятност в интервала [0, 1]). Тази случайност се използва още и при NFA (nondeterministic finite automaton). Там нещо може да се случи, а може и да не се случи, но не знаем с каква вероятност ще се случи. При POMDP (partially observable Markov decision process) се използва прогнозируемата случайност (нещо се случва с точно определена вероятност). В [3] доказахме еквивалентност между четирите вида модели (детерминирания, моделите с двете случайности и модела с комбинацията от двете случайности). Тоест, можем да работим, с който модел ни е най-удобно и ние сме избрали този.

Казваме, че имаме Full Observability когато можем по това, което виждаме да познаем кое е състоянието. Съответно, казваме че имаме Partial Observability в противния случай. Например, ако виждаме номера на състоянието, тогава имаме Full Observability, но ако виждаме само цвета, тогава не виждаме всичко. Например, ако виждаме „червено“ не можем да кажем дали сме в състояние 4 или в 5.

Ако имаме модела на света, то чрез него бихме могли да предскажем бъдещето. Например ако сме в състоянието 4 можем да предскажем, че следващото състояние ще е 6. Ако сме в червено състояние, можем да предскажем, че следващото ще е зелено или синьо. По същият начин както предсказваме бъдещето можем да предвидим и миналото. Трябва само да обърнем посоката на стрелките и милото става бъдеще. Единственият проблем е, че при обръщане на стрелките от детерминиран граф може да се получи недетерминиран, но ние избрахме да използваме като модели недетерминирани графи.

Какво ни е дадено? Дадена ни е историята до текущия момент. Тоест дадена ни е редицата от действия (outputs) и наблюдения (inputs или view).

a1, v2, a3, v4, … , at-1, vt

Тук номерацията не показва номера на стъпката, а номера на момента. Във всяка стъпка има два момента. В първия извеждаме информация (това е нашето действие), а във втория въвеждаме какво виждаме. Тоест, номера на стъпката ще е номера на момента разделен на две.

Предпочитаме да разделим времето не на стъпки, а на моменти, заради събитийните модели където състоянията ще се променят в определени моменти. За една стъпка състоянието ще може да се промени два пъти, защото в стъпката има два момента.

Моментите ще са два вида – входящи и изходящи, които ще наричаме още четни и нечетни моменти.

Нека отбележим, че входовете и изходите ще са вектори от скалари. Ще предполагаме, че тези скалари са крайни. Бихме могли да се ограничим до булеви вектори, но няма да го направим за да избегнем излишното кодиране (виж [1]).

Към историята ще добавим още и некоректните ходове, които сме пробвали преди да изиграем поредния си ход.

bad1, a1, v2, bad3, a3, v4, … , badt-1, at-1, vt

Тук елемента bad можем да си го мислим като списък от некоректни ходове или като множество, защото реда, в който сме пробвали некоректните ходове, е без значение. Ще считаме, че некоректните ходове са пробвани в същия момент, когато е изигран съответния коректен ход (затова списъка bad и следващия след него коректен ход a имат еднакъв индекс).

Дефиниция: Живот ще наричаме история, която не може да бъде продължена.

Една история не може да бъде продължена, ако е безкрайна или ако завършва със състояние, от което не излизат никакви стрелки. В [4] такива състояния нарекохме „внезапна смърт“.

Двоен модел


Фигура 1 е направена на базата на стандартния модел, който е базиран на стъпки. Ние ще използваме двойния модел, който е базиран на моменти.

Figure 2

Разликата между стандартния и двойния модел е илюстрирана на фигура 2. Двойния модел се получава от стандартния като всяко състояние бъде заменено от две състояния и стрелка помежду им. Всички стрелки, които са влизали в състоянието, сега ще влизат в първото, а стрелките които са излизали от състоянието, сега ще излизат от второто. Етикета, който е бил на състоянието сега е етикет на стрелката между новите състояния. При двойния модел само стрелките имат етикети, а състоянията нямат. Тук сме отбелязали нечетните състояния с по-малки кръгове, за да подчертаем, че имаме два вида състояния.

Изглежда сякаш в двойния модел състоянията са два пъти повече, но това не е така, защото ако две състояния са еквивалентни от гледна точка на бъдещето, то те мога да бъдат обединени (слети) в едно. В стандартния модел могат да бъдат обединени само състояния, които са еквивалентни от гледна точка на настоящето и на бъдещето. Тоест, в стандартния модел състоянието трябва да помни настоящето, докато в двойния няма такава нужда. Това е една от причините, поради която въвеждаме този модел. В тази статия за нас ще е много важно каква е информацията, която можем да извлечем от състоянието. Тоест, какво може да каже състоянието за миналото и за бъдещето. Настоящето е част от миналото, защото то вече се е случило.

В двойния модел състоянията ще са два вида. Състояния след вход и състояния след  изход. Ще ги наричаме още четни и нечетни състояния. По-важни са четните състояния, защото това са състоянията, в които мислим. В нечетните състояния ние не мислим, а само чакаме да видим каква информация ще ни даде света. (Може да предполагаме, че в нечетните моменти мисли светът. Така се редуваме, в един момент мислим ние, а в следващия мисли светът.)

Да вземем като пример света, в който играем шах срещу въображаем противник. Нашите действия ще са вектори от вида (x1, y1, x2, y2). Тези вектори описват нашия ход. Ще виждаме хода на противника и оценката (reward). Тоест, входа ще бъде вектор от вида (x1, y1, x2, y2, R). При двойния модел състоянията ще бъдат позициите на дъската. Четните състояния ще са тези, при които белите са на ход (т.е. ние сме на ход). Когато нашия ход завършва играта (например мат), тогава противника ще трябва да играе някакъв празен ход и да ни даде само оценката на играта. Т.е. вектор от вида (0, 0, 0, 0, R). Този празен ход трябва да премине към началната позиция, когато играта започва отначало.

При стандартния модел нещата ще са много по-сложни. Тогава състоянията ще са само позициите, при които белите са на ход, но ще трябва да се помни още и хода на противника довел до тази позиция. Тоест, състоянията ще са повече, защото позициите когато белите са на ход са два пъти по-малко, но ако всяка от тях може да се получи по средно 100 начина (от 100 различни позиции с 100 различни хода на противника), тогава, като теглим чертата получаваме, че стандартния модел ще има 50 пъти повече състояния.

Както казахме, при стандартния модел настоящето се налага да се помни, а в двойния не се налага. Да видим как стои въпросът с бъдещето. Ако играем шах срещу детерминиран противник, то тогава и двата модела ни дават детерминиран граф. Нека допуснем, че противника е недетерминиран и че за всяка позиция има по няколко възможни хода, които той може да изиграе. Тогава стандартния модел ни дава недетерминиран граф (един наш ход води до няколко различни ответни хода и съответните им позиции). Двойния модел пак си е детерминиран, защото нашия ход води до една определена позиция. От тази позиция излизат няколко възможни стрелки, които съответстват на възможните отговори на противника (ако противникът беше детерминиран щеше да излиза само една стрелка.)

Винаги ли двойния модел ни дава детерминиран граф? Не винаги, но винаги можем да го сведем до детерминиран. Да си представим същата игра, но сега няма да виждаме хода на противника, а само ще виждаме коя фигура е преместил. Тоест, няма да виждаме (x2, y2). Сега, когато знаем коя е фигурата, но не и къде е преместена, ще имаме няколко възможни позиции. Естествено би било да представим тази игра с недетерминиран граф, но можем да го направи и с детерминиран граф. Ако състоянието на света не е конкретна позиция на дъската, а е множество от възможни позиции, тогава на конкретния ход ще отговаря една единствена стрелка, която ще води до множество от възможни позиции. Тоест, при първия (недетерминирания) вариант света знае нещо повече за бъдещето, отколкото при втория. При детерминирания вариант света не знае коя точно е позицията. Знае кое е множеството от възможните позиции, а коя е точно позицията ще разбере по-късно когато това проличи по входа (по наблюденията). Това е като с писмото. В единия случай света знае какво пише в писмо, а във втория случай ще реши какво пише чак когато ти отвориш писмото.

Минимален модел


Един двоен модел на света ще го наричаме минимален, ако света знае за миналото и бъдещето само толкова колкото му е необходимо. При минималния модел, ако две състояния са еквивалентни спрямо бъдещето, то те съвпадат. Тоест, не се помни нищо от минало, което не ни е нужно, за да определим бъдещето. Освен това, минималния модел е детерминиран граф. Тоест, всяко нещо за бъдещето се разбира чак когато му дойде времето (когато то повлияе на наблюдението, но не по-рано).

Минимален модел не значи с най-малко състояния. Спрямо миналото минималността действително намалява състоянията, но спрямо бъдещето по-скоро ги увеличава (защото преминаваме от конкретни възможности към множества от конкретни възможности).

Процедурата по детерминизация винаги може да се приложи и винаги можем да получим детерминиран граф. Това, че графа е детерминиран не означава, че агента е детерминиран или че света е детерминиран. За да бъде агента детерминиран, трябва да няма разклонения в четните състояния, а за да бъде света детерминиран трябва да няма разклонения в нечетните състояния. Това, че графа е детерминиран означава, че състоянията знаят за бъдещето минималното. (Ако две състояния са различни, то те имат различно минало. Т.е. различни са защото имат различно минало, а не защото знаят нещо повече за бъдещето.)

Тук под детерминиран агент имахме предвид, че е принуден да играе детерминирано, защото има само един коректен ход. Обикновено под детерминиран агент разбираме такъв, който играе детерминирано без да е принуден да го прави.

Тотален модел


Когато един ход е некоректен стрелката по този ход просто липса и този ход просто не може да бъде направен. Бихме искали агента да може да пробва некоректните ходови и като ги пробва нищо да не се случи. Т.е. той да получи информация, че хода е некоректен, но да остане в същото състояние.

Тази цел ще я постигнем като добавим към всяко четно състояние (при което има некоректни ходове), по едно допълнително нечетно състояние (виж фигура 3). Всички некоректни ходове от четното състояние ще ги насочим към нечетното. От там ще се върнем обратно с една стрелка с етикет „bad. Този етикет ще е един специален нов вектор, който сме добавили за целта и който ще получаваме като вход само когато опитаме некоректен ход.

Figure 3

На фигура 3 възможните ходове са отбелязани със стрелки с червен, син и зелен цвят. В състоянието s0 има два некоректни хода, а в състоянието s4 има само един. В състоянието s2 няма некоректни ходове и затова за него не сме добавили допълнително нечетно състояние.

По този начин ще получим един тотален модел, при който всички ходове могат да се пробват, но коректните ходове реално променят състоянието на света, докато некоректните само дават информация, че са некоректни. Тоест, получаваме един нов тотален модел, който описва същия свят като предишния модел, с тази разлика, че некоректните ходове вече могат да се пробват.

Максимален модел


След като имаме минимален модел, може би има и максимален. Това трябва да е модела, при който състоянието знае всичко за миналото, всичко за това кои са коректните ходове и всичко за бъдещето.

Да знаем всичко за миналото е лесно, просто когато вървим назад (срещу стрелките) не трябва да има разклонения. Тоест, ако модела има формата на дърво, тогава състоянието ще знае всичко за миналото (тръгвайки от него назад ще можем да възстановим цялата история).

Да знае състоянието кои са некоректните ходове също не е трудно, защото това е крайна информация, която лесно ще добавим.

За да знаем всичко за бъдещето, трябва да няма недетерминираност. Тоест, ако хвърлим зар, трябва да знаем какво ще се падне. Ще построим модел, при който цялата недетерминираност ще е концентрирана в началното състояние. След като изберем началното състояние (по недетерминиран начин) нататък всичко ще е детерминирано.

Нека вземем дървото на всички достижими състояния. (Това е дърво, ако има еквивалентни състояния не ги сливаме в едно.) Ще детерминираме това дърво, макар това последното да не е задължително. От така полученото дърво ще получим всички стратегии на света. Това са поддървета, в които няма разклонения по наблюдението, а разклоненията по действията се запазват. Тези дървета са много (the cardinality of the continuum). От всичките тези дървета правим модел, където началните състояния ще са корените на всичките тези дървета.

Тук думата стратегия не е много подходящо да се използва, защото казваме стратегия, когато имаме някаква цел. Тук предполагаме, че агента има цел, а света няма цел. Ако предположим, че целия свят се опитва да ни помогне или да ни попречи, то това би било твърде егоцентрично. Въпреки това, ще предполагаме, че в света има агенти, които имат своите цели. Тоест, света няма цел, но въпреки това различните поведения на света ще наричаме стратегии.

Следователно направихме модел, който се състои от всички стратегии на света. Още преди да започне живота света избира по случаен начин една от стратегиите си и я следва до края на живота. Идеята е, още преди да започне играта да намислим как ще играем. Можем да намислим, че ако той ни играе с коня, ние ще отговорим с офицера и т.н. Едно такова намисляне представлява стратегия и се изразява с едно безкрайно дърво. Тези дървета са неизброимо много. Може да си намислим, че ще играем използвайки определена детерминирана програма. По този начин ние може да си намислим някоя изчислима стратегия, а те са само изброимо много.

Полученият модел е еквивалентен на модела, от който тръгнахме, защото всяка история, която е възможна при единия модел е възможна и при другия. При новия модел света се държи детерминирано, с изключение на първия момент, когато избираме началното състояние.

В този свят, ако вземем произволно състояние, то то знае почти всичко за бъдещето, с изключение на това, че не знае какво действие ще избере агента. Бихме искали да направим модел, при който дори и това да се знае от състоянието на света.

Тук има един проблем. Обикновено предполагаме, че света е даден, а агента е произволен. Тоест, няма как света да знае какво ще направи агента, защото той си няма идея кой агент ще му се падне. Сега ще предположим, че агента е фиксиран и че света би могъл да знае нещо за агента. Например, света би могъл да знае, че в определена ситуация агента няма да изиграе определен ход, макар че този ход е коректен и би могъл да бъде изигран. Това, че определен ход няма да бъде изигран от агента ще го отбележим с липсваща стрелка в графа на модела.

Сега ще предположим, че още преди да започне живота света и агента са решили как да играят. Тоест, избрали са своята стратегия, която ще следват до края на живота на агента. Това може да се опише с наредена двойка от две безкрайни дървета или чрез един безкраен път в дървото, защото резултата от прилагането на две фиксирани стратегии е един фиксиран път.

Така получихме максималния модел на света. Той се състои от всички възможни животи (това са пътища в дървото на достижимите състояния). Единственото, което ни липсва, това е информацията за некоректните ходове. За целта ще добавим примки (loops), както направихме, когато правехме модела да е тотален. Тук няма да получим тотален модел, защото ще добавим примки само по некоректните ходове, а не по всички липсващи стрелки. Така получаваме модела изобразен на фигура 4. (При s2 няма примка, защото от това състояние не излизат некоректни ходове)

Figure 4

На тази фигура е изобразен само един живот, а не всички възможни животи, които са част от максималния модел. Нас ни интересува само един живот и това е живота, който живеем. Затова може да предполагаме, че максималния модел съдържа само един живот и това е живота, който ни интересува. По този начин ще загубим еквивалентността с първоначалния модел, но получения модел е това, което ни трябва, защото другите възможни животи не са важни.

В така получения максимален модел от всяко състояние може да се възстанови цялата история и дори целия живот. Пътищата напред и назад са без разклонения. Примките, които добавихме, няма да ги броим за разклонения, защото символа bad не се среща при наблюденията след коректен ход. Тук състоянието знае кои ходове са некоректни, но не знае кои от тях агента е пробвал. Тази информация не е важна за света, защото от нея не зависи нито миналото нито бъдещето. Разбира се, тази информация е важна за агента, защото той може да не знае кои ходове са некоректни и затова му е полезно да знае кои ходове вече е пробвал.

Заключение


Опитваме се да разберем света, тоест да намерим неговия модел. Проблемът е, че този модел въобще не е единствен. Може да имаме недостижими и еквивалентни състояния, но това не е проблем. Може да има части на света, които никога не сме посещавали и които никога няма да посетим. Например, има ли живот на Марс? След като никога не сме ходили там и никога няма да отидем, то това е без значение (тоест, това няма да се отрази на нашия живот).

Най-същественият проблем е, че имаме модели, в които света знае повече и модели при които света знае по-малко. Кой модел търсим? Отговорът е, че търсим максималния модел. Тоест, ние ще се стремим максимално да разберем миналото и максимално да предскажем бъдещето. Ще се опитаме да предскажем дори и собственото си поведение. Ние сме част от света и за да го разберем трябва да се опитаме да предскажем дори и собственото си поведение.

За да опишем максималния модел ние ще използваме така наречения разширен модел. В този модел ще представим състоянието на света като вектор с огромен брой координати (хиляди или дори безбройно много). От теоретична гледна точка, те ще са безбройно много, но на практика ще изберем само най-интересните от тях.

Първите координати, които ще сложим във вектора описващ разширеното състояние, това ще е какво виждаме в момента. При двойния модел наблюдението не е функция на състоянието на света, защото, ако състоянието е четно, то може да има много стрелки с различни наблюдения, които да влизат в него. Ако състоянието е нечетно, то съответно може да има много стрелки, които да излизат от него. Тук обаче говорим за максималния модел и в него винаги има само една влизаща и една излизаща стрелка. Тоест, при максималния модел какво виждаме в момента се определя от състоянието на света.

Към това което виждаме в момента ще добавим още тестовите свойства на различни тестове. Това не са резенчетата от краставица, които са нещо реално. Тава са измислените краставици, които ние сме измислили на базата на реалните резенчета. Тоест, разширения модел няма да е нещо реално, а ще е нещо измислено.

Въпрос: Ако имаме Full Observability, тогава има ли нужда да добавяме тестови свойства към вектора на състоянието на разширения модел? Отговор: Да има нужда, защото при Full Observability ние знаем кое е състоянието на света, но това е състоянието при някой модел, който не е максималният. Ако имаме Full Observability с максимален модел, то света е толкова елементарен, че чак не е интересен.

Как да измислим едно тестово свойство? Помислете си за свойството „заключена ли е вратата“. Пробваме и получаваме ту „заключено“, ту „отключено“. Много трудно е да направим модел и да разберем кога е заключено и кога отключено. Много по-разбираемо би било, ако допуснем, че имаме не една, а много врати. Тогава трябва да имаме идея пред коя врата сме застанали в момента. В този модел може някои врати да са постоянно отключени, други постоянно заключени, а трети да променят състоянието си по някакви правила. В този случай няма да добавим към разширения модел една координата, която да отразява едно тестото свойство. Ще добавим много координати, по една за всяка врата (която да отразява свойството на вратата) и една координата, която да отразява пред коя врата сме в момента. Това представяне в [3] беше наречено тестово състояние.

Пред коя врата сме застанали в момента се определя от събитийните модели, които ще разгледаме в следващата статия.

References


[1] Dimiter Dobrev (2013). Giving the AI definition a form suitable for engineers. April, 2013. arXiv:1312.5713.

[2] Dimiter Dobrev (2017). Incorrect Moves and Testable States. Thin version in International Journal “Information Theories and Applications”, Vol. 24, Number 1, 2017, pp.85-90. Full version at viXra:1705.0108.

[3] Dimiter Dobrev (2017). How does the AI understand what’s going on. International Journal “Information Theories and Applications”, Vol. 24, Number 4, 2017, pp.345-369.

[4] Dimiter Dobrev (2018). The IQ of Artificial Intelligence. Jun 2018. arXiv:1806.04915.