[go: up one dir, main page]

EP1588229A2 - Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes - Google Patents

Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes

Info

Publication number
EP1588229A2
EP1588229A2 EP04700118A EP04700118A EP1588229A2 EP 1588229 A2 EP1588229 A2 EP 1588229A2 EP 04700118 A EP04700118 A EP 04700118A EP 04700118 A EP04700118 A EP 04700118A EP 1588229 A2 EP1588229 A2 EP 1588229A2
Authority
EP
European Patent Office
Prior art keywords
input data
simplex
neural network
point
data record
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP04700118A
Other languages
English (en)
French (fr)
Other versions
EP1588229A3 (de
Inventor
Georg Mogk
Thomas Mrziglod
Peter HÜBL
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Bayer AG
Original Assignee
Bayer Technology Services GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Bayer Technology Services GmbH filed Critical Bayer Technology Services GmbH
Publication of EP1588229A2 publication Critical patent/EP1588229A2/de
Publication of EP1588229A3 publication Critical patent/EP1588229A3/de
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/08—Learning methods
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/08—Learning methods
    • G06N3/09—Supervised learning

Definitions

  • the invention relates to a method for checking whether an input data set is within the permissible working range of a neural network, and to a corresponding computer program product and system.
  • Neural networks are used for data-driven modeling, for example for physical, biological, chemical and technical processes and systems, cf. Babel.: Possible uses of neural networks in industry: Pattern recognition using supervised learning processes - with examples from traffic and medical technology, Expert Verlag, Renningen-Malmsheim, 1997. In particular, the areas of application of neural networks include process optimization, image processing, pattern recognition, robot control and medical technology.
  • a neural network Before a neural network can be used for forecasting or optimization purposes, it must be trained.
  • the weights of the neurons are usually adjusted using an iterative process based on training data, cf. Betzmann F .: Process modeling: Modeling of continuous systems with neural networks, website NN-Tool, www.baermann.de and Bärmann F .: Neural networks. Lecture notes. FH-Gelsenmaschinen, Department of Physical Technology, Department of Neuroinformatics, 1998.
  • DE 195 31 967 discloses a method for training a neural network with the non-deterministic behavior of a technical system.
  • the neural network is integrated into a control loop in such a way that the neural network outputs a manipulated variable to the technical system as an output variable and the technical system generates a controlled variable from the manipulated variable supplied by the neural network, which is supplied to the neural network as an input variable.
  • the manipulated variable is overlaid with a noise of known noise distribution before it is fed to the technical system.
  • Further methods for training neural networks are known from DE 692 28 412 T2 and DE 198 38 654 Cl.
  • EP 0 762 245 B1 also describes a method for the detection of faulty ones Predictions known in a neuromodel-based or neural process control.
  • a common disadvantage of these methods known from the prior art is that they can only provide information about the sensitivity of the model made available by the neural network with regard to variations in the training data. However, it is not possible to make a statement about the trustworthiness of a forecast created by the neural network.
  • the invention is therefore based on the object of providing a method which makes it possible to check whether an input data record lies in the permissible working range of a neural network. Furthermore, the invention is based on the object of creating a corresponding computer program product.
  • the present invention makes it possible to check an input data record for a neural network to determine whether it is within the permissible working range of the neural network
  • the invention is based on the knowledge that no structural information flows into neural networks, but rather only training input data sets are used which have been determined, for example, by measurement technology. Because of this, such models can only provide reliable forecasts in the areas in which the models have been trained.
  • Hybrid models can be extrapolated as an overall model, but for each individual data driven sub-component, that is, for the neural networks included in the hybrid model, the interpolation range must be checked.
  • the working area of a neural network is defined by the convex envelope spanned by the training input data records of the neural network.
  • a neural network has a number of inputs and a number of b outputs.
  • data records for the a input and the b output parameters are metrologically recorded.
  • the input parameters can be data relating to the raw materials used, their composition and / or parameters of the production system, such as pressures, temperatures and the like.
  • the resulting product properties are then measured for the output parameters, for example. In this way you get training data sets, each one
  • the following definition of the convex hull is used to determine the permissible working range:
  • P be a given, finite set of n points p ⁇ t ... j? n .
  • a point x i.e. a certain one
  • the immediate vicinity of the convex envelope is also still considered to be a permissible work area, since neural networks can still provide meaningful results even in the immediate vicinity of the convex envelope.
  • the working area is limited to the convex hull, since an exact statement about where the "immediate neighborhood" ends cannot be made. In particular for critical applications, for example relating to continuous production, the working area is therefore on the inside of the convex hull, with the external environment in the immediate vicinity of the convex hull from
  • the invention can be resorted to three fundamentally different, very efficient methods.
  • a simplex is first formed from a number of d + 1 non-collinear points from the set P, where d is the prostitute sion of the space spanned by P.
  • a point is then selected from inside this simplex.
  • the center of gravity of the simplex can be used, which is calculated from the corner points of the simplex. This point is referred to below as x 0 .
  • the distance [x, x 0 ] between the point x defined by the input data set and the point x selected from the simplex is considered. Then it is checked whether there is an intersection of the segment [x, x 0 ] with a facet of the simplex.
  • the facets are the "side surfaces" of the Simplex.
  • the test as to whether the formation of a further simplex, which includes a section of the segment [x, x 0 ], is carried out as follows: First the corner points of the facet, the is cut from the distance [x, x 0 ]. Then another point is selected from the set P. This can be any point that does not belong to the corner points of the facet.
  • this experimentally formed further simplex contains a section of the segment [x, x 0 ], then this experimentally formed further simplex is used as a simplex for a further iteration of the method.
  • the further point selected from P is replaced by another point in order to form a further simplex on a trial basis and in order to check again whether a section of segment [x, x 0 ] lies in the trial-formed simplex perform.
  • Simplex is possible that includes a section of the segment [x, x 0 ], ie x lies outside the convex hull.
  • a different geometric property of the convex envelope is used. This property reads:
  • a module for checking whether an input data record is in a permissible working range of the neural network is connected upstream of a neural network. If the system in question is a system with several neural networks and / or a system with rigorous model components, that is to say a so-called hybrid model, such a module is preferably connected upstream of each neural network of the system. If several neural networks are used, these modules can be linked with a logical "AND" in order to ensure that an input data record is within the permissible working range of all of these neural networks. This is particularly important in hybrid models.
  • FIG. 1 shows a flow diagram of a first embodiment of a method for checking whether an input data record lies in the convex envelope
  • FIG. 2 shows a development of the method in FIG. 1 for determining a further simplex
  • FIG. 3 shows a further embodiment of a method according to the invention for checking whether an input data record lies in the convex envelope
  • FIG. 4 shows a graphical illustration of the method in FIG. 3
  • Figure 5 shows another embodiment of the method for checking whether a
  • Input data record lies in the convex hull, based on a check whether there is a solution for the system of equations given by the analytical definition of the convex hull,
  • Figure 6 is a block diagram of an embodiment of an inventive
  • FIG. 1 illustrates a first embodiment of the method for checking whether an input data record lies in the convex envelope. This method starts from a point x 0 inside the convex hull and checks whether the distance [x, x 0 ] lies inside the convex hull.
  • x is the point determined by the input sentence and you want to know whether it is also inside the convex hull.
  • ⁇ ) : ⁇ ⁇ + c ⁇ ( .
  • x,: a convex linear combination for a point x t € conv (P) that is closer to x than x 0 . If one assumes the linear combination described above for xo, in which the highest d + 1 coefficients are not equal to 0, and one chooses the largest possible c, one obtains in this way the intersection of the segment [xo, *] with a facet of the simplex, which is spanned by the points from P belonging to the coefficients.
  • the algorithm delivers a convex linear combination to represent the point. If the point lies outside, d points are obtained by which a hyperplane E is determined, which separates the point set P from the point x. This means that all points of R d that lie on the same side of E as point x do not belong to the convex hull. can. This can be used in a multiple evaluation to significantly speed up the entire evaluation.
  • FIG. 1 One form of implementation of this method is illustrated in FIG. 1:
  • step 100 an input data record for which a forecast is to be created is entered.
  • This input data record for the neural network determines a point x.
  • step 101 a number of d + 1 non-collinear points from the
  • step 102 the index / is set to zero.
  • step 103 a simplex S 1 is formed from the points selected in step 101.
  • step 104 a point x, from the inside of the simplex S ; selected.
  • the center of gravity is calculated from the corner points of the Simplex S in order to obtain the point x t .
  • step 105 a distance [x / x] between x and x is defined.
  • step 106 it is checked whether an intersection x / + 1 of the distance [x / x] with a facet of the simplex S s lies between x and x. It is therefore checked whether, starting from x, starting on the straight line direction x, first x or a facet of the Simplex S is reached.
  • step 108 checks whether it is possible to find a further simplex S M in P which contains both the intersection x / + 1 and a section of the straight line g. If this is not possible, it is output in step 109 that x lies outside the convex hull.
  • Step 106 performed again with respect to the further simplex.
  • FIG. 2 shows a further development of the method of FIG. 1 for carrying out the test in step 108.
  • the corner points of the facet of S on which the intersection point x / + 1 lies are first determined in step 200.
  • a further point is selected from P which is not already a corner point of the facet of S, and which is not collinear with the corner points of the facet.
  • step 202 a simplex S 'is formed from the corner points and the further point from P.
  • step 203 it is checked whether the simplex S 'contains a section of the route [x / x]. If this is the case, in step 204 the further simplex S M sought is set equal to the simplex S '. This then also answers the question of whether it is actually possible to form such a Simplex S / + 1 . If the check in step 203 shows that the simplex S 'contains no section of the straight line g, it is checked in step 205 whether all the points in question from P have already been selected in step 201. If this is not the case, a further point from P is selected in step 201, which has not yet been selected in order to carry out a further iteration of the method.
  • step 206 If no simplex S ; +1 could be found even after “trying out” all the points in question from P, appropriate information is output in step 206. This also means that point x lies outside the convex hull.
  • a particular advantage of this embodiment is that the method always leads to a statement after a finite number of steps as to whether the input data record is in the convex envelope and thus in the work area or not.
  • FIG. 3 shows a further embodiment of a method for checking whether an input data record lies in the convex envelope. This procedure does not result directly from the definition of the convex hull as a linear combination of the support points. Rather, another geometric property of the convex hull is used here, which is also illustrated graphically in FIG. 4:
  • Ti pi - x are the location vectors of the data points in a coordinate system that originates from the data point to be examined.
  • the inequality can be queried to "greater”, since the normal vector -k represents the same hyperplane as k. Points on the facets of the convex envelope lead to a scalar product equal to 0 and are therefore part of the convex envelope.
  • An optimization method is preferably used for the search for a hyperplane.
  • the point to be examined lies outside the convex hull. No hyperplane for which ⁇ 0 applies can be found for points within the convex hull.
  • Various methods can be used as an optimization method, such as the MATLAB routine fminsearch, as well as the gradient method, a Levenberg-Marquard algorithm or an evolution strategy, which can also be used in combination with local methods.
  • a major advantage for the runtime behavior of the algorithm is that if a corresponding hyperplane has been found for a data point, this too - 17 -
  • FIG. 3 illustrates this method using a flow chart.
  • step 300 the input data record, that is the point, is entered.
  • Step 301 uses one or more of the methods mentioned to check whether there is a hyperplane which contains x and for which k - ⁇ > 0, i - l, ..., n applies, where k is the normal vector of the hyperplane being sought and r i is the difference vector between a point p t and x given by a training input data record.
  • step 302 If there is such a hyperplane, it follows in step 302 that x lies in the convex hull. In the opposite case, information is output in step 303 that x lies outside the convex hull.
  • the check in step 301 as to whether there is a suitable hyperplane is illustrated in FIG. 4.
  • the points p t located in the shaded area in FIG. 4 span a convex envelope 400.
  • the point x is outside the convex hull 400.
  • Between the point x and the points p t there are the difference vectors r t p l , - x.
  • a hyperplane 401 runs through x and is described by the normal vector k. Since all points p. the convex hull 400 on the same side of the
  • FIG. 5 illustrates a further method for checking whether an input data record x lies in the convex envelope.
  • Equation 3 we transform Equation 3 by multiplying it by a matrix M on both sides.
  • x: M -x.
  • R (,) is the transpose of the matrix R w . If all components of the coefficient vector ⁇ found in this way meet the constraints ⁇ , ⁇ 0, a convex linear combination has been found for the point x and the point x is therefore inside the convex hull. Otherwise, we set all coefficients that violate the constraint to zero for the rest of the procedure and try to correct the components that do not violate the constraint so that this step is compensated for. In practice, this is accomplished by eliminating all components that violate the constraint from the vector ⁇ and all the associated columns from the matrix P. We denote the smaller dimension vector obtained in this way and the matrix with fewer columns obtained with ⁇ (, + 1) and R (, + 1) .
  • the method comes to a result after a maximum of n steps.
  • FIG. 5 An embodiment of this method is illustrated in FIG. 5.
  • step 500 the index i is set to zero.
  • step 501 a starting value for the n-dimensional vector ⁇ ⁇ 0 'that fulfills the constraints is selected.
  • ⁇ t 11 n can be selected, for example.
  • step 502 the matrix M is calculated. Based on this, the matrix P ⁇ and the vectors and x ( ' ⁇ are calculated in step 503.
  • ⁇ ⁇ (0 + P ii) T ⁇ (x - x () ) is calculated in step 504.
  • step 508 the index is incremented to perform another iteration of the method.
  • FIG. 6 shows a block diagram of an embodiment of a system 600 according to the invention.
  • the input module 601 is linked to a module 602, which is used to check whether an input data record lies within the convex envelope of the neural network 603. This check is carried out, for example, according to one of the related to the
  • FIGS 1 to 5 described method or by another method.
  • the module 602 is linked to the neural network 603. If module 602 determines that an input data record lies within the permissible working range of the neural network, which is given by the convex envelope, this is input
  • system 600 can also include further neural networks (hybrid model), each of which is preceded by a module corresponding to the module 602.
  • hybrid model the results of the individual modules 602 must then be linked with a logical “AND”. This ensures that all neural networks of the hybrid model 600 for a specific input data record of the input module 601 can be operated in a permissible working range.
  • system 600 can also contain rigorous model components.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Biomedical Technology (AREA)
  • Biophysics (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Evolutionary Computation (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Molecular Biology (AREA)
  • Artificial Intelligence (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Complex Calculations (AREA)
  • Computer And Data Communications (AREA)
  • Input From Keyboards Or The Like (AREA)

Abstract

Die Erfindung betrifft ein Verfahren zur Prüfung, ob ein Eingabedatensatz in dem zulässigem Arbeitsbereich eines neuronalen Netzes liegt, mit folgenden Schritten:- Definition der konvexen Hülle, die von den Trainingseingabesätzen des neuronalen Netzes aufgespannt wird, und deren Umgebung als zulässigen Arbeitsbereich eines neuronalen Netzes.- Prüfung, ob der Eingabedatensatz in der konvexen Hülle liegt.

Description

Verfahren zur Ermittlung des zulässigen Arbeitsbereichs eines neuronalen
Netzes
Die Erfindung betrifft ein Verfahren zur Prüfung, ob ein Eingabedatensatz im zulässigen Arbeitsbereich eines neuronalen Netzes liegt, sowie ein entsprechendes Compute rogrammprodukt und System.
Aus dem Stand der Technik sind eine Vielzahl von Anwendungsmöglichkeiten für neuronale Netze bekannt. Neuronale Netze werden zur datengetriebenen Modellbildung zum Beispiel für physikalische, biologische, chemische und technische Vorgänge und Systeme eingesetzt, vgl. Babel .: Einsatzmöglichkeiten neuronaler Netze in der Industrie: Mustererkennung anhand überwachter Lernverfahren - mit Beispielen aus der Verkehrs- und Medizintechnik, Expert Verlag, Renningen- Malmsheim, 1997. Insbesondere gehören zu den Einsatzgebieten neuronaler Netze die Prozessoptimierung, Bildverarbeitung, Mustererkennung, Robotersteuerung und die Medizintechnik.
Bevor ein neuronales Netz zu Prognose- oder Optimierungszwecken eingesetzt werden kann, muss es trainiert werden. Dabei werden üblicherweise die Gewichte der Neuronen durch ein iteratives Verfahren anhand von Trainingsdaten angepasst, vgl. Bärmann F.: Prozessmodellierung: Modellierung von Kontianlagen mit neuronalen Netzen, Internetseite NN-Tool, www.baermann.de und Bärmann F.: Neuronale Netze. Skriptum zur Vorlesung. FH-Gelsenkirchen, Fachbereich Physikalische Technik, Fachgebiet Neuroinformatik, 1998.
Für das Training eines neuronalen Netzes eignet sich besonders das sogenannte back- propagation Verfahren. Ein weiterer Ansatz ist in dem Programm „NN-Tool 2000" implementiert. Dieses Programm ist kommerziell erhältlich von Professor Frank Bärmann, Fachhochschule Gelsenkirchen, Fachbereich physikalische Technik. Das entsprechende Trainingsverfahren ist auch in der Publikation „Neural Network", Volume 5, Seiten 139 bis 144, 1992, „On a class of efficient learning algorithms for neural networks", Frank Bärmann, Friedrich Biegler-König, beschrieben.
Aus der DE 195 31 967 ist ein Verfahren zum Training eines neuronalen Netzes mit dem nichtdeterministischen Verhalten eines technischen Systems bekannt. Das neuronale Netz wird dabei so in einen Regelkreis eingebunden, dass das neuronale Netz als Ausgangsgröße eine Stellgröße an das technische System abgibt und das technische System aus der von dem neuronalen Netz zugeführten Stellgröße eine Regelgröße erzeugt, die dem neuronalen Netz als Eingangsgröße zugeführt wird. Die Stell- große wird mit einem Rauschen von bekannter Rauschverteilung überlagert, bevor sie dem technischen System zugeführt wird. Weitere Verfahren zum Trainieren neuronaler Netze sind bekannt aus DE 692 28 412 T2 und DE 198 38 654 Cl.
Ferner ist aus dem Stand der Technik ein Verfahren zur Abschätzung der Vertrau- enswürdigkeit der von einem neuronalen Netz abgegebenen Prognose bekannt:
Protzel P.: Kindermann L., Tagscherer M., Lewandowski A. „Abschätzung der Vertrauenswürdigkeit von Neuronalen Netzprognosen bei der Prozessoptimierung", VDI Berichte NR. 1526, 2000. Aus der EP 0 762 245 Bl ist ferner ein Verfahren zur Erkennung von fehlerhaften Vorhersagen in einer neuromodellgestützten oder neuro- nalen Prozessregelung bekannt.
Ein gemeinsamer Nachteil dieser aus dem Stand der Technik bekannten Verfahren ist, dass diese lediglich eine Aussage über die Sensitivität des durch das neuronale Netz zur Verfügung gestellten Modells bezüglich Variationen der Trainingsdaten liefern können. Eine Aussage über die Vertrauenswürdigkeit einer von dem neuronalen Netz erstellten Prognose ist damit aber nicht möglich.
Aus F. Bärmann; Handbuch zu NN-Tool 98, 1998, ist ein Ansatz bekannt, bei dem versucht wird, den Prognosefehler an einer bestimmten Stelle mit Hilfe des bekann- ten Prognosefehlers an benachbarten Datenpunkten zu schätzen. Allen diesen Verfahren ist gemeinsam, dass keine Aussage darüber getroffen wird, ob ein Eingangsdatensatz überhaupt in dem zulässigen Arbeitsbereich des neuronalen Netzes liegt. Aber nur in diesem Fall ist eine Fehlerschätzung möglich.
Der Erfindung liegt daher die Aufgabe zu Grunde ein Verfahren zu schaffen, welches es erlaubt zu prüfen, ob ein Eingabedatensatz in dem zulässigen Arbeitsbereich eines neuronalen Netzes liegt. Ferner liegt der Erfindung die Aufgabe zu Grunde ein entsprechendes Computeφrogrammprodukt zu schaffen.
Die der Erfindung zu Grunde liegende Aufgabe wird jeweils mit den Merkmalen der unabhängigen Patentansprüche gelöst. Bevorzugte Ausführungsformen der Erfindung sind in den abhängigen Patentansprüchen angegeben.
Die vorliegende Erfindung ermöglicht es, einen Eingabedatensatz für ein neuronales Netz daraufhin zu überprüfen, ob er in dem zulässigen Arbeitsbereich des neuronalen
Netzes liegt. Die Erfindung geht von der Erkenntnis aus, dass in neuronale Netze keine strukturellen Informationen einfließen, sondern lediglich Trainingseingabedatensätze verwendet werden, die zum Beispiel messtechnisch ermittelt worden sind. Aufgrund dessen können solche Modelle nur in den Bereichen vertrauenswürdige Prognosen liefern, in denen die Modelle trainiert worden sind.
Zwischen den gegebenen Trainingsdatenpunkten kann mit solchen Modellen sehr effizient interpoliert werden. Im Unterschied zu entsprechenden rigorosen Modellen können datengetriebene Modelle aber nicht oder nur sehr eingeschränkt extrapolie- ren. Insbesondere für die Überwachung und/oder Steuerung kritischer Applikationen ist es daher von großem Vorteil, dass geprüft werden kann, ob das verwendete Modell in dem zulässigen Arbeitsbereich verwendet wird.
Dies gilt im verstärkten Maße auch für Hybridmodelle, bei denen es sich um eine Verschaltung mehrerer Neuronaler Netze mit rigorosen Modellen handelt. Hybridmodelle sind zwar als Gesamtmodell extrapolierfähig aber für jede einzelne daten- getriebene Teilkomponente, das heißt für die in dem Hybridmodell beinhalteten neuronalen Netze, muss der Interpolationsbereich überprüft werden.
Erfindungsgemäß wird der Arbeitsbereich eines neuronalen Netzes durch die von den Trainingseingabedatensätzen des neuronalen Netzes aufgespannte konvexe Hülle definiert. Beispielsweise hat ein neuronales Netz eine Anzahl von Eingängen und eine Anzahl von b Ausgängen. Zur Modellbildung werden Datensätze für die a Eingangs- und die b Ausgangsparameter messtechnisch erfasst.
Soll beispielsweise eine Modellbildung für einen Herstellungsprozess erfolgen, so kann es sich bei den Eingangsparametern um Daten hinsichtlich der verwendeten Grundstoffe, deren Zusammensetzung und/oder um Parameter der Produktionsanlage, wie zum Beispiel Drücke, Temperaturen und dergleichen handeln. Für die Ausgangsparameter werden dann beispielsweise die resultierenden Produkteigenschaften gemessen. Auf diese Art und Weise erhält man Trainingsdatensätze, die jeweils einen
Satz Eingangsparameter und zugehörige Ausgangsparameter beinhalten. Mit Hilfe dieser Trainingsdatensätze wird das neuronale Netz trainiert, das heißt die Gewichtungen der Neuronen werden iterativ angepasst.
Nach einer bevorzugten Ausführungsform der Erfindung kommt folgende Definition der konvexen Hülle als Festlegung des zulässigen Arbeitsbereichs zur Anwendung:
Es sei P eine gegebene, endliche Menge von n Punkten p\t...j?n. Die Punkte p, (für i=l,..., ) der Menge P werden durch die Trainingseingabedatensätze, mit denen das neuronale Netz trainiert worden ist, gebildet. Ein Punkt x , das heißt ein bestimmter
Eingabedatensatz, gehört zu der von P aufgespannten konvexen Hülle, die als conv(P) bezeichnet wird, wenn es reelle Zahlen λl ,...,λn > 0 mit λ1 +... + λn =l gibt, so dass gilt px +... + λnpn = x für pteP (für i=l,...,n). (Zur Theorie der konvexen Hüllen siehe auch: Dieter Jungnickel; Optimierungsmethoden; Springer, Heidelberg; 1999; ISBN: 3540660577) Nach einer bevorzugten Ausführungsform der Erfindung wird auch die unmittelbare Umgebung der konvexen Hülle noch als zulässiger Arbeitsbereich betrachtet, da neuronale Netze auch in der unmittelbaren Nachbarschaft der konvexen Hülle noch sinnvolle Ergebnisse liefern können. Alternativ wird jedoch der Arbeitsbereich unmittelbar auf die konvexe Hülle beschränkt, da eine exakte Aussage hierüber, wo die „unmittelbare Nachbarschaft" endet, nicht getroffen werden kann. Insbesondere für kritische Anwendungen, die beispielsweise die fortlaufende Produktion betreffen, wird daher der Arbeitsbereich auf das Innere der konvexen Hülle beschränkt, wobei die äußere Umgebung in der unmittelbaren Nachbarschaft der konvexen Hülle vom
Arbeitsbereich ausgeschlossen wird.
Bei der praktischen Anwendung, insbesondere bei zeitkritischen Applikationen, ist es von besonderer Bedeutung effiziente Vorgehensweisen zu verwenden, um festzu- stellen, ob ein Eingabedatensatz in dem zulässigen Arbeitsbereich des zugehörigen
Neuronalen Netzes liegt.
Aus der Literatur sind die Algorithmen Quickhull ( seihe C.B.Barber, D.P. Dobkin und H.T. Huhdanpaa; " The Quickhull Algorithm for Convex Hulls"; ACM Transaction Mathematical Software; Vol 22, No 4; 1996; ρ469-483, Simplex- Algorithmus) sowie der Simplex-Algorithmus (siehe z.B. Dieter Jungnickel; Optimierungsmethoden; Springer, Heidelberg; 1999; ISBN: 3540660577) an sich bekannt. Diese Verfahren sind in hochdimensionalen Räumen (d.h. Eingangsdimension größer als 9) ineffizient, weil sie extrem lange Rechenzeiten benötigen oder auf handelübli- chen Rechnern am Speicherbedarf scheitern. In bevorzugten Ausfuhrungsformen der
Erfindung kann dagegen auf drei grundsätzlich verschiedene, sehr effiziente Verfahren zurückgegriffen werden.
Nach einer bevorzugten Ausführungsform der Erfindung wird zur Prüfung, ob ein Eingabedatensatz in der konvexen Hülle liegt, zunächst ein Simplex aus einer Anzahl von d + 1 nicht kollinearen Punkten aus der Menge P gebildet, wobei d die Dirnen- sion des von P aufgespannten Raums ist. Aus dem Inneren dieses Simplex wird dann ein Punkt ausgewählt. Hierfür kann zum Beispiel der Schwerpunkt des Simplex verwendet werden, der aus den Eckpunkten des Simplex berechnet wird. Dieser Punkt wird im Folgenden mit x0 bezeichnet.
Im nächsten Schritt wird die Strecke [x, x0] zwischen dem durch den Eingabedatensatz definierten Punkt x und dem aus dem Simplex gewählten Punkt xobetrachtet. Dann wird geprüft, ob es einen Schnittpunkt der Strecke [x, x0] mit einer Facette des Simplex gibt. Bei den Facetten handelt es sich um die „Seitenflächen" des Simplex.
Wenn es einen solchen Schnittpunkt nicht gibt, bedeutet dies, dass der Punkt x im Inneren der konvexen Hülle liegt.
Ist das Gegenteil der Fall, so ergibt sich daraus, dass der Punkt x außerhalb des Simplex liegt. Damit ist aber noch nicht die Frage beantwortet, ob der Punkt x innerhalb oder außerhalb der konvexen Hülle liegt. Es wird daher geprüft, ob es möglich ist einen weiteren Simplex aus d + 1 nicht kollinearen Punkten aus der Menge P so zu bilden, dass der weitere Simplex den Schnittpunkt mit der Facette und einen Abschnitt der Strecke [x, x0] beinhaltet.
Wenn dies nicht möglich ist, ergibt sich daraus, dass der Punkt x außerhalb der konvexen Hülle liegt (Satz von Caratheodory). Wenn ein solcher Simplex gebildet werden kann, wird erneut die Prüfung durchgeführt, ob ein Schnittpunkt der Strecke [x, x0] mit einer Facette des weiteren Simplex existiert. Da es nur eine endliche Anzahl von Punkten in P gibt, kommt dieses Verfahren nach einer endlichen Anzahl von
Iterationen zu der Aussage, ob x in der konvexen Hülle liegt oder nicht, da alle Simplices nacheinander geprüft werden können.
Nach einer bevorzugten Ausführungsform der Erfindung wird die Prüfung, ob die Bildung eines weiteren Simplex, das einen Abschnitt der Strecke [x, x0] beinhaltet, möglich ist, wie folgt durchgeführt: Zunächst werden die Eckpunkte der Facette, die von der Strecke [x, x0] geschnitten wird, bestimmt. Dann wird ein weiterer Punkt aus der Menge P ausgewählt. Hierbei kann es sich um einen beliebigen Punkt handeln, der nicht zu den Eckpunkten der Facette gehört.
Aus dem weiteren Punkt und den Eckpunkten wird dann versuchsweise ein weiterer
Simplex gebildet. Wenn dieser versuchsweise gebildete weitere Simplex einen Abschnitt der Strecke [x, x0] beinhaltet, so wird dieser versuchsweise gebildete weitere Simplex als Simplex für eine weitere Iteration des Verfahrens verwendet.
Wenn ein solcher Abschnitt von der Strecke [x, x0] in dem versuchsweise gebildeten
Simplex nicht beinhaltet ist, wird der weitere aus P gewählte Punkt durch einen anderen Punkt ersetzt, um versuchsweise einen weiteren Simplex zu bilden und um die nachfolgende Prüfung, ob ein Abschnitt von Strecke [x, x0] in dem versuchsweise gebildeten Simplex liegt, erneut durchzuführen.
Dieses Verfahren wird solange durchgeführt, bis entweder ein weiterer Simplex aufgefunden worden ist oder alle in Frage kommenden Punkte aus der Menge P gewählt worden sind, ohne dass es zu der Bildung eines Simplex, der die Nebenbedingung erfüllt, einen Abschnitt der Strecke [x, x0] zu beinhalten, gekommen ist. In die- sem Fall endet das Verfahren mit der Aussage, dass keine Bildung eines weiteren
Simplex möglich ist, das einen Abschnitt der Strecke [x, x0] beinhaltet, also x außerhalb der konvexen Hülle liegt.
Nach einer weiteren bevorzugten Ausführungsform der Erfindung wird eine andere geometrische Eigenschaft der konvexen Hülle verwendet. Diese Eigenschaft lautet:
Existiert eine Hyperebene durch den zu untersuchenden Punkt x , so dass sich alle p, e P auf einer Seite der Ebene befinden, dann liegt der Punkt x außerhalb der durch P aufgespannten konvexen Hülle. (Satz von Hahn-Banach) Existiert keine solche Ebene, so liegt der Punkt im Innern. Nach einer weiteren bevorzugten Ausführungsform der Erfindung wird zur Beantwortung der Frage, ob ein Punkt x in der konvexen Hülle liegt oder nicht, geprüft, ob sich das durch die analytische Definition der konvexen Hülle gegebene Gleichungssystem lösen lässt. Hierzu wird von einem iterativen Verfahren Gebrauch gemacht.
Nach einer weiteren bevorzugten Ausführungsform der Erfindung wird einem neuronalen Netz ein Modul zur Prüfung, ob sich ein Eingabedatensatz in einem zulässigen Arbeitsbereich des neuronalen Netzes befindet, vorgeschaltet. Handelt es sich bei dem betreffenden System um ein System mit mehreren neuronalen Netzen und / oder um ein System mit rigorosen Modellanteilen, das heißt ein sogenanntes Hybridmodell, so wird vorzugsweise jedem neuronalen Netz des Systems ein solches Modul vorgeschaltet. Werden mehrere Neuronale Netze verwendet, können diese Module mit einem logischem „UND" verknüpft werden, um zu gewährleisten, dass ein Ein- gabedatensatz im zulässigen Arbeitsbereich aller dieser Neuronalen Netze liegt. Dies ist insbesondere bei Hybridmodellen von Bedeutung.
Im weiteren werden bevorzugte Ausführungsformen der Erfindung mit Bezugnahme auf die Zeichnungen näher erläutert. Es zeigen:
Figur 1 ein Flussdiagramm einer ersten Ausführungsform eines Verfahrens zur Prüfung, ob ein Eingabedatensatz in der konvexen Hülle liegt,
Figur 2 eine Weiterbildung des Verfahrens der Figur 1 zur Bestimmung eines weiteren Simplex,
Figur 3 eine weitere Ausführungsform eines erfindungsgemäßen Verfahrens zur Prüfung, ob ein Eingabedatensatz in der konvexen Hülle liegt,
Figur 4 eine grafische Veranschaulichung des Verfahrens der Figur 3, Figur 5 eine weitere Ausführungsform des Verfahrens zur Prüfung, ob ein
Eingabedatensatz in der konvexen Hülle liegt, basierend auf einer Prüfung, ob es eine Lösung für das durch die analytische Definition der konvexen Hülle gegebene Gleichungssystem gibt,
Figur 6 ein Blockdiagram einer Ausführungsform eines erfindungsgemäßen
Systems.
Die Figur 1 veranschaulicht eine erste Ausführungsform des Verfahrens zur Prüfung, ob ein Eingabedatensatz in der konvexen Hülle liegt. Dieses Verfahren geht von einem Punkt x0 im Inneren der konvexen Hülle aus und überprüft, ob die Strecke [x, x0] im Inneren der konvexen Hülle liegt.
Dabei ist x der durch den Eingabesatz bestimmte Punkt, von dem man wissen möchte, ob er ebenfalls im Inneren der konvexen Hülle liegt.
Dazu wird getestet, ob die Strecke [x, x0] eine der Facetten der konvexen Hülle schneidet. Ist dies der Fall, liegt der Punkt x außerhalb. Hierbei wird die geometrische Eigenschaft der konvexen Hülle ausgenutzt, dass jede geradlinige Verbin- düng zweier beliebiger Punkte der konvexen Hülle vollständig in der konvexen Hülle liegt.
Dieses Verfahren basiert auf der im Folgenden beschriebenen Vorgehensweise:
Gegeben sei ein d -dimensionaler Raum Rd, wobei d die Anzahl der nicht kollineareren Trainingseingabedatensätze des neuronalen Netzes ist. Die Punktmenge P beinhaltet sämtliche Trainingseingabedatensätze, mit denen das neuronale Netz trainiert worden ist. Diese Punktmenge P ist also vollständig in dem Raum Rd beinhalte Weiter sei ein Punkt x0 aus dem Inneren der konvexen Hülle, die von P aufgespannt wird, mit einer bekannten Darstellung als konvexe Linearkombination der Punkte aus P, gegeben, d.h. es gibt λ 0),...,λ > 0 mit λ<0) + ... + λ = 1 und
/i i + • • • + λ^pn = x0. Nach dem Satz von Caratheodory können die Koeffizienten λt (i =l,...,n) so gewählt werden, so dass alle bis auf d+1 gleich 0 sind. Weiter sei x e Rd ein Punkt, für den zu untersuchen ist, ob dieser im Inneren von conv(P) liegt oder nicht.
Es sei [x, xo] die Strecke zwischen den Punkten x und x0. Die bekannten Koeffizien- ten λ|0) (i =l,...,n) werden nun so modifiziert, dass eine Linearkombination mit den neuen Koeffizienten einen Punkt xι ergibt, der sich auf der Strecke [x0x] befindet. Dieser Vorgang wird so lange wiederholt, bis man schließlich den Punkt x trifft, oder auf eine der Seitenbegrenzungen der konvexen Hülle stößt.
Zur Modifikation der Koeffizienten λ[0) wird eine geeignete Lösung des folgenden unterbestimmten, linearen Gleichungssystems gesucht:
Gleichung 1 n JεiPi = x - x0
1=1
Anschließend wird ein Faktor c>0 so bestimmt, dass λf + cεt ≥ 0 für i =1,..., n gilt.
Man setze nun λ ) := λ } + cε( . Dann ist x, := eine konvexe Linearkombination für einen Punkt xt € conv(P) , der näher an x liegt als x0. Ist man für xo von der obenbeschrieben Linearkombination ausgegangen, in der höchsten d+1 Koeffizienten ungleich 0 sind, und wählt man das größt mögliche c, dann erhält man auf diese Weise den Schnittpunkt der Strecke [xo,*] n it einer Facette des Simplexes, der von den zu den Koeffizienten gehörenden Punkten aus P aufgespannt wird.
Das Gleichungssystem der Gleichung 1 ist jedoch nicht eindeutig lösbar, und nicht für jede Lösung kann ein c > 0 gefunden werden, das den oben aufgeführten Anforderungen genügt, um neue Koeffizienten λf* zu bestimmen.
Im Weiteren ist ein iteratives Verfahren angegeben, das eine Antwort auf die Frage ermöglicht, ob eine Lösung des Gleichungssystems existiert und damit der Punkt x in der konvexen Hülle liegt oder nicht:
Initialisierungsschritt: Es sei d die Dimension des Raumes, in dem die konvexe Hülle liegt. Um einen Startwert x0 zu bestimmen werden d beliebige linear unabhängige Punkte q 0) e P für j = \,...,d ausgewählt. Man wähle nun ein
als Startwert. Des Weiteren setzen wir i = 0.
Iterationsschritt: Durch die Punkte wird eine ( -l)-dimensionale Hyper- fläche im Rd eindeutig festgelegt. Diese Hyperfläche soll durch Hinz mahme eines weiteren Punktes aus der Menge P zu einem ci-dimensionalen Simplex ausgebaut werden. Es sei nun q^ e P der Punkt mit der Eigenschaft, dass das längste mögliche Teilstück der Strecke x c im Inneren des Simplex liege.
Um diesen Punkt herauszufinden, muss man mehrfach nahezu dasselbe Gleichungssystem lösen, was sich performant durchfuhren lässt. Ist es nicht möglich, einen weiteren Eckpunkt des Simplex zu finden, so befindet sich der Punkt x außerhalb der konvexen Hülle und das Verfahren kommt zum Abbruch. Im anderen Fall besitzt das Gleichungssystem
Σ«.
eine eindeutige Lösung (ε,,...,εrf+1) und es kann ein c >0 mit den oben beschriebenen Eigenschaften gewählt werden. Man setze nun
λ λj + cεJ
für j =1,..., d+1. Man kann c so wählen, dass entweder eines der λ^'+1) (für = 1,..., d+1) gleich 0 wird oder c =\ gilt. Tritt der Fall c =1 auf, so liegt der Punkt x im Inneren der konvexen Hülle und das Verfahren kann beendet werden.
Im anderen Fall muss ein weiterer Iterationsschritt durchgeführt werden. Als Punkte bei denen das jeweils zugehörige λ^'+1 (j=\,..., d +1) ungleich 0 sind. Anschließend wird i um 1 erhöht.
Liegt der Punkt x im Inneren der konvexen Hülle von P, so liefert der Algorithmus eine konvexe Linearkombination zur Darstellung des Punktes. Liegt der Punkt außerhalb, so erhält man d Punkte, durch die eine Hyperebene E bestimmt ist, welche die Punktmenge P von dem Punkt x trennt. Dies bedeutet, dass alle Punkte des Rd, die auf derselben Seite von E liegen wie der Punkt x, nicht zur konvexen Hülle gehö- ren können. Dies kann bei einer Mehrfachauswertung genutzt werden, um die gesamte Auswertung erheblich zu beschleunigen.
Eine Realisierungsform dieses Verfahrens ist in der Figur 1 veranschaulicht:
In dem Schritt 100 wird ein Eingabedatensatz, für den eine Prognose erstellt werden soll, eingegeben. Dieser Eingabedatensatz für das neuronale Netz bestimmt einen Punkt x .
In dem Schritt 101 wird eine Anzahl von d + 1 nicht kollinearen Punkten aus der
Menge P gewählt.
In dem Schritt 102 wird der Index /auf Null gesetzt. In dem Schritt 103 wird ein Simplex Sl aus den in dem Schritt 101 gewählten Punkten gebildet.
In dem Schritt 104 wird ein Punkt x, aus dem Inneren des Simplex S; gewählt. Beispielsweise wird der Schwerpunkt aus den Eckpunkten des Simplex S, berechnet, um den Punkt xt zu erhalten.
In dem Schritt 105 wird eine Strecke [x/x] zwischen x und x, definiert.
In dem Schritt 106 wird geprüft, ob ein Schnittpunkt x/+1 der Strecke [x/x] mit einer Facette des Simplex Ss zwischen x und x, liegt. Es wird also geprüft, ob man von x, ausgehend auf der Geraden Richtung x laufend zuerst x oder eine Facette des Simplex S, erreicht.
Wenn es einen solchen Schnittpunkt x;+1 der Strecke [x/x] mit einer Facette von S, gibt, bedeutet dies, dass der Punkt x nicht innerhalb des Simplex S, liegt. Ist das Gegenteil der Fall, so wird in dem Schritt 107 ausgegeben, dass x in der konvexen Hülle liegt, da ja festgestellt worden ist, dass x in dem Simplex S{ liegt und dieser wiederum vollständig innerhalb der konvexen Hülle liegt.
Liegt dagegen der Punkt x außerhalb des Simplex S, , so wird in dem Schritt 108 geprüft, ob es möglich ist, einen weiteren Simplex SM in P zu finden, der sowohl den Schnittpunkt x/+1 und einen Abschnitt der Geraden g beinhaltet. Wenn dies nicht möglich ist, wird in dem Schritt 109 ausgegeben, dass x außerhalb der konvexen Hülle liegt.
Im gegenteiligen Fall wird der Index / in dem Schritt 110 um Eins erhöht und der
Schritt 106 mit Bezug auf den weiteren Simplex erneut durchgeführt.
Die Figur 2 zeigt eine Weiterbildung des Verfahrens der Figur 1 zur Durchfuhrung der Prüfung in dem Schritt 108. Zur Durchführung dieser Prüfung werden in dem Schritt 200 zunächst die Eckpunkte der Facette von S, auf der der Schnittpunkt x/+1 liegt, bestimmt.
In dem Schritt 201 wird ein weiterer Punkt aus P gewählt, der nicht bereits ein Eckpunkt der Facette von S, ist und der nicht kollinear zu den Eckpunkten der Facette ist.
In dem Schritt 202 wird ein Simplex S' aus den Eckpunkten und dem weiteren Punkt aus P gebildet.
In dem Schritt 203 wird geprüft, ob der Simplex S' einen Abschnitt der Strecke [x/x] beinhaltet. Wenn dies der Fall ist, wird in dem Schritt 204 der gesuchte weitere Simplex SM gleich dem Simplex S' gesetzt. Damit ist dann auch die Frage beantwortet, ob es tatsächlich möglich ist, einen solchen Simplex S/+1 zu bilden. Wenn die Prüfung in dem Schritt 203 ergibt, dass der Simplex S' keinen Abschnitt von der Geraden g beinhaltet, wird in dem Schritt 205 geprüft, ob zuvor bereits alle in Frage kommenden Punkte aus P in dem Schritt 201 gewählt worden sind. Ist dies nicht der Fall, so wird in dem Schritt 201 ein weiterer Punkt aus P gewählt, der zu- vor noch nicht gewählt worden ist, um eine weitere Iteration des Verfahrens durchzuführen.
Wenn auch nach „Ausprobieren" sämtlicher aus P in Frage kommender Punkte kein Simplex S;+1 gefunden werden konnte, so wird in dem Schritt 206 eine entspre- chende Information ausgegeben. Dies bedeutet zugleich, dass der Punkt x außerhalb der konvexen Hülle liegt.
Von besonderem Vorteil bei dieser Ausfuhrungsform ist, dass das Verfahren in jedem Fall nach einer endlichen Anzahl von Schritten zu einer Aussage fuhrt, ob der Eingabedatensatz in der konvexen Hülle, und damit im Arbeitsbereich liegt oder nicht.
Die Figur 3 zeigt eine weitere Ausfuhrungsform eines Verfahrens zur Prüfung, ob ein Eingabedatensatz in der konvexen Hülle liegt. Dieses Verfahren ergibt sich nicht unmittelbar aus der Definition der konvexen Hülle als Linearkombination der Stützstellen. Vielmehr wird hier eine andere geometrische Eigenschaft der konvexen Hülle verwendet, die in der Figur 4 auch grafisch verdeutlicht ist:
Existiert eine Hyperebene durch den zu untersuchenden Punkt x, so dass sich alle pt&P auf einer Seite der Ebene befinden, dann liegt der Punkt x außerhalb der durch
P aufgespannten konvexen Hülle. Existiert keine solche Ebene, so liegt der Punkt im Innern.
Wird die Ebene durch den Normalenvektor k dargestellt, so lässt sich die Bedingung „alle Punkte pi P liegen auf einer Seite der Ebene" folgendermaßen ausdrücken: k-η > 0, i = l...n
wobei Ti =pi - x die Ortsvektoren der Datenpunkte in einem Koordinatensystem sind, welches den zu untersuchenden Datenpunkt im Ursprung hat.
Ohne Beschränkung der Allgemeinheit, kann die Ungleichheit auf „größer" abgefragt werden, da der Normalenvektor -k dieselbe Hyperebene darstellt wie k. Punkte auf den Facetten der konvexen Hülle führen zu einem Skalarprodukt gleich 0 und sind somit Bestandteil der konvexen Hülle.
Vorzugsweise wird für die Suche nach einer Hyperebene ein Optimierungsverfahren eingesetzt.
Dabei wird bei variierendem Normalenvektor k folgende Zielfunktion minimiert:
Ist das Optimum von F kleiner als 0, so liegt der zu untersuchende Punkt außerhalb der konvexen Hülle. Für Punkte innerhalb der konvexen Hülle lässt sich keine Hyperebene finden, für die <0 gilt.
Für den Einsatz als Optimierungsverfahren kommen verschiedene Verfahren in Betracht, wie zum Beispiel die MATLAB-Routine fminsearch, sowie das Gradien- tenverfahren, ein Levenberg-Marquard-Algorithmus oder eine Evolutionsstrategie, die auch in Kombination mit lokalen Verfahren eingesetzt werden kann.
Ein für das Laufzeitverhalten des Algorithmus wesentlicher Vorteil ist, dass wenn für einen Datenpunkt eine entsprechende Hyperebene gefunden worden ist, diese auch - 17 -
eine Lösung für alle Punkte auf der Seite der Ebene darstellt, welche der konvexen Hülle gegenüberliegt. Ist für mehrere Datenpunkte simultan die Untersuchung auf Zugehörigkeit zur konvexen Hülle durchzuführen, so kann das Verfahren hierdurch erheblich beschleunigt werden.
Die Figur 3 veranschaulicht dieses Verfahren anhand eines Flussdiagramms. In dem Schritt 300 wird der Eingabedatensatz, das heißt der Punkt , eingegeben.
h dem Schritt 301 wird mittels eines oder mehreren der genannten Verfahren ge- prüft, ob es eine Hyperebene gibt, die x beinhaltet und für die gilt k - η > 0 , i - l,...,n , wobei es sich bei k um den Normalenvektor der gesuchten Hyperebene handelt und bei ri um den Differenzvektor zwischen einem durch einen Trainingseingabedatensatz gegebenen Punkt pt und x .
Wenn es eine solche Hyperebene gibt, folgt daraus in dem Schritt 302, dass x in der konvexen Hülle liegt. Im gegenteiligen Fall wird in dem Schritt 303 eine Information ausgegeben, wonach x außerhalb der konvexen Hülle liegt.
Die Prüfung in dem Schritt 301, ob es eine geeignete Hyperebene gibt, ist in der Figur 4 veranschaulicht. Die in dem grauschraffierten Bereich der Figur 4 befindlichen Punkte pt spannen eine konvexe Hülle 400 auf. Der Punkt x befindet sich außerhalb der konvexen Hülle 400. Zwischen dem Punkt x und den Punkten pt befinden sich die Differenzvektoren rt = pl , - x .
Durch x verläuft eine Hyperebene 401, die durch den Normalenvektor k beschrieben wird. Da sich alle Punkte p. der konvexen Hülle 400 auf derselben Seite der
Hyperebene 400 befinden, folgt daraus, dass x tatsächlich außerhalb der konvexen Hülle 400 liegt. Die Figur 5 veranschaulicht ein weiteres Verfahren zur Prüfung, ob ein Eingabedatensatz x in der konvexen Hülle liegt.
Bei diesem Verfahren wird geprüft, ob es eine Lösung für das Gleichungssystem gibt, welches der analytischen Definition der konvexen Hülle entnommen ist.
Gleichung 2 λlp1 + ... + λ„pn = x λ, +. . + λn = l
Dabei wird nach einer Lösung gesucht, so dass die Nebenbedingungen λj > 0 erfüllt sind. Bei dem folgenden Verfahren wird sukzessive versucht dies zu erreichen.
Wie bei dem Verfahren der Figuren 1 und 2 wird auch in diesem Fall von einer An- fangslösung für λ(0 := (λf>,...,λf)) ausgegangen, für die im allgemeinen die Ungleichungsnebenbedingungen nicht erfüllt sind.
Wir schreiben im folgenden Gleichung 2 in Matrix Form. Man erhält dann
Gleichung 3
Pmλ = χ
wobei bei dem Vektor x und der Punktematrix R(0) jeweils eine Zeile mit Einsen zugefügt wurde.
Initialisierungsschritt
Wir setzen t-0 und wählen einen beliebigen n-dimensionalen Vektor λ(0) = (λ15.»A) itλι + - --+K = ι und λ > 0. Iterationsschritt
Als erstes transformieren wir die Gleichung 3, indem wir sie auf beiden Seiten mit einer Matrix M multiplizieren. Die Matrix Mist dabei so zu wählen, dass die Zeilen der Matrix P{,) :=M-P orthonormiert sind (sollte solch eine Matrix M nicht existieren, können abhängige Zeilen in der Matrix P® weggelassen werden). Weiter sei x :=M -x . Es wird nun nicht versucht das Gleichungssystem P^λ = x direkt zu lösen, sondern wir gehen von dem bekannten Koeffizientenvektor λ ,) aus und setzen x(,) := _Pwλw . Wir suchen nun nach einer Lösung des äquivalenten Gleichungs- Systems
pu . (λ -λ0)) = x-x{i) .
Da in den meisten Fällen dieses Gleichungssystem unterbestimmt ist, suchen wir nach der Lösung λ, so dass λ -λw minimal ist (wobei ||| die euklidische Norm
bezeichnet). Hierbei können wir ausnutzen, dass die Matrix R(, orthonormiert ist. Es gilt
λ = λU +pUT - (x-χU),
wobei R(,) die Transponierte der Matrix Rw ist. Falls alle Komponenten des so gefundenen Koeffizientenvektors λ die Nebenbedingungen λ, ≥ 0 erfüllen, so ist eine konvexe Linearkombination für den Punkt x gefunden worden und der Punkt x liegt daher im Inneren der konvexen Hülle. Andernfalls setzen wir alle Koeffizienten, welche die Nebenbedingung verletzen, für den Rest des Verfahrens auf Null und versuchen die Komponenten, welche die Nebenbedingung nicht verletzen, so zu korrigieren, dass dieser Schritt kompensiert wird. Praktisch bewerkstelligt man dies dadurch, dass sowohl alle Komponenten, welche die Nebenbedingung verletzen, aus dem Vektor λ als auch alle zugehörigen Spalten aus der Matrix P eliminiert werden. Den so erhaltenen Vektor kleinerer Dimension und die so erhaltene Matrix mit weniger Spalten bezeichnen wir mit λ(,+1) und R(,+1) .
Für die Korrektur muss das (kleinere) Gleichungssystem
P(/+1)λ = x
gelöst werden. Dafür führen wir nun einen weiteren Iterationsschritt aus, wobei wir i um eins erhöhen, diesmal mit λ ,+1) als Startwert. Lässt sich das Gleichungssystem nicht lösen, so existiert keine konvexe Linearkombination für den Punkt x und der
Punkt befindet sich außerhalb der konvexen Hülle.
Da bei jedem Iterationsschritt immer mindestens eine Spalte eliminiert wird, kommt das Verfahren nach maximal n Schritten zu einem Ergebnis.
Eine Ausfuhrungsform dieses Verfahrens ist in der Figur 5 veranschaulicht.
In dem Schritt 500 wird der Index i gleich Null gesetzt. In dem Schritt 501 wird ein Startwert für den n -dimensionalen Vektor λ^0' , der die Nebenbedingungen erfüllt, gewählt. Hierzu kann beispielsweise λt = 11 n gewählt werden.
In dem Schritt 502 wird die Matrix M berechnet. Darauf basierend erfolgt in dem Schritt 503 die Berechnung der Matrix Pω und der Vektoren und x('} .
Daraus wird in dem Schritt 504 λ = λ(0 + Pii)T ■ (x - x( ) ) berechnet.
In dem Schritt 505 wird geprüft, ob alle λt (j=l,..,ή)des in dem Schritt 504 berechneten Vektors λ ≥ 0 sind. Wenn dies der Fall ist, folgt daraus in dem Schritt 506, dass der durch den Eingabedatensatz gegebene Punkt innerhalb der konvexen Hülle liegt. Ist das Gegenteil der Fall, so werden in dem Schritt 507 alle Komponenten des Vektors λ und die entsprechenden Spalten der Matrix P*' , die die Nebenbedingung verletzten, gestrichen. Daraus resultiert das kleinere Gleichungssystem P(,+1)λ = x .
In dem Schritt 508 wird der Index inkrementiert, um eine weitere Iteration des Verfahrens durchzuführen.
Die Figur 6 zeigt ein Blockdiagram einer Ausführungsform eines erfindungsgemäßen Systems 600. Das System 600 hat ein Eingabemodul 601 zur Eingabe eines Eingabedatensatzes, der in dem hier betrachteten Beispiel aus a= 3 Parametern besteht.
Das Eingabemodul 601 ist mit einem Modul 602 verknüpft, welches zur Prüfung dient, ob ein Eingabedatensatz innerhalb der konvexen Hülle des neuronalen Netzes 603 liegt. Diese Prüfung erfolgt beispielsweise nach einem der mit Bezug auf die
Figuren 1 bis 5 geschilderten Verfahren oder nach einem anderen Verfahren.
Das Modul 602 ist mit dem neuronalen Netz 603 verknüpft. Wenn das Modul 602 feststellt, dass ein Eingabedatensatz in dem zulässigen Arbeitsbereich des neuronalen Netzes liegt, der durch die konvexe Hülle gegeben ist, erfolgt eine Eingabe dieses
Eingabedatensatzes in das neuronale Netz 603, welches dann zumindest einen Prognosewert an seinem Ausgang 604 abgibt. Stellt das Modul 602 dagegen fest, dass der Eingabedatensatz nicht in dem zulässigen Arbeitsbereich liegt, so wird an dem Ausgang 605 ein entsprechendes Signal abgegeben, wonach für den aktuellen Eingabe- datensatz keine zuverlässige Prognose möglich ist.
Neben dem neuronalen Netz 603 kann das System 600 noch weitere neuronale Netze beinhalten (Hybridmodell), denen jeweils wiederum ein dem Modul 602 entsprechendes Modul vorgelagert ist. Die Ergebnisse der einzelnen Module 602 müssen dann mit einem logischen „UND" verknüpft werden. Dadurch wird sichergestellt, dass alle neuronalen Netze des Hybridmodells 600 für einen bestimmten Eingabe- datensatz des Eingabemoduls 601 in einem zulässigen Arbeitsbereich betrieben werden. Daneben kann das System 600 auch noch rigorose Modellanteile beinhalten.
Bezugszeichenliste
konvexe Hülle 400
Hyperebene 401 System 600
Eingabemodul 601
Modul 602 neuronales Netz 603
Ausgang 604 Ausgang 605

Claims

Patentansprttche
1. Verfahren zur Prüfung, ob ein Eingabedatensatz in einem Arbeitsbereich eines neuronalen Netzes liegt, mit folgenden Schritten:
Speicherung von Trainingseingabedatensätzen für das neuronale Netz, wobei durch die Trainingseingabedatensätze eine konvexe Hülle aufgespannt wird,
- Prüfung, ob der Eingabedatensatz in der konvexen Hülle liegt.
2. Verfahren nach Anspruch 1 mit folgenden weiteren Schritten:
Auswahl von einer Anzahl (d + l) nicht kollinearer Punkte aus der Menge der Trainingseingabesätze,
Bildung eines ersten Simplex ( Si ) aus den gewählten Punkten,
Auswahl eines Punktes (x, ) aus dem Inneren des Simplex (S ) ,
Definition einer Strecke zwischen dem Eingabedatensatz und dem gewählten Punkt,
Prüfung, ob ein Schnittpunkt (x/+I ) der Strecke mit einer Facette des ersten Simplex existiert,
Prüfung, ob ein zweiter Simplex (S/+1 ) aus der Anzahl von Punkten aus den Trainingseingabedatensätzen gebildet werden kann, der den Schnittpunkt und einen Abschnitt der Strecke beinhaltet. Verfahren nach Anspruch 2, wobei für die Durchführung der Prüfung, ob es möglich ist, einen zweiten Simplex zu bilden, folgende Schritte durchgeführt werden:
Bestimmung der Eckpunkte der Facette des ersten Simplex auf der der Schnittpunkt liegt,
Wahl eines weiteren nicht kollinearen Punkts aus der Menge der Trainingseingabedatensätze,
Bildung eines Simplex (S') aus den Eckpunkten und dem weiteren Punkt,
Prüfung, ob der Simplex einen Abschnitt der Geraden beinhaltet und Ausgabe des Simplex als zweiten Simplex, wenn dies der Fall ist,
Austausch des weiteren Punkts gegen einen anderen nicht kollinearen Punkt aus der Menge der Trainingseingabedatensätze und erneute Prüfung.
Verfahren nach einem der vorhergehenden Ansprüche 1 bis 3, wobei geprüft, wird, ob es eine Hyperebene gibt, die den Eingabedatensatz beinhaltet, so dass sich alle Trainingseingabedatensätze auf einer Seite der Hyperebene befinden.
Verfahren nach Anspruch 4, wobei zur Prüfung, ob eine Hyperebene existiert ein Minimum von F gesucht wird, wobei
und wobei die Hyperebene durch den Normalenverktor k dargestellt wird und rt = pl — x wobei x der durch den Eingabedatensatz definierte Punkt ist.
6. Verfahren nach einem der vorhergehenden Ansprüche 1 bis 5 mit folgenden weiteren Schritten:
Wahl eines initialen Vektors λ = (λl,...:^λn) mitλ, +... + λn = 1 und
λ > 0 (j=l,..,ή), wobei vorzugsweise λ = — gewählt wird, n
- Wahl einer Matrix M so, dass die Zeilen der Matrix P(, := -PW orfhonormiert sind,
Berechnung von λ = λ{,) + Pi, • (x - x(,)) , wobei xw := P(,)λw ,
- Prüfung ob alle λ} ≥ 0 sind (füry-1,...,«),
Streichung aller Komponenten aus der Matrix ^ und aus dem Vektor AΛ', die die Nebenbedingung λ} ≥ 0 (für/=l,...,«) verletzten,
- erneute Berechnung von λ .
7. System zur Ermittlung von zumindest einem Prognosewert mit
zumindest einem neuronalen Netz, welches mit Hilfe einer Menge von Trainingseingabedatensätzen trainiert worden ist, Mitteln zur Prüfung, ob ein Eingabedatensatz für das neuronale Netz in der konvexen Hülle liegt, die von den Trainingseingabedatensätzen aufgespannt wird.
8. System nach Anspruch 7 mit einem Hybridmodell, das zumindest ein erstes und ein zweites neuronales Netz beinhaltet, wobei das erste neuronale Netz mit Hilfe einer Menge von ersten Trainingseingabedatensätzen trainiert worden ist, und wobei das zweite neuronale Netz mit Hilfe einer Menge von zweiten Trainingseingabedatensätzen trainiert worden ist, wobei die Mittel zur Prüfung so ausgebildet sind, dass für einen ersten Eingabedatensatz für das erste neuronale Netz geprüft wird, ob der erste Eingabedatensatz in der konvexen Hülle liegt, die von den ersten Trainingseingabedatensätzen aufgespannt wird, und dass für einen zweiten Eingabedatensatz für das zweite neuronale Netz geprüft wird, ob der zweite Eingabedatensatz in der konvexen Hülle liegt, die von den zweiten Trainingseingabedatensätzen aufgespannt wird, wobei die Zuordnung des ersten Eingabedatensatzes zum ersten Neuronalen Netz und die Zuordnung des zweiten Eingabedatensatzes zum zweiten Neuronalen Netz aus einem Gesamtdatensatz automatisiert erfolgt.
9. System nach Anspruch 8, wobei die Mittel zur Prüfung so ausgebildet sind, dass die Prüfung gemäß einem Verfahren nach einem der vorhergehenden Ansprüche 1 bis 6 durchgeführt wird.
10. Computerprogrammprodukt, insbesondere digitales Speichermedium, zur Durchführung eines Verfahrens nach einem der vorhergehenden Ansprüche 1 bis 6.
EP04700118A 2003-01-16 2004-01-05 Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes Withdrawn EP1588229A3 (de)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
DE10301420A DE10301420A1 (de) 2003-01-16 2003-01-16 Verfahren zur Ermittlung des zulässigen Arbeitsbereichs eines neuronalen Netzes
DE10301420 2003-01-16
PCT/EP2004/000019 WO2004063832A2 (de) 2003-01-16 2004-01-05 Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes

Publications (2)

Publication Number Publication Date
EP1588229A2 true EP1588229A2 (de) 2005-10-26
EP1588229A3 EP1588229A3 (de) 2005-11-02

Family

ID=32602600

Family Applications (1)

Application Number Title Priority Date Filing Date
EP04700118A Withdrawn EP1588229A3 (de) 2003-01-16 2004-01-05 Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes

Country Status (4)

Country Link
US (1) US20040172375A1 (de)
EP (1) EP1588229A3 (de)
DE (1) DE10301420A1 (de)
WO (1) WO2004063832A2 (de)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050251376A1 (en) * 2004-05-10 2005-11-10 Alexander Pekker Simulating operation of an electronic circuit
EP1793243A1 (de) * 2005-12-05 2007-06-06 Leica Geosystems AG Verfahren zur Auflösung einer Phasenmehrdeutigkeit

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5835901A (en) * 1994-01-25 1998-11-10 Martin Marietta Corporation Perceptive system including a neural network
US5835907A (en) * 1995-12-20 1998-11-10 Mci Communications Corporation Emergency PCS system for identification and notification of a subscriber's location
US7203716B2 (en) * 2002-11-25 2007-04-10 Simmonds Precision Products, Inc. Method and apparatus for fast interpolation of multi-dimensional functions with non-rectangular data sets

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2004063832A2 *

Also Published As

Publication number Publication date
US20040172375A1 (en) 2004-09-02
WO2004063832A3 (de) 2005-09-09
WO2004063832A2 (de) 2004-07-29
EP1588229A3 (de) 2005-11-02
DE10301420A1 (de) 2004-07-29

Similar Documents

Publication Publication Date Title
DE69324052T2 (de) Neuronalnetzwerk-Lernsystem
EP2112568B1 (de) Verfahren zur rechnergestützten Steuerung und/oder Regelung eines technischen Systems
EP3785177B1 (de) Verfahren und vorrichtung zum ermitteln einer netzkonfiguration eines neuronalen netzes
DE112016001796T5 (de) Feinkörnige bildklassifizierung durch erforschen von etiketten von einem bipartiten graphen
DE102018111905A1 (de) Domänenspezifische Sprache zur Erzeugung rekurrenter neuronaler Netzarchitekturen
DE69224718T2 (de) Klassifizierungsverfahren für Rechnerarchitekturen
DE112021000251T5 (de) Verfahren zum auswählen von datensätzen zum aktualisieren eines moduls mit künstlicher intelligenz
DE69802372T2 (de) Klassifizierungssystem und -verfahren mit N-Tuple- oder RAM-basiertem neuronalem Netzwerk
DE69328596T2 (de) Optimierung eines Neuralnetzwerks mit Vorwärtskopplung
DE10023377C2 (de) Verfahren zur Erhöhung der Leistungsfähigkeit einer Computereinrichtung bei Finite-Elemente-Simulationen und eine solche Computereinrichtung
DE19703964C1 (de) Verfahren zur Transformation einer zur Nachbildung eines technischen Prozesses dienenden Fuzzy-Logik in ein neuronales Netz
EP1588229A2 (de) Verfahren zur ermittlung des zulässigen arbeitsbereichs eines neuronalen netzes
DE102021202335A1 (de) Verfahren und Vorrichtung zum Prüfen eines technischen Systems
DE102024201461A1 (de) Verfahren zum Optimieren eines herzustellenden Gyroskop-Systems
WO1998007100A1 (de) Rechnergestütztes verfahren zur auswahl von trainingsdaten für ein neuronales netz
DE102020213238A1 (de) Erzeugung von vereinfachten computer-implementierten neuronalen netzwerken
DE19831651C1 (de) Verfahren zum Erzeugen eines regel- und anpassbaren Netzwerkes von Modellen von Verhaltensmustern einschließlich Software-Systemen
DE102020212328A1 (de) Vorrichtung und computerimplementiertes Verfahren für eine Netzwerkarchitektursuche
DE102018109691A1 (de) Verfahren zur computerunterstützten Fertigungsoptimierung zumindest eines Fertigungsschritts
DE102023211078A1 (de) Verfahren sowie ein System zum Optimieren einer Netzwerkarchitektur eines künstlichen neuronalen Netzwerks
DE102022201718A1 (de) Computer-implementiertes Verfahren zum Erstellen eines Gültigkeitsmodells zum Ermitteln einer Modellierungsunzuverlässigkeit in einem Steuergerät mit begrenzter Rechenkapazität mithilfe maschineller Lernverfahren
DE102023206789A1 (de) Verfahren zum Training eines Faltungs-Neuronalnetzes, das in Schichten angeordnete Knoten und eine Beschneidungsmaske umfasst
DE102025102861A1 (de) Eine numerische Methode zur Lösung der Schrödinger-Gleichung in hochdimensionalen Räumen
EP1190383B1 (de) Verfahren zur rechnergestützten ermittlung einer zugehörigkeit einer vorgegebenen eingangsgrösse zu einem cluster
DE112023005296T5 (de) Fähigkeitenerwerb für dynamische behandlungskonzepte weitere anwendungsinformationen

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

PUAK Availability of information related to the publication of the international search report

Free format text: ORIGINAL CODE: 0009015

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK

AK Designated contracting states

Kind code of ref document: A3

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK

RIC1 Information provided on ipc code assigned before grant

Ipc: 7G 06N 3/08 A

17P Request for examination filed

Effective date: 20060309

DAX Request for extension of the european patent (deleted)
RBV Designated contracting states (corrected)

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

RIN1 Information on inventor provided before grant (corrected)

Inventor name: HUEBL, PETER

Inventor name: MRZIGLOD, THOMAS

Inventor name: MOGK, GEORG

17Q First examination report despatched

Effective date: 20110803

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20120214