自动笔的博客

HMM

Hidden Markov Model and EM Application

Model HMM是一个序列到序列的模型，支持有监督和无监督两种学习方式，首先先介绍马尔科夫链。 Markov Chain 假设有$n$个状态：$s_1,s_2,…,s_n$，可以认为这是一个时序序列。一个问题是给定这$n$个状态，怎样预测第$n+1$个状态。马尔科夫链是基于以下假设: 下一个状态只与当前状态有关即状态很多时候并不能直接观测到，但是状态会有表现形式，第$n...

Posted by An automatic pencil on July 26, 2019

EM算法（一）

介绍和推导

Why and When to Use EM Algorithm 不是所有的函数式都有解析解，EM算法是解决这种问题中的某一种（耦合问题），即一部分变量$A$相互依赖另一部分变量$B$，其中一部分变量确定另一部分就存在解析求解方法，但是都不确定没有办法直接求解。 k-means description 先介绍一个k-means聚类方法实际观察这类耦合问题。一个最简单的问题就是二维平面...

Posted by An automatic pencil on July 25, 2019

EM算法（二）

三硬币模型应用

EM算法计算的$q$ 上篇推导得到的E步要计算的，注意到$\theta_k$被固定，且注意到后面一部分是个常数，所以只需要计算前面一部分。记三硬币模型问题描述有$3$个硬币$A,B,C$,抛硬币正面的概率分别是$\pi,p,q$。现在先抛硬币$A$,如果是正面则抛硬币$B$,否则抛硬币$C$,已知观测到的值是第二次抛硬币的结果$Y$,估计$\pi,p,q$的值。...

Posted by An automatic pencil on July 25, 2019

HackerRank Problem Bear-and-steadyGene

滑动窗口

题目看题目戳我题解思路这个题目初次看到很自然的就会先考虑到先统计一下每种字符的数目，然后比较一下每种字符的数目和$n/4$的关系。不难知道，我们显然是把数目比较多的字符变到$n/4$，对所有字符做完这一点显然就能达到目的。考虑我们要操作的子串，两端记为$l$和$r$,如果这一段对于每种字符都不低于多出$n/4$的那些数目，我们就能把多的字符变少。而且需要注意一个性质，就是如...

Posted by An automatic pencil on January 3, 2019

HackerRank Problem Radio-Transmitters

贪心法

题目看题目戳我题解思路首先看个例子: 上图是题目中的一个例子，首先在数轴上标记出每个位置，然后从左到右先看2，如果在2放置，那么4会收到信号。再看4，如果在4放置，那么2，5，6都会收到信号。再看5，如果5放置，2就收不到信号了，所以为保证2能收到信号，显然在4放置更好。因为在4放置能保证左边覆盖掉的同时，右边尽可能大。然后后面的放置是一个道理。实...

Posted by An automatic pencil on December 26, 2018

强化学习（四）

策略迭代与值迭代实践

介绍上一次我们理解并证明了策略迭代和值迭代算法后，本次进行实践。问题给定一个$n*n$的网格，在某一个网格存在宝藏，给定宝藏位置，在每个网格处只能向上下左右四个方向移动。我们需要找出每个网格处为尽快找到宝藏我们应该采取的动作。设计解决方案状态空间：当前所在的网格位置构成的集合动作空间：上下左右以及不动即时奖励：除了宝藏位置，其他位置只要移动就为-1，宝藏位置...

Posted by An automatic pencil on December 25, 2018

HackerRank Problem Ema's Supercomputer

暴力大法

题目看题目戳我题解思路刚读题觉得好烦的题目，再一看数据范围，直接暴力。首先遍历两个加号的中心点位置，确定之后遍历每个加号大小，满足条件计数比较。代码 #include <bits/stdc++.h> using namespace std; // Complete the twoPluses function below. int twoPluses(...

Posted by An automatic pencil on December 18, 2018

HackerRank Problem Absolute Permutation

直接构造解

题目看题目戳我注意事项下标是从1开始的题解思路最先肯定是要举几个例子试一试咯。首先$k$是0的时候显然就是自然的序列。当$k>0$的时候，我们考虑在第$i$个位置上能放置什么数字。当$i\leq k$时，我们只能放$i+k$。所以有以下对应序列: $$ 1,2,...,k$$ $$1+k,2+k,...,k+k$$ 上面是下标序列，下面是对应的值。下面考虑第$k...

Posted by An automatic pencil on December 17, 2018

强化学习(三)

策略迭代和值迭代

两个问题预测(prediction) 控制(control) 预测就是给定一个策略，我们要根据贝尔曼最优方程求解最优价值函数。控制则是求解出最优策略和最优价值函数。预测问题的解决显然预测问题更好解决，所以我们先讨论预测问题的解决。解决方法基本思想就是迭代。由于策略已经给定，我们将贝尔曼方程改写成矩阵形式，有记迭代轮数为$k$,基本想法就是用上一轮的状...

Posted by An automatic pencil on December 14, 2018

HackerRank Problem Points on a Rectangle

题目看题目戳我题解思路由于要判断的矩形是平行于坐标轴的，所以我们可以先根据这些点确定出这个矩形，然后判断剩余点是否在这个矩形上。代码 #include <bits/stdc++.h> using namespace std; // Complete the solve function below. string solve(vector<vecto...

Posted by An automatic pencil on December 11, 2018

An Automatic Pencil Blog

HMM