Chapter 1 MODELING UNCERTAINTY IN NONLINEAR ANALOG SYSTEMS WITH AFFINE ARITHMETIC

格式：pdf
大小：356.86 KB
文档页数：16

Chapter1MODELING UNCERTAINTY IN NONLINEAR ANALOG SYSTEMS WITH AFFINE ARITHMETIC Wilhelm Heupke1,Christoph Grimm2,and Klaus Waldschmidt11Department of Computer EngineeringUniversity of Frankfurt2Institute for Microelectronic SystemsUniversity of HannoverAbstract This paper describes a semi-symbolic method for the analysis of mixedsignal systems.Aimed at control and signal processing applications,itdelivers a superset of the set of all reachable values.The method thatrelies on aﬃne arithmetic is precise for linear systems,but in the case ofnonlinear systems,approximations are needed.As for each approxima-tion a new term is added,the number of approximation terms increasesduring simulation and therefore slows down the simulation.This leadsto a quadratic time complexity in the number of time steps.A methodto avoid this and an example implementation based on SystemC-AMStogether with its performance are presented.Keywords:aﬃne arithmetic,intervals,SystemC-AMS,simulation,uncertainty,tol-erance1.IntroductionToday’s automotive,telecom,and ambient intelligence applicationsconsist of sensors,actuators,analog and digital circuits,and a large por-tion of software.At the system level designers usually specify and modelsuch applications by continuous-time block diagrams with directed sig-nalﬂow.For the veriﬁcation and analysis of such systems,most notablya transient simulation is used:Input stimuli are speciﬁed and the sim-ulator computes the output signals.The transient simulation allowsdesigners to get important insight into the behavior of the modeled sys-D R A F T Page1January26,2006,2:16pm D R A F T2tem and provides a simple functional veriﬁcation.However,within the design process of many of the above mentioned systems,much time is spent for analyzing the impact of uncertainties introduced by diﬀerent realization variants:Static variations of operating conditions(e.g.production tolerances)Dynamic variations of operations conditions(e.g.temperature drift)Quantization and rounding indigital signal processing and analog/digital conversionPhysical eﬀects in analog circuits(e.g.noise).One big problem is,that some deviations are compensated and do not have a large inﬂuence on some output of interest,while another deviation of same value will be ampliﬁed and thus violates the speciﬁcation.The established analog or mixed-signal simulators at the electrical level provide diﬀerent methods that help designers to evaluate the impact of deviations:noise analysis,sensitivity analysis,worst case analysis, Monte Carlo analysis,AC analysis,and sometimes combinations thereof. These analyses are either based on the fact that analog circuits have a working point and can be linearized(AC analysis,noise analysis), require monotonicity(sensitivity analysis),or use a very high number of simulation runs toﬁnd corner cases(worst case simulation)and to compute statistical properties at the outputs(Monte Carlo analysis).Although these analyses are very useful,they have several drawbacks: Methods based on linearizations are usually restricted to analog circuits and are not applicable to mixed-signal systems or even DSP software. In order to overcome these problems designers have to provide discrete models and additional models that are used for AC analysis.Further-more,time domain simulations are used in combination with FFT meth-ods to get information about the spectral distribution of noise,for ex-ample.Unfortunately,transient simulations and Monte Carlo methods do not provide information about the contribution of single sources of uncertainty to the total uncertainty at e.g.outputs in a direct and easy way;usually the interpretation is rather diﬃcult.A direct and easy in-terpretation is of particular interest for the case of design automation at system level.The above mentioned classical analyses are aimed towards the electri-cal level and are based on linearization and linear equation solvers.The method proposed in this paper is intended for a system level simulation D R A F T Page2January26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic3 with a discrete time static dataﬂow model of computation,which is im-plied by the use of SystemC-AMS.One should be aware that there is no automatic way to use the electrical level models at the system level or vice versa,yet.Compared with purely numerical simulation,the symbolic or formal techniques provide designers with more information,e.g.about the ori-gin of a deviation[Henzinger and Ho,1995;Zhang and Mackworth, 1996;Henzinger,1996;Hartong et al.,2002].Unfortunately,symbolic or formal techniques are far away from being applicable to the design of complex and heterogeneous systems[Stauner et al.,1997].In this situation,semi-symbolic techniques are very attractive if they combine advantages of symbolic techniques with the general applicability of sim-ulation.A promising approach is the use of aﬃne arithmetic[Andrade et al.,1994]for semi-symbolic analysis[Fang et al.,2003;Lemke et al., 2002]or even a semi-symbolic simulation[Heupke et al.,2003].Fang and Rutenbar[Fang et al.,2003]are doing a static analysis of rounding errors in DSP algorithms with aﬃne arithmetic.In[Heupke et al.,2003;Grimm et al.,2004a]we use aﬃne arithmetic for semi-symbolic transient simulations of complex signal processing systems. The simulation result is a numerical output together with a symbolic, aﬃne approximation of the contributions of diﬀerent(symbolic)sources of uncertainty.An important advantage of the proposed method is the safe inclusion of all reachable values by the aﬃne expression,therefore delivering reliable results.On the other hand the increasing number of terms and the resulting over-approximation caused by each nonlinear operation are a disadvantage.In this paper we introduce a method for semi-symbolic simulation with aﬃne arithmetic that eﬃciently handles these approximation terms.Section2gives a brief introduction to aﬃne arithmetic and semi-symbolic simulation with aﬃne arithmetic as described in[Heupke et al., 2003].Section3introduces a method to handle the over-approximation terms in semi-symbolic simulation based on aﬃne arithmetic.This en-ables aﬃne arithmetic to reach the same asymptotic time complexity conventional numerical simulation has.Section4demonstrates the ap-plicability of the method by a simple example.Figure1.1shows a system we implemented as a test in order to val-idate the behavior by transient simulations with aﬃne expressions as data type.It contains two elements that can be troublesome:Theﬁrst is feedback.Another range arithmetic,the interval arith-metic,will not deliver a meaningful result for the simulation of systems D R A F T Page3January26,2006,2:16pm D R A F T4i p u l a t i n gr i a b l e Figure 1.1.Simulated System with Nonlinear Blockwith feedback,while aﬃne arithmetic works ﬁne in this respect [Heupke et al.,2003].The second is the emphasized nonlinear block in the system,which is interesting,as it creates additional approximation terms in each iteration through the loop.This results in a high number of terms,that would slow down the simulation more and more,if nothing is done about that.2.Semi-Symbolic Simulation with AﬃneArithmeticAﬃne ArithmeticAﬃne arithmetic [Andrade et al.,1994],introduced by Comba et al.,is a kind of improved interval arithmetic,and therefore allows us to compute with uncertain values.In each aﬃne expression the inﬂuence of independent sources of uncertainty i to a variable ˆx with the central value x 0is represented by a symbolic sum of terms x i i .Noise symbols i represent arbitrary,but for one simulation run ﬁxed values from the interval [−1,1].The partial deviations x i then scale these intervals.The i are a symbolic representation and a certain value is never assigned to them.ˆx =x 0+ni =1x i i , i ∈[−1,1]Basic mathematical operations are deﬁned byˆx ±ˆy :=(x 0±y 0)+ni =1(x i ±y i ) iD R A F T Page 4January 26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic5andcˆx:=cx0+ni=1cx i iThe operation rad(ˆx)is the radius of the aﬃne expressionˆx.rad(ˆx)=ni=1|x i|The results of linear operations give precise limits and have no over-approximation(no unnecessary expansion of the error interval).Note that the subtraction of two aﬃne expressions which include the same noise symbols m may reduce the partial deviation of the result, in contrast to the same values with diﬀerent noise symbols.This allows to model error cancellation,for example in feedback loops.In Table1.1 the variables with a hat denote aﬃne arithmetic variables while the ones written with a capital letter are corresponding interval variables.The diameter is obviously twice the radius for aﬃne forms.In the case of intervals the diameter is the diﬀerence between supremum and inﬁmum of the interval.aﬃne form diameter interval diameterˆx=17.3+2.5 15.0X=[14.8,19.8]5.0ˆy=15.4+2.5 15.0Y=[12.9,17.9]5.0ˆz=15.4+2.5 25.0Z=[12.9,17.9]5.0ˆx−ˆy=1.9+0.0 10.0X−Y=[−3.1,6.9]10.0ˆx−ˆz=1.9+2.5 1−2.5 210.0X−Z=[−3.1,6.9]10.0Table1.1.Aﬃne Expressions and their interval counterpartsTable1.1shows the diﬀerence between aﬃne arithmetic and interval arithmetic in the case of diﬀerent or same source of uncertainty.The variables x and y share an uncertainty caused by the same source of uncertainty and therefore both have a term 1.For demonstration pur-poses also the inﬂuence of this uncertainty is of same magnitude and direction/sign.In contrast to that the variable z has a term 2that shows that the uncertainty of z has a diﬀerent source of uncertainty, although both have the same magnitude in example given in table1.1. The eﬀect shows up in the subtraction of x-y.Interval arithmetic in-creases the interval diameter instead of bringing it to zero,while aﬃne arithmetic keeps the correlation and delivers the precise result.This is because the information contained in interval arithmetic is too lim-ited,as the range of values is not the only important information that is needed to describe the inﬂuence of uncertainty.D R A F T Page5January26,2006,2:16pm D R A F T6This eﬀect of interval arithmetic may be tolerated sometimes,but a simulation of a control loop,where a too pessimistic result is fed back over and over,results in a permanently increasing diameter and depend-ing on the system will increase exponentially in the worst case.This will deliver with interval arithmetic that the result is[−∞,+∞]within a limited number of simulation time steps[Heupke et al.,2003].For sure this is a safe inclusion,but would be useless pessimistic.The concept in the form described in this paper can be extended to dynamic uncertainties and therefore to analyze eﬀects like colored noise as described in[Grimm et al.,2004b].An important aspect is the guarantee,that after each operation,the result is a superset of all reachable values.Therefore,for example,multiplication of two aﬃne expressions is de-ﬁned byˆx·ˆy:=x0·y0+mi=1(x0·y i+x i·y0) i+rad(ˆx)·rad(ˆy)· m+1.In general,the error introduced by some nonlinear operation is over-approximated by a new noise symbol m+1.All nonlinear operations introduce new noise symbols and therefore some systems may present a problem,because of the permanently in-creasing number of terms.But some systems include strategies to reduce the inﬂuence of deviations(e.g.feedback).Caused by these strategies, the inﬂuence of these noise symbols converges to zero and for a sta-ble system they are absolutely summable.Section3describes how this property delivers a solution for the problem of the increasing number of terms.SystemC-AMS based ImplementationFor the implementation we chose SystemC-AMS,but the concept mentioned below can be implemented in every language that supports operator overloading,e.g.VHDL-AMS.SystemC-AMS is an extension of the class library SystemC,aimed at supporting the modeling of mixed-signal(analog and digital)systems. It provides means to simulate analog,mixed-signal and signal process-ing systems as a block diagram.Regarding the abstraction level it is comparable to Matlab.In contrast SystemC allows us to immediately reuse the code portion for these blocks,that have to be implemented in Software later on.Additionally the code of the models,that will be implemented in digital hardware,can be automatically synthesized to D R A F T Page6January26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic7 create e.g.an ASIC or FPGA implementation.Only for the blocks, that model analog behavior,there is no automatic way for implementa-tion.These blocks are speciﬁed by transfer functions or static nonlinear functions implemented in C++.Static dataﬂow is used as the model of computation.The implementation of the aﬃne arithmetic is based on the libaa library[Gay,2003]which deﬁnes linear and nonlinear operations on aﬃne arithmetic variables in a class called AAF(aﬃne arithmetic forms).It allows us to model computations with uncertainties in general.Using the AAF class with SystemC-AMS is very simple:In SystemC-AMS,as in SystemC,signals are instantiated with a template parameter T.This parameter speciﬁes the value type of the signal.For example by sca sdf signal<double>my signal a signal with a value range of a variable with double precision is instantiated in SystemC-AMS.Of course,one can as well specify the template parameter AAF instead of double.This small change is all that is needed with SystemC-AMS to turn the numerical simulation into a semi-symbolic simulation based on aﬃne arithmetic.Instead of using operators deﬁned for double values, the compiler will use the operators deﬁned in the AAF class,which over-load the standard operators.The results of the simulation are aﬃne expressions that semi-symbolically represent possible deviations.For example,one can write the following code:AAF a(2.0),b(3.0),c(2.0),y;//constructor which adds a noise symbol//x_i with partial deviation0.1:AAF uncertainty(Interval(-0.1,+0.1));a=a+uncertainty;y=(a+b)*(c+uncertainty);cout<<"y="<<y<<endl;This simple program produces the following output:y=10+(e1*0.7)+(e2*0.01)So after the uncertainty is introduced one can use a variable of type AAF like any other variable.The advantage of semi-symbolic simulation compared with a numeri-cal simulation becomes obvious if the uncertainties at the output of the simulated system exceed some speciﬁed range.In this case,the symbolic representation provides designers with the contribution of all sources of uncertainty to the deviation at the output.It also models the eﬀects that are created by the combination of uncertainties.This together al-lows the designer to identify sources of uncertainty where improvements D R A F T Page7January26,2006,2:16pm D R A F T8are most fruitful.As a long term perspective one day a mixed-signal synthesis system can be directed this way,where further optimization is needed.3.Handling nonlinearityEach nonlinear operation approximation creates an additional term, as can be seen in the code example.These approximations are a problem for the aﬃne arithmetic,as potentially a high number of very small and thereby insigniﬁcant terms in the symbolic expression is created.This problems shows up especially if the system that is modeled con-tains a loop and this system has at least one component that creates an approximation in the path of this loop(e.g.by multiplication of two aﬃne expressions).Then any kind of memory(e.g.some modeled energy storage)in a block within the modeled system will contain most of the approximation terms that are created in each simulation cycle of this loop.If there is a constant number of approximations this means that in each simulation cycle the number of terms increases by this constant number.To cope with that,we introduce a method that’cleans up’the aﬃne arithmetic expression variables.It somewhat resembles the garbage col-lection concept,used to free unneeded memory of variables,that is used in some programming languages like e.g.Java.If the number of noise symbols in the aﬃne expressions increases above a certain level,the simplification()method is called.For all variables in the system,all terms smaller than a cut level l,set by the user,are summed up separately by the ones with a positive and the ones with a negative sign to two special noise terms.Deleting the terms with an absolute value below this cut level could potentially lead to inaccurate results in the case of a high number of simulation time steps and certain functional blocks,e.g.integrators,be-cause in this example they may grow to a big one over time.Therefore it is better to sum them.This way it delivers a safe inclusion,but it means that the correlation of the individual terms is lost.But it does not exhibit the same problem like interval arithmetic does,as described above,because the correlation of this sum is still valid for all AAF vari-ables in the future time steps and the terms with diﬀerent signs are kept separate.Furthermore these uncertainties are usually far smaller than the nominal values and if l again is far smaller than the other uncer-tainties,any kind of over-approximation would not create a problem.So the inﬂuence of approximations decreases below the level l after several time steps.D R A F T Page8January26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic9 Please note that if the simpliﬁcation method would be called too often, the unneeded over-approximation could potentially show up signiﬁcantly and in the above mentioned example the concept of feedback that makes these terms converge to0,would not work.On the other hand if called not often enough,the computation time will increase signiﬁcantly.Our experiences has shown,that the choice of the time point,when to call the simpliﬁcation method,was for the example system not very critical.The method resembles the typical strategy of leaving away smaller terms.But with aﬃne arithmetic we do not have to really leave the smaller terms away,instead we can handle their sum as a new uncer-tainty.So not only the modeled uncertainties of the real system,but obviously also uncertainties caused by the modeling process,like these simpliﬁcations,are analyzed.Implementation of the simpliﬁcation method In the present implementation the simpliﬁcation method is invoked every1.000th simulation cycle,but later on it might be automatically invoked by some heuristic.For example the change in the highest index of the noise terms since the last simpliﬁcation could be used as a crite-rion,when to call this method.The cut level l is set to a constant small fraction of the smallest explicitly introduced uncertainty by the user.The change in an aﬃne expression can be seen by the following exam-ple of a simpliﬁcation with l=1.0·10−4.First a variable was printed immediately before the simpliﬁcation:28.9796+(e1*2.9925)+(e5*0.000856951)+(e6*1.14971e-006)+(e7*1.11085e-006)+(e8*-1.34821e-007)+(e9*1.07968e-006)+(e10*-1.12145e-007)After the simpliﬁcation the printed variable changed to:28.9796+(e1*2.9925)+(e5*0.000856951)+(e34*3.34024e-006)+(e35*-2.46966e-007)Usually this happens with far more terms,but for demonstration pur-poses it would be diﬃcult to show.In this case 34sums up the positive insigniﬁcant terms and 35sums up the negative insigniﬁcant terms.By handling a list with pointers to all aﬃne variables in the system, it is possible to access all AAF variables.This list is added as a static member of the AAF class,so that all AAF variables share it.The AAF class saves the aﬃne expression in one variable for the cen-tral value x0and two pointers to dynamically allocated arrays called coefficients and indices.In aﬁrst run across all AAF variables and D R A F T Page9January26,2006,2:16pm D R A F T10across all coeﬃcients in these variables,the signiﬁcant terms are col-lected,based on the cut level l.A term x i of an aﬃne variableˆx is signiﬁcant if it fulﬁlls the condition|x i|>l.The second run goes again across all variables.For each of the variables it is determined how many signiﬁcant terms are contained,based on the result of theﬁrst run.Then two new arrays for the coeﬃcients and the indices are allocated and the signiﬁcant terms are copied to the new arrays.After that the memory of the old arrays is freed.Eﬃciency gained by the simpliﬁcationThe following text analyses the eﬀort to handle one variable.So the total eﬀort also scales with the number of variables for all similar simu-lation methods.Let us assume a system with a loop,n be the number of total sim-ulation time steps and c be a constant that describes the maximum number of nonlinear operations,along the path of the loop.Remember that these nonlinear operations add terms.Further let k be the number of explicitly introduced uncertainties.With conventional simulation based on the static dataﬂow model of computation and with variables of type e.g.double the space complexity is O(1)and the simulation time is O(n).In contrast to that in the naive implementation the maximum memory needed for each aﬃne variable iscn+k⊆O(n)because in each of the n steps c uncertainties are added by over-approximations and a maximum of k has been added intentionally at the elaboration phase.This means that the space complexity is O(n).Even worse is the resulting time complexity.This is because in each simulation time step each term of an aﬃne variable needs to be handled, e.g.an arithmetic operation has to be performed for it by the CPU:n(ci+k)=cn(n+1)/2+kni=1=n2/2+(c+k)n⊆O(n2)System theory requires for every stable system that every bounded input delivers a bounded output.Obviously every technically meaningfulD R A F T Page10January26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic11 system to be implemented is stable.Furthermore a discrete system is stable if and only if the impulse response is absolutely summable:∞|h(i)|<∞i=−∞This implies an important aspect:The impulse response of the opened control loop converges to zero.So every introduced over-approximation term will converge to zero with the number of iterations through the control loop in the given example.This means that we can apply a trick that copes with the terms caused by the over-approximation:From time to time we sum up all approximation terms that got extremely small (smaller than l)by a simpliﬁcation method,thereby keeping the safe inclusion,but reducing the number of terms.On the other hand,this means,if the number of terms can not be reduced,we get a strong indication that the system might be unstable.This simpliﬁcation method,if called every m simulation time steps, is a substantial step forward regarding eﬃciency,because in the m time steps between two simpliﬁcation operations,a maximum of c terms adds in each time step.To this adds the number of k explicitly introduced terms.As c,m and k are all constants,we get asymptotically the same space complexity like pure numerical simulation:cm+k⊆O(1)The time complexity of the simulation with the simpliﬁcation method needs cm+k computations in one simulation time step in the worst-case of the time step before the next simpliﬁcation method call.This happens in the worst-case n times.To this adds the eﬀort of the simpliﬁcation method,called n/m times.The simpliﬁcation method itself needs in the ﬁrst and the second pass to touch every term.This gives a total time complexity of O(n),also the same complexity numerical simulation has:(cm+k)n+2n/m(cm+k)=(cm+k+2(cm+k)/m)n⊆O(n)4.Experimental ResultsThe system shown in Figure1.1was implemented in SystemC-AMS and the AAF class.With this setup transient simulation runs were per-formed.D R A F T Page11January26,2006,2:16pm D R A F T12number of computation time computation timetime steps without simpliﬁcation[s]with simpliﬁcation[s] 1,000112,000424,0001658,000611016,0002442032,0009994064,000408379128,000−159256,000−319512,000−6401,024,000−1275Table1.2.Measured Computation TimeTable1.2shows the time needed for the simulation with and without using the simpliﬁcation method.The time interval that was simulated was the same for all values in the table and was scaled to deliver time re-sults that are easy to interpret.Only the step width in time was changed for each row.The simpliﬁcation method was called every1,000th time step,respectively never in the case of no simpliﬁcation.The table shows the clear advantage of the simpliﬁcation method, as the computation time increases linear with the number of simulated time steps,if the simpliﬁcation method is used.It is very clear to see a quadratic increase of the needed computation time for the simulation without the use of the simpliﬁcation method,that shows up as a four fold increase of the required computation time for a two fold increase in the number of time steps.So it gets obvious,that aﬃne arithmetic would be much harder to use without this simpliﬁcation method for long simulation runs in the presence of feedback and nonlinearity.For a visual representation,we convert aﬃne expressions to intervals, by use of the rad operator.These intervals can be plotted as shown in Figure1.2as a range.In the case of an uncertainty that is substantially smaller than the central value,two separate traces with diﬀerent scalings are plotted.We use for both types of plots the program gnuplot,as usual waveform viewers do not support interval type signals.Figure1.2shows the step response of a feedback loop that contains a nonlinear control path,which is shown in Figure1.1.D R A F T Page12January26,2006,2:16pm D R A F TModeling Uncertainty in Nonlinear Analog Systems with Aﬃne Arithmetic 1350 0.02 0.04 0.06 0.08 0.10.12 0.14 0.16 0.18 0.2Time Figure 1.2.System within the stable areaFigure 1.3shows the step response close to the stability border and Figure 1.4the same system,but beyond the stability border.Interesting to note are typical chaotic eﬀects of nonlinear systems near the stability border,that show up very clearly in the uncertainty and which are not linear with the central value in Figure 1.3.0 0.02 0.04 0.06 0.08 0.10.12 0.14 0.16 0.18 0.2Time Figure 1.3.System near the stability border5.ConclusionWithout the described method semi-symbolic simulation with aﬃne arithmetic has quadratic time complexity.On the other hand,with the presented method,simulation with aﬃne arithmetic has linear time complexity,even in the presence of nonlinearities and feedback.This D R A F T Page 13January 26,2006,2:16pm D R A F T1450 0.02 0.04 0.06 0.08 0.10.12 0.14 0.16 0.18 0.2Time Figure 1.4.System beyond the stability bordermeans that aﬃne arithmetic is feasible for simulation even with a large number of time steps in nonlinear feedback systems.Compared with purely numerical simulation these extensions allow designers to analyze the noise and sensitivity to diﬀerent sources of un-certainty,such as thermal or quantization pared with analy-ses in ‘analog’simulators,the described method is applicable to digital signal processing methods and to discrete time approximations of analog circuits.This allows designers an analysis of heterogeneous systems that include large fractions of DSP software.The symbolic representation of the contributions to the deviations at the outputs can be interpreted easily and delivers a safe inclusion,an important aspect for the design of security critical systems,that could create otherwise dangerous situ-ations if their deviation is too large.Compared with formal approaches for model checking or property reﬁnement of hybrid systems [Henzinger and Ho,1995;Henzinger,1996;Heupke et al.,2003]it allows us to model and verify properties such as robustness or precision,that are key issues in the design of analog and mixed-signal systems.D R A F T Page 14January 26,2006,2:16pm D R A F T。

Sliding Mode Control

Chapter 5Sliding Mode Control5.1. IntroductionIn this chapter, controllers are designed which achieve wheel-slip control for vehicle motion. Control schemes developed in this chapter are based on controlling wheel slip. Control of braking force is attained by controlling the wheel slip because of the relationship between wheel slip and adhesion coefficient caused by road-tire interaction. Wheel slip dynamic equations are given by which show the nonlinearities and uncertainties of the system (see chapter 3). Hence, a nonlinear control strategy based on sliding mode, which is a standard approach to tackle the parametric and modeling uncertainties of a nonlinear system, is chosen for slip control. For sliding mode controller, Lyaponov stability method is applied to keep the nonlinear system under control. The sliding mode approach is method which transformed a higher-order system into first-order system. In that way, simple control algorithm can be applied, which is very straighforward and robust.5.2. Background5.2.1. Modeling inaccuraciesNonlinear system model imprecision may come from actual uncertainty about the plant (e.g., unknown plant parameters), or from the purposeful choice of a simplified representation of the system’s dynamics. Modeling inaccuracies can be classified into two major kinds: structured (or parametric) uncertainties and unstructured uncertainties (or unmodeled dynamics). The first kind corresponds to inaccuracies on the terms actually included in the model, while the second kind corresponds to inaccuracies on the system order.Modeling inaccuracies can have strong adverse effects on nonlinear control systems. One of the most important approaches to dealing with model uncertainty are robust control.The typical structure of a robust controller is composed of a nominal part, similar to a feedback control law, and additional terms aimed at dealing with model uncertainty.Sliding mode control is an important robust control approach. For the class of systems to which it applies, sliding mode controller design provides a systematic approach to the problem of maintaining stability and consistent performance in the face of modeling imprecision. On the other hand, by allowing the tradeoffs between modeling and performance to be quantified in a simple fashion, it can illuminate the whole design process.5.2.2. Sliding surfacesThis section investigates variable structure control (VSC) as a high-speed switched feedback control resulting in sliding mode. For example, the gains in each feedback path switch between two values according to a rule that depends on the value of the state at each instant. The purpose of the switching control law is to drive the nonlinear plant’s state trajectory onto a prespecified (user-chosen) surface in the state space and to maintain the plant’s state trajectory on this surface for subsequent time. The surface is called a switching surface. When the plant state trajectory is “above” the surface, a feedback path has one gain and a different gain if the trajectory drops “below” the surface. This surface defines the rule for proper switching. This surface is also called a sliding surface (sliding manifold). Ideally, once intercepted, the switched control maintains the plant’s state trajectory on the surface for all sebsequent time and the plant’s state trajectory slides along this surface.The most important task is to design a switched control that will drive the plant state to the switching surface and maintain it on the surface upon interception. A Lyapunov approach is uesd to characterize this task.Lyapunov method is usually used to determine the stability properties of an equlibrium point without solving the state equation. Let V(x) be a continuously differentiable scalar function defined in a domain D that contains the origin. A functionV(x) is said to be positive definite if V(0)=0 and V(x)>0 for x. It is said to be negative definite if V(0)=0 and V(x)>0 for x. Lyapunov method is to assure that the function ispositive definite when it is negative and function is negative definite if it is positive. In that way the stability is assured.A generalized Lyapunov function, that characterizes the motion of the state trajectory to the sliding surface, is defined in terms of the surface. For each chosen switched control structure, one chooses the “gains” so that the derivative of this Lyapunov function is negative definite, thus guaranteeing motion of the state trajectory to the surface. After proper design of the surface, a switched controller is constructed so that the tangent vectors of the state trajectory point towards the surface such that the state is driven to and maintained on the sliding surface. Such controllers result in discontinuous closed-loop systems.Let a single input nonlinear system be defined asxnf t b t u t()(,)(,)()=+x x(5.1)Here, x(t) is the state vector, u(t) is the control input (in our case braking torque or pressure on the pedal) and x is the output state of the interest (in our case, wheel slip). The other states in the state vector are the higher order derivatives of x up to the (n-1)th order. The superscript n on x(t) shows the order of differentiation. f(x,t) and b(x,t) are generally nonlinear functions of time and states. The function f(x) is not exactly known, but the extent of the imprecision on f(x) is upper bounded by a known, continuous function of x; similarly, the control gain b(x) is not exactly known, but is of known sign and is bounded by known, continuous functions of x. The control problem is to get the state x to track a specific time-varying state xdin the presence of model imprecision on f(x) and b(x). Atime varying surface s(t) is defined in the state space R (n)by equating the variable s t(;)x,defined below, to zero.s t d n x t(;)()~()x=+−δ1(5.2) Here, δ is a strict positive constant, taken to be the bandwidth of the system, and~()()()x x xt t d t=− is the error in the output state where x d t()is the desired state. The problem of tracking the n-dimensional vector x d t() can be replaced by a first-order stabilization problem in s. s t(;)x verifying (5.2) is referred to as a sliding surface, and the system’s behavior once on the surface is called sliding mode or sliding regime. From (5.2)the expression of s contains ~()x n−1, we only need to differentiate s once for the input u toappear. Furthermore, bounds on s can be directly translated into bounds on the tracking error vector ~x, and therefore the scalar s represents a true measure of tracking performance. The corresponding transformations of performance measures assuming ~x(0)=0 is:∀ t ≥0, s t()≤φ => ∀ t ≥0,~()()()x i t i≤2δε(5.3)i=0,...,n-1where εφδ=−/n1 (Slotine and Li 1990 ). In this way, an nth-order tracking problem can be replaced by a 1st-order stabilization problem.The simplified, 1st-order problem of keeping the scalar s at zero can now be achieved by choosing the control law u of (5.1) such that outside of S(t)1 22ddts s≤−η(5.4)where η is a strictly positive constant. Condition (5.4) states that the squared “distance”to the surface, as measured by s 2, decreases along all system trajectories. Thus, itconstrains trajectories to point towards the surface s(t). In particular, once on the surface, the system trajectories remain on the surface. In other words, satisfying the sliding condition makes the surface an invariant set (a set for which any trajectory starting from an initial condition within the set remains in the set for all future and past times). Furthermore (5.4) also implies that some disturbances or dynamic uncertainties can be tolerated while still keeping the surface an invariant set.xFigure 5.1: Graphical interpretation of equations (5.2) and (5.4) (n=2)(Resource: Slotine and Li 1991)Finally, satisfying (5.2) guarantees that if x(t=0) is actually off x d (t=0), the surface S(t) will be reached in a finite time smaller than s t ()/=0η. Assume for instance that s(t=0)>0, and let t reach be the time required to hit the surface s=0.Integrating (5.4) between t=0 and t reach leads to0-s(t=0)=s(t= t reach )-s(t=0)≤-η( t reach -0)which implies thatt reach ≤ s t ()/=0ηThe similar result starting with s(t=0)>0 can be obtained ast reach ≤ s(t =0) /ηStarting from any initial condition, the state trajectory reaches the time-varyingsurface in a finite time smaller than s(t =0) /η, and then slides along the surface towards x d t () exponentially, with a time-constant equal to 1/λ.In summary, the idea is to use a well-behaved function of the tracking error, s,according to (5.2), and then select the feedback control law u in (5.1) such that s 2 remains characteristic of a closed-loop system, despite the presence of model imprecision and of disturbances.5.2.3. Controller DesignThe controller design procedure consists of two steps. First, a feedback control law u is selected to verify sliding condition (5.4). However, in order to account for the presence of modeling imprecision and of disturbances, the control law has to be discontinuous across S(t). Since the implementation of the associated control switching is imperfect, this leads to chattering(see figure 5.2), chattering is undesirable in practice, since it involves high control activity and may excite high frequency dynamics neglected in the course of modeling.Thus, in a second step, the discontinuous control law u is suitably smoothed to achieve an optimal trade-off between control bandwidth and tracking precision. The first step achieves robustness for parametric uncertainty, the second step achieves robustness to high-frequency unmodeled dynamics. This section discuss the first step.Consider a simple second order system&&()(,)()x t f x t u t =+(5.5)where f(x,t) is generally nonlinear and/or time varying and is estimated as $(,)f x t , u(t) is the control input, and x(t) is the state to be controlled so that it follows a desired trajectory x d t (). The estimation error on f(x,t) is assumed to be bounded by some known function F=F(x,t), so that$(,)(,)(,)f x t f x t F x t −≤(5.6)we define a sliding variable according to (5.2)s t ddtx t x t x t ()()~()~&()~()=+=+γγ (5.7)Differentiation of the sliding variable yields&()&&()&&()~&()s t x t x d t xt =−+γ (5.8)Substituting Equation (4.5) in Equation (4.8), we have&()(,)()&&()~&()s t f x t u t x d t xt =+−+γ(5.9)The approximation of control law $()u t to achieve &()s t =0 is$()$(,)&&()~&()u t f x t x d t xt =−+−γ(5.10)$()u t can interpreted as the best estimate of the equivalent control.To account for the uncertainty in f while satisfying the sliding condition122ddts t s t (())(),≤−ηη>0(5.11)take the control law as:u t u t k x t s t ()$()(,)sgn(())=−(5.12)By choosing k(x,t) large enough, such ask x t F x t (,)(,)=+ηensures the satisfaction of condition (5.11), since122ddt s t s t s t f x t f x t s t k x t s t (())&()()((,)$(,))()(,)()==−−≤−ηs t (),η >0.(5.13)Hence, by using (5.12), we ensure the system trajectory will take finite time to reach the surface S(t), after which the errors will exponentially go to zero.From this basic example, we can see the main advantages of transforming theoriginal tracking problem into a simple 1st-order stabilization problem in s. In first-order systems, the intuitive feedback control strategy “if the error is negative, push on the positive direction; if the error is positive, push on the negative direction” works. The same statement is not true in higher-order system.Now consider the second order system in the form of&&()(,)(,)()xt f x t b x t u t =+(5.14)where b(x,t) is bounded as0≤≤≤b x t b x t b x t min (,)(,)max (,)The control gain b(x,t) and its bound can be time varying or state dependent. Since the control input is multiplied by the control gain in the dynamics, the geometric mean of the lower and upper bound of the gain is a reasonable estimate:$(,)min (,)max (,)b x t b x t b x t =Bounds can then be written in the formββ−≤≤1$b bwhere β=(max /min )b b 1/2since the control law will be designed to be robust to the bounded multiplicative uncertainty,β is called the gain margin of the design.It can be proved that the control lawu t b x t u t k x t s t ()$(,)[$()(,)sgn(())]=−−1(5.15)withk x t x t F x t x t u t (,)(,)((,))((,))$()≥++−βηβ1(5.16)satisfies the sliding condition.The control law for higher order system can be deducted based on similar approach.5.2.4. Chattering ReductionAn ideal sliding mode exists only when the state trajectory x(t) of the controlled plant agrees with the desired trajectory at every t t ≥1 for some t 1. This may requireinfinitely fast switching. In real systes, a switched controller has imperfections which limit switching to a finite frequency. The representative point then oscillates within aneighborhood of the switching surface. This oscillation, called chattering, is illustrated on figure 5.2.xFigure 5.2: Chattering as a result of imperfect control switchings(Resource: Slotine and Li 1991)Control laws which satisfying sliding condition (5.4) and lead to “perfect” tracking in the face of model uncertainty, are discontinuous across the surface S(t), thus causing control chattering. Chattering is undesirable, since it involves extremely high control activity, and furthermore may excite high-frequency dynamics neglected in the course of modeling. Chattering must be reduced (eliminated) for the controller to perform properly.This can be achieved by smoothing out the control discontinuity in a thin boundary layer neighboring the switching surface{}B t x s x t (),(;)=≤φφ>0(5.17)where φ is the boundary layer thickness, and εφλ=−/n 1 is the boundary layer width. Inother words, outside of B(t), we choose control law as before which guarantees that the boundary layer is attractive, hence invariant; all trajectories starting inside B(t=0) remain inside B(t) for all t ≥0; and then u is interpolated inside B(t). For example, sgn(s) in (5.12) can be replaced by sφinside B(t).This approach leads to tracking to within a guaranteed precision ε (rather thanperfect tracking), and more generally guarantees that for all trajectories starting inside B(t=0)∀ t ≥0, ~()()()x i t i ≤2λεi=0,...,n-1(5.18)5.3 SummaryDue to its robustness properties, sliding mode controller can solve two major design difficulties involved in the design of a braking control algorithm:1. the vehicle system is highly nonlinear with time-varying parameters and uncertainties;2. the performance of the system depends strongly on the knowledge of the tire/road surface condition;For the class of systems to which it applies, sliding controller design provides a systematic approach to the problem of maintaining stability and consistent performance in the face of modeling imprecision.For wheel slip control system, the vehicle and brake system are highly nonlinear and time-varying systems. That makes sliding mode controller ideal candidate for the application。

Part1MonetaryPolicy,Inflation,andtheBusinessCycle

14.461Advanced Macroeconomics I(1st half)Jordi GalíMITFall2005Part1:Monetary Policy,Inflation,and the Business Cycle The lectures will provide an overview of the recent literature on dynamic optimizing models with nominal rigidities and their implications for the design of monetary policy. Lecture notes will be handed out during the course.A list of topics to be be covered and reading list with some of the key articles is provided below.Motivation and EvidenceBeyond RBC Theory.Long Run Evidence.Reduced Form Evidence.The Effects of Monetary Policy Shocks.Walsh,Carl E.(2003):Monetary Theory and Policy,Second Edition,MIT Press,chapter1.McCandless,George T.,Warren Weber(1995):“Some Monetary Facts,”Federal Reserve Bank of Minneapolis,Quartely ReviewBarro,Robert(1998):The Determinants of Economic Growth,MIT Press,chapter3. (NBER WP#5698)Bruno,Michael,and William Easterly(1998):“Inflation Crises and Long Run Growth,”Journal of Monetary Economics,vol.41,no.1,3-26Cooley,Thomas F.and Gary D.Hansen(1995):“Money and the Business Cycle,”in in T. Cooley ed.:Frontiers of Business Cycle Research(Princeton University Press),section7.2.Stock,James,and Mark W.Watson(2000):“Business Cycle Fluctuations in U.S. Macroeconomic Time Series,”in J.B.Taylor and M.Woodford eds.,Handbook of Macroeconomics,volume1A.(also NBER WP6528))Romer,Christina,and David Romer(1989):“Does Monetary Policy Matter?A New Test in the Spirit of Friedman and Schwartz,”NBER Macroeconomics Annual,4,121-170.Christiano,Lawrence J.,Martin Eichenbaum,and Charles L.Evans(1998):“Monetary Policy Shocks:What Have We Learned and to What End?,”in J.B.Taylor and M.Woodford eds.,Handbook of Macroeconomics,volume1A,65-148.(also NBER WP6400).Peersman,Gert and Frank Smets(2003):“The Monetary Transmission Mechanism in the Euro Area:More Evidence from VAR Analysis,”in Angeloni et al.(eds.)Monetary Policy Transmission in the Euro Area,Cambridge University Press,(also ECB WP no.91).Galí,Jordi(1992):”How Well Does the IS-LM Model Fit Postwar U.S.Data?,”Quarterly Journal of Economics709-738.Bernanke,Ben S.,and Ilian Mihov(1997):“Measuring Monetary Policy,”Quarterly Journal of Economics,vol.CXIII,no.3,869-902.Eichenbaum,Martin and Charles E.Evans(1995):“Some Empirical Evidence on the Effects of Shocks to Monetary Policy on Exchange Rates,”Quarterly Journal of Economics110,no.4,975-1010.Bils,Mark and Peter J.Klenow(2004):“Some Evidence on the Importance of Sticky Prices,”Journal of Political Economy,vol112(5),947-985.Dhyne,Emmanuel et al.(2005):“Price Setting in the Euro Area:Some Stylised Facts from Individual Consumer Price Data,”mimeo.Alvarez,Luis et al.(2005):“Sticky Prices in the Euro Area:Evidence from Micro-Data,”mimeo.A Simple Framework for Monetary Policy AnalysisHouseholds.Firms.Marginal costs and markups.Elements of equilibrium.Money demand. Capital accumulation.Walsh,Carl E.(2003):Monetary Theory and Policy,Second Edition,MIT Press,chapter2 (also related:chapter3)Woodford,Michael(2003):Interest and Prices:Foundations of a Theory of Monetary Policy,Princeton University Press,chapter1.Flexible PricesThe classical monetary model.Optimal price setting.Neutrality.Monetary policy rules and price level determination.Sources of non-neutrality.Optimal monetary policy. Hyperinflations.Walsh,Carl E.(2003):Monetary Theory and Policy,Second Edition,MIT Press,chapter2.Woodford,Michael(2003):Interest and Prices:Foundations of a Theory of Monetary Policy,Princeton University Press,chapter2.Cooley,Thomas F.and Gary D.Hansen(1995):“Money and the Business Cycle,”in in T. Cooley ed.:Frontiers of Business Cycle Research(Princeton University Press).Cooley,Thomas F.and Gary D.Hansen(1989):“Inflation Tax in a Real Business Cycle Model,”American Economic Review79,733-748.King,Robert G.,and Mark Watson(1996):“Money,Prices,Interest Rates,and the Business Cycle,”Review of Economics and Statistics,vol78,no1,35-53.Chari,V.V.,and Patrick J.Kehoe(1999):“Optimal Fiscal and Monetary Policy,”in in J.B. Taylor and M.Woodford eds.,Handbook of Macroeconomics,volume1C,1671-1745.Correia,Isabel,and Pedro Teles(1999):“The Optimal Inflation Tax,”Review of Economic Dynamics,vol.2,no.2325-346.A Baseline Sticky Price ModelThe Calvo model.The new Keynesian Phillips curve.The output gap and the natural rate of interest.The effects of monetary policy shocks.Evidence on inflation dynamics.Alternative time-dependent models:convex price adjustment costs,the Taylor model,the truncated Calvo model.State-dependent models.Walsh,Carl E.(2003):Monetary Theory and Policy,Second Edition,MIT Press,chapter5.Woodford,Michael(2003):Interest and Prices:Foundations of a Theory of MonetaryPolicy,Princeton University Press,chapter4.Calvo,Guillermo(1983):“Staggered Prices in a Utility Maximizing Framework,”Journal of Monetary Economics,12,383-398.Yun,Tack(1996):“Nominal Price Rigidity,Money Supply Endogeneity,and Business Cycles,”Journal of Monetary Economics37,345-370.King,Robert G.,and Alexander L.Wolman(1996):“Inflation Targeting in a St.Louis Model of the21st Century,”Federal Reserve Bank of St.Louis Review,vol.78,no.3.(NBER WP#5507).Fuhrer,Jeffrey C.and George R.Moore(1995):“Inflation Persistence”,Quarterly Journal of Economics,Vol.110,February,pp127-159.Galí,Jordi and Mark Gertler(1998):“Inflation Dynamics:A Structural Econometric Analysis,”Journal of Monetary Economics,vol44,no.2,195-222.Sbordone,Argia(2002):“Prices and Unit Labor Costs:A New Test of Price Stickiness,”Journal of Monetary Economics,vol.49,no.2,265-292.Galí,Jordi,Mark Gertler,David López-Salido(2001):“European Inflation Dynamics,”European Economic Review vol.45,no.7,1237-1270.Galí,Jordi,Mark Gertler,David López-Salido(2005):“Robustness of the Estimates of the Hybrid New Keynesian Phillips Curve,”Journal of Monetary Economics,forthcoming.Eichenbaum,Martin and Jonas D.M.Fisher(2004):“Evaluating the Calvo Model of Sticky Prices,”NBER WP10617.Mankiw,N.Gregory and Ricardo Reis(2002):“Sticky Information vs.Sticky Prices:A Proposal to Replace the New Keynesian Phillips Curve,”Quartely Journal of Economics,vol. CXVII,issue4,1295-1328.Rotemberg,Julio(1996):“Prices,Output,and Hours:An Empirical Analysis Based on a Sticky Price Model,”Journal of Monetary Economics37,505-533.Chari,V.V.,Patrick J.Kehoe,Ellen R.McGrattan(2000):“Sticky Price Models of the Business Cycle:Can the Contract Multiplier Solve the Persistence Problem?,”Econometrica, vol.68,no.5,1151-1180.Wolman,Alexander(1999):“Sticky Prices,Marginal Cost,and the Behavior of Inflation,”Economic Quarterly,vol85,no.4,29-48.Dotsey,Michael,Robert G.King,and Alexander L.Wolman(1999):“State Dependent Pricing and the General Equilibrium Dynamics of Money and Output,”Quarterly Journal of Economics,vol.CXIV,issue2,655-690.Dotsey,Michael,and Robert G.King(2005):“Implications of State Dependent Pricing for Dynamic Macroeconomic Models,”Journal of Monetary Economics,52,213-242.Golosov,Mikhail,Robert E.Lucas(2005):“Menu Costs and Phillips Curves”mimeo.Gertler,Mark and John Leahy(2005):“A Phillips Curve with an Ss Foundation,”mimeo.Monetary Policy Design in the Baseline ModelA benchmark case.Optimal monetary policy and its implementation.The Taylor Principle. Simple Monetary Policy Rules.Second order approximation to welfare losses.Evidence on Monetary Policy rules.The effects of technology shocks:theory and evidence.Galí,Jordi(2003):“New Perspectives on Monetary Policy,Inflation,and the BusinessCycle,”in Advances in Economics and Econometrics,volume III,edited by M.Dewatripont, L.Hansen,and S.Turnovsky,Cambridge University Press(also available as NBER WP#8767).Woodford,Michael(2003):Interest and Prices:Foundations of a Theory of Monetary Policy,Princeton University Press,chapter6.Yun,Tack(2005):“Optimal Monetary Policy with Relative Price Distortions”American Economic Review,vol.95,no.1,89-109Blanchard,Olivier and Charles Kahn(1980),“The Solution of Linear Difference Models under Rational Expectations”,Econometrica,48,1305-1311Bullard,James,and Kaushik Mitra(2002):“Learning About Monetary Policy Rules,”Journal of Monetary Economics,vol.49,no.6,1105-1130.Woodford,Michael(2001):“The Taylor Rule and Optimal Monetary Policy,”American Economic Review91(2):232-237(2001).Rotemberg,Julio and Michael Woodford(1999):“Interest Rate Rules in an Estimated Sticky Price Model,”in J.B.Taylor ed.,Monetary Policy Rules,University of Chicago Press.Benhabib,Jess,Stephanie Schmitt-Grohe,and Martin Uribe(2001):“The Perils of Taylor Rules,”Journal of Economic Theory96,40-69.Levin,Andrew,Volker Wieland,and John C.Williams(2003):“The Performance of Forecast-Based Monetary Policy Rules under Model Uncertainty,”American Economic Review,vol.93,no.3,622-645.Clarida,Richard,Jordi Galí,and Mark Gertler(2000):“Monetary Policy Rules and Macroeconomic Stability:Evidence and Some Theory,”Quarterly Journal of Economics,vol. 115,issue1,147-180.Taylor,John B.(1998):“An Historical Analysis of Monetary Policy Rules,”in J.B.Taylor ed.,Monetary Policy Rules,University of Chicago Press.Orphanides,Athanasios(2003):“The Quest for Prosperity Without Inflation,”Journal of Monetary Economics50,633-663Galí,Jordi(1999):“Technology,Employment,and the Business Cycle:Do Technology Shocks Explain Aggregate Fluctuations?,”American Economic Review,vol.89,no.1,249-271.Basu,Susanto,John Fernald,and Miles Kimball(2004):“Are Technology Improvements Contractionary?,”American Economic Review,forthcoming(also NBER WP#10592).Francis,Neville,and Valerie Ramey(2005):“Is the Technology-Driven Real Business Cycle Hypothesis Dead?Shocks and Aggregate FLuctuations Revisited,”Journal of Monetary Economics,forthcoming.Galí,Jordi and Pau Rabanal(2004):“Technology Shocks and Aggregate Fluctuations: How Well Does the RBC Model Fit Postwar U.S.Data?,”NBER Macroeconomics Annual 2004,225-288.(also as NBER WP#10636).Christiano,Lawrence,Martin Eichenbaum,and Robert Vigfusson(2003):“What happens after a Technology Shock?,”NBER WP#9819.Galí,Jordi,J.David López-Salido,and Javier Vallés(2003):“Technology Shocks and Monetary Policy:Assessing the Fed’s Performance,”Journal of Monetary Economics,vol.50, no.4.,723-743.Extensions of the Baseline Model and their Implications for Monetary PolicyCost-push shocks.Nominal wage rigidities.Monetary frictions.Inflation inertia.Real wage rigidities.Steady state distortions.Estimated medium-scale models.Giannoni,Marc P.,and Michael Woodford(2003):“Optimal Inflation Targeting Rules,”in B.Bernanke and M.Woodford,eds.The Inflation Targeting Debate,Chicago,Chicago University Press.(also NBER WP#9939).Woodford,Michael(2003):Interest and Prices:Foundations of a Theory of Monetary Policy,Princeton University Press,chapters6-8.Clarida,Richard,Jordi Galí,and Mark Gertler(1999):“The Science of Monetary Policy:A New Keynesian Perspective,”Journal of Economic Literature,vol.37,no.4,1661-1707.Erceg,Christopher J.,Dale W.Henderson,and Andrew T.Levin(2000):“Optimal Monetary Policy with Staggered Wage and Price Contracts,”Journal of Monetary Economics vol.46,no.2,281-314.Huang,Kevin X.D.,and Zheng Liu.(2002):“Staggered Price-setting,staggeredwage-setting and business cycle persistence,”Journal of Monetary Economics,vo.49,405-433.Woodford,Michael(2003):“Optimal Interest Rate Smoothing,”Review of Economic Studies,vol.70,no.4,861-886.Steinsson,Jón(2003):“Optimal Monetary Policy in an Economy with Inflation Persistence,”Journal of Monetary Economics,vol.50,no.7.Blanchard,Olivier J.and Jordi Galí(2005):“Real Wage Rigidities and the Nw Keynesian Model”mimeo.Benigno,Pierpaolo,and Michael Woodford(2005):“Inflation Stabilization and Welfare: the Case of a Distorted Steady State”Journal of the European Economic Association, forthcoming.Khan,Aubhik,Robert G.King and Alexander L.Wolman(2003):“Optimal Monetary Policy,”Review of Economic Studies,825-860.Christiano,Lawrence J.,Martin Eichenbaum,and Charles L.Evans(2001):“Nominal Rigidities and the Dynamic Effects of a Shock to Monetary Policy,”Journal of Political EconomySmets,Frank,and Raf Wouters(2003):“An Estimated Dynamic Stochastic General Equilibrium Model of the Euro Area,”Journal of the European Economic Association,vol1, no.5,1123-1175.Monetary Policy in the Open EconomyEmpirical issues.Two country models.Small Open Economy.Monetary Unions.Local Currency Pricing.Benigno,Gianluca,and Benigno,Pierpaolo(2003):“Price Stability in Open Economies,”Review of Economic Studies,vol.70,no.4,743-764.Galí,Jordi,and Tommaso Monacelli(2005):“Monetary Policy and Exchange Rate Volatility in a Small Open Economy,”Review of Economic Studies,vol.72,issue3,2005,707-734.Clarida,Richard,Jordi Galí,and Mark Gertler(2002):“A Simple Framework for International Monetary Policy Analysis,”Journal of Monetary Economics,vol.49,no.5, 879-904.Benigno,Pierpaolo(2004):“Optimal Monetary Policy in a Currency Area,”Journal of International Economics,vol.63,issue2,293-320.Monetary and Fiscal Policy InteractionsFiscal policy rules and equilibrium determination.Distortionary taxes and optimal policy. Non-Ricardian economies and the effects ernment spending.Optimal monetary and fiscal policy in currency unions.Leeper,Eric(1991):“Equilibria under Active and Passive Monetary Policies,”Journal of Monetary Economic s27,129-147.Sims,Christopher A.(1994):“A Simple Model for the Determination of the Price Level and the Interaction of Monetary and Fiscal Policy,”Economic Theory,vol.4,381-399.Woodford,Michael(1996):“Control of the Public Debt:A Requirement for Price Stability,”NBER WP#5684.Davig,Troy and Eric Leeper(2005):“Fluctuating Macro Policies and the Fiscal Theory,”mimeo.Schmitt-Grohé,Stephanie,and Martin Uribe(2004):“Optimal Fiscal and Monetary Policy under Sticky Prices,”Journal of Economic Theory114,198-230Schmitt-Grohé,Stephanie,and Martin Uribe(2003):“Optimal Simple and Implementable Monetary and Fiscal Rules,”NBER WP#10253.Blanchard,Olivier and Roberto Perotti(2002),“An Empirical Characterization of the Dynamic Effects of Changes in Government Spending and Taxes on Output,”Quarterly Journal of Economics,vol CXVII,issue4,1329-1368.Fatás,Antonio and Ilian Mihov(2001),“The Effects of Fiscal Policy on Consumption and Employment:Theory and Evidence,”INSEAD,mimeo.Galí,Jordi,J.David López-Salido and Javier Vallés(2005):“Understanding the Effects of Government Spending on Consumption,”mimeo.Galí,Jordi,and Tommaso Monacelli(2005):“Optimal Monetary and Fiscal Policy in a Currency Union:A New Keynesian Perspective,”miemo.。

人工智能导论 AI introduction

Effectors
List of Possible Actions
Goals/Utility
What’s involved in Intelligence?
● Ability to interact with the real world
to perceive, understand, and act e.g., speech recognition and understanding and synthesis e.g., image understanding e.g., ability to take actions, have an effect
Academic Disciplines relevant to AI
● Philosophy Logic, methods of reasoning, mind as physical system, foundations of learning, language, rationality. Formal representation and proof, algorithms, computation, (un)decidability, (in)tractability modeling uncertainty, learning from data utility, decision theory, rational economic agents neurons as information processing units. how do people behave, perceive, process cognitive information, represent knowledge. building fast computers design systems that maximize an objective function over time knowledge representation, grammars

OF THE INITIAL DATA SAMPLE

Pattern Recognition and Image Analysis, Vol. 10, No. 2, 2000, pp. 187–194.Original Text Copyright © 2000 by Pattern Recognition and Image Analysis. English Translation Copyright © 2000 by MAIK “Nauka/Interperiodica” (Russia).Problems of Further Development of the Group Methodof Data Handling Algorithms. Part IA. G. Ivakhnenko* and G. A. Ivakhnenko***Glushkov Cybernetics Institute, National Academy of Sciences of Ukraine,pr. Akademika Glushkova 40, Kiev, 252207 Ukraine **National Institute for Strategic Studies, ul. Pirogova 7a, Kiev, 252030 Ukrainee-mail: gai@gmdh.kiev.ua; gai@.uaAbstract —The GMDH algorithms for solving interpolation problems of artiﬁcial intelligence differ from each other in the form of the reference function and the iteration rules of the multilayer model structure. In some multilayer algorithms, the number of terms in the iteration rule is constant, which leads to the skipping of some models. In the algorithm called combinatorial, the iteration rule increases by one term when passing to each next row, which ensures an exhaustive search through all of the equations. For exact and complete data, the min-imum of the external criterion is nonsharp, and to determine an optimal method, extrapolation of the locus of points of the minimum of the external criterion should be performed. A comparison of linear, polynomial, and ratio-polynomial (with respect to the coefﬁcients) functions may give a method for improving the accuracy of problem solutions. To reduce computational time, a threshold GMDH algorithm is developed which prelimi-narily estimates the effectiveness of the input variables at the information level and searches for model-candi-dates based on the most effective input variables (arguments or features).Received December 27, 19991. PREPROCESSINGOF THE INITIAL DATA SAMPLEIt is expedient to accept the following procedure for preprocessing large samples of initial data.(1) The “wild points” (the values of variables are obviously impossible) are removed and replaced by the tripled mean deviation.(2) The mean value of the variables is calculated after the wild points are removed.(3) The missing values in the sample are replaced by the mean value.(4) The quantitative variables are normalized to ﬁt into the range between 0 and 1.(5) Each qualitative variable is assigned the value 0or 1, depending on its class.If it is required to recognize several patterns, the sample is divided into several subsamples, and the pat-terns or classes are recognized pairwise.2. ACHIEVEMENT OF THE MODEL UNIQUENESS AND ESTIMATION OF ITS REPRESENTATIVENESSIn recursive search modeling methods, the initial data are represented in the sample of experimental data as a table with N rows, which are called observations,or realizations, or images (in pattern recognition). The model sought for is an equation that expresses the valueof the output variable through the current and past (i.e.,retarded) values of the input variables. In the GMDH algorithms, the model is sought in the form of a linear polynomial. The complexity of the model structure is determined by the number of terms in the polynomial.The optimal model (most accurate under the preset noise level) corresponds to a minimum of the external accuracy criterion.We use the term speciﬁc complexity for the ratio of the number of terms in the polynomial S describing the model to the number M + 1 of the input variables (pri-mary and secondary features) increased by one (to take into account the presence of the free term).The graphically represented dependence of the external criterion on the speciﬁc complexity of the model answers all questions about the number of min-ima in the model and the sufﬁciency or representative-ness of the sample. The number of models that can be obtained based on a given sample equals the number of sufﬁciently sharp minima of the dependence. A sample is considered sufﬁcient or representative if it gives only one sharp minimum. The uniqueness of the minimum can be achieved by dividing the sample into parts according to the clusters of the optimal physical clus-tering. The resulting sample must contain only the rows included in the ﬁrst cluster (in decreasing order of the number of points).For the second model, the points of the second clus-ter are used, etc. The model is considered most repre-sentative if it gives the absolute minimum of the exter-nal criterion.188 PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 2000A. G. IVAKHNENKO, G. A. IVAKHNENKOFigure 1 shows the typical forms of a characteristic that expresses the dependence of the external accuracy criterion on the speciﬁc complexity of the model. The form of the characteristic allows us to judge the initial data sample. In the case shown in Fig. 1a, we can con-clude that the sample contains no sufﬁciently effective variables. Figure 1b corresponds to a large noise vari-ance or incomplete data. Figure 1c shows the formation of an uncertainty zone in the region of exact data, which impedes the choice of a unique nonphysical optimal model.Finally, Fig. 1d shows a sample containing data cor-responding to two models. In this case, we can obtain more accurate models by dividing the sample into two parts with the use of clustering.3. PROBLEMS RELATEDTO THE UNCERTAINTY ZONE IN THE DOMAINOF EXACT AND COMPLETE DATA Interpolation problems of artiﬁcial intelligence,such as the problem of predicting random processes,dependence detection, pattern recognition, etc., can be solved by either constructing mathematical models or searching for analogs in prehistory. The deductive log-ical modeling methods only apply to comparatively simple cases, where the mechanism of operation of theobject is clear and the set of arguments is known. These methods give a complete physical model of the object,which is only optimal if the set of the input exactly measured variables is complete. For an unknown set of input variables measured with errors, more accurate results are given by the simpliﬁed nonphysical model obtained with the use of the recursive search Group Method of Data Handling (GMDH) [1–3].The GMDH is based on sorting models of gradually increasing complexity and estimating them according to an external criterion on an independent data subsample.As the input variables, any parameters that may affect the process can be used. A computer automatically deter-mines the structure of the model and the degree of inﬂu-ence of the parameters on the output value. The model corresponding to the minimum value of the external criterion is considered the best.The GMDH has been developed for complex system modeling, prediction, identiﬁcation and approximation of multifactor systems, diagnostics, pattern recogni-tion, and data sample clustering. It is proved analyti-cally that only this recursive method of self-organiza-tion gives an optimal nonphysical model whose accu-racy is higher and whose structure is simpler than the structure of the usual complete physical model for inac-curate, noisy, or short data samples.The recent GMDH developments led to the creation of decision support systems based on normative predic-tion (according to an “if–then” scenario) and control optimization with the use of simpliﬁed linear program-ing algorithms and neural networks with active neu-rons. These neural networks implement the doubly multilayer structure: neurons with multilayer structures are gathered into a multilayer network. This makes it possible to optimize the set of input parameters at each level while the accuracy increases. The accuracy of pre-diction, approximation, or pattern recognition can be enhanced beyond the values reached by the usual neural networks with simple neurons or by the usual statistical methods. V ery accurate predictions of the New Y ork stock exchange and other complex objects were obtained with the use of a doubly multilayer neural network in which every neuron was operated by the GMDH algorithm.In the combinatorial GMDH algorithm, the number of terms in the polynomial model gradually increases,while an external accuracy criterion decreases; the exter-nal criterion is calculated based on an independent mate-rial, i.e., on a separate test data subsample. The depen-dences of only external criteria on the model complexity have minima. The internal criteria, which are calculated from the same data from which the coefﬁcients of models are estimated, result in increasing the accuracy of the model with its complexity; this leads to the choice of an overcomplicated nonoptimal model. As an external accuracy criterion, either the regularity criterion or the cross-validation criterion [4] is recommended.Fig. 1. Various forms of dependence of an external criterion AR on the model complexity: (a) the dependence has no minimum; (b) the data are incomplete or inaccurate; (c) the dependence has an uncertainty zone; (d) the sample contains a mixture of data corresponding to two models.PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 2000PROBLEMS OF FURTHER DEVELOPMENT OF THE GROUP METHOD189An application of the combinatorial GMDH algo-rithm may involve two difﬁculties. First, the criterionminimum becomes nonunique for exact experimental data, i.e., under low noise. In Fig. 2, an entire uncer-tainty zone (the LOR interval) appears instead of a point of minimum. The optimal physical model then corresponds to the midpoint of the uncertainty zone.However, for very accurate and complete data, when the coordinate of the point R is one, an optimal simpli-ﬁed nonphysical model can only be found by searching for a model according to some external or internal accuracy criterion in the uncertainty zone. It is sufﬁ-cient to apply the search according to the external crite-rion only once to ﬁnd a criterion minimum, which determines an optimal nonphysical model. The physi-cal complete model (more precisely, its polynomial approximation) can be found by extrapolation of the line that is the locus of the points of minimum (LPM) of char-acteristics constructed for various noise variances. Under certain conditions, the LPM line passes through the point P with coordinates 1/( M + 1), 1 and through the point of minimum obtained based on the available data.Extrapolation of the LPM up to its intersection point with the abscissa axis speciﬁes the structure of the sought physical model, which should be applied under exact input data. For noisy and incomplete data, the nonphysical model corresponding to the minimum of the external accuracy criterion remains optimal.Solving pattern recognition problems does not require extrapolation of the LPM, because the optimal model or the discriminant function is usually supposed to be used in an environment with the same noise level under which the data sample is obtained. For this rea-son, in pattern recognition, nonphysical models corre-sponding to the minima of external accuracy criteria are applied. The higher the noise, the simpler the nonphys-ical recognizing model; under exact input data, the physical and nonphysical models coincide.Predicting random processes also requires con-structing a nonphysical model. The physical model is largely needed to logically interpret the nonphysical model and reveal the mechanism of operation of the object used to obtain the data sample.4. ACHIEVEMENT OF THE POLYNOMIAL COMPLEXITY OF THE ALGORITHM Another difﬁculty involved in applying the combi-natorial algorithm is that the algorithm has exponential computing-time complexity. Adding one new variable doubles the computing time T :where t 0 and t 1 are time constants, and M is the number of features.T t 0t 12M,+= For polynomial algorithms, the computing time T is proportional to the number of features to be taken into account [6]:To achieve polynomial complexity in the new threshold GMDH algorithm, we introduce a second auxiliary criterion for the effectiveness of the input variables, which are called predictors or features. For binary features, the criterion of the number of resolved disagreements [6] is recommended.The effectiveness of continuous features is esti-mated based on the absolute value of the correlation coefﬁcient of the output variable and the feature to be estimated [7]. If the variables have different dimen-sions, then they are normalized to ﬁt into the range between zero and one.The primary features are those included in the data sample. As is shown in Fig. 3, in different interpolation problems, different primary features are used. The least number of features is required to detect dependences and recognize patterns. The values of the primary fea-tures are used to generate values of additional second-ary features. The secondary features to start with are the coordinates of the two ﬁrst analogs. The analog of a row in a sample is the nearest row in the same sample.T t 0t 1M .+= OS / M + 1RLSNM Number of featuresExternal criterionP (1/ M + 1;1)00.20.40.60.80.9Model complexity 1.00.90.80.70.60.50.40.30.20.10LPMPMFig. 2.The dependence of the external accuracy criterion on the complexity of the model structure for the physical model in the absence of noise (PM) and a simpliﬁed nonphysical model for the same noise variance as in the initial data sam-ple (SNM); LPM is the locus of the points of minimum of the external accuracy criterion.190PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 2000A. G. IVAKHNENKO, G. A. IVAKHNENKOAnalogs can be considered retarded arguments of some virtual process of row formation in the data sample [8].As secondary features, the covariances (pairwise prod-ucts of normalized values) of primary features can also be used [7]. All primary and secondary features together are ranked according to effectiveness. The ordered set of features is subjected to a threshold anal-ysis according to the following rules:(1) The rule of merging two features. Two neighbor-ing features are replaces by one average feature if they have close effectivenesses that differ by no more than a certain threshold value E1 . This rule follows from the metrology law about averaging close values of two measurements.(2) The rule of changing the order of features. If the difference of the effectivenesses of two neighboring features is larger than E1 but smaller than another threshold E2 , then, in addition to the ordered set under analysis, another sequence of features is formed, in which the close features are exchanged. Testing the two orderings of the features implements Gabor’s principle of freedom of choice. In practice, this rule reduces to estimating one more additional model [3].As it is known, in a single GMDH algorithm without the use of a network, the number of variables over which the external criterion search is performed is either constant (if the search is exhaustive) or reduces when passing from one row to another at the expense of eliminating noneffective input variables. The distin-guishing feature of the threshold GMDH algorithm is that the number of search variables increases by one when passing to each next row.In the ﬁrst row, only the output variable is used, and its mean value is found. In the second search row, one most effective variable is used. In the second row, the search involves two variables, etc. If the effectiveness of the added search variable is close to the effectiveness of the preceding variable, then one more equation of a model-candidate is formed. The search continues until the minimum of the external criterion is attained.5. VERIFICATION OF THE NECESSITY OF AN ORTHOGONAL DATA SAMPLE If the sequence of features ranked according to effectiveness contains regions of accumulation, i.e., the features are distributed nonuniformly, then it is recom-mended to preliminarily orthogonalize the sample by the Karhunen–Loéve algorithm [9].Example. Suppose that a sample of experimental data contains values of seven input variables, V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , and V 7 (the number of features is M = 7).Suppose also that computation of the correlation coefﬁ-cient between the features and the output variable yields the following sequence of features ranked according to effectiveness:Let us set the following threshold values: the thresh-old value for the merging of features is E = 0.01, and the threshold value for the change of order is e = 0.1.The results of an analysis of the series of features ranked by effectiveness are as follows.(1) No two features must be merged.(2) We must try to change the order of only one pair of features, V 4 and V 5.(3) The features are uniformly distributed over the effectiveness interval, and there is no need to apply pre-liminary orthogonalization.As a reference basis function, we choose a linear poly-nomial. Gradually decreasing the effectiveness threshold,we obtain the following set of models-candidates:E V 1()0.9E V 2()0.75E V 3()0.6===E V 4()0.45E V 5()0.4==E V 6()0.23E V 7()0.1== k – k – k – k + k – k – k – k +(a)(b)k –k –k –(c)k ,k , k ,(d)k , sFig. 3. Discrete templates of GMDH ﬁlters for (a) the implicit predicting ﬁlter, (b) the explicit predicting ﬁlter, (c) the smoothing ﬁlter, and (d) the ﬁlter of dependence detection and pattern recognition; T is the time axis and V is the axis corresponding to the virtual process of image formation.PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 2000PROBLEMS OF FURTHER DEVELOPMENT OF THE GROUP METHOD 191;;;;;;;;.For the complexity S = 5, we obtain two models-candidates; the external criterion determines which should be included in the extremal characteristic shown in Fig. 2. We can stop increasing the complexity of model equations as soon as the coordinates of the point O of the minimum of the external criterion are found.Calculation of the external criterion makes it possi-ble to construct its dependence on the complexity of the model structure (see Fig. 2). If the problem is to recog-nize two patterns, then the optimal model obtained is the best discriminant function [7].If the number of input variables is not too large,then, instead of the rule of order veriﬁcation, the sim-pler and less rigid rule of noneffective variable elimina-tion is used. For example, all input variables with a cor-relation coefﬁcient less than 0.2 in absolute value are disregarded. This drastically reduces the amount of computations involved in the usual combinatorial GDMH algorithm, especially if the search through model-candi-dates terminates as soon as the minimum of the external accuracy criterion is attained.A calculation of a sequence of initial variables ranked according to the effectiveness criterion, thresh-old analysis of this sequence, and organization of a search for the structure of a model-candidate optimiz-ing the external accuracy criterion solve the problem of constructing a recursive GMDH algorithm with poly-nomial complexity.The algorithm for estimating feature effectiveness has polynomial complexity, because its computational time is proportional to the number of features. The threshold analysis of the sequence of features ranked by effectiveness does not require much time. The con-struction of models-candidates and the estimation of their coefﬁcients also have polynomial complexity due to the application of the bordering procedure [1, 2]. The coefﬁcients of each model are calculated based on the estimates of the coefﬁcients of models of lower com-plexity.The computer programs implementing the border-ing procedure are designed for both the inclusion andthe removal of a term of the polynomial model [1, 2].The bordering procedure substantially reduces computa-tional time in searching GMDH algorithms. But estimat-ing the feature effectiveness according to the absolute value of the correlation coefﬁcient reduces the computa-tional time even further. The ordering of features deter-mined by this absolute value is subsequently veriﬁed by the method of threshold analysis of the ranked sequence of features based on the external accuracy criterion.Thus, the threshold algorithm of model self-organiza-tion as a whole has polynomial complexity, which is conﬁrmed by experimental computations.6. THE THRESHOLD GMDH ALGORITHMWITH SELECTION OF THE SET OF EFFECTIVE V ARIABLES The optimal threshold value separating effective and noneffective variables can be obtained by repeatedly applying the combinatorial GMDH algorithm while the number of the effective variables subject to search suc-cessively increases. In the example considered above,the combinatorial algorithm should be applied to data samples containing the following input variables:Increasing the number of the effective variables that form the input of the algorithm terminates as soon as the minimum of the external accuracy criterion is attained.The described algorithm is often applied instead of the veriﬁcation of the order of variables, especially when the choice of the threshold value for the order veriﬁcation is impeded.S 1y a 01==S 2y a 02a 12V 1+==S 3y a 03a 13V 1a 23V 2++==S 4y a 04a 14V 1a 24V 2a 34V 3+++==S 5y a 05a 15V 1a 25V 2a 35V 3a 45V 4++++==S 5y b 05b 15V 1b 25V 2b 35V 3b 45V 4++++==S 6y a 06a 16V 1a 26V 2a 36V 3a 46V 4a 65V 5+++++==S 7y a 07a 17V 1a 27V 2a 37V 3 +a 47V 4a 57V 5a 67V 6+++++==S 8y a 08a 18V 1a 28V 2a 38V 3 +a 48V 4a 58V 5a 68V 6a 78V 7++++++==S 1Y ;=S 2YV 1;=S 3YV 1V 2;=…………………S 8YV 1V 2…V 7.=PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 20007. THE APPLICATIONOF THE RATIO-POLYNOMIAL REFERENCE FUNCTION TO SOLVE INTERPOLATION PROBLEMS OF ARTIFICIAL INTELLIGENCE Problems of process prediction, dependence detec-tion, and pattern recognition are usually solved with the use of a polynomial reference (or support) function, lin-ear with respect to the coefﬁcients. Both primary and secondary features are used as arguments; the second-ary features are expressed by simple nonlinear depen-dencies via the primary features.For essentially nonlinear objects, the solution accu-racy can be improved by extending the search by form-ing ratio-polynomial functions. The table shows an example of such an extension performed under the fol-lowing two constraints: (i) each argument is included in the ratio-polynomial function only once and (ii) all coefﬁcients are positive.These constraints are not vital and can be removed,but this would increase the amount of the model-candi-dates to be searched through to optimize the external accuracy criterion, which is already fairly large. For this reason, we only consider the constrained extension of search domains, as in the table.8. A METHOD FOR SUBSTANTIALLYREDUCING THE SEARCHIn the table, only ratio-polynomial functions with positive coefﬁcients are to be searched through. For such functions, the output variable is related to thecomputational time almost does not change:T = 10 min.9. A GENERAL DESCRIPTIONOF A NONLINEAR GMDH ALGORITHM WITH A RATIO-POLYNOMIAL REFERENCEFUNCTION The recursive search approach to modeling, which is also called the self-organization of models, performs all tasks except those related to the choice and compu-tation of a criterion by searching, i.e., testing a large number of possible solutions by an external criterion,which is calculated on a separate part of the data sam-ple. The less the value of the external accuracy crite-rion, the better the corresponding model or algorithm.An important role is also played by Gabor’s choice principle [3]. The GMDH algorithms search through a large number of candidates to solve the following two problems.(1) The effectiveness of the primary and secondary fea-tures and the sets of two, three, and more features are esti-mated. The freedom-of-choice principle requires that the sets to be estimated be formed not only by the most effective features selected in the preceding row, but also by the next most effective features and sets.(2) The models optimizing the external criterion in every row are compared to each other, and an optimal model is selected.PATTERN RECOGNITION AND IMAGE ANALYSIS V ol. 10 No. 2 2000PROBLEMS OF FURTHER DEVELOPMENT OF THE GROUP METHOD 19310. A METHOD FOR ESTIMATINGTHE COEFFICIENTSOF RATIO-POLYNOMIAL MODELS To estimate the coefﬁcients of the models, we trans-form all ratio-polynomial functions into auxiliary poly-nomials and include additional columns of digits into the data sample for all of the terms of these polynomi-als. Then, we apply algorithms for estimating coefﬁ-cients of polynomial models.Example. It is required to estimate the coefﬁcients of the ratio-polynomial modelLet us form the auxiliary polynomialThe variables y , V 1, and yV 2 are treated as argumentswhose values are easy to calculate with the use of the data sample. The coefﬁcients are estimated by the usual least-square method [11].11. PREPROCESSING OF LARGE DATA SAMPLESThe ﬁrst descent is performed by applying the cor-relation analysis to the elements in the data sample,reducing the sample to the one-moment form, and dividing it into uniform subsamples used to obtain models by GMDH algorithms.Reduction to the one-moment form involves an increase in the number of arguments. To each sample row,which contains the current variable values indexed by k ,we add several future values indexed by k + 1, k + 2, etc.,and retarded arguments indexed by k – 1, k – 2, etc. This allows us to arbitrarily change the order of rows, simi-lar to the problem of pattern recognition.The correlation analysis of sample elements is based on the idea of the genetic approach to modeling. The combinatorial GMDH algorithm, where the iteration rule increases by one term when passing to each next row, is very similar to the genetic optimization of the choice of the number of genders of living organisms during the evolution of species in Nature, which took millions of years.Another, multilayer GMDH algorithm [1, 2] with an invariable rule of iteration resembles the actions of a selectionist who obtains the required features in several generations. Thus, all GMDH algorithms have genetic analogs. However, only those of them should be called genetic in which the number of models-candidates sub-ject to search is reduced by taking into account the generic (correlation) relations. Close arguments and models merge, and noneffective ones are disregarded.The threshold GMDH algorithm implements such a selection.y a 0a 1V 1+1b 1V 2+----------------------.=y a 0a 1V 1b 1yV 2.–+=The concept of optimal physical clustering, which is implemented by the objective computer clustering (OCC) algorithm, makes it possible to divide the data sample into subsamples of uniform vectors contained in one cluster. In solving problems of random process prediction, it is recommended to form predictions for all uniform samples and select the most accurate pre-diction. In recognizing patterns and situations, it is also recommended to obtain discriminant functions for all uniform subsamples to select the most effective deci-sion rule. Thus, the reduction of computational time is due to the processing of small subsamples instead of one large sample.In processing large data samples, each element is characterized by two values, namely, of the output vari-able or argument and of the contribution of the element to the absolute value of the correlation coefﬁcient between the variable under consideration and the out-put variable. We refer to this contribution as the effec-tiveness of the sample element. A rational reduction of sample size consists in the elimination of the least effective elements. The effectiveness of a sample ele-ment equals the difference of two correlation coefﬁ-cients, one calculated for the argument value speciﬁed in the sample, and the other, for the element equal to the mean value of the variable. A simpliﬁed calculation of the effectiveness of an element can be performed by the formula,where W is the value of the output variable, is its mean value, V is the value of the argument at the sample element under consideration, and is the mean value of the variable to which this element belongs.The denominator equals the maximum effectiveness over all of the sample elements. Thus, the effectiveness of each element is normalized by the largest value, and we can set a certain threshold effectiveness value, say,0.3. The rows and columns in the sample that contain only elements with effectiveness less than the threshold value are removed from the sample. The effectiveness threshold is raised until the size of the sample becomes acceptable for calculations on an available computer.The limiting parameters of models that can be com-puted on a PC can be expressed by the empirical equa-tion m ≤ 27 – 0.046M – 1, where M is the number of sample arguments-candidates and m is the number of arguments in the model.We see that, if the sample contains 350 rows, then a model with ten terms can be obtained in a reasonable time, which is sufﬁcient for the majority of practical problems.The further processing of large samples reduces to splitting them into subsamples of uniform vectors by the OCC algorithm, and the subsample that gives a most accurate prediction (in process prediction) ore W –()*V –()max W –()*V –()()---------------------------------------------=W V。

下载提示

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第8章非线性系统分析

页数:72
第8章非线性系统分析

页数:115
Updating Nonlinear Finite Element Models

页数:10
an introduction to the analysis of algorithms

页数:2
第7章非线性系统分析

页数:87
第7章非线性系统的分析

页数:129
Algorithms for Non-negative Matrix Factorization

页数:7
第8章非线性系统分析

页数:49
第七章非线性系统的分析

页数:129
第七章非线性系统分析

页数:48
simulation modeling and analysis

页数:2
Nonlinear Systems and Dynamics

页数:2

Chapter 1 MODELING UNCERTAINTY IN NONLINEAR ANALOG SYSTEMS WITH AFFINE ARITHMETIC

合集下载

Sliding Mode Control

Part1MonetaryPolicy,Inflation,andtheBusinessCycle

人工智能导论 AI introduction

OF THE INITIAL DATA SAMPLE

文档推荐

最新文档