下载文档原格式
机器学习题库一、 极大似然1、 ML estimation of exponential model (10)A Gaussian distribution is often used to model data on the real line, but is sometimesinappropriate when the data are often close to zero but constrained to be nonnegative. In such cases one can fit an exponential distribution, whose probability density function is given by()1xb p x e b-=Given N observations x i drawn from such a distribution:(a) Write down the likelihood as a function of the scale parameter b.(b) Write down the derivative of the log likelihood.(c) Give a simple expression for the ML estimate for b.2、换成Poisson 分布：()|,0,1,2,...!x e p x y x θθθ-==()()()()()1111log |log log !log log !N Ni i i i N N i i i i l p x x x x N x θθθθθθ======--⎡⎤=--⎢⎥⎣⎦∑∑∑∑3、二、 贝叶斯假设在考试的多项选择中，考生知道正确答案的概率为p ，猜测答案的概率为1-p ，并且假设考生知道正确答案答对题的概率为1，猜中正确答案的概率为1，其中m 为多选项的数目。
Viterbi算法第一篇：Viterbi算法隐马尔可夫模型中的Viterbi算法2008年1月24日这篇文章简单描述一下Viterbi算法——一年之前我听过它的名字，直到两周之前才花了一点时间研究了个皮毛，在这里做个简单检讨。
先用一句话来简单描述一下：给出一个观测序列o1,o2,o3 …，我们希望找到观测序列背后的隐藏状态序列s1, s2, s3, …；Viterbi以它的发明者名字命名，正是这样一种由动态规划的方法来寻找出现概率最大的隐藏状态序列（被称为Viterbi路径）的算法。
这里需要抄一点有关隐马可夫序列（HMM，Hidden Markov Model）的书页来解释一下观测序列和隐藏状态序列。
首先从最简单的离散Markov过程入手，我们知道，Markov随机过程具有如下的性质：在任意时刻，从当前状态转移到下一个状态的概率与当前状态之前的那些状态没有关系。
所以，我们可以用一个状态转移概率矩阵来描述它。
假设我们有n个离散状态S1, S2,…Sn，我们可以构造一个矩阵A，矩阵中的元素aij表示从当前状态Si下一时刻迁移到Sj状态的概率。
但是在很多情况下，Markov模型中的状态是我们观察不到的。
例如，容器与彩球的模型：有若干个容器，每个容器中按已知比例放入各色的彩球（这样，选择了容器后，我们可以用概率来预测取出各种彩球的可能性）；我们做这样的实验，实验者从容器中取彩球——先选择一个容器，再从中抓出某一个球，只给观察者看球的颜色；这样，每次取取出的球的颜色是可以观测到的，即o1, o2,…，但是每次选择哪个容器是不暴露给观察者的，容器的序列就组成了隐藏状态序列S1, S2,…Sn。
这是一个典型的可以用HMM描述的实验。
HMM有几个重要的任务，其中之一就是期望通过观察序列来猜测背后最有可能的隐藏序列。
在上面的例子中，就是找到我们在实验中最有可能选择到的容器序列。
Viterbi正是用来解决这个问题的算法。
奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。
1.A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。
其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。
算法以得到的次序访问这些节点。
因此，A*搜索算法是最佳优先搜索的范例。
2.集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。
使用启发式函数评估它检查的每个节点的能力。
不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。
3.二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。
4.分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。
5.Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。
6.数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。
7.Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。
该密钥以后可与一个对称密码一起，加密后续通讯。
8.Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。
9.离散微分算法（Discrete differentiation）10.动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法11.欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。
HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationFLUOXETINE HClC17H18F3NO•HClM.W. = 345.79CAS — 59333-67-4STABILITY INDICATINGA S S A Y V A L I D A T I O NMethod is suitable for:ýIn-process controlþProduct ReleaseþStability indicating analysis (Suitability - US/EU Product) CAUTIONFLUOXETINE HYDROCHLORIDE IS A HAZARDOUS CHEMICAL AND SHOULD BE HANDLED ONLY UNDER CONDITIONS SUITABLE FOR HAZARDOUS WORK.IT IS HIGHLY PRESSURE SENSITIVE AND ADEQUATE PRECAUTIONS SHOULD BE TAKEN TO AVOID ANY MECHANICAL FORCE (SUCH AS GRINDING, CRUSHING, ETC.) ON THE POWDER.ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationTABLE OF CONTENTS INTRODUCTION........................................................................................................................ PRECISION............................................................................................................................... System Repeatability ................................................................................................................ Method Repeatability................................................................................................................. Intermediate Precision .............................................................................................................. LINEARITY................................................................................................................................ RANGE...................................................................................................................................... ACCURACY............................................................................................................................... Accuracy of Standard Injections................................................................................................ Accuracy of the Drug Product.................................................................................................... VALIDATION OF FLUOXETINE HCl AT LOW CONCENTRATION........................................... Linearity at Low Concentrations................................................................................................. Accuracy of Fluoxetine HCl at Low Concentration..................................................................... System Repeatability................................................................................................................. Quantitation Limit....................................................................................................................... Detection Limit........................................................................................................................... VALIDATION FOR META-FLUOXETINE HCl (POSSIBLE IMPURITIES).................................. Meta-Fluoxetine HCl linearity at 0.05% - 1.0%........................................................................... Detection Limit for Fluoxetine HCl.............................................................................................. Quantitation Limit for Meta Fluoxetine HCl................................................................................ Accuracy for Meta-Fluoxetine HCl ............................................................................................ Method Repeatability for Meta-Fluoxetine HCl........................................................................... Intermediate Precision for Meta-Fluoxetine HCl......................................................................... SPECIFICITY - STABILITY INDICATING EVALUATION OF THE METHOD............................. FORCED DEGRADATION OF FINISHED PRODUCT AND STANDARD..................................1. Unstressed analysis...............................................................................................................2. Acid Hydrolysis stressed analysis..........................................................................................3. Base hydrolysis stressed analysis.........................................................................................4. Oxidation stressed analysis...................................................................................................5. Sunlight stressed analysis.....................................................................................................6. Heat of solution stressed analysis.........................................................................................7. Heat of powder stressed analysis.......................................................................................... System Suitability stressed analysis.......................................................................................... Placebo...................................................................................................................................... STABILITY OF STANDARD AND SAMPLE SOLUTIONS......................................................... Standard Solution...................................................................................................................... Sample Solutions....................................................................................................................... ROBUSTNESS.......................................................................................................................... Extraction................................................................................................................................... Factorial Design......................................................................................................................... CONCLUSION...........................................................................................................................ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationBACKGROUNDTherapeutically, Fluoxetine hydrochloride is a classified as a selective serotonin-reuptake inhibitor. Effectively used for the treatment of various depressions. Fluoxetine hydrochloride has been shown to have comparable efficacy to tricyclic antidepressants but with fewer anticholinergic side effects. The patent expiry becomes effective in 2001 (US). INTRODUCTIONFluoxetine capsules were prepared in two dosage strengths: 10mg and 20mg dosage strengths with the same capsule weight. The formulas are essentially similar and geometrically equivalent with the same ingredients and proportions. Minor changes in non-active proportions account for the change in active ingredient amounts from the 10 and 20 mg strength.The following validation, for the method SI-IAG-206-02 , includes assay and determination of Meta-Fluoxetine by HPLC, is based on the analytical method validation SI-IAG-209-06. Currently the method is the in-house method performed for Stability Studies. The Validation was performed on the 20mg dosage samples, IAG-21-001 and IAG-21-002.In the forced degradation studies, the two placebo samples were also used. PRECISIONSYSTEM REPEATABILITYFive replicate injections of the standard solution at the concentration of 0.4242mg/mL as described in method SI-IAG-206-02 were made and the relative standard deviation (RSD) of the peak areas was calculated.SAMPLE PEAK AREA#15390#25406#35405#45405#55406Average5402.7SD 6.1% RSD0.1ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::PRECISION - Method RepeatabilityThe full HPLC method as described in SI-IAG-206-02 was carried-out on the finished product IAG-21-001 for the 20mg dosage form. The method repeated six times and the relative standard deviation (RSD) was calculated.SAMPLENumber%ASSAYof labeled amountI 96.9II 97.8III 98.2IV 97.4V 97.7VI 98.5(%) Average97.7SD 0.6(%) RSD0.6PRECISION - Intermediate PrecisionThe full method as described in SI-IAG-206-02 was carried-out on the finished product IAG-21-001 for the 20mg dosage form. The method was repeated six times by a second analyst on a different day using a different HPLC instrument. The average assay and the relative standard deviation (RSD) were calculated.SAMPLENumber% ASSAYof labeled amountI 98.3II 96.3III 94.6IV 96.3V 97.8VI 93.3Average (%)96.1SD 2.0RSD (%)2.1The difference between the average results of method repeatability and the intermediate precision is 1.7%.HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationLINEARITYStandard solutions were prepared at 50% to 200% of the nominal concentration required by the assay procedure. Linear regression analysis demonstrated acceptability of the method for quantitative analysis over the concentration range required. Y-Intercept was found to be insignificant.RANGEDifferent concentrations of the sample (IAG-21-001) for the 20mg dosage form were prepared, covering between 50% - 200% of the nominal weight of the sample.Conc. (%)Conc. (mg/mL)Peak Area% Assayof labeled amount500.20116235096.7700.27935334099.21000.39734463296.61500.64480757797.52000.79448939497.9(%) Average97.6SD 1.0(%) RSD 1.0ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::RANGE (cont.)The results demonstrate linearity as well over the specified range.Correlation coefficient (RSQ)0.99981 Slope11808.3Y -Interceptresponse at 100%* 100 (%) 0.3%ACCURACYACCURACY OF STANDARD INJECTIONSFive (5) replicate injections of the working standard solution at concentration of 0.4242mg/mL, as described in method SI-IAG-206-02 were made.INJECTIONNO.PEAK AREA%ACCURACYI 539299.7II 540599.9III 540499.9IV 5406100.0V 5407100.0Average 5402.899.9%SD 6.10.1RSD, (%)0.10.1The percent deviation from the true value wasdetermined from the linear regression lineHPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::ACCURACY OF THE DRUG PRODUCTAdmixtures of non-actives (placebo, batch IAG-21-001 ) with Fluoxetine HCl were prepared at the same proportion as in a capsule (70%-180% of the nominal concentration).Three preparations were made for each concentration and the recovery was calculated.Conc.(%)Placebo Wt.(mg)Fluoxetine HCl Wt.(mg)Peak Area%Accuracy Average (%)70%7079.477.843465102.27079.687.873427100.77079.618.013465100.0101.0100%10079.6211.25476397.910080.8011.42491799.610079.6011.42485498.398.6130%13079.7214.90640599.413080.3114.75632899.213081.3314.766402100.399.618079.9920.10863699.318079.3820.45879499.418080.0820.32874899.599.4Placebo, Batch Lot IAG-21-001HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::VALIDATION OF FLUOXETINE HClAT LOW CONCENTRATIONLINEARITY AT LOW CONCENTRATIONSStandard solution of Fluoxetine were prepared at approximately 0.02%-1.0% of the working concentration required by the method SI-IAG-206-02. Linear regression analysis demonstrated acceptability of the method for quantitative analysis over this range.ACCURACY OF FLUOXETINE HCl AT LOW CONCENTRATIONThe peak areas of the standard solution at the working concentration were measured and the percent deviation from the true value, as determined from the linear regression was calculated.SAMPLECONC.µg/100mLAREA FOUND%ACCURACYI 470.56258499.7II 470.56359098.1III 470.561585101.3IV 470.561940100.7V 470.56252599.8VI 470.56271599.5(%) AverageSlope = 132.7395299.9SD Y-Intercept = -65.872371.1(%) RSD1.1HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationSystem RepeatabilitySix replicate injections of standard solution at 0.02% and 0.05% of working concentration as described in method SI-IAG-206-02 were made and the relative standard deviation was calculated.SAMPLE FLUOXETINE HCl AREA0.02%0.05%I10173623II11503731III10103475IV10623390V10393315VI10953235Average10623462RSD, (%) 5.0 5.4Quantitation Limit - QLThe quantitation limit ( QL) was established by determining the minimum level at which the analyte was quantified. The quantitation limit for Fluoxetine HCl is 0.02% of the working standard concentration with resulting RSD (for six injections) of 5.0%. Detection Limit - DLThe detection limit (DL) was established by determining the minimum level at which the analyte was reliably detected. The detection limit of Fluoxetine HCl is about 0.01% of the working standard concentration.ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::VALIDATION FOR META-FLUOXETINE HCl(EVALUATING POSSIBLE IMPURITIES)Meta-Fluoxetine HCl linearity at 0.05% - 1.0%Relative Response Factor (F)Relative response factor for Meta-Fluoxetine HCl was determined as slope of Fluoxetine HCl divided by the slope of Meta-Fluoxetine HCl from the linearity graphs (analysed at the same time).F =132.7395274.859534= 1.8Detection Limit (DL) for Fluoxetine HClThe detection limit (DL) was established by determining the minimum level at which the analyte was reliably detected.Detection limit for Meta Fluoxetine HCl is about 0.02%.Quantitation Limit (QL) for Meta-Fluoxetine HClThe QL is determined by the analysis of samples with known concentration of Meta-Fluoxetine HCl and by establishing the minimum level at which the Meta-Fluoxetine HCl can be quantified with acceptable accuracy and precision.Six individual preparations of standard and placebo spiked with Meta-Fluoxetine HCl solution to give solution with 0.05% of Meta Fluoxetine HCl, were injected into the HPLC and the recovery was calculated.HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::META-FLUOXETINE HCl[RECOVERY IN SPIKED SAMPLES].Approx.Conc.(%)Known Conc.(µg/100ml)Area in SpikedSampleFound Conc.(µg/100mL)Recovery (%)0.0521.783326125.735118.10.0521.783326825.821118.50.0521.783292021.55799.00.0521.783324125.490117.00.0521.783287220.96996.30.0521.783328526.030119.5(%) AVERAGE111.4SD The recovery result of 6 samples is between 80%-120%.10.7(%) RSDQL for Meta Fluoxetine HCl is 0.05%.9.6Accuracy for Meta Fluoxetine HClDetermination of Accuracy for Meta-Fluoxetine HCl impurity was assessed using triplicate samples (of the drug product) spiked with known quantities of Meta Fluoxetine HCl impurity at three concentrations levels (namely 80%, 100% and 120% of the specified limit - 0.05%).The results are within specifications:For 0.4% and 0.5% recovery of 85% -115%For 0.6% recovery of 90%-110%HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::META-FLUOXETINE HCl[RECOVERY IN SPIKED SAMPLES]Approx.Conc.(%)Known Conc.(µg/100mL)Area in spikedSample Found Conc.(µg/100mL)Recovery (%)[0.4%]0.4174.2614283182.66104.820.4174.2614606187.11107.370.4174.2614351183.59105.36[0.5%]0.5217.8317344224.85103.220.5217.8316713216.1599.230.5217.8317341224.81103.20[0.6%]0.6261.3918367238.9591.420.6261.3920606269.81103.220.6261.3920237264.73101.28RECOVERY DATA DETERMINED IN SPIKED SAMPLESHPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::REPEATABILITYMethod Repeatability - Meta Fluoxetine HClThe full method (as described in SI-IAG-206-02) was carried out on the finished drug product representing lot number IAG-21-001-(1). The HPLC method repeated serially, six times and the relative standard deviation (RSD) was calculated.IAG-21-001 20mg CAPSULES - FLUOXETINESample% Meta Fluoxetine % Meta-Fluoxetine 1 in Spiked Solution10.0260.09520.0270.08630.0320.07740.0300.07450.0240.09060.0280.063AVERAGE (%)0.0280.081SD 0.0030.012RSD, (%)10.314.51NOTE :All results are less than QL (0.05%) therefore spiked samples with 0.05% Meta Fluoxetine HCl were injected.HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationED. N0: 04Effective Date:APPROVED::Intermediate Precision - Meta-Fluoxetine HClThe full method as described in SI-IAG-206-02 was applied on the finished product IAG-21-001-(1) .It was repeated six times, with a different analyst on a different day using a different HPLC instrument.The difference between the average results obtained by the method repeatability and the intermediate precision was less than 30.0%, (11.4% for Meta-Fluoxetine HCl as is and 28.5% for spiked solution).IAG-21-001 20mg - CAPSULES FLUOXETINESample N o:Percentage Meta-fluoxetine% Meta-fluoxetine 1 in spiked solution10.0260.06920.0270.05730.0120.06140.0210.05850.0360.05560.0270.079(%) AVERAGE0.0250.063SD 0.0080.009(%) RSD31.514.51NOTE:All results obtained were well below the QL (0.05%) thus spiked samples slightly greater than 0.05% Meta-Fluoxetine HCl were injected. The RSD at the QL of the spiked solution was 14.5%HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationSPECIFICITY - STABILITY INDICATING EVALUATIONDemonstration of the Stability Indicating parameters of the HPLC assay method [SI-IAG-206-02] for Fluoxetine 10 & 20mg capsules, a suitable photo-diode array detector was incorporated utilizing a commercial chromatography software managing system2, and applied to analyze a range of stressed samples of the finished drug product.GLOSSARY of PEAK PURITY RESULT NOTATION (as reported2):Purity Angle-is a measure of spectral non-homogeneity across a peak, i.e. the weighed average of all spectral contrast angles calculated by comparing all spectra in the integrated peak against the peak apex spectrum.Purity Threshold-is the sum of noise angle3 and solvent angle4. It is the limit of detection of shape differences between two spectra.Match Angle-is a comparison of the spectrum at the peak apex against a library spectrum.Match Threshold-is the sum of the match noise angle3 and match solvent angle4.3Noise Angle-is a measure of spectral non-homogeneity caused by system noise.4Solvent Angle-is a measure of spectral non-homogeneity caused by solvent composition.OVERVIEWT he assay of the main peak in each stressed solution is calculated according to the assay method SI-IAG-206-02, against the Standard Solution, injected on the same day.I f the Purity Angle is smaller than the Purity Threshold and the Match Angle is smaller than the Match Threshold, no significant differences between spectra can be detected. As a result no spectroscopic evidence for co-elution is evident and the peak is considered to be pure.T he stressed condition study indicated that the Fluoxetine peak is free from any appreciable degradation interference under the stressed conditions tested. Observed degradation products peaks were well separated from the main peak.1® PDA-996 Waters™ ; 2[Millennium 2010]ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationFORCED DEGRADATION OF FINISHED PRODUCT & STANDARD 1.UNSTRESSED SAMPLE1.1.Sample IAG-21-001 (2) (20mg/capsule) was prepared as stated in SI-IAG-206-02 and injected into the HPLC system. The calculated assay is 98.5%.SAMPLE - UNSTRESSEDFluoxetine:Purity Angle:0.075Match Angle:0.407Purity Threshold:0.142Match Threshold:0.4251.2.Standard solution was prepared as stated in method SI-IAG-206-02 and injected into the HPLC system. The calculated assay is 100.0%.Fluoxetine:Purity Angle:0.078Match Angle:0.379Purity Threshold:0.146Match Threshold:0.4272.ACID HYDROLYSIS2.1.Sample solution of IAG-21-001 (2) (20mg/capsule) was prepared as in method SI-IAG-206-02 : An amount equivalent to 20mg Fluoxetine was weighed into a 50mL volumetric flask. 20mL Diluent was added and the solution sonicated for 10 minutes. 1mL of conc. HCl was added to this solution The solution was allowed to stand for 18 hours, then adjusted to about pH = 5.5 with NaOH 10N, made up to volume with Diluent and injected into the HPLC system after filtration.Fluoxetine peak intensity did NOT decrease. Assay result obtained - 98.8%.SAMPLE- ACID HYDROLYSISFluoxetine peak:Purity Angle:0.055Match Angle:0.143Purity Threshold:0.096Match Threshold:0.3712.2.Standard solution was prepared as in method SI-IAG-206-02 : about 22mg Fluoxetine HCl were weighed into a 50mL volumetric flask. 20mL Diluent were added. 2mL of conc. HCl were added to this solution. The solution was allowed to stand for 18 hours, then adjusted to about pH = 5.5 with NaOH 10N, made up to volume with Diluent and injected into the HPLC system.Fluoxetine peak intensity did NOT decrease. Assay result obtained - 97.2%.ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationSTANDARD - ACID HYDROLYSISFluoxetine peak:Purity Angle:0.060Match Angle:0.060Purity Threshold:0.099Match Threshold:0.3713.BASE HYDROLYSIS3.1.Sample solution of IAG-21-001 (2) (20mg/capsule) was prepared as per method SI-IAG-206-02 : An amount equivalent to 20mg Fluoxetine was weight into a 50mL volumetric flask. 20mL Diluent was added and the solution sonicated for 10 minutes. 1mL of 5N NaOH was added to this solution. The solution was allowed to stand for 18 hours, then adjusted to about pH = 5.5 with 5N HCl, made up to volume with Diluent and injected into the HPLC system.Fluoxetine peak intensity did NOT decrease. Assay result obtained - 99.3%.SAMPLE - BASE HYDROLYSISFluoxetine peak:Purity Angle:0.063Match Angle:0.065Purity Threshold:0.099Match Threshold:0.3623.2.Standard stock solution was prepared as per method SI-IAG-206-02 : About 22mg Fluoxetine HCl was weighed into a 50mL volumetric flask. 20mL Diluent was added. 2mL of 5N NaOH was added to this solution. The solution was allowed to stand for 18 hours, then adjusted to about pH=5.5 with 5N HCl, made up to volume with Diluent and injected into the HPLC system.Fluoxetine peak intensity did NOT decrease - 99.5%.STANDARD - BASE HYDROLYSISFluoxetine peak:Purity Angle:0.081Match Angle:0.096Purity Threshold:0.103Match Threshold:0.3634.OXIDATION4.1.Sample solution of IAG-21-001 (2) (20mg/capsule) was prepared as per method SI-IAG-206-02. An equivalent to 20mg Fluoxetine was weighed into a 50mL volumetric flask. 20mL Diluent added and the solution sonicated for 10 minutes.1.0mL of 30% H2O2 was added to the solution and allowed to stand for 5 hours, then made up to volume with Diluent, filtered and injected into HPLC system.Fluoxetine peak intensity decreased to 95.2%.ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationSAMPLE - OXIDATIONFluoxetine peak:Purity Angle:0.090Match Angle:0.400Purity Threshold:0.154Match Threshold:0.4294.2.Standard solution was prepared as in method SI-IAG-206-02 : about 22mg Fluoxetine HCl were weighed into a 50mL volumetric flask and 25mL Diluent were added. 2mL of 30% H2O2 were added to this solution which was standing for 5 hours, made up to volume with Diluent and injected into the HPLC system.Fluoxetine peak intensity decreased to 95.8%.STANDARD - OXIDATIONFluoxetine peak:Purity Angle:0.083Match Angle:0.416Purity Threshold:0.153Match Threshold:0.4295.SUNLIGHT5.1.Sample solution of IAG-21-001 (2) (20mg/capsule) was prepared as in method SI-IAG-206-02 . The solution was exposed to 500w/hr. cell sunlight for 1hour. The BST was set to 35°C and the ACT was 45°C. The vials were placed in a horizontal position (4mm vials, National + Septum were used). A Dark control solution was tested. A 2%w/v quinine solution was used as the reference absorbance solution.Fluoxetine peak decreased to 91.2% and the dark control solution showed assay of 97.0%. The difference in the absorbance in the quinine solution is 0.4227AU.Additional peak was observed at RRT of 1.5 (2.7%).The total percent of Fluoxetine peak with the degradation peak is about 93.9%.SAMPLE - SUNLIGHTFluoxetine peak:Purity Angle:0.093Match Angle:0.583Purity Threshold:0.148Match Threshold:0.825 ED. N0: 04Effective Date:APPROVED::HPLC ASSAY with DETERMINATION OF META-FLUOXETINE HCl.ANALYTICAL METHOD VALIDATION10 and 20mg Fluoxetine Capsules HPLC DeterminationSUNLIGHT (Cont.)5.2.Working standard solution was prepared as in method SI-IAG-206-02 . The solution was exposed to 500w/hr. cell sunlight for 1.5 hour. The BST was set to 35°C and the ACT was 42°C. The vials were placed in a horizontal position (4mm vials, National + Septum were used). A Dark control solution was tested. A 2%w/v quinine solution was used as the reference absorbance solution.Fluoxetine peak was decreased to 95.2% and the dark control solution showed assay of 99.5%.The difference in the absorbance in the quinine solution is 0.4227AU.Additional peak were observed at RRT of 1.5 (2.3).The total percent of Fluoxetine peak with the degradation peak is about 97.5%. STANDARD - SUNLIGHTFluoxetine peak:Purity Angle:0.067Match Angle:0.389Purity Threshold:0.134Match Threshold:0.8196.HEAT OF SOLUTION6.1.Sample solution of IAG-21-001-(2) (20 mg/capsule) was prepared as in method SI-IAG-206-02 . Equivalent to 20mg Fluoxetine was weighed into a 50mL volumetric flask. 20mL Diluent was added and the solution was sonicated for 10 minutes and made up to volume with Diluent. 4mL solution was transferred into a suitable crucible, heated at 105°C in an oven for 2 hours. The sample was cooled to ambient temperature, filtered and injected into the HPLC system.Fluoxetine peak was decreased to 93.3%.SAMPLE - HEAT OF SOLUTION [105o C]Fluoxetine peak:Purity Angle:0.062Match Angle:0.460Purity Threshold:0.131Match Threshold:0.8186.2.Standard Working Solution (WS) was prepared under method SI-IAG-206-02 . 4mL of the working solution was transferred into a suitable crucible, placed in an oven at 105°C for 2 hours, cooled to ambient temperature and injected into the HPLC system.Fluoxetine peak intensity did not decrease - 100.5%.ED. N0: 04Effective Date:APPROVED::。
维特比算法基因组序列全文共四篇示例，供读者参考第一篇示例：维特比算法是一种常用于基因组序列分析的算法，它是一个概率模型，通常用于预测最可能的序列。
在基因组学研究中，通过维特比算法可以有效地识别基因结构和进行基因组序列比对，进而推断基因功能和进行基因突变分析。
基因组序列是生物体内的所有基因的总和，它记录了生物体内所含有的所有遗传信息。
通过对基因组序列的研究，科学家们可以了解生物体的遗传背景，预测基因功能，甚至研究基因突变的影响。
基因组序列的长度通常非常庞大，因此如何高效地分析和处理这些序列成为了研究者们面临的首要挑战。
维特比算法正是为了解决这一难题而被广泛应用的。
它是一种最大后验概率准则下的解码算法，通过动态规划的方式计算出基因组序列中最可能的路径，并输出这条路径对应的序列。
维特比算法的优势在于其高效性和准确性，能够有效地处理大规模的基因组序列数据。
在维特比算法中，首先需要构建一个状态转移矩阵和一个发射概率矩阵。
状态转移矩阵描述了基因组序列中不同状态之间的转移概率，比如嘌呤到嘌呤、嘌呤到嘧啶等。
发射概率矩阵则描述了每个状态发射不同碱基的概率，比如在嘌呤状态下发射A的概率、C的概率等。
通过这两个矩阵，可以计算出基因组序列中每个碱基的概率分布。
接着，维特比算法利用动态规划的思想遍历整个基因组序列，计算出每个位置上最可能的状态。
具体来说，对于每个位置i和每个状态j，维特比算法会计算出到达位置i并处于状态j的最大可能概率。
通过不断更新这些概率值，最终可以得到整条基因组序列中最可能的状态路径。
一旦得到最可能的状态路径，就可以根据状态路径和发射概率矩阵推断出具体的碱基序列。
这个过程可以帮助研究人员快速准确地识别基因结构、预测基因功能和进行基因序列比对。
维特比算法还可以用于研究基因突变的影响，通过比较不同基因组序列间的状态路径，可以发现可能的突变点并推断其影响。
维特比算法在基因组序列分析中起到了至关重要的作用。
维特比算法（Viterbi Algorithm）是一种动态规划算法，主要用于寻找最有可能产生观测事件序列的隐含状态序列，特别是在马尔可夫信息源和隐马尔可夫模型中。
维特比算法由安德鲁·维特比（Andrew Viterbi）于1967年提出，并广泛应用于CDMA和GSM数字蜂窝网络、拨号调制解调器、卫星、深空通信和802.11无线网络中解卷积码。
维特比算法是一种特殊但应用最广的动态规划算法。
利用动态规划，可以解决任何一个图中的最短路径问题。
而维特比算法是针对一个特殊的图——篱笆网络（Lattice）的有向图最短路径问题而提出的。
它之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
具体来说，维特比算法从开始S出发一列一列地算，首先是S—>A，仅凭该列三条连接还不能判断从那条线路出发的路径最短，因此继续往下看。
S—>A—>B的路径共有9种可能，首先比较S—>A—>B1的三条路径，经过B1的这三条路径中很容易找出最优的一条路径即S—>A2—>B1，其他两条绝对不是最有路径中的路段，因为从B1出发往后继续走的路程概率是一样的，因此从S—>A—>B1的三条路径中除了最短那条外其余两条绝对不可能出现在全局最短路径中。
这样就筛选掉了两条路径得到如下图的结果。
注意上述S—>A—>B找候选路径中A—>B的连线方式是An—>B1的方式而不是A1—>Bn的方式，因为这种方式并不能确定最短的那个路段就是最可能的候选路径之一。
S—>A—>B其他两条最优候选路径。
2013c12 $ÊÆÆ 117ò14ÏDec.,2013Operations Research Transactions Vol.17No.4ÄuÄ 5y p Ûê¼ .í2 ViterbiŽ{∗“œ1,2,† Êœ3Á‡ÄkÏL Hadar d C†•{òp Ûê¼ .=†•†ƒ d ˜ •þŠÛê¼ .§, |^Ä 5y nïá ˜ •þŠÛê¼ . ViterbiŽ{§• ÏL pÛê¼ .Ú˜ •þŠÛê¼ .ƒm d'Xïá p Ûê¼ .ÄuÄ 5yí2 ViterbiŽ{.ïÄ(J3˜½§Ýþí2 A ¤kÛê¼ .©z¥¤ 9 )è¯K ViterbiŽ{§l ?˜Ú´LÚuÐ p Ûê¼ . Ž{nØ.'…c p Ûê¼ .§Ä 5y n§ViterbiŽ{¥ã©aÒO211.622010êÆ©aÒ60J10,60J22Extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model∗YE Fei1,2,†WANG Yifei3Abstract Firstly,high-order hidden Markov model is transformed into an equivalent first-order vector-valued hidden Markov model by using Hadar’s equivalent transforma-tion method.Secondly,the Viterbi algorithm for thefirst-order vector-valued hiddenMarkov model is established according to the dynamic programming principle.Finally,the extended Viterbi algorithm based on dynamic programming for high-order hiddenMarkov model is established by using the equivalence relation between high-order hiddenMarkov and thefirst-order vector-valued hidden Markov model.This study extends therelated Viterbi algorithms discussed in almost all literatures of hidden Markov model,and then contributes to the algorithmic theory of high-order hidden Markov model.Keywords high-order hidden Markov model,dynamic programming principle,Viter-bi algorithmChinese Library Classification O211.622010Mathematics Subject Classification60J10,60J22Âv Fϵ2013c3 15F*Ä7‘8µI[g,‰ÆÄ7(No.30871341),þ°½-:ƉÄ7(No.S30104),þ°½ ”-:Æ‰ï ‘8Ä7(No.J50101)1.Ô)Æ êƆOŽÅÆ ,SÔ)244000;School of Mathematics and Computer,Tongling University,Tongling244000,Anhui,China2.H®ŒÆ ¬‰ÆOŽ¢ ¥%,H®210093;Computational Experiment Center for Social Science, Nanjing University,Nanjing210093,China3.þ°ŒÆêÆX,þ°200444;Department of Mathematics,Shanghai University,Shanghai200444, China†ÏÕŠöCorresponding author,Email:postyf@44“œ, Êœ17ò0Úó19-V40c“§Bellman1˜g JÑ Ä 5yŽ{§ïá )û˜a`z¯K #•{.1953c BellmanéÄ 5yŽ{?1 ?˜Ú õ§‰Ñ äk y“¿Âþ Ä 5y V g.Ä 5yŽ{†©£{a q§•´ò–¦) ¯K©)¤e Z‡ƒq f¯K§ÏLÅÚ¦)f¯K ¼ ¯K •`).éu©£{˜…‡¦f¯K´ƒpÕá § ´3k œ¹eÃ{ò¯K©)•ƒpÕá f¯K§džX J^©£{¦)§k f¯Kò -E OŽéõg§ —OŽþ P{§ü$ OŽ Ç[1,2].• ;•f¯K -E OŽ§Ä 5yŽ{ÏL Bellman•§±48 /ªò f¯KÚ Œ f ¯KéXå5§¦^®¼ f¯K )5OŽ Œ f¯K§† ¦Ñ•Œ¯K )[3,4].Œ…Ä 5yŽ{ gŽ¢Ÿ´©£gŽÚ)ûP{§U wÍ/ü$¯K¦) OŽE,ݧ¦ ¯K ¦)•I s¤õ‘ªžm.Ä 5yŽ{g Bellman JÑ–8§® Øä ´LÚuЧ8c®¤•˜«-‡ êÆ`z•{§3²L+n!ó§EâÚ•`›› •¡ 2• A^.Viterbi u1967c3©z[5]¥JÑ ˜«šëY)èŽ{§¿^5»ÈòÈè§ù«Ž{ 5 ¡•ViterbiŽ{.‘ §Omura3©z[6]¥lÄ 5y ÝéViterbiŽ{?1 -# ã§Viterbi•3©z[7]¥éù«Ž{?1 ?˜Ú ´LÚuÐ., §Omura ÚForney©O3©z[6,8]¥•ÑViterbiŽ{Œ±Š••Œq,)èì.ViterbiŽ{g JÑ–8§®²3éõ•¡¼ A^.Ù¥˜‡“L5 ~f´|^ViterbiŽ{5)ûÛê¼ . )è¯K§•=3‰½*ÿS ^‡e§éÑ•kŒU )d*ÿS Ûõ´».©z[9,10]ïÄ ˜ Ûê¼ . )è¯K§ÏL½Â˜‡Viterbi Cþ§ïá ˜ Ûê¼ .)è¯K ViterbiŽ{.©z[11,12]Äu˜ Ûê¼ .ViterbiŽ{ nÚ•{§©OÏL½Â˜‡í2 Viterbi Cþ§ïÄ ˜a Ûê¼ .Ún Ûê¼ . )è¯K§ïá )è¯Kí2 ViterbiŽ{.C c5§˜ ïÄö}Áïá?¿p Ûê¼ . Ž{nØ¿^5©Û˜ ¢S ¯K§¼ ˜ k¿Â (J.©z[13]Äu .ü {§ÏL ORED(Order Reducing)Ž{ÚFIT(Fast Incremental Training)Ž{§ïá ˜a?¿p Ûê¼ . Ž{n ا 3¤ïÄ .¥••Ä G =£† §G ƒm •6'X§¿v kïÄ)è¯K ViterbiŽ{.©z[14]ïÄ ˜a?¿p Ûê¼ .¥ Š¯KÚ)è¯K§¿^5©Û3DNA S ¥ÏéCpG ¯K§ƒéu˜ Ûê¼ . •Ð J§ .•••Ä G =£† §G ƒm •6'X.©z[15,16]ïÄ ˜a?¿p Ûê¼ .n‡Ä ¯K Ž{¿A^uŠÑ£O§•,3 .¥Óž•Ä G =£ÚÑÑ*ÿ†•õ G ƒm éX§ ïá Ž{•·^u3ŠÑ£O¥ †–m ( .§ØäkÊ·5.©z[17]JÑ ˜a•äk˜…¿Â p Ûê¼ .§¿ïÄ ùa p Ûê¼ . Š¯KÚÆS¯K§‰Ñ ƒA Ž{§ v kïÄ)è¯KÚƒA Ž{.©z[18]3Hadar ïÄÄ:þ§Äu Hadar d C†•{ÚLi |Ü•{§¦^ .ü {ïá õ*ÿS e p Ûê¼ . Baum-WelchŽ{§‰Ñ õ*ÿS e p Ûê¼ . ëê- úª§¿¦^˜ Ûê¼ . I O Eâ5 OŽù ëê- úª. © é©z[17]¤JÑ ˜a?¿p Ûê¼ .§ÄkÏL Hadar d C†•{òp Ûê¼ .=†•†ƒ d ˜ •þŠÛê¼ .§, |^Ä 5y nïá ˜ •þŠÛê¼ . ViterbiŽ{§• ÏL p Ûê¼4ÏÄuÄ 5y p Ûê¼ .í2 ViterbiŽ{45.Ú˜ •þŠÛê¼ .ƒm d'Xïá p Ûê¼ .ÄuÄ 5yí2 ViterbiŽ{. © ïÄ)û ©z[17]¤JÑ ˜a?¿p Ûê¼ . )è¯K§3˜½§Ýþí2 A ¤kÛê¼ .©z¥¤ 9 )è¯K ViterbiŽ{§l ?˜Ú´LÚuÐ p Ûê¼ . Ž{nØ.1p Ûê¼ . Ä (½Â1.1[17]p Ûê¼ .´˜‡äk V-‘ÅL§ ÚO ..˜‡‘ÅL§•p àg Markovó§£ã G ƒm =£5Ƨ´ØŒ*ÿ §¡•G L§.,˜‡‘ÅL§£ã G †*ÿŠƒm ÚO'X§´Œ±*ÿ §¡•*ÿL§.Ù¥GL§{ q t}Tt=2−r Ú*ÿL§{o t}Tt=1©O÷vP( q t|{ q l}l<t)=P( q t|{ q l}t−1l=t−n),(1.1)P(o t|{o l}l<t,{ q l}l t)=P(o t|{ q l}tl=t−(m−1)).(1.2)ª¥, q t∈ S L«tž• G §o t∈ V L«tž• *ÿŠ,r=max{n,m}.3ùa p Ûê¼ .¥§b½G =£VÇ ûu n(n 2)‡G §Óžb½ÎÒuÑVÇ ûu m(m 2)‡G §l U B\•õ ÚO A §U é˜ ¢S L§Jø•\O( £ã.e¡äN`²ùa p Ûê¼ .¥˜ ëêÚÎÒ ¹Â.(1)G 8µS={s0,s1,···,s N−1},ª¥§N L« .¥MarkovóG ê8.Ø”˜…5§Œ-S={0,1,···,N−1}.(2)*ÿŠ8µV={v1,v2,···,v M},ª¥§M L« .¥z‡G éA *ÿŠê8.(3)G =£Vǵa i n···i1i0=P( q t=i0| q t−1=i1,···, q t−n=i n),ª¥§i n,···,i1,i0∈ S.…=£VÇ a i n···i1i0´†žm tÕá §÷v0 a in ···i1i0 1,N−1i0=0a i n···i1i0=1,P A={ a i n···i1i0}.(4)ÎÒuÑVǵb im−1 (i0)( )=P(o t=v | q t=i0,···, q t−(m−1)=i m−1),46“œ, Êœ17òª¥§i m−1,···,i0∈ S,v ∈ V.…ÎÒuÑVÇ b i m−1···i0( )´†žm tÕá §÷v0 b i m−1···i0( ) 1,M=1b im−1 (i0)( )=1.(1.3)P B={ b i m−1···i0( )}.(5)ЩG Vǵπi r···i1=P( q2−r=i r,···, q1=i1),ª¥§r=max{n,m},i r,···,i1∈ S.…÷v0 πir ···i1 1,N−1i r=0···N−1i1=0πi r···i1=1.(1.4)P π={ πir (i1)}.• •Bå…§˜…¦^ÎÒ λ=( π, A, B)L«p Ûê¼ . Nëê.Ù¥ πÚ A£ã p ê ‰Åó ÚO5Ÿ§ B£ã G †*ÿŠƒm ÚO'X.éu‰½ ëê• λ p Ûê¼ .§*ÿS O=o1o2···o T U UìX eÚ½ )µÚ½1ŠâЩVÇ πir (i1)ÀJЩG q2−r=i r,···, q1=i1.Ú½2-t=1.Ú½3ŠâÎÒuÑVÇ b i m···i1( ) )˜‡*ÿŠo t=v .Ú½4ŠâG =£VÇ a in (i1i0)a e˜‡G q t+1=i0.Ú½5-t=t+1¶e t<T§Kˆ£ Ú½3§ÄK(å.51.13þã p Ûê¼ .¥äk X e•›µ(1)G 8Ú*ÿÎÒ8Ñ´k• .(2)G =£VÇ a in (i1i0)´†žmÕá §=é?¿ tÑkP( q t+1=i0| q t=i1,···, q t−n+1=i n)=P( q t=i0| q t−1=i1,···, q t−n=i n).(1.5)(3)ÎÒuÑVÇ b i m−1···i0( )´†žmÕá §=é?¿ tÑkP(o t+1=v | q t+1=i0,···, q t−m+2=i m−1)=P(o t=v | q t=i0,···, q t−m+1=i m−1).(1.6)(4)®uÑ ÎÒé ¡ G =£VÇÚÎÒuÑVÇv kK•.2p Ûê¼ . Hadar d C†p Ûê¼ . G L§•{ q t}Tt=2−r §*ÿL§•{o t}Tt=1§-Q t=[ q t, q t−1,···, q t−(r−1)],(2.1)4ÏÄuÄ 5y p Ûê¼ .í2 ViterbiŽ{47•´Ûõ §…÷vª¥§1 t T.w,§•þŠG L§{Q t}Tt=1P(Q t|{Q l}l<t)=P( q t q t−1··· q t−(r−1)| q t−1 q t−2··· q2−r)=P( q t| q t−1 q t−2··· q2−r)=P( q t| q t−1 q t−2··· q t−r)=P( q t q t−1··· q t−(r−1)| q t−1 q t−2··· q t−r)=P(Q t|Q t−1).(2.2) , §é?¿ 2 t T−1,÷vP(Q t+1=[i0,i1,···,i r−1]|Q t=[i1,i2,···,i r])=P( q t+1=i0, q t=i1,···, q t−r+2=i r−1| q t=i1,···, q t−r+2=i r−1, q t−r+1=i r)=P( q t+1=i0| q t=i1,···, q t−r+2=i r−1, q t−r+1=i r)=P( q t=i0| q t−1=i1,···, q t−r+1=i r−1, q t−r=i r)=P( q t=i0, q t−1=i1,···, q t−r+1=i r−1| q t−1=i1,···, q t−r+1=i r−1, q t−r=i r)=P(Q t=[i0,i1,···,i r−1]|Q t−1=[i1,i2,···,i r]),(2.3)ª¥§[i0,i1,···,i r−1],[i1,i2,···,i r]∈{0,1,···,N−1}r.u´Œ e (Ø.½n2.1[17] Q t=[ q t, q t−1,···, q t−(r−1)]§K G L§{Q t}T t=1 ¤ ˜‡˜ àg •þŠMarkov L§.Óž§*ÿL§{o t}T÷vt=1P(o t|{o l}l<t,{Q l}l t)=P(o t|{o l}l<t,{ q l}l t)=P(o t|{ q l}l t))=P(o t|{ q l}tl=t−(r−1)=P(o t|Q t).(2.4) , §é?¿ 2 t T,÷vP(o t=v |Q t=[i0,i1,···,i r−1])=P(o t=v | q t=i0, q t−1=i1,···, q t−r+1=i r−1)=P(o t−1=v | q t−1=i0, q t−2=i1,···, q t−r=i r−1)=P(o t−1=v |Q t−1=[i0,i1,···,i r−1]).(2.5)d dŒ…§*ÿŠo t=ÚG Q t k'§…3?˜ž•lÓ˜G uÑÓ˜ÎÒ V Ç´ƒÓ .nþ¤ãŒe (Ø.½n2.2[17] Q t=[ q t, q t−1,···, q t−(r−1)]§K G L§{Q t}T t=1Ú*ÿL§{o t}T t=1 ¤ ˜‡˜ àg•þŠÛê¼ ..48“œ, Êœ17òe¡äN`²˜ •þŠÛê¼ .{Q t,o t}Tt=1¥˜ ëêÚÎÒ ¿Â.(1)G 8µS={0,1,···,N−1}r.(2)*ÿŠ8µV={v1,v2,···,v M}.(3)G =£Vǵa ij=P(Q t+1=j|Q t=i),ª¥§•þi c r−1‡©þ u•þj r−1‡©þ§…÷v0 a ij 1,j∈ Sa ij=1.P A={ a ij}.(4)ÎÒuÑVǵb i( )=P(o t=v |Q t=i),…÷v0 b i( ) 1,M=1b i( )=1.P B={ b i( )}.(5)ЩG Vǵπi=P(Q1=i),…÷v0 πi 1,i∈ Sπi=1.P π={ πi}.••Bå…§˜…¦^ÎÒ λ=( π, A, B)L«˜ •þŠÛê¼ .{Q t,o t}T t=1 Nëê.Ù¥ πÚ A£ã ê ‰Åó{Q t}T t=1 ÚO5Ÿ§ B£ã *ÿŠ†G ƒm ÚO'X.…ëê λ=( π, A, B)Ú λ=( π, A, B)ƒm•3e 'X.5Ÿ2.1[17] i=[i1,···,i r]§j=[i0,···,i r−1]§Ù¥i0,i1,···,i r∈ S.Këê λ= ( π, A, B)Ú λ=( π, A, B)ƒm÷vπi r···i1= πi, a i n···i0= a ij, b i m···i1( )= b i( ).(2.6)?˜ÚŒ±y²˜ •þŠÛê¼ .{Q t,o t}Tt=1Ú p Ûê¼ .´ d §•Ò´`ùü‡ . )Ó˜*ÿS VÇ´ƒÓ .•=•3±e(Ø.½n2.3[17] O=o1···o T•?˜*ÿS §KP(O| λ)=P(O| λ).(2.7)4ÏÄu Ä 5y p Ûê¼ .í2 Viterbi Ž{49y ² O =o 1···o T •?˜*ÿS §Šâ5Ÿ2.1ŒP (O | λ)=N −1 i 2−r =0···N −1 i T =0P (o 1···o T , q 2−r =i 2−r ,···, q T =i T | λ)=N −1 i 2−r =0···N −1 i T =0πi 2−r ···i 1 b i 2−m ···i 1(o 1) a i 2−n ···i 2 b i 3−m ···i 2(o 2)··· a i T −n ···i T b i T −m +1···i T (o T )=N −1 i 2−r =0···N −1 i T =0πi 2−r ···i 1 b i 2−r ···i 1(o 1) a i 2−r ···i 2 b i 3−r ···i 2(o 2)··· a i T −r ···i T b i T −r +1···i T (o T )= i 1∈ S···i T ∈ Sπi 1 b i 1(o 1) a i 1i 2 b i 2(o 2)··· a i T −1i T b i T (o T )=i 1∈ S ···i T ∈ SP (o 1···o T ,Q 1=i 1,···,Q T =i T | λ)=P (O | λ).ª¥§i t =[i t ,···,i t −r +1](1 t T ).¿…é?¿ 1 t T −1§•þi t c r −1‡©þ u •þi t +1 r −1‡©þ.½n 2.4 O =o 1···o T •?˜‰½ *ÿS §KP ( q 2−r ··· q T |O, λ)=P (Q 1···Q T |O, λ).(2.8)y ²Ø” q 2−r =i 2−r ,···, q T =i T §Ù¥i 2−r ,···,i T ∈ S §Šâ5Ÿ2.1ŒP (o 1···o T , q 2−r =i 2−r ,···, q T =i T | λ)= πi 2−r···i 1b i 2−m···i 1(o 1) a i 2−n···i 2b i 3−m···i 2(o 2)···a i T −n ···i Tb i T −m +1···i T (o T )= πi 2−r ···i 1 b i 2−r ···i 1(o 1) a i 2−r ···i 2 b i 3−r ···i 2(o 2)··· a i T −r ···i T b i T −r +1···i T (o T )= πi 1b i 1(o 1) a i 1i 2b i 2(o 2)··· a i T −1i Tb i T(o T )=P (o 1···o T ,Q 1=i 1,···,Q T =i T | λ).,P ( q 2−r =i 2−r ,··· q T =i T |O, λ)=P (O, q 2−r =i 2−r ,··· q T =i T | λ)P (O | λ),P (Q 1=i 1,···,Q T =i T |O, λ)=P (O,Q 1=i 1,···,Q T =i T |λ)P (O | λ).?˜Ú§Šâ½n 2.3ŒP ( q 2−r =i 2−r ,··· q T =i T |O, λ)=P (Q 1=i 1,···,Q T =i T |O, λ).3p Ûê¼ .í2 Viterbi Ž{¤¢p Ûê¼ . )è¯K §´•‰½ .ëê λ=( π, A, B )Ú*ÿS O =o 1o 2···o T §3,«•Z ¿Âe (½˜‡G S Q ∗= q ∗2−r q ∗3−r ··· q∗T §l « .50“œ, Êœ17òÛõÜ©§éÑ•kŒU )d*ÿS ´»./•Z0 ¿Âkéõ«§dØÓ ½ÂŒ ØÓ (Ø[19]. ©¤?Ø •Z¿Âþ G S Q∗= q∗2−r q∗3−r··· q∗T§´•Q∗=argmaxQ P( Q|O, λ)=argmaxQP( Q,O| λ).(3.1)ª¥§ Q= q2−r q3−r··· q T L«†*ÿS éA G S .Šâp Ûê¼ . ½Â§´•P( Q,O|λ)= π q2−r··· q1 b q2−m··· q1(o1) a q2−n··· q2 b q3−m··· q2(o2)··· a q T−n··· q T b q T−(m−1)··· q T(o T).(3.2)w,§ŽÑª(3.2)I‡2T−1g¦{.?˜Ú§X J^¡Þ{éÑ•`G S §K I‡N T+r−1(2T−1)g¦{$Ž§OŽ E,Ý•O(N T+r−1)§‘X T O\§OŽþ¥•ê?O•§Œ…¡Þ{¤I OŽþéŒ.• ü$OŽE,ݧéu˜ Ûê¼ . )è¯K§<‚æ^ ÄuÄ 5y ViterbiŽ{§l wÍ/J p OŽ Ç[20].Édéu§e¡òäN©Û¿ E p Ûê¼ .ÄuÄ 5yí2 ViterbiŽ{.Ä 5yŽ{Š•˜«ïÄõ ãûü¯K nØÚ•{§• )ûp Ûê¼ . )è¯K§Äk7L½ÂÑÜ· G CþÚûüCþ Ä ‡ƒ§¿¦ƒ÷v Bellman•`5 nÚà 5 n[21,22].du p Ûê¼ .¥ G =£VÇÚÎÒuÑVÇÚõ‡{¤G ƒ'§±—u† ¦^p Ûê¼ .¥ê¼ó G Cþ q tŠ•Ä 5yŽ{¥ G Cþ´ØÜ· .Äu d§ ép Ûê¼ .G L§{ q t}Tt=2−r§|^c¡¤ã Hadar d C†•{ E˜‡# G CþQ t= [ q t, q t−1,···, q t−(r−1)]§¿òd CþQ tŠ•Ä 5yŽ{¥ G Cþ.Óž§•¼ ˜‡† p Ûê¼ . d ˜ •þŠÛê¼ .{Q t,o t}Tt=1§¿^ÎÒ λ=( π, A, B)L «§ Nëê.Šâ½n2.3Œ•§éu?˜‰½ *ÿS O=o1···o T§÷vP( q2−r,···, q T|O, λ)=P(Q1,···,Q T|O, λ).(3.3)ª¥§Q1=[ q1,···, q2−r],···,Q T=[ q T,···, q T−(r−1)].?˜Ú§´• p Ûê¼ .•Z´»Ú˜ •þŠÛê¼ .{Q t,o t}Tt=1•Z´»ƒm•3±e(Ø.½n3.1 O=o1···o T•,‡‰½ *ÿS §G S Q∗= q∗2−r··· q∗T•p Ûê¼ . ,^•Z´»§=÷vQ∗=argmaxQP( Q,O| λ).(3.4)-Q∗t =[ q∗t,···, q∗t−(r−1)](1 t T)§K G S Q∗=Q∗1···Q∗T÷vP(Q∗,O| λ)=maxQP(Q,O| λ).(3.5)•Ò´`§G S Q∗=Q∗1···Q∗T•˜ •þŠÛê¼ .{Q t,o t}Tt=1,^•Z´».‡ƒ½,.4ÏÄu Ä 5y p Ûê¼ .í2 Viterbi Ž{51Äu þã½n 3.1§Äk ŠâÄ 5y n ïᘠ•þŠÛê¼ .{Q t ,o t }T t =1Viterbi Ž{§, ÏL p Ûê¼ .Ú˜ •þŠÛê¼ .{Q t ,o t }Tt =1ƒm d 'X ïáp Ûê¼ .Äu Ä 5y í2 Viterbi Ž{§ÏL ù«Ž{Œ† ¦ p Ûê¼ . •Z ´».3ùp A T 5¿ ´§é?Û 1 t T −1§•þQ t c r −1‡©þ u •þQ t +1 r −1‡©þ.Äk •Ä˜ •þŠÛê¼ .{Q t ,o t }T t =1§´•P (Q ,O | λ)= πQ 1 b Q 1(o 1) a Q 1Q 2 b Q 2(o 2)··· a Q T −1Q T b Q T (o T ).(3.6)u ´Œ±ò¦)˜ •þŠÛê¼ .{Q t ,o t }T t =1 •Z ´»Q ∗w Š´˜‡õ ãûü¯K . S O =o 1o 2···o T •Ý•T ž§Œ©•T −1‡ ã.Œ¦^u t (Q t +1)L «d G Q t G Q t +1¤ ¤ 1t ã ûüC þ§Óž•I ¼êŒP •v t (Q t ,Q t +1,u t (Q t +1))= a Q t Q t +1 b Q t +1(o t +1).(3.7)?˜Ú§ŒP c t ‡ ã •`•I ¼ê•g t (Q t +1)=max Q 1Q 2···Q tP (Q 1Q 2···Q t Q t +1,o 1o 2···o t o t +1)=max Q 1Q 2···Q tπQ 1 b Q 1(o 1) a Q 1Q 2 b Q 2(o 2)··· a Q t Q t +1 b Q t +1(o t +1).(3.8)ØJ w Ñù‡õ ãûü¯K ´÷v Bellman •`5 n Úà 5 n §u ´ŒïáÄ 5y ^S Ž{ Ä O Ž•§§•¡•Bellman •§§äN X e µg t (Q t +1)=max Q t ∈ S(g t −1(Q t ) a Q t Q t +1) b Q t +1(o t +1),(3.9)g 0(Q 1)= πQ 1 b Q 1(o 1).(3.10)–d §l Ä 5y Ý`² ¦)Q ∗ L §.w ,§ù´˜‡k X N r ‡g d ©àÚN r ‡g d ªà õ ãûüL §.äN Œ^ã1L «.---????G Q tG Q t +1G Q t +2v t (Q t ,Q t +1,u t )= a Q t Q t +1 b Q t +1(o t +1)v t +1(Q t +1,Q t +2,u t +1)= a Q t +1Q t +2 b Q t +2(o t +2)ûüu t (Q t +1)ûüu t +1(Q t +2)ãt T (Q t ,u t )ãt +1T (Q t +1,u t +1)ã1p Ûê¼ .õ ãûüL §'X ã• •\äN Ú•B /L «Ñª(3.9)¥ 4í'X §Œ- δt (i )=max Q 1···Q t −1P (Q 1···Q t −1,Q t =i ,o 1o 2···o t | λ).(3.11)52“œ, Êœ17ò§L«÷˜^´»Q1···Q t−1Q t§…Q t=i§ )* S o1o2···o t •ŒVÇ.˜…¡ δt(i)•Viterbi Cþ.u´•`•I¼êŒP•g t(Q t+1)= δt+1(Q t+1).(3.12)?˜Ú§Bellman•§ŒP•δt+1(Q t+1)=maxQ t∈ S (δt(Q t) a QtQ t+1) b Q t+1(o t+1),(3.13)δ1(Q1)= πQ1 b Q1(o1).(3.14)yØ”Q t=[ q t, q t−1,···, q t−(r−1)]=i=[i1,i2,···,i r],(3.15)Q t+1=[ q t+1, q t,···, q t−r]=j=[i0,i1,···,i r−1].(3.16)ª¥§0 i r,i r−1,···,i1,i0 N−1.Kª(3.13)C•δt+1(j)=maxi∈ S(δt(i) a ij) b j(o t+1).(3.17)ª(3.17)‰Ñ ˜ •þŠÛê¼ .{Q t,o t}Tt=1ÄuÄ 5yŽ{ Bellman•§.Äu d§e¡òïáp Ûê¼ . Bellman•§.•d§Äk•p Ûê¼ .½Â˜‡í2 Viterbi Cþδt(i r,···,i1).½Â3.1éu?¿ 0 i r,···,i1 N−1,1 t T§-δt(i r,···,i1)=maxq2−r··· q t−rP( q2−r··· q t−r, q t−r+1=i r,···, q t=i1,o1o2···o t| λ),(3.18) K¡δt(i r,···,i1)•p Ûê¼ .í2 Viterbi Cþ.§L«÷˜^´» q2−r··· q t§… q t−r+1=i r,···, q t=i1§ )* S o1o2···o t •ŒVÇ.½n3.2 0 i r,i r−1,···,i1 N−1,i=[i1,i2,···,i r]§Ké?¿ 1 t T÷vδt(i r,···,i1)= δt(i).(3.19) y²Šâ½n2.4§´•P( q2−r q3−r··· q t−r, q t−r+1=i r,···, q t=i1,o1o2···o t| λ)=P(Q1Q2···Q t−1,Q t=i,o1o2···o t| λ).?˜ÚŒδt(i r,···,i1)=maxq2−r q3−r··· q t−rP( q2−r q3−r··· q t−r, q t−r+1=i r,···, q t=i1,o1o2···o t| λ)=maxQ1···Q t−1P(Q1···Q t−1,Q t=i,o1o2···o t| λ)= δt(i).4ÏÄuÄ 5y p Ûê¼ .í2 ViterbiŽ{53 , §d5Ÿ2.1Œ•ëê λ=( π, A, B)Ú λ=( π, A, B)ƒm÷vπi r···i1= πi, a i n···i0= a ij, b i m···i1( )= b i( ).(3.20)Äuª(3.20)Ú½n3.2§|^í2 Viterbi Cþδt(i r,···,i1)§Œ p Ûê¼ .Ïé•Z G S Q∗ Ž{3.1.Ž{3.1ÄuÄ 5y p Ûê¼ .í2 ViterbiŽ{Ú½1Щzδ1(i r,···,i1)= πir···i1 b i m···i1(o1),(3.21)ϕ1(i r,···,i1)=0.(3.22)ª¥§0 i r,···,i1 N−1.Ú½248OŽδt(i r−1,···,i0)=max0 i r N−1(δt−1(i r,···,i1) a in (i0)) b i m−1···i0(o t),(3.23)ϕt(i r−1,···,i0)=argmax0 i r N−1(δt−1(i r,···,i1) a in (i0)).(3.24)ª¥§0 i r−1,···,i0 N−1,2 t T.Ú½3¥äP∗=max0 i r,···,i1 N−1δT(i r,···,i1),(3.25)( q∗T−(r−1),···, q∗T)=argmax0 i r,···,i1 N−1δT(i r,···,i1).(3.26)Ú½4´»(•Z G S )£ˆq∗t−r=ϕt( q∗t−(r−1),···, q∗t),2 t T,(3.27) l •`G SQ∗= q∗2−r··· q∗T.(3.28)53.1X J¦^ÄuÄ 5yí2 ViterbiŽ{¦)p Ûê¼ . )è¯K§•I‡(T−1)N r+1+N r g¦{$Ž§$Žþ†*ÿS •ÝT¥‚5'X§OŽ E ,Ý•O(N r+1)§ƒéu¡Þ{ OŽE,ÝO(N T+r−1)§3T ŒžOŽþòŒ•~ .53.2X J m=n=1§K p Ûê¼ .òz•˜ Ûê¼ .§í2 Viterbi C þƒA/òz•˜ Ûê¼ . Viterbi Cþ§u´Œ ©z[9,10]¥'u˜ Ûê¼ .)è¯K ViterbiŽ{.X J m=1,n=2§Œ ©z[11]¥'u˜a Ûê¼ .)è¯K ViterbiŽ{.X J m=3,n=3§Œ ©z[12]¥'u˜a n Ûê¼ .)è¯K ViterbiŽ{.X J m=1§ n?¿§Œ ©z[14]¥'u˜a?¿p Ûê¼ .)è¯K ViterbiŽ{.。
动态规划：卷积码的Viterbi译码算法学院：网研院姓名：xxx 学号：xxx 一、动态规划原理动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
二、卷积码的Viterbi译码算法简介在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。
（2,1,3）卷积码编码器是最常见的卷积码编码器，在本次实验中也使用了（2,1,3）卷积码编码器，下面介绍它的原理。
（2,1,3）卷积码是把信源输出的信息序列，以1个码元为一段，通过编码器输出长为2的一段码段。
该码段的值不仅与当前输入码元有关，而且也与其之前的2个输入码元有关。
如下图所示，输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出out2是输入和第二个编码器存储的值逻辑加操作的结果。
