ARTS 第 47 周

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

题图：Photo by Louis Pellissier

Contents

• Algorithm: 349. Intersection of Two Arrays
• Review: Forecasting at Uber: An Introduction
• Tip: R 中的 embed() 函数
• Share: 演绎法中的逻辑缺陷

Algorithm

349. Intersection of Two Arrays

题目：349. Intersection of Two Arrays

难度：Easy

Companies: twosigma

题意：Given two arrays, write a function to compute their intersection.

示例 1：

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

示例 2：

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.
• The result can be in any order.

解法：这一题思路很简单，直接用两个集合就完事了，但要注意最后把集合转换成列表再返回。

代码：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        lookup = set()
        result = set()

        for i in nums1:
            lookup.add(i)

        for i in nums2:
            if i in lookup:
                result.add(i)

        return list(result)

时空复杂度都为 $O(n)$。

Review

Forecasting at Uber: An Introduction

本周阅读了不少文章（实际上处于研究需要，我每周都会读很多文章），这一篇来自 Uber Engineering 的博客《Forecasting at Uber: An Introduction》是这周我读过的几篇文章之一，非常有价值，属于提纲挈领的一篇 Introduction 文章。

文章介绍了在 Uber 内部，工程人员是如何利用预测来构建更好的产品和服务的。首先从 Uber 遇到的挑战说起，讲到了几大重要的预测算法，包括经典的统计学方法（ARIMA、ETS 和 Theta method）和机器学习算法（RNN、QRF、GBM、SVR 和 GP）以及一些复合方法，之后对常用的两种预测方法 Sliding Window 和 Expanding Window 做了对比和介绍，最后讲解了置信区间的重要性。

文章言简意赅，语言简洁通俗，内容却非常富有启发性，对于预测感兴趣的建议一读。

Tips

R 中的 embed() 函数

在对时间序列做预测的时候，如果想要使用一些常用的机器学习算法，那么必然会遇到一些问题，因为常用的机器学习算法并不能 handle 时间顺序，换句话说，Most ML methods have no awareness of time. 为了将时间序列的预测问题转换成机器学习常见的分类回归问题，我们需要对时间序列做一些特别的预处理：将时间序列经过多次平移，获得一个常用机器学习算法能够接受的矩阵，将最后一列当做 label feed 给算法。大体的思路可以用下面这个平移之后的矩阵来表示：

其中 ${y_K, \cdots, y_N}$ 这一列就是我们的原始时间序列，从 ${y_K}$ 到 ${y_2}$ 就是我们的训练集矩阵，而 ${y_1}$ 就是训练集的 label 了。

那么为了执行这样的操作，一个常规的思路就是进行平移了，不论是 Numpy 还是 R 中都提供了简单的 shift() 函数，可以很方便地执行这样的平移操作。

而 R 中还有个更方便快捷的函数，叫做 embed()，你只需要提供原始的时间序列和滞后数，embed() 就会返回一个上面格式的矩阵：

embed(x = ts.data, dimension = 5)

举例：

> embed(ts.data, 5)
      [,1] [,2] [,3] [,4] [,5]
 [1,]   84   75   45   24   23
 [2,]   36   84   75   45   24
 [3,]   20   36   84   75   45
 [4,]    1   20   36   84   75
 [5,]   74    1   20   36   84
 [6,]   39   74    1   20   36
 [7,]   21   39   74    1   20
 [8,]    9   21   39   74    1
 [9,]   11    9   21   39   74
[10,]   43   11    9   21   39

Share

演绎法中的逻辑缺陷

「演绎法」或者叫「推断法」是我们生活中常用的一种逻辑推理方法，最早在两千多年前由古希腊哲学家们提出来，后来经过数学家们几个世纪的研究加以完善，形成了我们今天所见的「演绎法」。

我们中学时经常做的证明题，很多时候就是使用的演绎法。给我们几个前提或者叫公理，比如 $A_1$、$A_2$……，然后让我们证明某个命题 $P_1$。

实际上，如果我们仅仅使用了 $A_1$ 和 $A_2$ 两个公理就证明了 $P_1$，那么 $P_1$ 的真实性唯一地依赖于公理 $A_1$ 和 $A_2$ 的真实性，而并不依赖于其他并未明确用于推断的公理 $A_3$、$A_4$、$A_5$ 等等。

这就产生了一个问题，尽管数学被我们认为是某种「最高的真理」，但作为数学基础的演绎推断法并不是没有逻辑缺陷的。问题来了：

我们使用 $A_1$、$A_2$ 推导出了 $P_1$，然后使用 $A_3$、$A_4$、$A_5$ 推导出了 $P_2$，那么 $P_1$ 和 $P_2$ 是否有可能是矛盾的呢？

答案是肯定的。著名的数理逻辑学家哥德尔证明了：

基于所给定公理系统的推断，人们并不能证明，又该公理系统不可能导致矛盾的结果。

这同时也证明了：

如果利用某个公理系统，我们可以同时演绎地得到命题 P 及其否定命题，那么我们就可以使用这个公理系统推断出任何我们想要的结果。

看起来是不是有点绕？我们再来看一个历史上真实存在的趣闻好了：

在很久很久以前，英国的著名数学家哈代(G. H Hardy)有一天在剑桥大学的一个晚餐会上提到了上面这个论断，于是一个坐在他对面的学者就向他提问：

学者：如果我说 2 + 2 = 5，你能证明你所给出的任意命题吗？ 哈代：我可以。 学者：那么请证明，麦克塔格特¹是罗马主教。 哈代：如果 2 + 2 = 5，那么 5 = 4，两边减去 3，就是 2 = 1；麦克塔格特和罗马主教是两个人，但是因为 2 = 1，所以麦克塔格特就是罗马主教。

这样是不是通俗直观一些了？尽管演绎推断法具有一些逻辑缺陷，但它仍然是我们常用且有效的逻辑推理方法之一。