華南理工大學《人工智能》復習資料匯總

華南理工大學《人工智能》復習資料匯總華南理工大學《人工智能》復習資料匯總17/17華南理工大學《人工智能》復習資料匯總華南理工大學《人工智能》復習資料Ch2.【狀態(tài)空間表示】S，F，GS：初始狀態(tài)的會集F：操作的會集G：目標狀態(tài)的會集比方：{Q5}{，a，b，c}{，Q0，Q7}【狀態(tài)空間圖】【狀態(tài)空間圖找尋使用的數據結構】OPEN表：已生成但沒觀察的節(jié)點(待觀察節(jié)點)CLOSED表：觀察過的節(jié)點及節(jié)點間關系(找尋樹)

【A*算法】f（x）＝g（x）＋h（x）g(x)為當前點的代價h(x)為距離目標的距離A*對A算法的改進：對h(x)作限制，使其總是小于實質最小距離（hx）h*（x），擁有齊全性【與或圖】Q與Q1，Q2與等價（即Q能夠分解為Q1+Q2）Q1與{Q1i},{Q1i}或’等價（即Q1能夠變換為{Q1i}或{Q1i}’）【與或圖中的看法】根源問題：直接可解的問題。停止節(jié)點：根源問題對應的節(jié)點端節(jié)點：無子節(jié)點的節(jié)點與節(jié)點：子節(jié)點為與關系或節(jié)點：子節(jié)點為或關系【廣度/深度優(yōu)先找尋特點】【與或圖的廣度/深度找尋】Step1:S0放入OPEN表廣度優(yōu)先：齊全的(必然能找到最優(yōu)解)，找尋效率低，OPENStep2:OPEN表第一個點（記為N）取出放入CLOSED表，表為隊列結構冠以編號n。深度優(yōu)先：不能夠保證找到最優(yōu)解，OPEN表為貨倉結構Step3:若n可擴展：有界深度優(yōu)先找尋：即使能求出解，也不用然是最優(yōu)(1)擴展N，其子節(jié)點放入OPEN表(深度:尾部，廣度:首部)可變界深度優(yōu)先找尋算法：深度可變，每次深度高出閾值(2)觀察這些節(jié)點可否停止節(jié)點。若是，放入CLOSED表，的點，都被看作待觀察點(在CLOSED表中)標為可解節(jié)點，并對長輩點標示。若S0被標可解，得解。(3)從OPEN表刪除擁有可解長輩的節(jié)點。轉Step2?！締⑹臼秸覍に惴ǚ诸悺縎tep4:若N不能擴展：(1)標示N為不能解。按選擇范圍分類：(2)標示長輩節(jié)。若S0被標不能解，失敗。全局擇優(yōu)找尋：考慮所有待觀察節(jié)點(3)從OPEN表刪除擁有不能解長輩的節(jié)點。轉Step2。局部擇優(yōu)找尋：只考慮當前節(jié)點的子節(jié)點【與或圖啟示式找尋】由下往上更新函數，函數=子點價+子點與父點距離。例子PP3Ch3.P117-120【博弈樹】與點：手(MIN)力干MAX的。因此站在我方MAX）的立，由MIN出棋的點擁有與點的性?；螯c：我方（MAX）力通往取。MAX出棋的點擁有或點的性?！睛良糁?β剪枝】α剪枝：MIN點,若其倒推上確界β不大于MIN的父點倒推下確界α,即α≥β,不用展MIN點其他子點β剪枝：MAX點,若其倒推下確界α不小于MAX的父點倒推上確界β,即α≥β,不用展MAX點其他子點

Ch3.【失散數學相關定義】命（proposition）：擁有真假意的句(predicate)：刻畫個體的性、狀或個體的關系，比方P(x,y):x是y的父個體域：個體元的化范。(如P(x,y)中，x,y是元)全個體域:包所有事物的會集函數：個體之的關系,比方father(x):x的父：個體常元和元都是。若t1，t2，,，tn是，f（t1，t2，,，tn）是原子公式：若t1，t2，,，tn，P（t1，t2，,，tn）稱原子公式，稱原子或原子公式公式：原子公式是公式。若A、B是公式，?A，A∪B等都是公式域：接于量此后被量作用的公式指量：量后的量束量：量域中，與量的指元相同的量自由量：除了束量之外的量一：個體元被量化的二：個體元、函數符號、符號被量化從公式獲取命：(1)把中的個體元代入個體常元(2)把中的個體元所有量化P(x)表示"x是素數",xP(x)，P(a)都是命合取范式：B1B2?Bn，如(P(x)Q(x))(Q(y)R(y))(P(z)S(z))8析取范式：B1B2?Bn，如(D(y)L(a，y))（P(x)C(z))(P(u))L(u，v))公式永真性：P個體域D所有建立，P在D上永真。P在全個體集建立，P永真公式可足性：P個體域D最少有一個個體建立，P在D上可足?！境Ｓ眠壿嫷葍r式】【子句集】文字：原子公式及其否定子句：任何文字的析取【子句集特點】沒有含、等“?”作用原子沒有量(、)合取范式元素之元不相同會集形式【由謂詞公式獲取子句集】(子句集特點的序號)依照含等價式消去含關系依照量律、雙重否定律、摩根定律3.存在量：受x束，定f(x)替y(Skolem函數)不受x束，常量代替y(Skolem常量)全稱量：直接消去4.依照分配率合取5.各個合取子句量更名6.把合取符號替逗號，成會集【常用推理定律】【Skolem標準型】消去存在量，把全稱量移到最左，右式合取，如x[P(x，f(x))?R(x,g(x))]Skolem準型與原公式一般其實不等價【命題邏輯中的概括原理定義】與前提：G是F1、F2、?、Fn的，當且當每個解I，若是F1、F2、?、Fn都真，G也真。F1、F2、?、FnG的前提。互文字：L與?L式：C1包含L1，C2包含L2，L1與L2互。把L1和L2除，并把節(jié)余部解析取，獲取C12本子句：上例中C1與C2消解基：上例中L1與L2比方：C12PSR【概括原理定理】1.公式A不能足當且當其子句集S不能足。G是公式F1、F2、?、Fn的，當且當F1F2?Fn=>GG是公式F1、F2、?、Fn的，當且當F1F2?Fn?G不能足式是其本子句的果子句集S的C1，C2替C12獲取S1，S1不足=>S不足子句集S增加C12獲取S2，S2不足=>S不足【概括反演法】否定目公式G，?G加入到F1F2?Fn中，獲取子句集S。S行，并把果并入S，直到獲取空子句，原得?！敬娑x】替：{t1/x1,t2/x2,?,tn/xn}替的分子：t1,t2,?,tn是替的分母：x1,x2,?,xn是互不相同的個體元(ti,,xi不相同,xi不循出在tj中,如{f(x)/y,g(y)/x}不是替)基替：t1,t2,?,tn是不含元的（稱基）空替：沒有元素的替，作ε表達式：、原子公式、文字、子句的稱基表達式：沒有元的表達式/特例：公式E施替θ，Eθ，所得果稱E在θ下的例復合/乘：θ＝{t1/x1,t2/x2,?,tm/xm}，λ＝{u1/y1,u2/y2,?,un/yn}，除{t1λ/x1,t2λ/x2,?,tmλ/xm,u1/y1,u2/y2,?,un/yn}中：(1)tiλ/xi當tiλ＝xi(2)ui/yi當yi∈{x1,?,xn}獲取θ與λ的復合或乘，θ?λ比方：θ={a/x,f(u)/y,y/z},λ={b/u,z/y,g(x)/z}{a/x，f(b)/y，z/z，b/u，z/y，g(x)/z},去：z/z，z/y，g(x)/z獲取：θ·λ={a/x，f(b)/y，b/u}

合一：F1λ=F2λ=?=FnλλF的合一，F可合一的（一個公式的合一一般不唯一）最一般合一：σF的一個合一，若是F任何合一θ都存在λ使得θ＝σ?λ，σF的最一般合一，極MGU（一個公式集的MGU不唯一）差異集：S是擁有相同名的原子公式集，從各公式左開始，同向右比，直到第一個不都相同的止，用些的差異部分紅的會集【合一算法】Step1：置k＝0，Fk＝F，σk＝ε；Step2：若Fk只含有一個公式，算法停止，σk就是最一般合一；Step3：求Fk的差異集Dk；Step4：若Dk中存在元素xk和tk，其中xk是元，tk是且xk不在tk中出，置Sk＋1＝Fk{tk/xk},σk+1=k?{tk/xk}，k＝k+1爾后Step2；Step5：算法停止，F的最一般合一不存在。任一非空有限可合一的公式集，必然存在最一般合一，而且用合一算法必然能找到最一般合一【合一算法例子】求公式集F＝{Q(a,x,f(g(y))),Q(z,h(z,u),f(u))}的最一般合一解：解k＝0；F0＝F，σ0＝ε，D0＝{a,z}1＝σ0·{a/z}={a/z}F1=F0{a/z}={Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}k＝1；D1={x,h(a,u)}2=σ1·{h(a,u)/x}＝{a/z,h(a,u)/x}F2=F1{a/z,h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k＝2；D2＝{g(y),u}3＝{a/z,h(a,g(y))/x,g(y)/u}F3=F2{g(y)/u}={P(a,h(a,g(y)),f(g(y)))}S3元素集，σ3MGU。【謂詞邏輯中的概括原理定義】二元式（二元消解式）:（C1σ－{L1σ}）∪（C2σ－{L2σ}）,其中：本子句：C1，C2無相同元的子句消解文字：L1，L2σL1和?L2的最一般合一因子：Cσ。其中σC的子句文字的最一般合一因子：Cσ元句子【合必然義】【概括式】子句的C1，C2式，是以下二元式之一:1）C1和C2的二元式；2）C1和C2的因子的二元式；3）C1因子和C2的二元式；4）C1的因子和C2的因子的二元式。注意事：兩個子句不能夠含有相同的元的子句內部含有可合一的文字，需行化【謂詞邏輯的消解原理/概括原理】中的消解（）式是它的本子句的果：C1C2＝>（C1σ－{L1σ}）∪（C2σ－{L2σ}）【謂詞邏輯的定理】若是子句集S是不能足的，那么必存在一個由S推出空子句的消解序列?！緫酶爬ㄔ砬笕栴}答案】Step1：前提化子句集SStep2：確定目，化子句，并析取助新子句，并入到S形成S’。Step3：S’用原理。Step4：當只剩助，束。(例子CH3P105)【概括策略】Step1：子句集S置入CLAUSES表Step2：若Nil在CLAUSES，成功Step3：若CLAUSES存在可子句，，并將式并入CLAUSES表，step2Step4：失【廣度優(yōu)先找尋概括策略】用于確定策略step3的找尋次序第一：0（原子句集S）兩兩行，生1下一：1與0、1兩兩行，獲取2再一：2與0、1、2兩兩行，獲取3這樣推，直至出Nil【概括策略齊全性】一個策略是完的，若是于不能足的子句集，使用策略行，最必出空子句Nil。（廣度先是完的，亦稱水平浸透法）【概括策略出發(fā)點】1）化性策略。2）限制性策略。

（3）有序性策略（包含排序策略）【概括策略種類】除策略支持集策略性策略元策略策略祖先型策略【正向演繹推理--初始事F0】任意公式前束范式表示；消去量，更名與或表示：析取部分用與點表示合取部分用或點表示【正向演繹推理--F－】形如L=>W，L一文字W任意與或型公式；(消去量，更名)【正向演繹推理—目標謂詞】文字的析取式(消去量，更名)【正向演繹推理圖解】F0':P(x)(Q(x)R(x))F1':P(y)S(y)F2':Q(z)N(z)G':S(a)N(a)N(a){a/x}?S(a)N(x){a/x}?S(x)Q(z)F1{x/z}?P(y)Q(x)R(x)F2{x/y}?P(x)Q(x)∧R(x)F0?P(x)∨(Q(x)∧R(x))【代換集一致性】有代集{u1,u2,?，un}，其中每個ui都是代{ti1/vi1,ti2/vi2,?，tim(i)/vim(i)}U1＝{v11,?,im(1)v,?，vn1,?,nm(n)v}（所有下的量）U2＝{t11,?im(1),t,?，tn1,?nm(n),t}（所有上的）{u1,u2,?，un}是一致的，當且當U1和U2是可合一合一復合：U1和U2的最一般合一解上所有代是一致的，有解，最后的代是合一復合U【反向演繹推理--目標公式】任意公式(消去量，更名)與或表示：與點合取；或點析取【反向演繹推理--B－】W=>L；一文字；W任意與或型公式(消去量，更名)【反向演繹推理—解】CAT(x)DOG(y)AFRAID(x,y)CAT(x)DOG(y)AFRAID(x,y){x/x5}{FIDO/y}{x/y2,y/x2}CAT(x5)DOG(FIDO)AFRAID(y2,x2)R5R2MEOWS(x)BARKS(y)FRIENDLY(y){MYRTLE/x}{FIDO/y}{y/x1}MEOWS(MYERTLE)BARKS(FIDO)FRIENDLY(x1)R1WAGSTAIL(y)DOG(y){FIDO/y}{FIDO/y}WAGSTAIL(FEDO)DOG(FIDO)

【雙向演繹推理】分從基于事的F-正向推理出，也從基于目的B-逆向推理出，同行雙向演推理。止的條件：正向推理和逆向推理互相完好般配。即所有獲取的正向推理與或的葉點，正好與逆向推理獲取的與或的葉點一一般配【不確定性知識分類】隨機不確定性(概率)模糊不確定性(看法)不完好性(事物認識不充分)不一致性(推移)【逆概率方法公式】P(Hi|E)P(E|Hi)P(Hi)nP(E|Hj)P(Hj)j1【正向/反向演繹比較】【逆概率—多個憑據】Em)P(E1/Hi)P(E2/Hi)P(Em/Hi)P(Hi)P(Hi/E1E2nP(E1/Hj)P(E2/Hj)P(Em/Hj)P(Hj)j1其就是bayes公式。格要求各據獨立?！拘拚蜃印縋(H|E)[P(E|H)]P(H)方括號內修正因子：P(E)【可信度法—不確定性胸襟】IfEthenH(CF(H,E))其中CF(H,E)可信度因子/度CF(H,E)=MB(H,E)-MD(H,E)【MB和MD】MB（MeasureBelief）：相信增加度，因憑據E的出現使結論H為真的相信增加度：MB(H,E)max{P(H|1當P(H)＝1E),P(H)}P(H)否則1()PHMD（MeasureDisbelief）：不相信增加度，因E的出現使H為真的不相信增加度：1當()＝0PH(,E)min{P(H|E),P(H)}P(H)(否則)PH因此，CF(H,E)為：P(H|E)P(H)當P(H|E)P(H)1()PHCF(H,E)0當P(H|E)＝P(H)P(H)P(H|E)當P(H|E)P(H)P(H)【可信度法--不確定性流傳】組合憑據：E=E1E2,En：CF(E)=min{CF(E1),CF(E2),,CF(En)}E=E1E2,En：CF(E)=max{CF(E1),CF(E2),,CF(En)}E=E1：CF(E)=-CF(E1)推理結論的CF值：CF(H)=CF(H,E)max{0,CF(E)}重復結論的CF值：【主觀貝葉斯法】表示形式：ifEthen(LS,LN)H(P(H))(LS,LN)EH(P(H))【LS和LN】LS：充分性量度，E對H支持程度，范圍為[0，∞）：LN：必要性量度，E對H支持程度，范圍為[0，∞）：LS、LN>0,不獨立，有以下拘束關系：LS>1時，LN<1；LS<1時，LN>1；LS=1時，LN=1；

經過LN,LS把先驗概率轉變成后驗概率：LS=O(H|E)/O(H)P(H|E)越大，O(H|E)越大，則LS越大，表示E對H為真的支持越強，當LS∞，P(H|E)1，E的存在對H為真是充分的LN=O(H|E)/O(H)P(H|E)越大，O(H|E)越大，則LN越大，表示E對H為真的支持越強。當LN=0，P(H|E)=0，E的不存在以致H為假，說明E對H是必要的【幾率函數】P(E|S)與P(H|S)】其中C(E|S)由題目給出，用于刻畫不確定性，值越大，證明在觀察S下，E存在的可能性越大。將兩式結合，和獲取CP公式：【貝葉斯網絡圖示】以隨機變量為節(jié)點，以條件概率為節(jié)點間關系強度的有向無環(huán)圖（DirectedAcyclicGraph，DAG）每個節(jié)點旁的條件概率表(簡稱CPT)中的值對應一個條件事件的概率【條件獨立關系】若是x滿足ai貝葉斯網絡中節(jié)點互相獨立：那么不做任何辦理(1)給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的否則(2)給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點將h中ai代替為x滿足的更一般的拘束(Markovblanket)，這個節(jié)點關于其他節(jié)點都是條件獨立的3.輸出假設h【條件獨立關系的判斷】d-分別（d-separation)：【候選除掉算法】給定y，x和z條件獨立：P(z|x,y)P(z|y)給定y，x和z條件獨立：P(z|x,y)P(z|y)給定y，x和z不條件獨立：P(x,z)P(x)P(z)【貝葉斯網絡推理】概率推理可分為：因果推理、診斷推理、辯解推理、混雜推理【因果推理】【BP算法誤差項】由原因到結果的推理，自上而下的推理，比方已知L建立時，求P(M|L)更新規(guī)則:P(M|L)P(M,B|L)P(M,B|L)【診斷推理】由結果到原因的推理,自下而上的推理。比方已知?M成立，求P(?L|?M)P(L|M)P(M|L)P(L)P(M)【辯解推理】不過給定?B，求P(?L)。這種情況下，能夠說?B講解?M，使?L不確定。P(L|B,P(M,B|L)P(L)M)M,B)P(Ch5.FIND-S算法】候選假設：<a1，a2，,，an>“?”：可接受任何值“”：不接受任何值算法流程：1.將h初始化為H中最特別假設2.對每個正例x（循環(huán)）對h的每個屬性拘束ai

【BP算法權值更新】Thelearningruleforthehidden-to-outputunits:Thelearningrulefortheinput-to-hiddenunits:Summary:Ch6.【算法的基本操作】復制從舊種群生命力的個體行復制。方法：依照個體適量/適量，每個個體分配概率范(0~1)，生隨機數，般配的個體：交織在般配池中任兩個染色體，隨機一點或多點交點地址；交雙染色體交點右的部分，即可獲取兩個新的染色體數字串異在染色體以二制的系中，它隨機地將染色體的某一個基出處10，或由01?！舅惴ǖ奶攸c】參數的行操作，而非參數自己(因此可模擬自然界化體系)同使用多個找尋點的找尋信息(找尋效率高、并行、不墜入局部最)直接以目函數作找尋信息(不需數和其他助信息)使用概率找尋技(復制交織異基于概率，有很好靈便性)在解空行高效啟式找尋(而非盲目找尋、完好隨機找尋)待的函數基本無量制(不要求、可微)擁有并行算的特點(適合大模復的化)【算法的構成要素】染色體方法使用固定度的二制符號來表示集體中的個體個體適量價目函數J到個體適量f之的算子①運算:使用比率算子；②交織運算:使用點交織算子；③異運算:使用基本位異算子或平均異算子基本算法的運行參數下述4個運行參數需要提前定：①M：集體大小，即集體中所含個體的數量，一般取20~100；G：算法的止化代數，一般取100~500；③Pc：交織概率，一般取0.4~0.99；④Pm：異概率，一般取0.0001~0.1。

十大算法【C4.5】【信息增益的計算】希望信息:本會集s含有si個Ci的元,i={1,?,m}，一個定的本分所需的希望信息是：:擁有{a1,a2,?,av}的屬性A的E(A)屬性A致的s的劃分的希望信息的加平均和：信息增益:例子:【信息增益比】C4.5算法】1.建根點2.若所有本x，x3.若Attribute空，最寬泛的4.信息增益比最大的屬性，每個可能建立子點，解決【k-means】【聚目】聚內部距離平方之和的最小化：k-means算法】定:k-means算法以k入參數，把n個象的會集分k個集，使得果簇內的相似度高，而簇的相似度低。簇的相似度是關于簇中象的均胸襟，能夠看做簇的心或重心。算法：把對象劃分紅k個非空子集；計算當前的每個聚類的質心作為每個聚類的種子點；把每一個對象分配到與它近來的種子點所在的聚類返回到第2步,當滿足某種停止條件時停止。停止條件:當分配不再發(fā)生變化時停止；當前后兩次迭代的目標函數值小于某一給定的閾值；當達到給定的迭代次數時。時間復雜性：計算復雜度為O(nkt)，其中n是對象的總數，k是簇的個數，t是迭代的次數【SVM】Margin】*Marginisdefinedasthewidththattheboundarycouldbeincreasedbybeforehittingadatapoint*Thelineardiscriminantfunction(classifier)withthemaximummarginisthebest.*Dataclosesttothehyperplanearesupportvectors.

DualProblemfor(aiisLagrangemultiplier):Solution(Eachnon-zeroaiindicatesthatcorrespondingxiisasupportvector.):Classifyingfunction(reliesonaninnerproductbetweenthetestpointxandthesupportvectorsxi.involvedcomputingtheinnerproductsxi‘*xjbetweenalltrainingpoints):【Slackvariables】Target：【MaximumMarginClassification】Maximizingthemarginisgoodaccordingtointuitionandtheory.Impliesthatonlysupportvectorsareimportant;othertrainingexamplesareignorable.【Kernels】*WemayuseKernelfunctionstoimplicitlymaptoanewfeaturespaceKernelmustbeequivalenttoaninnerproductinsomefeaturespaceSolvingofSVM】SolvingSVMisaquadraticprogrammingproblemTarget:maximummargin->==>SuchthatNonlinearSVM】Theoriginalfeaturespacecanalwaysbemappedtosomehigher-dimensionalfeaturespacewherethetrainingsetisseparable

DualProblemofthesoftmarginisthesameforhard.Solution:Classifyingfunctionofthesoftmarginisthesame.KernelTrick】Mapdatapointstohigherdimensionalspaceinordertomakethemlinearlyseparable.Sinceonlydotproductisused,wedonotneedtorepresentthemappingexplicitly.Discriminantfunction:(Noneedtoknowthismappingexplicitly,becauseweonlyusethedotproductoffeaturevectorsinboththetrainingandtest.)Kernelfunction:dotproductoftwofeaturevectorsinsomeexpandedfeaturespce:【OptimizationProblem】【NonlinearSVMoptimization】從繁集生關依照繁集I，生成所有非空子集。于每個子集m,若sup(m→(I-m))≥min_sup，出此其中sup(m→(I-m))==【Apriori】【支持度與置信度】A→C：【用Apriori算法挖掘強關系規(guī)則】接操作:{ABC?X}和{ABC?Y}可接，生成{ABC?}XY(個數相同，只有最后一個元素不相同)生成繁k-集Lk的算法：·依照k-1集Lk-1，接生成候集Ck·出Ck中支持度大于min_sup的元素，構成Lk例子：

【EM】在概率模型中找參數最大似然估也許最大后估的算法，其中概率模型依于無法的藏量。最大希望算法兩個步交替行算：第一步是算希望（E），利用藏量的有估，算其最大似然估；第二步是最大化（M），最大化在E步上求得的最大似然來算參數的。M步上找到的參數估被用于下一個E步算中，個程不斷交替行。體來，EM的算法流程以下：1.初始化分布參數2.重復直到收：步：估未知參數的希望，出當前的參數估。步：重新估分布參數，以使得數據的似然性最大，出未知量的希望估?！綪ageRank】【基本思想】*PageRank將網x指向網y的接xy的一張投票。但是PageRank不不過考慮網頁得票的絕對數量，它還解析投票者自己的聲威性.來自聲威網頁的投票能夠提升被投票網頁的聲威性【更具基本思想】*鏈接是源網頁對目標網頁聲威性的隱含表達.網頁i入邊（in-links）越多，表示i的聲威性值越高。指向網頁i的網頁自己也有自己的聲威性值關于網頁i的聲威性得分而言，一個擁有高分值的源網頁比一個低分值的源網頁更加重要。-換言之，若其他聲威性網頁指向網頁i，則i也可能是聲威性網頁。PageRank優(yōu)點與缺點】優(yōu)點：防欺騙網頁所有者難以設置其他重要網頁指向自己的網頁.(2)ageRank值獨立于盤問，是一種全局胸襟.PageRank值是經過所有網頁計算獲取并加以存儲，而不是提交盤問時才計算.缺點：不能夠劃分全局重要性網頁和盤問主題重要性網頁Web圖】Web視為有向圖G=(V,E)，V表示極點（網頁），一條邊(i,j)E當且僅當網頁i指向網頁j，n為總的網頁數。網頁P(i)定義為:Oj是網頁j的出邊數是Web圖的毗鄰矩陣表示：經過使用冪法能夠求解PATP，但是Web圖不符合求解條件。

Aij表示用戶在狀態(tài)i（網頁i）轉移到狀態(tài)j（網頁j）的概率。（公式和web圖一致）步轉移后的概率分布：【穩(wěn)態(tài)概率分布】關于任意初始概率向量P0,Pk將收斂于一個牢固的概率向量,即,可作為PageRank值向量，其合理性：-它反響了隨機沖浪的長遠概率.-一個網頁被接見的概率越高，其聲威性越高.【收斂性】一個有限馬爾可夫鏈收斂于一個唯一的穩(wěn)態(tài)概率分布：假如矩陣A是不能約（irreducible）和非周期的aperiodic）。條件1：隨機矩陣A不是一個隨機矩陣，因為很多網頁沒有出邊，以致A中某些行全為0.解決方案1：刪除沒有出邊的網頁.解決方案2：將沒有出邊的網頁指向網絡中所有其他網頁條件2：不能約不能約意味著強連通(所有點對都有雙向路徑)，A不吻合。條件3：非周期i到i的所有路徑都是K的倍數(k>1)，則成為周期的。一