参数估计有两种形式：点估计与区间估计。本文选择几种常用的点估计方法作一些讨论。
用于估计未知参数的统计量称为点估计（量）。参数 $\theta$ 的估计量常用 $\hat{\theta} = \hat{\theta}(x_{1},x_{2}, \dots, x_{n})$ 表示，参数 $\theta$ 的可能取值范围称为参数空间，记为 $\Theta = \{\theta\}$。
文章目录
最大似然估计
贝叶斯估计

最大似然估计
最大似然估计，即对似然函数最大化，其关键是从样本 $x$ 和含有位置参数 $\theta$ 的分布 $p(x,\theta)$ 获得似然函数。设 $x=(x_{1},x_{2},\dots,x_{n})$ 是来自含有未知参数的某分布 $p(x,\theta)$ 的一个样本，那么其联合分布为：

$p(x,\theta) = \prod_{i=1}^{n}p(x_{i},\theta)$ 其中 $p(x_{i},\theta)$ 在连续场合是指密度函数在 $x_{i}$ 处的值，在离散场合为分布列中的一个概率 $P_{\theta}(X=x_{i})$ 。对样本分布 $p(x,\theta)$ 我们知道：

样本如何产生？先有 $\theta$ 后有 $x$，即先有一个给定的 $\theta$ 的值 $\theta_{0}$，然后由分布 $p(x,\theta_{0})$ 经过随机抽样产生样本观察值 $x$。
如今我们有了 $x$ 如何追溯参数 $\theta_{0}$ 呢？当给定样本观察值 $x$ 时样本分布 $p(x,\theta)$ 仅是 $\theta$ 的函数，可记为 $L(\theta,x)$ 或 $L(\theta)$，并称其为似然函数。对于不同的 $\theta_{1},\theta_{2}\in\Theta$，可使得样本观察值 $x$ 出现的机会不同。若 $L(\theta_{1}) > L(\theta_{2})$，表明 $\theta_{1}$ 会使 $x$ 出现的机会比 $\theta_{2}$ 更大些，即 $\theta_{1}$ 比 $\theta_{2}$ 更像真值 $\theta_{0}$。也就是说 $L(\theta)$ 成为了度量 $\theta$ 更像真值的程度，其值越大越像。按此思路，在参数空间 $\Theta$ 中使 $L(\theta)$ 最大的 $\hat{\theta}$ 就是最像 $\theta_{0}$ 的真值，这个 $\hat{\theta}$ 就是 $\theta$ 的最大似然估计。

这里给出两个实例。
1.伯努利分布实例
假设 $P(X=1)=p,P(X=0)=1-p$ 综合起来就有

$P(X)=p^{X}(1-p)^{1-X}$

此时如果有一组数据 $D$ 是从这个随机变量中采样得到的，那么就有

$\begin{aligned}
\ max_{p}\log P(D)&= \max_{p}\log\prod_{i}^{N}P(D_{i}) \\
        &=\max_{p}\sum_{i}^{N}\log P(D_{i}) \\
        &=\max_{p}\sum_{i}^{N}[D_{i}\log p+(1-D_{i})\log(1-p)]
\end{aligned}$

对上式求导，则有

$\nabla_{p}\max_{p}\log P(D)=\sum_{i}^{N}[D_{i}\frac{1}{p}+(1-D_{i})\frac{1}{p-1}]$

求极值，令导数为 $0$，就有

$\begin{aligned}
& \sum_{i}^{N}[D_{i}\frac{1}{p}+(1-D_{i})\frac{1}{p-1}]=0 \\
& \sum_{i}^{N}[D_{i}(p-1)+(1-D_{i})p]=0 \\
& \sum_{i}^{N}(p-D_{i})=0 \\
& p=\frac{1}{N}\sum_{i}^{N}D_{i}
\end{aligned}$

即全部采样的平均值。
2.高斯分布实例
令 $p(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(x-\mu)^{2}}{2\sigma^{2}}}$，采用同样的方法有

$\begin{aligned}
 \max_{p}\log P(D) &= \max_{p}\log\prod_{i}^{N}P(D_{i})  \\
		 &= \max_{p}\sum_{i}^{N}\log P(D_{i}) \\
		 &= \max_{p}\sum_{i}^{N}[-\frac{1}{2}\log(2\pi\sigma^{2})-\frac{(D_{i}-\mu)^{2}}{2\sigma^{2}}] \\
		 &= \max[-\frac{N}{2}\log(2\pi\sigma^{2})-\frac{1}{2\sigma^{2}}\sum_{i}^{N}(D_{i}-\mu)^{2}]
 \end{aligned}$

此处包含两个参数，分别估计。
首先对 $\mu$ 求导，有

$\frac{\partial\max_{\mu}\log P(D)}{\partial \mu} = -\frac{1}{\sigma^{2}}\sum_{i}^{N}(\mu-D_{i})$

令导数为 $0$，有

$-\frac{1}{\sigma^{2}}\sum_{i}^{N}(\mu-D_{i})=0,\quad \mu=\frac{1}{N}\sum_{i}^{N}D_{i}$

注意很容易看出这个结果与最小二乘计算完全相同，实质上最小二乘法可以与极大似然法中假定误差遵循正态分布的特殊情况相对应。
其次对 $\sigma^{2}$ 求导，有

$\frac{\partial\max_{\sigma^{2}}\log P(D)}{\partial\sigma^{2}} = -\frac{N}{2\sigma^{2}}+\frac{1}{2\sigma^{4}}\sum_{i}^{N}(D_{i}-\mu)^{2}$

令导数为 $0$，有

$-\frac{N}{2\sigma^{2}}+\frac{1}{4\sigma^{4}}\sum_{i}^{N}(D_{i}-\mu)^{2}=0$

$\sigma^{2} = \frac{1}{N}\sum_{i}^{N}(D_{i}-\mu)^{2}$

可见最终计算结果与期望方差计算方式完全一致。注意最大似然估计并不一定具有无偏性。
对似然函数添加或剔除一个与参数 $\theta$ 无关的量 $c(x)>0$，不影响寻求最大似然估计的最终结果，故 $c(x)L(\theta)$ 仍然是 $\theta$ 的似然函数。例如，对于正态分布而言：

$L(\mu,\sigma^{2}) = \prod_{i=1}^{n}\frac{1}{\sqrt{2\pi}\sigma^{2}}e^{-\frac{(x_{i}-\mu)^{2}}{2\sigma^{2}}} \propto (\sigma^{2})^{-\frac{n}{2}}\exp\left\{-\frac{1}{2\sigma^{2}}\sum_{i=1}^{n}(x_{i}-\mu)^{2}\right\}$
不变原理： 设 $X\sim p(x,\theta), \theta\in\Theta$，若 $\theta$ 的最大似然估计为 $\hat{\theta}$ ，则对任意函数 $\gamma=g(\theta)$，$\gamma$ 的最大似然估计为 $\hat{\gamma}=g(\hat{\theta})$。
贝叶斯估计
统计学中有两个主要学派：频率学派（又称经典学派）和贝叶斯学派。前述最大似然估计属于经典统计学范畴。频率学派利用总体信息和样本信息进行统计推断，贝叶斯学派与之的区别在于还用到了先验信息。
贝叶斯学派最基本的观点是：任一未知量 $\theta$ 都可以看做随机变量，可用一个概率分布区描述，这个分布称为先验分布 （记为 $\pi(\theta)$）。因为任一未知量都有不确定性，而在表述不确定性地程度时，概率与概率分布是最好的语言。依赖于参数 $\theta$ 的密度函数在经典统计学中记为 $p(x,\theta)$，它表示参数空间 $\Theta$ 中不同的 $\theta$ 对应不同的分布。在贝叶斯统计中应记为 $p(x|\theta)$ ，表示随机变量 $\theta$ 给定某个值时，$X$ 的条件密度函数。
从贝叶斯观点看，样本 $x$ 的产生要分两步进行：首先，设想从先验分布 $\pi(\theta)$ 中产生一个样本 $\theta'$ ，这一步人是看不到的，所以是“设想”；再从 $p(x|\theta')$ 中产生一个样本 $x=(x_{1},x_{2},x_{3},\dots,x_{n})$ 。这时样本 $x$ 的联合条件密度函数为：

$p(x|\theta')=\prod_{i=1}^{n}p(x_{i}|\theta')$ 这个联合分布综合了总体信息和样本信息，又称为似然函数。它与极大似然估计中的似然函数没有什么区别。$\theta'$ 仍然是未知的，它是按照先验分布 $\pi(\theta)$ 产生的，为了把先验信息综合进去，不能只考虑 $\theta'$，对 $\theta$ 的其它值发生的可能性也要加以考虑，故要用 $\pi(\theta)$ 进行综合。这样一来，样本 $x$ 和参数 $\theta$ 的联合分布为：

$h(x,\theta)=p(x|\theta)\pi(\theta)$ 这个联合分布综合了总体信息、样本信息和先验信息。
我们的核心目标是对 $\theta$ 进行估计，若把 $h(x,\theta)$ 作如下分解：

$h(x,\theta) = \pi(\theta|x)m(x)$ 其中 $m(x)$ 是 $X$ 的边际密度函数:

$m(x) = \int_{\Theta}h(x,\theta)\mathrm{d}\theta = \int_{\Theta}p(x|\theta)\pi(\theta)\mathrm{d}\theta$ 它与 $\theta$ 无关。因此，能用来对 $\theta$ 进行估计的只有条件分布 $\pi(\theta|x)$，它的计算公式是：

$\pi(\theta|x)=\frac{h(x,\theta)}{m(x)} = \frac{p(x|\theta)\pi(\theta)}{m(x)} =  \frac{p(x|\theta)\pi(\theta)}{\int_{\Theta}p(x|\theta)\pi(\theta)\mathrm{d}\theta}$ 这就是贝叶斯公式的密度函数形式。 这个条件分布称为 $\theta$ 的后验分布，它集中了总体信息、样本信息和先验信息中有关 $\theta$ 的一切信息。也可以说是总体和样本对先验分布 $\pi(\theta)$ 作调整的结果，比先验分布更接近 $\theta$ 的实际情况。上述公式是在 $x$ 和 $\theta$ 都是连续随机变量场合下的贝叶斯公式。其它场合下的贝叶斯公式如下：

$x$ 离散，$\theta$ 连续： $\pi(\theta|x_{j})=\frac{p(x_{j}|\theta)\pi(\theta)}{\int_{\Theta}p(x_{j}|\theta)\pi(\theta)\mathrm{d}\theta}$
$x$ 连续，$\theta$ 离散：$\pi(\theta_{i}|x) =\frac{p(x|\theta_{i})\pi(\theta_{i})}{\sum_{i}p(x|\theta_{i})\pi(\theta_{i})}$
$x$ 离散，$\theta$ 离散：$\pi(\theta_{i}|x_{j}) =\frac{p(x_{j}|\theta_{i})\pi(\theta_{i})}{\sum_{i}p(x_{j}|\theta_{i})\pi(\theta_{i})}$

先验分布的确定十分关键，其原则有二：一是要根据先验信息；二是要使用方便，即在数学上处理方便。先验分布的确定有一些比较成熟的方法，如共轭先验分布法，此处不做详细讨论。
回到我们的核心目标，寻求参数 $\theta$ 的估计 $\hat{\theta}$ 只需要从后验分布 $\pi(\theta| x)$ 中合理提取信息即可。常用的提取方式是用后验均方误差准则，即选择这样的统计量

$\hat{\theta} = \hat{\theta}(x_{1},x_{2},\dots,x_{n})$ 使得后验均方误差达到最小，即

$\min\mathrm{MSE}(\hat{\theta} | x) =\min E^{\theta|x}(\hat{\theta}-\theta)^{2}$ 这样的估计 $\hat{\theta}$ 称为 $\theta$ 的贝叶斯估计，其中 $E^{\theta|x}$ 表示用后验分布 $\pi(\theta|x)$ 求期望。求解上式并不困难，

KaTeX parse error: No such environment: split at position 7: \begin{̲s̲p̲l̲i̲t̲}̲
E^{\theta|x}(\… 这是关于 $\hat{\theta}$ 的二次三项式，二次项系数为正，必有最小值：

$\hat{\theta} = \int_{\Theta}\theta\pi(\theta|x)\mathrm{d}\theta=E(\theta|x)$ 也就是说，在均方误差准则下， $\theta$ 的贝叶斯估计 $\hat{\theta}$ 就是 $\theta$ 的后验期望 $E(\theta|x)$。
类似的可证，在已知后验分布为 $\pi(\theta|x)$ 的情况下，参数函数 $g(\theta)$ 在均方误差下的贝叶斯估计为 $\hat{g}(\theta)=E[g(\theta)|x] $。
贝叶斯公式中，$m(x)$ 为样本的边际分布，它不依赖于 $\theta$ ，在后验分布计算中仅起到一个正则化因子的作用，加入把 $m(x)$ 省略，贝叶斯公式可改写为如下形式：

$\pi(\theta|x) \propto p(x|\theta)\pi(\theta)$ 上式右边虽然不是 $\theta$ 的密度函数或分布列，但在需要时利用正则化立即可以恢复密度函数或分布列原型。这时，可把上式右端称为后验分布的核，加入其中还有不含 $\theta$ 的因子，仍可剔去，使核更为精炼。

题目一：括号合法匹配：

题意：给定一个由()[]四种符号组成的字符串，求其中合法满足合法匹配的最长子串的长度。合法匹配有如下几种形式：()、[]、（合法串）、[合法子串]、合法子串+合法子串+....（如()[][][]()[]）。

分析：

dp问题三个重要环节：描述状态、状态转移方程、递推边界。

区间dp的话状态描述一般为二位数组，表示起点和终点。

因为是入门，我们暂且假设已经分析出该题为区间dp，所以状态描述就有了，dp[i][j]表示从i到j最长合法子串的长度。。。

首先我们先来看一下有一个字符的情况，比如结果为0,；两个字符的时候呢，如果这两个字符相同，为0+2，否则，还是0；再看3个字符的时候，即在2个字符的基础上加一个字符，此时的最大值可能为1+2的形式或者2+1的形式（分段）；分为四段时，则有可能为1+3、2+2,3+1三种形式，显然我们需要枚举断点，且取多种形式中的最大值作为结果：

其实这样看的话还少了两种形式：0+4和4+0,（可视作一种）；

而对于这一形式所需要的dp值我们是不知道的，所以我们可以先处理这种情况，其值由得来，如果区间两端元素相同，上式dp值+2，否则，就等于dp[i+1][j-1]（其实上述分段取值时已经包含了两端字符不相等时的情况，所以else可以省去），这样的话状态转移方程也就有了：





第三递推边界的话较容易考虑，但不太好想的地方是断点的范围，因为断点的选择决定了我们应该対哪些初始状态赋值，所以这个地方应该手动模拟一下，防止重复计算或者遗漏状态。

AC代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include<algorithm>
#include <set>
#include <queue>
#include <stack>
#include<vector>
#include<map>
#include<ctime>
#define ll long long
#define INF 0x7fffffff
using namespace std;
ll dp[110][110];
int main()
{
    string str;
    while(cin>>str&&str!="end")
    {
        memset(dp,0,sizeof(dp));
        ll n=str.length();
        for(ll len=1;len<n;++len)//枚举长度
        {
            for(ll j=0;j<=n-2&&j+len<=n-1;++j)
            {
                if(str[j]=='('&&str[j+len]==')'||str[j]=='['&&str[j+len]==']')
                {
                    dp[j][j+len]=dp[j+1][j+len-1]+2;
                }
                for(ll k=j;k<j+len;++k)
                {
                    dp[j][j+len]=max(dp[j][j+len],dp[j][k]+dp[k+1][j+len]);
                }
            }
        }
        cout<<dp[0][n-1]<<endl;
        str.clear();

    }
    return 0;

}


 

Progress Monitoring

题目链接：CodeForces - 509F 

题意：给出一个序列b，b是一棵树dfs下的节点输出顺序，同一层的节点值小的优先搜索；问这棵树有几种结构形式；

思路：dp[i][j]表示i为根i+1~j是其子树的节点，然后就是看i+1~j是否可以再分为多棵树；

假设可以继续分为以i+1， k+1为根的两棵树(i+1, k在同一层) ，则必须满足b[i+1]<b[k+1]或者k==j，如下：



至于为什么是dp[i+1][k]*dp[k][j]，而不是dp[i+1][k]*dp[k+1][j]或者dp[i+1][k-1]*dp[k][j]，我也是有点不思其解；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[510][510];//dp[i][j]表示以i为根节点的i+1~j是i的孩子节点, 注:这里的孩子并不指每个节点直接与i相连, 而是i->i+1->i+2->i+3->...->j, 是一条链;
int b[510];
ll dfs(int i, int j){
	if(i==j) return 1;//一个节点可以作为一棵树;
	if(dp[i][j]!=-1) return dp[i][j];//记忆化搜索;
	ll ans=0;
	//遍历i的所有孩子节点, 看能否以其中的节点为根节点, 产生两条链, 判断条件如下:
	//k是最右的节点, 可以单独成为一颗树;
	//b[k+1]>b[i+1], k~j可以单独成树;
	//这里表示从k开始分叉;
	for(int k=i+1; k<=j; k++){
		if(k==j||b[k+1]>b[i+1]){
			ans=(ans+dfs(i+1, k)*dfs(k, j)%mod)%mod;
		}
	}
	dp[i][j]=ans;
	return dp[i][j];
}
int main(){
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d", &b[i]);
	}
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", dfs(1, n));
	return 0;
}

 

题目如下：

解题思路：巨坑的一个题目。一般来说，leetcode这一类题目分为两种形式，一种是问能不能分割/有几种分割的方法，一种是列出所有分割的集合。本题是第二种，但是有一些特别坑的用例，其结果是无法分割，又非常容易超时。因此解题方法需要先判断能不能分割，能的话再计算怎么分割。首先看能不能分割：可以采用动态规划的方法。记dp[i] = 0表示s[0:i]区间不能分割,dp[i] = 1表示可以，我们可以得出这样的递推表达式，dp[i] = dp[j] if dp[j] == 1 and s[j+1:i+1] in wordDict，这样能很容易判断出s是否可以被分割；接下来是找出所有分割的集合，同样用动态规划的方法，记dp[i]表示s[0:i]区间所有分割的集合，那么有：dp[i] = dp[j] * s[j+1:i+1] if len(dp[j]) > 0 and s[j+1:i+1] in wordDict。
代码如下：

class Solution(object):
    def wordBreak(self, s, wordDict):
        dic = {}
        dp = [0] * len(s)
        for i in wordDict:
            dic[i] = 1

        for i in range(len(s)):
            if s[:i+1] in dic:
                dp[i] = 1
                continue
            for j in range(i+1):
                if dp[j] > 0 and s[j+1:i+1] in dic:
                    dp[i] = 1
                    break
        if dp[-1] == 0:
            return []

        dp = [[] for i in s]
        for i in range(len(s)):
            if s[:i+1] in dic:
                dp[i].append(s[:i+1])
            for j in range(i+1):
                if len(dp[j]) > 0 and s[j+1:i+1] in dic:
                    for k in dp[j]:
                        length = len(k.replace(' ',''))
                        dp[i].append(k + ' ' + s[length:i+1])
        return dp[-1]

 
转载于:https://www.cnblogs.com/seyjs/p/9549083.html