2009年12月27日星期日

Free SMS

功能:
通过互联网免费发送短信

原理:
Google Calendar可以通过运营商发送短信提醒
Google App Engine可以当虚拟主机运行简单的程序
Google App Engine上可以跑Google Calendar API的类库

详解:
假设你想给A发短信,而且不想花钱。
1、让A注册一个Google账号,如果A已经有Google账号,此步可以省略;
2、你自己用一个Google账号B,在Calendar里面创建一个新日历,比如名字叫aaa,分享给A;
3、让A打开他账号下的Calendar,如果还没设置SMS,要先点Set up your mobile phone to receive
notifications,选中国、输入手机号,点"发送验证码",然后A的手机短信收到一个验证码,填到网页的验证码输入框中,点"Finishe
Setup",然后页面显示状态变成了绿色的"Phone number successfully
validated"。关键--让A找到你分享给A的日历aaa,设置提醒,默认通过SMS,提前事件一分钟发送;
4、你去开通Google App Engine,在xxxxx.appspot.com部署一个网站,网站后台程序自动通过Calendar
API向账号B的日历aaa添加事件,事件的时间设置为当前时间+75秒,这样你基本上就可以实时给A发消息了。程序关键的一段代码(Java):
private void send_msg(String to, String msg) throws Exception {
// login
CalendarService myService = new CalendarService("useless");
myService.setUserCredentials(USERNAME, PASSWORD);
// get URL
CalendarFeed resultFeed = myService
.getFeed(
new URL(
"http://www.google.com/calendar/feeds/default/owncalendars/full"),
CalendarFeed.class);
String post_url = null;
for (int i = 0; i < resultFeed.getEntries().size(); ++i) {
CalendarEntry entry = resultFeed.getEntries().get(i);
if (entry.getTitle().getPlainText().equals(to)) {
post_url = "http://www.google.com/calendar/feeds"
+ entry.getId().substring(
entry.getId().lastIndexOf("/"))
+ "/private/full";
break;
}
}
// create event
if (post_url == null)
throw new Exception(to + " not found");
CalendarEventEntry myEntry = new CalendarEventEntry();
myEntry.setTitle(new PlainTextConstruct(msg));
long now = DateTime.now().getValue() + (TIMEZONE * 3600 + DELAY) * 1000;
When eventTimes = new When();
eventTimes.setStartTime(new DateTime(now));
eventTimes.setEndTime(new DateTime(now + 60 * 1000));
myEntry.addTime(eventTimes);
myService.insert(new URL(post_url), myEntry);
}
然后外面简单包一层就可以用了
public class SimpleServlet extends HttpServlet {
private static final String USERNAME = "B@gmail.com";
private static final String PASSWORD = "B";
// now() + delay = the event time
private static final long DELAY = 60 + 15;//seconds
private static final int TIMEZONE = 8;//hours
public void doGet(HttpServletRequest req, HttpServletResponse resp)
throws IOException {
String to = req.getParameter("to");
String msg = req.getParameter("msg");
send_msg(to, msg);
}
}
(其中时区的问题你得自己动脑筋想一想)
配置web.xml
<servlet>
<servlet-name>api</servlet-name>
<servlet-class>SimpleServlet</servlet-class>
</servlet>
<servlet-mapping>
<servlet-name>api</servlet-name>
<url-pattern>/api</url-pattern>
</servlet-mapping>
5、通过Web发送短信
打开Firefox或UCWeb,输入网址,形如http://xxx.appspot.com/api?to=aaa&msg=balabala

限制:
msg不能超过57个字符(不同账号可能会有出入)
可能有一天app engine会撞墙
可能有一天你app engine的quota会用完
可能有一天Google会Ban掉你这样调用API的

开发:
个人认为用Java+Eclipse+Google Plug-in最方便,可以本地debug、一键部署
http://code.google.com/appengine/docs/java/tools/eclipse.html

应用:
1、私聊
用Web发送,用短信接收,所以只要能上网,就可以随时随地免费发短信,而且接受者可以不用上网。比飞信省流量,还不用装客户端。P.S.因为你可以登陆账号B,所以如果什么话说出去后又后悔了,可以在15秒内登陆Google
Calendar删除该Event即可。

2、当Twitter用
把自己的日历publish出去,让你那几个闺蜜来订阅。然后你api?to=yourself&msg=balabalalalala她们就收到短信了。

3、群聊
为了识别说话人的身份,Servlet程序需要多做一点工作。不然群里你一言我一语都不知道哪句话是谁说的就乱套了。
另外,怎样才能用一种简单的方式,不让自己的留言也发条短信给自己,我还没想好。

4、Monitor
比如你有一个系统,后台跑一个cronjob,让它
50 0 * * * wget "http://xxxx.appspot.com/api?to=your_team&msg=`grep
ERROR logfile | wc -l`" -O /dev/null

2009年10月17日星期六

时钟纸牌

《随机算法》一书中,时钟纸牌是这样一个程序:考虑13*4张标准扑克牌,随机排成13堆。先从第13堆中取一张,然后迭代地,每次从第x堆中取一张牌,其中x是上一次取的牌的面值,直到某次第x堆中没有牌为止。
命题:最后一次取的那张牌是13。
证明:假设最后一次取的牌不是13,是X,那么此时第X堆中没有牌,而程序开始时第X堆中有4张牌,所以在此之前已经从第X堆中取4张牌了,而每次从X堆中取牌,都必须要求上一次翻开的是X,所以在此之前已经翻开4张X了。一共就4张X,这次又翻出一张X,矛盾。

2009年5月11日星期一

Principle of Shrink Method in collaborative filtering

Scalable Collaborative Filtering with Jointly Derived Neighborhood InterpolationWeights等很多篇流行的协同过滤算法的文献中,都提到了Shrink技巧。

 

Shrink技巧的理论基础是高斯假设下的贝叶斯参数估计,这部分内容是经典的,可以在贝叶斯方法、模式分类等的领域相关教科书中找到。我们将假设和推导过程整理、重述如下:

假设我们要估计参数,视为随机变量,关于的先验知识是它服从正态分布,即其概率密度函数为:

的一组观测值视为独立同分布的样本,其总体为随机变量,满足条件正态分布。我们关心的是,有了一组观测后,我们应该如何用的信息修正先验知识。为此,计算后验概率密度函数:




其中c为归一化系数,倒数第二步将其整理为
的二次型,是为了将其凑成正态密度函数的形式。上式告诉我们服从正态分布,记为,则

将上面两个式子中
二项式对应项系数相等,得到下面两个方程:


从中很容易反解出我们关心的


从中可以得到两点结论:

1、后验期望总可以表示成样本均值和先验期望的凸组合;

2、当观测足够多,即n充分大时,趋向于0,即我们确信
非常接近其期望。而收敛到样本均值



中取



即得到文献中的Shrink技巧的实用形式:

2009年5月3日星期日

Implement RBM for netflix CF

RBM的实现

RBM预测器(隐层节点数F

参数

权值矩阵W,维数M×K×F(K=5)

Bias矩阵b,维数M×K

原始显层节点向量v0,元素取值于K,维数不超过M,与当前用户的评分个数相同,重构后的显层节点向量v1,与v0维数相同,mv0下标集到M的映射,即v0j表示电影mj的实际评分

隐层节点0-1向量第一次采样h0,第二次采样h1,维数F

每个用户对应的隐层节点向量的期望Eh,维数U×F

训练算法

1)初始化W~N(0, 0.001),bik=电影ik分的评分次数占电影i评分次数的比例

迭代2)3)直到收敛

2)对于每个用户u

2.a)根据u的实际评分生成v0

2.b)h0采样

,生成随机数p来自U[0,1],若

h0f=1,否则h0f =0

2.c)轮盘赌法重构v1


生成随机数p来自U[0,)

 其中k使得

2.d) h1采样

生成随机数p来自U[0,1],若

h1f=1,否则h1f =0

2.e)更新W

  h0f=1

  h1f=1

3)计算Eh



预测函数





实验结果

F=16,lrate=0.002
[1]1.0528 0.0508 1
[2]0.9617 -0.0018 135 0.0911
[3]0.9516 0.0024 273 0.0101
[4]0.9476 0.0007 411 0.0041
[5]0.9454 0.0008 550 0.0022
[6]0.9440 0.0011 689 0.0014
[7]0.9434 -0.0007 828 0.0006
...
[20]0.9404 -0.0003 2636 0.0002
...
[30]0.9400 -0.0024 4029 0.0001
...

各列含义:[迭代步数]RMSE(on ProbeSet) 平均偏差(on ProbeSet) 逝去时间(秒) RMSE改进量
发现前几步RMSE下降非常快。
注:使用Weight Decay可以略微改进结果
将2.e)改成

 

 

实验结果
F=16,lrate=0.002,decay=0.0001
...
[20]0.9393 -0.0011 2719 0.0005
...