Simple SVD with Bias for Netflix Prize

In my linear algebra class this summer, I used the Netflix Prize challenge as a pratical example for an application of singular value decomposition (SVD). To be more precise, I explained the term \(p_u^Tq_i\) in the simple SVD with bias model:

$$\hat{r}_{ui} = \mu + b_u + b_i + p_u^Tq_i.$$

The above model can be found in section 2.1 in this progress paper of the winning team. In this note, I will explain this model and give an implementation in Python. A C implementation of the moddel can be found in my GitHub repository here:

Read More

Clustering Weibo Tags

I started a projected last October to collect Weibo's top search data (微博热搜榜) hourly. Together with the keywords or tags (关键词), most recent related weibos (or tweets) are collected as well. The result is save to a JSON file, with the format explained in this page.

In this post, I would like to explore this data set and try to cluster tags. To be more precise, multiple tags can be used to refer to a same event, and these different tags are related and even share the same meaning. The task is to group similar tags together based on the data collected.

Read More

Principal Component Analysis

This is the note I used as an example of applications in Linear Algebra I lectured at Purdue University. It is slightly modified so that it is more or less self contained.

Principal Component Analysis (PCA) is a linear algebra technique for data analysis, which is an application of eigenvalues and eigenvectors. PCA can be used in

  1. exploratory data analysis (visualizing the data)
  2. features reduction

We will learn the basic idea of PCA and see its applications in handwritten-digits recognition, eigenfaces and etc.

Read More

Linear Regression

This is the note I used as an example of applications in Linear Algebra I lectured at Purdue University. It is slightly modified so that it is more or less self contained.

Starting from least-squares solution, we are going to give an introductory exploration on (linear) regression in this note.

import numpy as np
import sklearn.linear_model
import matplotlib.pyplot as plt
from IPython.display import set_matplotlib_formats

plt.rcParams["figure.figsize"] = (8, 6)
set_matplotlib_formats('png', 'pdf')

Least-squares solution

Let \(A\) be an \(m \times n\) matrix, and \(B\) be a vector in \(\mathbb{R}^m\). A least-squares solution to a linear system \(Ax = B\) is an \(\hat{x}\) such that \(|A \hat{x} - B| \le |A x - B|\) for all \(x\). Here, \(|x|\) is the length of the vector \(x\). If the system \(Ax = B\) is consistent, then a least-squares solution is just a solution.

Read More

LeetCode Contest 209


第一题Special Array With X Elements Greater Than or Equal X

给定一个数组,找出 x 使得恰有 x 个数不小于 x

暴力枚举所有可能的 x

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for n in range(len(nums) + 1):
            if sum(1 for v in nums if v >= n) == n:
                return n
        return -1

Read More

LeetCode Contest 208

第二题 WA 了一次,其他都能一次 AC。这次拖慢速度的竟然不是手速,而是阅读速度。。。排名150左右。

第一题Crawler Log Folder

给定一系列类似于 cd 的操作,问最后的文件路径深度是多少。

模拟题,因为只需要知道深度,所以我们并不关心文件夹的名字,只考虑对深度影响 ../ -> -1,./ -> 0,其他 -> +1 。

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0
        for path in logs:
            if path == '../':
                depth = max(0, depth - 1)
            elif path == './':
                depth += 1
        return depth

Read More

LeetCode Contest 204

偶尔冒泡参加 Leetcode 的比赛。这次四题都做出来了,但是第一、三和四题都各自错了一次。排名250左右。

第一题Detect Pattern of Length M Repeated K or More Times

问一个数组里面是否存在长度为 m 的子数组被重复至少 k 次。

因为数据比较小,直接暴力搜索就行。第一次 WA 是因为 n - m * k + 1 写成 n - m * k 了。

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        n = len(arr)
        for i in range(n - m * k + 1):
            t = True
            for s in range(m):
                for t in range(k):
                    if arr[i + s] != arr[i + s + t * m]:
                        t = False
                if not t:
            if t:
                return True
        return False

Read More

SIR to fit COVID-19 data in the U.S.

Life is quite disrupted during this hard time of pandemic. It is especially stressful to see new cases rising again within the U.S.. When will the pandemic come to its peak? I belive many have asked about this question and many have given it serious thought. In this blog post, I want to give this question an answer using SIR model.

Read More

LeetCode Contest 188

快半年没有参加 LeetCode 的每周比赛了,感觉已经跟不上节奏了哈。四题用了1个小时,错了一次罚时5分钟,然后就排到350左右了。

第一题Build an Array With Stack Operations

模拟题,用 "Push" 和 "Pop" 构建一个给定的数组。

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ret = []
        cur = 0
        for t in target:
            ret.extend(["Push", "Pop"] * (t - cur - 1))
            cur = t
        return ret

Read More

[npnet] 循环神经网络

循环神经网络 (RNN, Recurrent Neural Network) 相对于之前的线性模型 (Linear Model) 或者卷积神经网络 (Convolution Neural Network) 能更好地处理具有顺序性的数据。比如说温度,每一个时间点的温度都跟之前若干个时间点的温度有联系。更重要的是,某个地方的温度在一天或者一年的时间内有一定的周期性。又比如说语言,一些单独的字或词需要有序地组织起来才能表达出清晰的意思。这样的数据用 RNN 能更好的归纳出规律。我们在这篇笔记中讨论简单 RNN 的理论以及实现。本文的主要参考文章:The Unreasonable Effectiveness of Recurrent Neural Networks

Read More