Abstract:
Method and apparatus for selecting an optimized subset of trajectories from an available class of potential trajectories in a velocimetry application. In an exemplary method, a neural network is constructed wherein each neuron in the network represents a trajectory in the overall class. A binary output of each neuron indicates whether the object represented by the neuron is to be selected. In the exemplary method, the neural network is in an initially converged state. The network is then alternately excited and constrained so that it settles to additional converged states. During excitation, correction factors including a parameter-optimizing term are applied to neuron input potentials. During constraint, the parameter-optimizing terms are interrupted. Each time the network converges, the outputs of the neurons in the network are decoded to establish a subset of trajectories to be selected, and a value for an optimization parameter associated with the established subset is computed. The excitation and constraint phases are repeated in an attempt to establish subsets of trajectories having superior optimization parameter values. Once the excitation and constraint phases have been repeated a suitable number of times, the trajectories identified in a subset of objects having a superior optimization parameter value are selected. In exemplary embodiments, neurons are updated in a novel block-sequential fashion.

Description:
DESCRIPTION 
     1. Technical Field 
     The present invention relates to a process and a device for the extraction of a subset of objects optimizing a measurement and using a neural network. 
     2. Prior Art 
     Neuromimetic networks have been widely studied for many years and various applications have been developed, particularly for the resolution of shape recognition and optimization problems. 
     Neuromimetic networks use a digital information and are systems performing calculations based on the behaviour of physiological neurons. A neuromimetic model is characterized by three basic parts, i.e. a network of formal neurons, an activation rule and evolution dynamics. 
     The network is formed from a set of formal neurons. A formal neuron is an arithmetic unit constituted by an input, called potential (designated u) and an output, corresponding to a digital activation level (called p). At each instant, the activation level of each neuron is communicated to other neurons. Thus, the neurons are connected together by weighted connections, called synaptic weights. The weight of the connection between the output of the neuron i and the input of the neuron j is designated w ij . The total activation quantity at the input u j  received by the neuron j from the other neurons at each instant is used by said neuron to update its network. It is sometimes called the potential (or activation potential) of the neuron j. The activation rule of a neuromimetic network is a local procedure followed by each neuron on updating its activation level as a function of the activation context of the other neurons. Thus, the output of a neuron is given by a non-linear transfer function applied to the potential. This non-linear function can be a threshold function, which is also known as the MacCullogh and Pitts function and defined by the neuron i considered at the date t, by: ##EQU1## The evolution dynamics constitutes the rule permitting the updating of neurons. At the outset (t=0), the outputs of neurons are drawn at random (0 or 1) and then the network evolves by updating its neurons. In order to update a neuron i at instant t, its potential at said date is calculated: 
     
         u.sub.i (t)=u.sub.i (t-1)+Δu.sub.i (t)               (2) 
    
     The potential variation Δu i  (t) will correspond to the evolution dynamics. Different models exist in the prior art for defining said dynamics. According to the sign of Δu i  (t) between two updatings of the neuron i, it is said that the neuron is inhibited (negative potential variation tending to bring the output to 0) or excited (positive potential variation tending to bring the output to 1). If its potential is strictly positive, the neuron places its output at 1 and it is activated. If its potential is strictly negative it places its output at 0 and is deactivated. If its potential is 0, the value of the output remains unchanged. Thus, the output of neuron i can be induced to change between two updatings. It is said that the network has converged if, for each neuron, no updating modifies the potential of the neuron. The convergence mode is defined by the order in which the neurons are updated. Its choice is of great importance for the quality of the convergence. The convergence mode can be: 
     asynchronous: one neuron is updated at once, the new output calculated during its updating being used for the updating of the other neurons and the neurons can be sequentially updated in a fixed order (reference is then made to sequential asynchronous mode) or in random manner (reference is then made to random asynchronous mode); 
     synchronous: all the neurons are updated simultaneously; 
     synchronous by block: the neuron blocks are synchronously updated. 
     Certain evolution dynamics will now be given for solving the optimization problems. 
     The model used as a basis for the main neural optimization algorithms is the model presented by J. Hopfield and D. Tank in the article entitled &#34;Neural computation of decisions in optimization problems&#34; (Biological Cybernetics, vol. 52, pp. 141-152, 1985). They define an energy function E: ##EQU2## 
     The neural outputs p i  are analog between 0 and 1 and I i  represents an input bias. This energy can be seen as the physical energy of a spin glass system. As the energy E encodes the problem, the latter amounts to minimizing said energy at the convergence of the network. J. Hopfield in an article entitled &#34;Neural networks and physical systems with emergent collective computational abilities&#34; (Proceedings of the National Academy of Sciences vol. 79, pp. 2554-2558, 1982) demonstrates in the Hopfield theorum that: 
     if the evolution dynamics of the network are: ##EQU3## if the activation rule used is that of MacCullogh-Pitts, and if the matrix of the synaptic weights is symmetrical (w ij  =w ji ), 
     then, for any neuron i and at any date t: ##EQU4## 
     Thus, the energy will decrease, during the evolution of the system, until it reaches a minimum. 
     In the prior art, the operator adjusts parameters in order to establish compromises between satisfying constraints and optimizing the measurement. 
     The process of the invention makes it possible to know if a solution is or is not related with the others. This knowledge guarantees both the satisfying of all the constraints linked with the considered application and the optimization of the measurement. 
     The object of the invention is to propose a process and a device for extracting a subset of objects obtained from a set, in pairs and related or not related and optimizing a measurement which can advantageously use an original neuromimetic network. 
     OBJECT OF THE INVENTION 
     The invention relates to a process for the extraction of a subset of objects, such as potential trajectories in a velocimetry application, optimizing a measurement, using a neural network, characterized in that it comprises the following stages: 
     a stage of constructing a recursive neural network from objects and relations between the objects by associating with each object the binary output of a formal neuron p i  (t) at a date t: 
     p i  (t)=1 the object belongs to the sought subset, p i  (t)=0 the object does not belong to the sought subset; 
     a stage of using an inhibiting process in order to obtain subsets of objects in pairs which are or are not related and for passing from one subset to another on trying to increase the quality of the solution; 
     a stage of initializing the output and the potential associated with each neuron; 
     a stage of recursive dynamic operation of the network; 
     a stage of choosing the best from among the listed subsets by comparing qualities. 
     Advantageously, the stage of initializing the output and the potential associated with each neuron is such that the output and potential associated with each neuron prove, for each neuron, the following conditions: 
     on the outputs of the neurons: if initialization takes place of a neuron i with an output representing 1 (activated neuron), then the neurons j corresponding to objects related to the object i (e ij  =1) must be deactivated: 
     
         (p.sub.i (t=0)=1)(∀jε{1 . . . N} e.sub.ij =1p.sub.j (t=0)=0) 
    
     on the potentials: 
     
         p.sub.i (t=0)=1u.sub.i (t=0)≧0 
    
     
         p.sub.i (t=0)=0u.sub.i (t=0)≦0 
    
     Advantageously in the case of seeking objects pairwise and related, the stage of initializing the output and the potential associated with each neuron is such that the output and the potential associated with each neuron prove, for each neuron, the following conditions: 
     on the outputs of neurons: on initializing a neuron i with an output representing 1 (activated neuron) then the neurons j corresponding to object not related with the object i (e ij  =0) must be deactivated: 
     
         (p.sub.i (t=0)=1)∀jε{1 . . . N} e.sub.ij =0p.sub.j (t=0)=0) 
    
     on the potentials: 
     
         p.sub.i (t=0)=1u.sub.i (t=0)≧0 
    
     
         p.sub.i (t=0)=0u.sub.i (t=0)≦0 
    
     Advantageously, the recursive dynamic operating stage for the network comprises an updating of the set of neurons of the network in a certain order (e.g. random or sequential) simultaneously considering the neurons of a block constituted by a neuron i (centre) and the neighbouring neurons j associated with the objects which are respectively related or not related therewith (neurons j for which e ij  =1 respectively e ij  =0) (reference is made to the blockwise synchronous convergence mode). In order to update this block, application simultaneously takes place to the potentials of the various neurons of the block corrections, which are dependent on the values of the outputs of the other neurons and relations existing between the objects, the mathematical expression of the correction to be applied to the potential of a neuron differing according to whether it is considered as the centre of a block or as neighbours of a centre of another block. The corrections are defined in such a way that as soon as a neuron i is activated, all the neurons j proving e ij  =1 or respectively e ij  =0 are deactivated at the same time. 
     The invention also relates to a device comprising a neural network incorporating: 
     a choice circuit for an integer i between 1 and N, a first table memory of the values of the outputs p i  of the neurons connected to the output of the choice circuit of an integer, a second table memory of the neighbours of each neuron connected to the output of the choice circuit of an integer, a third memory of relations between the objects connected to the input of the second memory, a fourth memory of potentials of neurons connected to the output of the second memory and to the output of the choice circuit of an integer, a fifth memory containing the current value of the quality function E to be optimized connected to the output of the first memory, a first computing circuit making it possible to compute the potential variation to be applied to the neuron i connected to the output of the choice circuit of an integer, to the output of the fifth memory, to the output of the third memory and to the output of the first memory, a second computing circuit making it possible to compute the potential variation to be applied to neighbouring neurons of the neuron i connected to the outputs of the choice circuit and the fifth, third and first memories, 
     a first adder receiving the outputs of the first computing circuit and the fourth memory and connected at the input to the fourth memory, at least one second adder receiving the outputs of the second computing circuit and the fourth memory and connected at the input to the fourth memory, at least two binary thresholding function circuits F respectively connected to the outputs of said two adders and to the input of the first memory. 
     This neural network is applicable to processes for the optimum control of means in time relating in general terms to: 
     velocimetry, 
     resolution of routing problems in telecommunications networks, 
     optimization of communications between satellites, 
     optimization of component arrangement geometry in CAD, 
     planning flight schedules, 
     planning industrial production. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates the different stages of the process according to the invention. 
     FIG. 2 illustrates the dynamic operating stage. 
     FIG. 3 illustrates a neural network associated with the device for performing the process of the invention. 
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     The lexicon at the end of the description forms part thereof. 
     In order to facilitate the description hereinafter will be given the case where subsets are sought pairwise which are not related. Obviously the invention also applies to seeking subsets of objects in pairs and which are related by substituting the matrix (1-e ij ) for the matrix (e ij ) of relations. 
     The process of the invention comprises several stages as illustrated in FIG. 1. 
     Use is made of a formal neural network able to determine a subset of objects in pairs, not related and of maximum quality, where the quality is measured by a random function E ({p i  }) of the outputs of the neurons. The following stages are involved: 
     construction of a recursive neural network from objects and relations between the objects associating with each object the binary output of a formal neuron p i  (t): 
     p i  (t)=1 the object belongs to the sought subset, p i  (t)=0 the object does not belong to the sought subset; 
     use of an inhibiting process in order to obtain subsets of objects in pairs and not related, passage taking place from one subset to another on attempting to increase the quality of the solution; 
     initializing the output and the potential associated with each neuron in such a way that they prove, for each neuron, the following conditions: on the outputs of the neurons: on initializing a neuron i with an output representing 1 (activated neuron), then the neurons j corresponding to objects related to the object i (e ij  =1) must be deactivated, 
     
         (p.sub.i (t=0)=1)(∀jε{1, . . . , N} e.sub.ij =1p.sub.j (t=0)=0) 
    
     on the potentials 
     
         p.sub.i (t=0)=1u.sub.i (t=0)≧0 
    
     
         p.sub.i (t=0)=0u.sub.i (t=0)≦0 
    
     recursive dynamic operation of the network: an updating of the set of neurons of the network takes place in a certain order (e.g. random or sequential) simultaneously considering the neurons of a block constituted by a neuron i (centre) and neighbouring neurons associated with the objects related with the object i (neurons j for which e ij  =1). 
     In order to update this block, simultaneous application takes place to the potentials of the neurons of the block corrections dependent on the values of the outputs of the other neurons and relations existing between the objects. The mathematical expression of the corrections to be applied to the potential of a neuron differs according to whether it is considered to be the centre of a block or as a neighbour of a centre of another block. The corrections are defined in such a way that as soon as a neuron i is activated, all the neurons j proving e ij  =1 are deactivated at the same time. 
     Dynamic operation generates subsets of objects in pairs and which are related, each of the subsets being associatable with a local maximum of the quality function. 
     Whenever the network has converged, following the decoding of the outputs of the neurons, a subset of objects in pairs and not related is obtained, which locally maximises the quality function. Each of these subsets is stored. Globally a list of solution subsets is obtained with a choice of the best from among the listed subsets by comparing qualities. 
     Recursive dynamic operation of said second neural network. 
     Updating takes place of the &#34;block&#34; of neurons (i and neurons j related to i) corresponding in synchronous manner (all the neurons of the block are simultaneously updated) considering the neuron i as being the &#34;centre&#34; of the block and the neurons j as the &#34;neighbours&#34; of the centre. 
     Thus, dynamic operation consists of scanning the set of blocks of neurons in a certain order (asynchronous dynamics) and updating the neurons of each block in synchronous manner, reference being made to synchronous dynamics by block or block-synchronous. 
     Determination of the correction to be applied to the potential u i  of a neuron i at a date t. 
     It differs as a function of whether the neuron whose potential is to be corrected is considered as being the centre of a block or as the neighbour of another centre. On considering a neuron block of centre i and neighbours V={j} (for any j in V, e ij  =1) at the date t, consideration is given to whether the neuron i is or is not activated: 
     if the neuron i is activated the block is left unchanged, if the neuron i is deactivated, the following stages are performed: storage takes place of the value of the measurement of the quality obtained at the date t-1:E ({p j  (t-1)}); 
     the following evolution of the network is tested, the neuron i is activated and the neighbouring neurons j deactivated if the latter were activated and from this is deduced the variation of the measurement of the corresponding quality ΔE ({p j  (t-1)}) 
     A) The correction to be applied to the potential of the neuron i includes a linear combination of two terms: 
     One term tends to excite the neuron i, if neuron i is deactivated, with a certain probability as a function of the optimization parameter ΔE ({p j  (t-1)}). For example, the excitation term may be given by: 
     
         max(0,ΔE ({p.sub.j (t-1)})), 
    
     
         (1-p.sub.i (t)).max(0,ΔE ({p.sub.j (t-1)})), 
    
     the results of a Metropolis conducted at a certain temperature in a simulated annealing method, or the results of a Creutz procedure conducted at a certain energy in a microcanonic annealing method. 
     Also, if the network has been updated less than a certain number of times since the last convergence of the network, then an inhibiting term is applied in an attempt to increase the quality of the subset of objects decoded at the next convergence of the network. Otherwise, an interruption process prevents the inhibiting term from being included in the correction applied to the potential of the neuron i. 
     For example, this inhibition can consist of: 
     inhibiting a certain number of neurons, fixed by the user and drawn at random, inhibiting a random number of neurons drawn in random manner, inhibiting neurons among those corresponding to objects incompatible with many others. 
     Globally, the network alternates pulsation phases (when the last inhibition is taken into account) and relaxation phases (when the interruption process stops the taking into account of the inhibition). During the relaxation phase the network converges. Once the network has converged, an inhibition is again applied (pulsation phase). Thus, the pulsation and relaxation phases are alternated a certain number of times fixed by the user (as a function of the time which he has for finding a solution and the quality of the solution which he seeks). At the end of each relaxation phase, i.e. at each convergence, the neurons having an output representing 1 encode a subset of objects in pairs and not related. 
     B) The correction to be applied to the neuron potential j neighbouring i at the date t is given by a term serving to inhibit the neuron j by a quality equal to the excitation received by the neuron i at the same date, e.g. the inhibition can be given by: 
     -e ij  max(0,ΔE ({p j  (t-1)})) if the excitation on i at t is max(0,ΔE ({p j  (t-1)})) 
     -(1-p i  (t)).max(0,ΔE ({p j  (t-1}) if the excitation on i is (1-p i  (t)).max(0,ΔE ({p j  (t-1)})). 
     Advantageously the potential of each neuron is limited between two values fixed by the user in order to accelerate convergence, e.g: 
     the potential between the values of the order of magnitude of the corrections to be applied to the potential when the neuron is updated is limited, the values of the potentials are limited between -10 - ∞ and 10 - ∞, so that any strictly negative correction to be applied to the potential of an activated neuron deactivates it and any strictly positive correction to be applied to the potential of a deactivated neuron activates it. 
     FIG. 3 gives a device associated with said neural network in the relaxation phase and comprising: 
     a first table memory 55 of the values of the outputs p i  of the neurons, a second table memory 56 lists neighbours of each neuron, a third memory 57 of relations between the objects, a fourth memory 58 of potentials of neurons, a fifth memory 67, a first computing circuit 59 making it possible to compute the potential variation to be applied to the neuron i, a second computing circuit 60 making it possible to compute the potential variation to be applied to neighbouring neurons of the neuron i, a first adder 61 receiving the outputs of the first computing circuit and the fourth memory, at least one second adder 62 receiving the outputs of the second computing circuit and the fourth memory, at least two thresholding function circuits with a binary memory F respectively connected to the outputs of said two adders. 
     In the case of a digital device, said different elements are connected (directly or indirectly) to a clock. 
     LEXICON 
     Object 
     An object is a potential trajectory in a velocimetry application. 
     Neuron 
     A neuron i is defined by a potential u i  and by a binary output p i . When, during dynamic operation of the network, the neuron is considered at the date t, then: 
     a calculation takes place of a correction Δu i  (t) to be applied to the potential u i  (t+1)=u i  (t)+Δu i  (t), 
     the output is updated: 
     
         if u.sub.i (t+1)&gt;0 then p.sub.i (t+1)=1 
    
     
         if u.sub.i (t+1)&lt;0 then p.sub.i (t+1)=0 
    
     activated neuron p i  =1 
     deactivated neuron p i  =0. 
     Relation 
     Expression of the incompatibility of two potential trajectories in a velocimetry application. 
     There is a set of objects from which it is wished to extract a subset proving a certain property based on relations between the objects. Considered in pairs, there is or is not a relation (resulting from an application) between the objects. If an object i is related to an object j, then e ij  =1, if not e ij  =0 (e ij ) is the matrix of relations between the objects. 
     Note: The process is the equivalent of seeking the largest subset of related objects. For this purpose it is sufficient to consider the related matrix (1-e ij ) and to use the process described in the present invention.