State determination an iterative algorithm

a r X i v :q u a n t -p h /0511167v 1 16 N o v 2005Calculating state-to-state transition probabilities within TDDFTNina Rohringer,Simone Peter,Joachim Burgd¨o rferInstitute for Theoretical Physics,Vienna University of Technology,A-1040Vienna,AustriaAbstractThe determination of the elements of the S-matrix within the framework of time-dependent density-functional theory (TDDFT)has remained a widely open question.We explore two different methods to calculate state-to-state transition probabilities.The first method closely follows the extraction of the S-matrix from the time-dependent Hartree-Fock approximation.This method suffers from cross-channel correlations resulting in oscillating transition probabilities in the asymptotic channels.An alternative method is proposed which corresponds to an implicit functional in the time-dependent density.It gives rise to stable and accurate transition probabilities.An exactly solvable two-electron system serves as benchmark for a quantitative test.As a matter of principle,time-dependent density functional theory [1]provides a highly efficient method to solve the time-dependent quantum many-body problem.It yields directly the time-dependent one-particle density n ( r ,t )of the many-body system.All physical ob-servables of the quantum system can,in principle,be determined from the density.In practice there a two essential ingredients to a TDDFT calculation.First an approximation to the time-dependent exchange-correlation potential V xc [n ]( r ,t )has to be found which viathe non-interacting Kohn-Sham system determines the evolution of the density.The second ingredient are functionals that allow the extraction of physical observables from the density.For some of the observables such as the ground-state energy extraction is straight forward within ground-state density functional theory [2].Excited-state spectra have been obtained from linear-response functionals [3,4].Beyond linear response,the time-dependent dipole moment which governs the emission of high-harmonic radiation can be directly determined from n ( r ,t ).Ionization probabilities can be approximately extracted by identifying the in-tegrated density beyond a certain critical distance from the bound system with the flux of ionized particles [5,6].However,in general,on the most fundamental level,state-to-state transition probabilities contain the full information on the response of a many-body systemto an external perturbation.One example are bound-bound transition amplitudes required, e.g.in coherent control calculations of laser-matter interactions within TDDFT[7],cur-rently a hot topic since atto-second laser pulses allow the control of the electron dynamics. This poses one fundamental question:How can state-to-state transition probabilities be extracted from TDDFT?The ultimate goal of the study of the in general non-linear response of the many-body sys-tem to a time-dependent perturbation is the determination of the state-to-state transition amplitudeS if=limχf|U(t,−t)|χi ,(0.1)t→∞where|χi,f are the initial(final)channel states of the system prior to(i)and after(f)the perturbation,and U(t1,t2)is the time evolution operator of the system.The challenge is, thus,to construct a functional S i,f[n]that allows to extract S if from TDDFT.The present paper addresses methods to extract transition probabilities between discrete states of the many-body system.As point of reference,we investigatefirst the evaluation of eq.(0.1) employing Kohn-Sham orbitals in close analogy to the time-dependent Hartree-Fock(TDHF) method(see[8,9,10,11]and references therein).This method would be the equivalent of the at least zeroth order of a time-dependent many-body perturbation theory(S-matrix theory)in which the time-dependent non-interacting Kohn-Sham system is considered as the unperturbed system.This method involves three steps of approximations:The initial state,thefinal state and the many-body propagator are approximated by their TDDFT equivalents.We encounter similar conceptual problems(“cross-channel correlations”)as TDHF does.We then formulate a novel functional that allows the determination of S i,f[n] which is shown to be free of these deficiencies.We test the method with the help of an exactly solvable two-electron model.We consider an interacting N-electron system of Hamiltonian H0with stationary eigenstates χi,f which is subject to a perturbation V(t)which is switched on at time t=0and switched offat time t=τ.The initial state of the system|χi is assumed to be the ground state and evolves according to the time-dependent many-body Schr¨o dinger equation(in a.u.)∂ithe unperturbed systemS i,f=limt→∞χf|Ψ(t) .(0.3) For later reference we note that the time evolution of the projection amplitude for t>τis given in terms of the eigenenergies of the asymptoticfinal states,εf,byχf|Ψ(t) =exp(−iεt(t−τ)) χf|Ψ(τ) .(0.4) Since the perturbation vanishes for t>τ,the state-to-state transition probability is given by P i,f=|S i,f|2=| χf|Ψ(τ) |2.Within TDDFT,the time-dependent density is represented through the time-dependent Kohn-Sham spin-orbitalsΦσ,j( r,t)asn( r,t)= σ=↑,↓nσ( r,t)= σ=↑,↓Nσ j=1|Φσ,j( r,t)|2,(0.5) where Nσdenotes the number of electrons of spinσ.The one-particle spin-orbitalsΦσ,j( r,t) evolve according to the time-dependent Kohn-Sham equation governed by the one-particle Kohn-Sham HamiltonianH KSσ[n↑,n↓]=−1is imposed onχf when the evolution is calculated by forward-propagation.The simplest choice for channel states|χf are Kohn-Sham Slater determinants built up from occupied and virtual Kohn-Sham orbitals|Φσ,j of the ground state DFT problem,i.e.S if∼=limt→∞ χDF Tf|ΨT DDF T(t) .(0.7)Reliable transition probabilities can only be expected if both,time-dependent and station-ary Kohn-Sham Slater determinants are good approximations for the time-dependent and stationary many-body wavefunctions,respectively.Excited states often show a higher de-gree of correlation and a single Kohn-Sham Slater determinant is no longer a satisfactory approximation.In those cases,more elaboratefinal-state channel functions are needed.Al-ternatively,configuration-interaction(CI)or multi-configuration Hartree-Fock(MCHF)can be employed[14,15].Within TDDFT,linear response theory allows the calculation of the excitation spectrum by including particle-hole excitations[3,4].As a by-product,improved excited-states,i.e.the particle-hole reduced density matrix,are generated in terms of an expansion in single-particle excitations of Kohn-Sham orbitals.In the present case of a two-electron system this approach should give an improved wavefunction compared to the initial single Kohn-Sham Slater determinant[16].As discussed below,also this approach suffers from the same short-comings as does eq.(0.7).We therefore introduce a new functional which depends only on the time-dependent den-sity.For simplicity and in line with the present model system,the derivation is presented for two-electron systems.Generalizations to arbitrary many-electron systems are straight forward.Starting point is the expansion of the exact time-dependent wavefunction in terms of a complete set offinal-state wavefunctionsΨ( r1, r2,t)= f χf|Ψ(t) χf( r1, r2).(0.8) Using the stationary one-particle reduced density matrixρ(1)f′,f( r)=2 d r2χ∗f′( r, r2)χf( r, r2)(0.9) and the time-dependent transition density matrix defined byT f′,f(t)= χf′|Ψ(t) ∗ χf|Ψ(t) (0.10) the exact time-dependent density is given byn( r,t)= f,f′T f′,f(t)ρ(1)f′,f( r)=Tr T(t)ρ(1)( r) .(0.11)FIG.1:state |N cm=1,n rel=0 (figure b)and second excited state|N cm=2,n rel=0 of exact calculation (full line)and TDDFT calculation(dashed line)for a confining frequencyω=0.25.TDDFT occupation probabilities are obtained using the approximate S-matrix eq.(0.7),final channel states are Slater determinants of Kohn-Sham orbitals|0,0 ,|0,1 and|0,2 .Parameters of the laser pulse: F0=0.07,ωL=0.1839,τ=168The transition density matrix and,in particular,transition probabilities|S i,f|2can be directly determined by inversion of eq.(0.11).Our primary interest lies in the diagonal elements(f′=f)of the transition density matrix T f′,f(t)→S∗i,f′(t)S i,f(t)at times after the switch-offof the external perturbation t>τ.In this case the inversion problem of dimension N F×N F(N F:dimension of truncatedfinal-state space considered)can be drastically sim-plifiing eq.(0.4),for non-degeneratefinal states(εf=εf′),the transition probabilities T ff can be extracted from a time-average over an interval(t−τ)|εf′−εf|≫2π,¯n( r,t):= tτn( r,t′)t−τdt′,(0.12) leading to the read-out functional¯n( r,t)= fρ(1)f,f( r)|S fi|2.(0.13)limt→∞Unlike eq.(0.11),eq.(0.13)requires only an N F-dimensional inversion.In practice,theapplication of eq.(0.13)requires evaluating thefinal state densitiesρ(1)f,f( r)at N F distinctpoints r j j=1,...,N f,so that the matrix R f,j:=ρ(1)f,f( r j)does not become near-singular and remains invertible.The state-to-state transition probabilities then become|S i,f|2=limt→∞N fj=1¯n( r j,t)R−1f,j f=1,..,N f.(0.14)We have tested the functionals(eqs.(0.7)and(0.14))for an exactly solvable system of two electrons confined to a harmonic quantum dot[17,18].In its present1D version, the electron-electron interaction must be replaced by a soft Coulomb potential[19].The Hamiltonian of the system is given byˆH(t)= i=1,2 ˆp2i2x2i−F(t)x i +1b+(x1−x2)2,(0.15) where x i and p i are the coordinates and momenta of electron i(i=1,2).The softening parameter b is set to b=0.55.Similar systems to describe helium in one dimension were studied in the past[5,15,19].The laserfield F(t)with driving frequencyωL=0.1839 and a peakfield amplitude F0=0.07is treated in dipole approximation.A pulse length τ=168was chosen with a two cycle turn on,a two cycleflat top and a two cycle turn off.Introducing center of mass(c.o.m.)coordinates R=x1+x2and relative coordinates r=x1−x2the Schr¨o dinger equation(0.2)can be separated,since the Hamiltonian of eq.(0.15)splits intoˆH=ˆH rel+ˆH cm(t).The eigenstates of the unperturbed system are char-acterized by the set of quantum numbers(N cm,n rel),the number of nodes of the c.o.m.and relative wavefunction.Initial state is the spin-singlet ground state|N cm=0,n rel=0 .The time dependence of the total Hamiltonian is confined to the c.o.m.Hamiltonian.The exact time-dependent wavefunction therefore separates into a time-dependent c.o.m.and a time-independent relative part,Ψ(r,R,t)=g(r)h(R,t).Since the system starts out from the ground state,h(R,t)represents a coherent state of the one-dimensional harmonic oscillator driven by an external electricfield.The dynamics of the density of this model system is subject to the harmonic potential theorem[20,21],i.e.the density is rigidly shifted without any distortion.In the case of a two-electron spin-singlet system evolving from the ground state,the time-dependent Kohn-Sham scheme consists in solving the Kohn-Sham equation for one doubly-occupied Kohn-Sham orbitalΦ(x,t).For spin-unpolarized two-particle systems the exactFIG.2:Comparison of exact occupation probabilities(solid line)and transition probabilities ob-tained by inversion of eq.(0.14)(dashed line)for the ground state(figure a),first excited state (figure b)and second excited state(figure c).V xc(t)can be constructed using the exact density derived from the Schr¨o dinger equation and inverting the Kohn-Sham equation[22,23].Since the harmonic two-electron quantum dot satisfies the harmonic potential theorem the time-dependence of the exchange-correlation potential is a rigid shift and the exact V xc(t)is easily constructed.We also employed the adiabatic local spin density approximation(ALSDA)with self-interaction correction(SIC) [24].Since no reliable correlation potential is available for a one-dimensional electron system we only consider exchange.The L1norm of the deviation between the exact and TDDFT density is about0.2for the highly correlated system ofω=0.25.The ground state Kohn-Sham equation generates a set of excited virtual Kohn-Sham orbitals|n .Figure1shows a comparison of exact occupation probabilities and those obtained from the approximate S-matrix(eq.(0.7))by projectingΨT DDF T(t)=Φ(x1,t)Φ(x2,t)onto Kohn-Sham Slater determinants.Shown are the occupation of the ground state(figure a,projection onto the Kohn-Sham determinant|0,0 ),thefirst excited state(figure b,projection onto|0,1 ) and the second excited state(figure c,projection onto0,2 ).The second excited state |N cm=2,n rel=0 involves a configuration mixture of at least two Kohn-Sham Slater de-terminants to be well represented(configurations|0,2 and|1,1 ).Neither the projectiononto a single Kohn-Sham configuration state|0,2 (figure1c)nor the projection onto the exact excited state(not shown)yields satisfactory transition probabilities.After the switch-offof the laser,the density undergoes oscillations resulting in time-dependent Hartree and exchange correlation potentials which give rise to oscillations in the occupation probabili-ties.These are the signatures of the”spurious cross-channel correlations”well-known from TDHF[9,10].For the present system,exact excitedfinal states can be easily calculated.We have checked that cross-channel correlations persist when we project onto exact exit-channel states rather than Kohn-Sham determinants.Moreover,we also tested channel states ob-tained from a TDDFT linear-response equation.In this equation the exchange-correlation kernel of TDDFT was approximated by the exchange-only time-dependent optimized ef-fective potential[4,25]and the exact Kohn-Sham orbitals obtained by the exact ground state exchange-correlation potential have been used.The obtained excited-state wavefunc-tions,however,do not significantly differ from the single Kohn-Sham Slater determinants although the excitation energies are considerably improved compared to the Kohn-Sham en-ergy differences.With presently available approximations to the exchange-correlation kernel, TDDFT linear-response theory does not provide improved excited-state wavefunctions.We thus conclude that the projection amplitude of eq.(0.7)is not well-suited to determine an approximate S-matrix within TDDFT.To test the newly proposed read-out functional which depends only on the density,we use the exact time-dependent density n(x,t).In this way,errors due to the approximate exchange-correlation potential can be ruled out and the quality of the proposed functional for state-to-state transition probabilities can be directly assessed.The sum in eqs.(0.12), (0.13)and(0.14)is truncated after the second excited state.Figure2shows a comparison of transition probabilities obtained by projecting the wavefunction according to eq.(0.3) (solid line)and by the new density functional of eq.(0.14)(dashed line)for the three lowest lying states.In the limit of t→∞,i.e.as the averaging interval in eq.(0.12)increases, the transition probability converges within the numerical accuracy towards the exact result. Numerical errors are due to the truncation of the sum overfinal states in eq.(0.14).Note that simply averaging over the cross-channel correlation in eq.(0.7)(seefigure1)would lead, in general,to incorrect results.Similar good agreement can be found for other initial states and other systems[26].In conclusion,we have investigated two different methods to extract state-to-state transi-tion amplitudes from TDDFT calculations.In thefirst method,the correlated many-body wavefunction is approximated by a Slater determinant of the time-dependent Kohn-Sham orbitals.This approximate wave-function is projected onto appropriatefinal states(exact states or Kohn-Sham configuration states).The resulting state-to-state transition prob-abilities suffer oscillations after the switch-offof the external perturbation.The second read-out functional to calculate state-to-state transition probabilities directly involves the time-dependent densities and represents thus a well-suited density functional within the framework of TDDFT.The problem of cross-channel correlations can be avoided and well-defined transition probabilities can be determined in the asymptotic limit t→∞.First results obtained by evaluating the read-out functional with densities resulting from the exact solution of a one-dimensional two-electron Schr¨o dinger equation are very promising. The application of the read-out functional to double excitation of helium are currently being investigated.Work supported by FWF-SFB016.[1] E.Runge,E.K.U.Gross,Phys.Rev.Lett.52,997(1984).[2]P.Hohenberg and W.Kohn,Phys.Rev.136,B864(1964)[3]M.E.Casida,in Recent developments and applications of modern density functional theory,edited by J.M.Seminaro(Elsevier,Amsterdam,1996)p.391[4]M.Petersilka,E.K.U.Gross,K.Burke,Int.J.Quant.Chem.80,534(2000).[5] ppas,R.van Leeuwen,J.Phys.B:At.Mol.Opt.Phys.31,L249(1998)[6]M.Petersilka,E.K.U.Gross,Laser Physics9,105(1999).[7]J.Werschnik,E.K.U.Gross,J.Chem.Phys.123,62206(2005).[8]P.Bonche,S.Koonin,J.W.Negele,Phys.Rev.C13,1226(1976).[9]J.J.Griffin,P.C.Lichtner,M.Dworzecka,Phys.Rev.C21,1351(1980).[10]Y.Alhassid,S.E.Koonin,Phys.Rev.C23,1590(1981).[11]J.W.Negele,Rev.Mod.Phys.54,913(1982)[12] A.G¨o rling,M.Levy,Phys.Rev.B47,13105(1993).[13] A.G¨o rling,M.Levy,Phys.Rev.A50,196(1994).[14]M.H.Beck,A.J¨a ckle,G.A.Worth and H.-D.Meyer,Physics Reports324,1(2000).[15]J.Zanghellini,M.Kitzler,T.Brabec,A.Scrinzi,J.Phys.B:At.Mol.Opt.Phys.37,763(2004).[16]Angel Rubio,private communications[17]M.Taut,Phys.Rev.A48,3561(1993).[18]ufer,J.B.Krieger,Phys.Rev.A33,1480(1986)[19]R.Grobe,J.H.Eberly,Phys.Rev.A48,4664(1993).[20]J.F.Dobson,Phys.Rev.Lett.73,2244(1994).[21]G.Vignale,Phys.Rev.Lett.74,3233(1995).[22]I.D’Amico,G.Vignale,Phys.Rev.B59,7876(1999).[23]M.Lein,S.K¨u mmel,Phys.Rev.Lett.94,143003(2005)[24]J.P.Perdew,A.Zunger,Phys.Rev.B23,5048(1982).[25] C.A.Ullrich,U.J.Gossmann,E.K.U.Gross,Phys.Rev.Lett.74,872(1995).[26]N.Rohringer,S.Peter,J.Burgd¨o rfer to be published。

非线性方程重根的三阶迭代方法李福祥;田金燕;费兆福;巩英海;曹作宝【摘要】为提高求解非线性方程的收敛速度和计算效率,以牛顿法为基础提出一种求解非线性方程重根的迭代方法,该方法以重数已知为前提,迭代格式根据重数为奇数和偶数两种情形分别给出,两种迭代格式每步迭代都只需计算三个函数值(包含一阶导数值)且完全摆脱了二阶导数值的计算,其收敛效果皆可达到三阶.算例实验结果验证了该迭代方法的有效性.他丰富了非线性方程求根的方法,在理论上和应用上都有一定的价值.【期刊名称】《哈尔滨理工大学学报》【年(卷),期】2013(018)006【总页数】4页(P117-120)【关键词】非线性方程;牛顿法;重根;迭代法;三阶收敛【作者】李福祥;田金燕;费兆福;巩英海;曹作宝【作者单位】哈尔滨理工大学应用科学学院,黑龙江哈尔滨 150080;哈尔滨理工大学应用科学学院,黑龙江哈尔滨 150080;哈尔滨理工大学应用科学学院,黑龙江哈尔滨 150080;哈尔滨理工大学应用科学学院,黑龙江哈尔滨 150080;哈尔滨理工大学应用科学学院,黑龙江哈尔滨 150080【正文语种】中文【中图分类】O24求解非线性方程f(x)=0是数学界经久不衰的研究课题，究其原因就是其在科学研究以及生产生活中的广泛应用，而迭代法又是求解非线性方程最为常用的方法之一．本文着重研究求解非线性方程重根的情形．寻找非线性方程重根的迭代方法通常以重数已知为前提，最为经典的当属二阶收敛的Newton迭代法，为提高其收敛速度一系列高阶迭代方法得到人们的广泛研究，这些方法大多是三阶收敛的，大致可分为两类，一类叫做单点法每步迭代需要计算三个函数值分别是 f，f'，和f″，比如欧拉－切比雪夫方法［1－2］哈雷方法［3］，Chun and Neta 方法［4］，Biazar and Ghanbari法［5］，和 Osada 法［6］等都属于此类，此类方法相比于经典的Newton法收敛效率大幅提高，但是每部迭代需要计算二阶导数值，这无疑增加了迭代过程的复杂度;另一类叫做多点法(本文的方法属此类)又可以被分成两子类，一个子类需要计算两个函数值和一个一阶导数值，比如文［7］，文［9］，文［10］等人给出的方法，另一子类需要计算两个一阶导数值和一个函数值，比如文［11－14］等人给出的方法，此类方法不仅提高了收敛速率，计算量也得到了很好的控制．再次就是四阶收敛的迭代方法，例如文［15－18］等人提出的方法，增加一个函数计算(f或f')将收敛速率提高到了四阶．由于受到上述研究工作的启发，为提高求解非线性方程的收敛速度和计算效率，本文以牛顿法为基础提出一种求解非线性方程重根的迭代方法，迭代格式根据重数为奇数和偶数两种情形分别给出，两种迭代格式每步迭代都只需计算三个函数值(包含一阶导数值)且完全摆脱了二阶导数值的计算，其收敛效果皆可达到三阶．正如引言中所提到的，本文的迭代方法同样以重数m已知为前提，当m为奇数时迭代格式如下所示:从迭代格式可以发现，不管重数是奇数还是偶数，每步迭代都仅需计算三个函数值，接下来我们将给出其收敛性证明．定理设x*∈D是充分光滑的实值函数f:D⊆R→R在开区间D上的m重根，当x0∈D充分靠近x*时，由式(1)、(2)决定的迭代方法至少是三阶收敛的．注意到，无论重数m是奇数还是偶数，由式(1)、(2)决定的三阶迭代方法每步迭代都只需计算三个函数值．其效率指数为，这里p指代收敛阶数，c指代所需计算函数个数．在这里将本文给出的方法应用到如下数值算例中，为展示本文迭代方法的属性及可行性，我们将从引言中提到的两类三阶迭代法中分别挑选出四种方法与本文迭代法(用M代表)做对比，SM(属单点法，需计算 f，f'，和f″)代表文［14］提出的迭代法，HMM(需计算 f，f，f')出自于文［10］，LM － 1(同HMM)和 LM －2(需计算 f，f'，f')都出自文献［12］．所有的数学计算都将用数学软件Mathematica完成，选择|x－x*|≤10－100作为终止条件．数值计算结果将呈现在表1中，其中en保留五位有效小数，n表示迭代次数．2)f2=ex－2+1 －x，f2(x)=0 有 2 重根 x*=2，选择x0=2.4为初始值;3)f3(x)=sin［(x－3)5］，f3(x)=0有 5重根x*=3，选择x0=2.5为初始值．4)f4(x)=(x－1)(ex－1－1)，f4(x)=0 有 2 重根x*=1，选择x0=1.5为初值．从表1中可以看出，本文构造的迭代方法M与同收敛阶的其他方法SM，HMM，LM－1，LM－2均能以较快的速度收敛．由算例可以明显发现本文提出的迭代方法是三阶收敛的．田金燕(1988—)，女，硕士研究生;费兆福(1989—)，男，硕士研究生．【相关文献】［1］TRAUB J F．Iterative Methods for the Solution of Equations［M］．NJ，Prentice-Hall:Englewood Cliffs，1964:10 －85．［2］NETA B．New Third Order Nonlinear Solvers for Multiple Roots，Appl ［J］．Math．Comput．，2008，202:162 －170．［3］HALLEY E．A New Exact and Easy Method of Finding the Roots of Equations Generally and without any Previous Reduction［J］．Phil．Trans．Roy．Soc．Lori．，1694，18:136 －148．［4］CHUN C，Neta B．A Third Order Modification of Newton’s Method for Multiple Roots［J］．Appl．Math．Comput．，2009，211:474－479．［5］BIAZAR J，GHANBARI B．A New third-order Family of Nonlinear Solvers for Multiple Roots［J］．Comput．Math．Appl．，2010，59:3315－3319．［6］OSADA N．An Optimal Multiple Root-finding Method of Order Three ［J］．Comput．Appl．Math．，1994，51:131 －133．［7］DONG C．A Basic Theorem of Constructing an Iiterative Formula of the Higher Order for Computing Multiple Roots of an Equation［J］．Math．Numer．Sinica，1982，11:445 －450．［8］NETA B．New Third Order Nonlinear Solvers for Multiple Roots ［J］．Appl．Math．Comput．，2008，202:162 － 170．［9］CHUN C，Bae H，Neta B．New Families of Nonlinear Third-order Solvers for Finding Multiple Roots［J］．Comput．Math．Appl．，2009，57:1574－1582．［10］HOMEIER H H H．On Newton-type Methods for Multiple Roots with Cubic Convergence ［J］．Comput．Appl．Math．，2009，231:249－254．［11］DONG C．A Family of Multipoint Iterative Functions for Finding Multiple Roots of Equations ［J］．Int．J．Comput．Math．，1987，21:363－367．［12］LI S，LI H，CHENG L．Some Second-derative-free Variants of Halley’s Method for Multiple Roots［J］．Appl．Math．Comput．，2009，215:2192 －2198．［13］SHARMA J R，SHARMA R．New Third and Fourth Order Nonlinear Solvers for Computing Multiple Roots［J］．Appl．Math．Comput，2011，217:9756 －9764．［14］SHARMA J R，SHARMA R．Modified Chebyshev-Hally Type Method and Its Variants for Computing Mmultiple Roots［J］．Numer Algor，2012，61:567 －578．［15］LI S，CHENG L，NETA B．Some Fourth-order Nonlinear Solvers with Closed Formulae for Multiple Roots ［J］．Comput．Math．Appl．，2010，59:126 －135．［16］NETA B．Extension of Murakami’s high-order Nonlinear Solver to Multiple Roots ［J］．Int．J．Comput．Math，2010，87:1023 －1031．［17］NETA B，JOHNSON A N．High Order Nonlinear Solver for Multiple Roots ［J］．Comput．Math．Appl，2008，55:2012 －2017．［18］SHARMA J R，SHARMA R．New Third and Rourth Order Nonlinear Solvers for Computingmultiple Roots［J］．Appl．Math．Comput，2011，217:9756 －9764．。

Conditional Random Fields:Probabilistic Modelsfor Segmenting and Labeling Sequence DataJohn Lafferty LAFFERTY@ Andrew McCallum MCCALLUM@ Fernando Pereira FPEREIRA@ WhizBang!Labs–Research,4616Henry Street,Pittsburgh,PA15213USASchool of Computer Science,Carnegie Mellon University,Pittsburgh,PA15213USADepartment of Computer and Information Science,University of Pennsylvania,Philadelphia,PA19104USAAbstractWe present,a frame-work for building probabilistic models to seg-ment and label sequence data.Conditional ran-domfields offer several advantages over hid-den Markov models and stochastic grammarsfor such tasks,including the ability to relaxstrong independence assumptions made in thosemodels.Conditional randomfields also avoida fundamental limitation of maximum entropyMarkov models(MEMMs)and other discrimi-native Markov models based on directed graph-ical models,which can be biased towards stateswith few successor states.We present iterativeparameter estimation algorithms for conditionalrandomfields and compare the performance ofthe resulting models to HMMs and MEMMs onsynthetic and natural-language data.1.IntroductionThe need to segment and label sequences arises in many different problems in several scientificfields.Hidden Markov models(HMMs)and stochastic grammars are well understood and widely used probabilistic models for such problems.In computational biology,HMMs and stochas-tic grammars have been successfully used to align bio-logical sequences,find sequences homologous to a known evolutionary family,and analyze RNA secondary structure (Durbin et al.,1998).In computational linguistics and computer science,HMMs and stochastic grammars have been applied to a wide variety of problems in text and speech processing,including topic segmentation,part-of-speech(POS)tagging,information extraction,and syntac-tic disambiguation(Manning&Sch¨u tze,1999).HMMs and stochastic grammars are generative models,as-signing a joint probability to paired observation and label sequences;the parameters are typically trained to maxi-mize the joint likelihood of training examples.To define a joint probability over observation and label sequences, a generative model needs to enumerate all possible ob-servation sequences,typically requiring a representation in which observations are task-appropriate atomic entities, such as words or nucleotides.In particular,it is not practi-cal to represent multiple interacting features or long-range dependencies of the observations,since the inference prob-lem for such models is intractable.This difficulty is one of the main motivations for looking at conditional models as an alternative.A conditional model specifies the probabilities of possible label sequences given an observation sequence.Therefore,it does not expend modeling effort on the observations,which at test time arefixed anyway.Furthermore,the conditional probabil-ity of the label sequence can depend on arbitrary,non-independent features of the observation sequence without forcing the model to account for the distribution of those dependencies.The chosen features may represent attributes at different levels of granularity of the same observations (for example,words and characters in English text),or aggregate properties of the observation sequence(for in-stance,text layout).The probability of a transition between labels may depend not only on the current observation, but also on past and future observations,if available.In contrast,generative models must make very strict indepen-dence assumptions on the observations,for instance condi-tional independence given the labels,to achieve tractability. Maximum entropy Markov models(MEMMs)are condi-tional probabilistic sequence models that attain all of the above advantages(McCallum et al.,2000).In MEMMs, each source state1has a exponential model that takes the observation features as input,and outputs a distribution over possible next states.These exponential models are trained by an appropriate iterative scaling method in the 1Output labels are associated with states;it is possible for sev-eral states to have the same label,but for simplicity in the rest of this paper we assume a one-to-one correspondence.maximum entropy framework.Previously published exper-imental results show MEMMs increasing recall and dou-bling precision relative to HMMs in a FAQ segmentation task.MEMMs and other non-generativefinite-state models based on next-state classifiers,such as discriminative Markov models(Bottou,1991),share a weakness we callhere the:the transitions leaving a given state compete only against each other,rather than againstall other transitions in the model.In probabilistic terms, transition scores are the conditional probabilities of pos-sible next states given the current state and the observa-tion sequence.This per-state normalization of transition scores implies a“conservation of score mass”(Bottou, 1991)whereby all the mass that arrives at a state must be distributed among the possible successor states.An obser-vation can affect which destination states get the mass,but not how much total mass to pass on.This causes a bias to-ward states with fewer outgoing transitions.In the extreme case,a state with a single outgoing transition effectively ignores the observation.In those cases,unlike in HMMs, Viterbi decoding cannot downgrade a branch based on ob-servations after the branch point,and models with state-transition structures that have sparsely connected chains of states are not properly handled.The Markovian assump-tions in MEMMs and similar state-conditional models in-sulate decisions at one state from future decisions in a way that does not match the actual dependencies between con-secutive states.This paper introduces(CRFs),a sequence modeling framework that has all the advantages of MEMMs but also solves the label bias problem in a principled way.The critical difference between CRFs and MEMMs is that a MEMM uses per-state exponential mod-els for the conditional probabilities of next states given the current state,while a CRF has a single exponential model for the joint probability of the entire sequence of labels given the observation sequence.Therefore,the weights of different features at different states can be traded off against each other.We can also think of a CRF as afinite state model with un-normalized transition probabilities.However,unlike some other weightedfinite-state approaches(LeCun et al.,1998), CRFs assign a well-defined probability distribution over possible labelings,trained by maximum likelihood or MAP estimation.Furthermore,the loss function is convex,2guar-anteeing convergence to the global optimum.CRFs also generalize easily to analogues of stochastic context-free grammars that would be useful in such problems as RNA secondary structure prediction and natural language pro-cessing.2In the case of fully observable states,as we are discussing here;if several states have the same label,the usual local maxima of Baum-Welch arise.bel bias example,after(Bottou,1991).For concise-ness,we place observation-label pairs on transitions rather than states;the symbol‘’represents the null output label.We present the model,describe two training procedures and sketch a proof of convergence.We also give experimental results on synthetic data showing that CRFs solve the clas-sical version of the label bias problem,and,more signifi-cantly,that CRFs perform better than HMMs and MEMMs when the true data distribution has higher-order dependen-cies than the model,as is often the case in practice.Finally, we confirm these results as well as the claimed advantages of conditional models by evaluating HMMs,MEMMs and CRFs with identical state structure on a part-of-speech tag-ging task.2.The Label Bias ProblemClassical probabilistic automata(Paz,1971),discrimina-tive Markov models(Bottou,1991),maximum entropy taggers(Ratnaparkhi,1996),and MEMMs,as well as non-probabilistic sequence tagging and segmentation mod-els with independently trained next-state classifiers(Pun-yakanok&Roth,2001)are all potential victims of the label bias problem.For example,Figure1represents a simplefinite-state model designed to distinguish between the two words and.Suppose that the observation sequence is. In thefirst time step,matches both transitions from the start state,so the probability mass gets distributed roughly equally among those two transitions.Next we observe. Both states1and4have only one outgoing transition.State 1has seen this observation often in training,state4has al-most never seen this observation;but like state1,state4 has no choice but to pass all its mass to its single outgoing transition,since it is not generating the observation,only conditioning on it.Thus,states with a single outgoing tran-sition effectively ignore their observations.More generally, states with low-entropy next state distributions will take lit-tle notice of observations.Returning to the example,the top path and the bottom path will be about equally likely, independently of the observation sequence.If one of the two words is slightly more common in the training set,the transitions out of the start state will slightly prefer its cor-responding transition,and that word’s state sequence will always win.This behavior is demonstrated experimentally in Section5.L´e on Bottou(1991)discussed two solutions for the label bias problem.One is to change the state-transition struc-ture of the model.In the above example we could collapse states1and4,and delay the branching until we get a dis-criminating observation.This operation is a special case of determinization(Mohri,1997),but determinization of weightedfinite-state machines is not always possible,and even when possible,it may lead to combinatorial explo-sion.The other solution mentioned is to start with a fully-connected model and let the training procedurefigure out a good structure.But that would preclude the use of prior structural knowledge that has proven so valuable in infor-mation extraction tasks(Freitag&McCallum,2000). Proper solutions require models that account for whole state sequences at once by letting some transitions“vote”more strongly than others depending on the corresponding observations.This implies that score mass will not be con-served,but instead individual transitions can“amplify”or “dampen”the mass they receive.In the above example,the transitions from the start state would have a very weak ef-fect on path score,while the transitions from states1and4 would have much stronger effects,amplifying or damping depending on the actual observation,and a proportionally higher contribution to the selection of the Viterbi path.3In the related work section we discuss other heuristic model classes that account for state sequences globally rather than locally.To the best of our knowledge,CRFs are the only model class that does this in a purely probabilistic setting, with guaranteed global maximum likelihood convergence.3.Conditional Random FieldsIn what follows,is a random variable over data se-quences to be labeled,and is a random variable over corresponding label sequences.All components of are assumed to range over afinite label alphabet.For ex-ample,might range over natural language sentences and range over part-of-speech taggings of those sentences, with the set of possible part-of-speech tags.The ran-dom variables and are jointly distributed,but in a dis-criminative framework we construct a conditional model from paired observation and label sequences,and do not explicitly model the marginal..Thus,a CRF is a randomfield globally conditioned on the observation.Throughout the paper we tacitly assume that the graph isfixed.In the simplest and most impor-3Weighted determinization and minimization techniques shift transition weights while preserving overall path weight(Mohri, 2000);their connection to this discussion deserves further study.tant example for modeling sequences,is a simple chain or line:.may also have a natural graph structure;yet in gen-eral it is not necessary to assume that and have the same graphical structure,or even that has any graph-ical structure at all.However,in this paper we will be most concerned with sequencesand.If the graph of is a tree(of which a chain is the simplest example),its cliques are the edges and ver-tices.Therefore,by the fundamental theorem of random fields(Hammersley&Clifford,1971),the joint distribu-tion over the label sequence given has the form(1),where is a data sequence,a label sequence,and is the set of components of associated with the vertices in subgraph.We assume that the and are given andfixed. For example,a Boolean vertex feature might be true if the word is upper case and the tag is“proper noun.”The parameter estimation problem is to determine the pa-rameters from training datawith empirical distribution. In Section4we describe an iterative scaling algorithm that maximizes the log-likelihood objective function:.As a particular case,we can construct an HMM-like CRF by defining one feature for each state pair,and one feature for each state-observation pair:. The corresponding parameters and play a simi-lar role to the(logarithms of the)usual HMM parameters and.Boltzmann chain models(Saul&Jor-dan,1996;MacKay,1996)have a similar form but use a single normalization constant to yield a joint distribution, whereas CRFs use the observation-dependent normaliza-tion for conditional distributions.Although it encompasses HMM-like models,the class of conditional randomfields is much more expressive,be-cause it allows arbitrary dependencies on the observationFigure2.Graphical structures of simple HMMs(left),MEMMs(center),and the chain-structured case of CRFs(right)for sequences. An open circle indicates that the variable is not generated by the model.sequence.In addition,the features do not need to specify completely a state or observation,so one might expect that the model can be estimated from less training data.Another attractive property is the convexity of the loss function;in-deed,CRFs share all of the convexity properties of general maximum entropy models.For the remainder of the paper we assume that the depen-dencies of,conditioned on,form a chain.To sim-plify some expressions,we add special start and stop states and.Thus,we will be using the graphical structure shown in Figure2.For a chain struc-ture,the conditional probability of a label sequence can be expressed concisely in matrix form,which will be useful in describing the parameter estimation and inference al-gorithms in Section4.Suppose that is a CRF given by(1).For each position in the observation se-quence,we define the matrix random variableby,where is the edge with labels and is the vertex with label.In contrast to generative models,con-ditional models like CRFs do not need to enumerate over all possible observation sequences,and therefore these matrices can be computed directly as needed from a given training or test observation sequence and the parameter vector.Then the normalization(partition function)is the entry of the product of these matrices:. Using this notation,the conditional probability of a label sequence is written as, where and.4.Parameter Estimation for CRFsWe now describe two iterative scaling algorithms tofind the parameter vector that maximizes the log-likelihood of the training data.Both algorithms are based on the im-proved iterative scaling(IIS)algorithm of Della Pietra et al. (1997);the proof technique based on auxiliary functions can be extended to show convergence of the algorithms for CRFs.Iterative scaling algorithms update the weights asand for appropriately chosen and.In particular,the IIS update for an edge feature is the solution ofdef.where is thedef. The equations for vertex feature updates have similar form.However,efficiently computing the exponential sums on the right-hand sides of these equations is problematic,be-cause is a global property of,and dynamic programming will sum over sequences with potentially varying.To deal with this,thefirst algorithm,Algorithm S,uses a“slack feature.”The second,Algorithm T,keepstrack of partial totals.For Algorithm S,we define the bydef,where is a constant chosen so that for all and all observation vectors in the training set,thus making.Feature is“global,”that is,it does not correspond to any particular edge or vertex.For each index we now define thewith base caseifotherwiseand recurrence.Similarly,the are defined byifotherwiseand.With these definitions,the update equations are,where.The factors involving the forward and backward vectors in the above equations have the same meaning as for standard hidden Markov models.For example,is the marginal probability of label given that the observation sequence is.This algorithm is closely related to the algorithm of Darroch and Ratcliff(1972),and MART algorithms used in image reconstruction.The constant in Algorithm S can be quite large,since in practice it is proportional to the length of the longest train-ing observation sequence.As a result,the algorithm may converge slowly,taking very small steps toward the maxi-mum in each iteration.If the length of the observations and the number of active features varies greatly,a faster-converging algorithm can be obtained by keeping track of feature totals for each observation sequence separately. Let def.Algorithm T accumulates feature expectations into counters indexed by.More specifically,we use the forward-backward recurrences just introduced to compute the expectations of feature and of feature given that.Then our param-eter updates are and,whereand are the unique positive roots to the following polynomial equationsmax max,(2)which can be easily computed by Newton’s method.A single iteration of Algorithm S and Algorithm T has roughly the same time and space complexity as the well known Baum-Welch algorithm for HMMs.To prove con-vergence of our algorithms,we can derive an auxiliary function to bound the change in likelihood from below;this method is developed in detail by Della Pietra et al.(1997). The full proof is somewhat detailed;however,here we give an idea of how to derive the auxiliary function.To simplify notation,we assume only edge features with parameters .Given two parameter settings and,we bound from below the change in the objective function with anas followsdefwhere the inequalities follow from the convexity of and.Differentiating with respect to and setting the result to zero yields equation(2).5.ExperimentsWefirst discuss two sets of experiments with synthetic data that highlight the differences between CRFs and MEMMs. Thefirst experiments are a direct verification of the label bias problem discussed in Section2.In the second set of experiments,we generate synthetic data using randomly chosen hidden Markov models,each of which is a mix-ture of afirst-order and second-order peting models are then trained and compared on test data.As the data becomes more second-order,the test er-ror rates of the trained models increase.This experiment corresponds to the common modeling practice of approxi-mating complex local and long-range dependencies,as oc-cur in natural data,by small-order Markov models.OurFigure3.Plots of error rates for HMMs,CRFs,and MEMMs on randomly generated synthetic data sets,as described in Section5.2. As the data becomes“more second order,”the error rates of the test models increase.As shown in the left plot,the CRF typically significantly outperforms the MEMM.The center plot shows that the HMM outperforms the MEMM.In the right plot,each open square represents a data set with,and a solid circle indicates a data set with.The plot shows that when the data is mostly second order(),the discriminatively trained CRF typically outperforms the HMM.These experiments are not designed to demonstrate the advantages of the additional representational power of CRFs and MEMMs relative to HMMs.results clearly indicate that even when the models are pa-rameterized in exactly the same way,CRFs are more ro-bust to inaccurate modeling assumptions than MEMMs or HMMs,and resolve the label bias problem,which affects the performance of MEMMs.To avoid confusion of dif-ferent effects,the MEMMs and CRFs in these experiments use overlapping features of the observations.Fi-nally,in a set of POS tagging experiments,we confirm the advantage of CRFs over MEMMs.We also show that the addition of overlapping features to CRFs and MEMMs al-lows them to perform much better than HMMs,as already shown for MEMMs by McCallum et al.(2000).5.1Modeling label biasWe generate data from a simple HMM which encodes a noisy version of thefinite-state network in Figure1.Each state emits its designated symbol with probabilityand any of the other symbols with probability.We train both an MEMM and a CRF with the same topologies on the data generated by the HMM.The observation fea-tures are simply the identity of the observation symbols. In a typical run using training and test samples, trained to convergence of the iterative scaling algorithm, the CRF error is while the MEMM error is, showing that the MEMM fails to discriminate between the two branches.5.2Modeling mixed-order sourcesFor these results,we usefive labels,(),and26 observation values,();however,the results were qualitatively the same over a range of sizes for and .We generate data from a mixed-order HMM with state transition probabilities given byand,simi-larly,emission probabilities given by.Thus,for we have a standardfirst-order HMM.In order to limit the size of the Bayes error rate for the resulting models,the con-ditional probability tables are constrained to be sparse. In particular,can have at most two nonzero en-tries,for each,and can have at most three nonzero entries for each.For each randomly gener-ated model,a sample of1,000sequences of length25is generated for training and testing.On each randomly generated training set,a CRF is trained using Algorithm S.(Note that since the length of the se-quences and number of active features is constant,Algo-rithms S and T are identical.)The algorithm is fairly slow to converge,typically taking approximately500iterations for the model to stabilize.On the500MHz Pentium PC used in our experiments,each iteration takes approximately 0.2seconds.On the same data an MEMM is trained using iterative scaling,which does not require forward-backward calculations,and is thus more efficient.The MEMM train-ing converges more quickly,stabilizing after approximately 100iterations.For each model,the Viterbi algorithm is used to label a test set;the experimental results do not sig-nificantly change when using forward-backward decoding to minimize the per-symbol error rate.The results of several runs are presented in Figure3.Each plot compares two classes of models,with each point indi-cating the error rate for a single test set.As increases,the error rates generally increase,as thefirst-order models fail tofit the second-order data.Thefigure compares models parameterized as,,and;results for models parameterized as,,and are qualitatively the same.As shown in thefirst graph,the CRF generally out-performs the MEMM,often by a wide margin of10%–20% relative error.(The points for very small error rate,with ,where the MEMM does better than the CRF, are suspected to be the result of an insufficient number of training iterations for the CRF.)HMM 5.69%45.99%MEMM 6.37%54.61%CRF 5.55%48.05%MEMM 4.81%26.99%CRF 4.27%23.76%Using spelling featuresFigure4.Per-word error rates for POS tagging on the Penn tree-bank,usingfirst-order models trained on50%of the1.1million word corpus.The oov rate is5.45%.5.3POS tagging experimentsTo confirm our synthetic data results,we also compared HMMs,MEMMs and CRFs on Penn treebank POS tag-ging,where each word in a given input sentence must be labeled with one of45syntactic tags.We carried out two sets of experiments with this natural language data.First,we trainedfirst-order HMM,MEMM, and CRF models as in the synthetic data experiments,in-troducing parameters for each tag-word pair andfor each tag-tag pair in the training set.The results are con-sistent with what is observed on synthetic data:the HMM outperforms the MEMM,as a consequence of the label bias problem,while the CRF outperforms the HMM.The er-ror rates for training runs using a50%-50%train-test split are shown in Figure5.3;the results are qualitatively sim-ilar for other splits of the data.The error rates on out-of-vocabulary(oov)words,which are not observed in the training set,are reported separately.In the second set of experiments,we take advantage of the power of conditional models by adding a small set of or-thographic features:whether a spelling begins with a num-ber or upper case letter,whether it contains a hyphen,and whether it ends in one of the following suffixes:.Here wefind,as expected,that both the MEMM and the CRF benefit signif-icantly from the use of these features,with the overall error rate reduced by around25%,and the out-of-vocabulary er-ror rate reduced by around50%.One usually starts training from the all zero parameter vec-tor,corresponding to the uniform distribution.However, for these datasets,CRF training with that initialization is much slower than MEMM training.Fortunately,we can use the optimal MEMM parameter vector as a starting point for training the corresponding CRF.In Figure5.3, MEMM was trained to convergence in around100iter-ations.Its parameters were then used to initialize the train-ing of CRF,which converged in1,000iterations.In con-trast,training of the same CRF from the uniform distribu-tion had not converged even after2,000iterations.6.Further Aspects of CRFsMany further aspects of CRFs are attractive for applica-tions and deserve further study.In this section we briefly mention just two.Conditional randomfields can be trained using the expo-nential loss objective function used by the AdaBoost algo-rithm(Freund&Schapire,1997).Typically,boosting is applied to classification problems with a small,fixed num-ber of classes;applications of boosting to sequence labeling have treated each label as a separate classification problem (Abney et al.,1999).However,it is possible to apply the parallel update algorithm of Collins et al.(2000)to op-timize the per-sequence exponential loss.This requires a forward-backward algorithm to compute efficiently certain feature expectations,along the lines of Algorithm T,ex-cept that each feature requires a separate set of forward and backward accumulators.Another attractive aspect of CRFs is that one can imple-ment efficient feature selection and feature induction al-gorithms for them.That is,rather than specifying in ad-vance which features of to use,we could start from feature-generating rules and evaluate the benefit of gener-ated features automatically on data.In particular,the fea-ture induction algorithms presented in Della Pietra et al. (1997)can be adapted tofit the dynamic programming techniques of conditional randomfields.7.Related Work and ConclusionsAs far as we know,the present work is thefirst to combine the benefits of conditional models with the global normal-ization of randomfield models.Other applications of expo-nential models in sequence modeling have either attempted to build generative models(Rosenfeld,1997),which in-volve a hard normalization problem,or adopted local con-ditional models(Berger et al.,1996;Ratnaparkhi,1996; McCallum et al.,2000)that may suffer from label bias. Non-probabilistic local decision models have also been widely used in segmentation and tagging(Brill,1995; Roth,1998;Abney et al.,1999).Because of the computa-tional complexity of global training,these models are only trained to minimize the error of individual label decisions assuming that neighboring labels are correctly -bel bias would be expected to be a problem here too.An alternative approach to discriminative modeling of se-quence labeling is to use a permissive generative model, which can only model local dependencies,to produce a list of candidates,and then use a more global discrimina-tive model to rerank those candidates.This approach is standard in large-vocabulary speech recognition(Schwartz &Austin,1993),and has also been proposed for parsing (Collins,2000).However,these methods fail when the cor-rect output is pruned away in thefirst pass.。

algorand原理Algorand是一种基于去中心化区块链技术的算法，其核心思想是使用密码学互操作来实现去中心化区块链的整个生态系统的完全一致性。

Algorand采用了一种被称为随机互动算法的机制，将所有的事务分为两个类别，一个是提议类别，另一个是投票类别。

这种算法将所有的事务按照顺序进行排列，在每一个周期中，随机选择一个人作为领导人，该领导人就要向大家提出一个提议。

这个提议包括两部分内容，一部分是某笔交易的内容，而另一部分则是一个随机的难题。

而其他参与者必须回答这个领导人提出的难题，其实质上就是进行了一个共识过程，所有人共同解决。

Algorand是一个基于概率的分布式共识协议，旨在解决区块链网络中的双花问题和分叉问题。

Algorand采用Pure Proof of Stake (PPoS) 模型，并采用一种称为分层随机选择（Hierarchical Byzantine Agreement）的算法来确保网络的高度安全性和快速的交易确认。

其核心原理可以分为以下4个关键点：1. 可验证的随机函数（VRF）：Algorand引入了可验证的随机函数，确保生成随机数的过程是公开的、可验证的，并且不利于操纵。

这种随机函数的使用使得区块提议者和投票者的选择过程变得无法预测，从而防止了潜在的攻击行为。

2. 随机权益证明（randPoS）：Algorand利用随机权益证明来选举权益者，确保网络中的权益者是由随机选择的，并且没有明显的操纵可能性。

这种证明机制与传统的PoS（Proof of Stake）类似，但在随机性和公平性上有所提升。

3. 分层随机选择（HBA）：Algorand使用了一种名为分层随机选择的算法来实现网络的共识过程。

这个算法确保了即使在网络出现分区或者节点故障的情况下，依然能够达成一致的共识，从而保障了网络的安全性和可用性。

4. 均衡共识：Algorand的共识算法旨在实现区块链网络的高吞吐量和低延迟。