[论文笔记] Edge-Assisted Hierarchical Federated Learning withNon-IID Data

提出了一种分层的联邦学习以及对应算法(HierFAVG)降低通信延时问题,与传统的 FAVG(Federated Averaging) 做对比。

原文地址

Edge-Assisted Hierarchical Federated Learning withNon-IID Data

背景

将 ML 或 DL 模型应用在边缘设备上是一个革命性的突破。然而,传统的模型训练是在计算中心完成的,近几年出于隐私保护问题,用户数据将不会上传至计算中心,数据保留在用户手中。在不上传数据的情况下,FL (联邦学习)提出了让各个设备协同训练一个共享模型,然后上传模型的更新信息到云中心进行模型聚合。但是,这种做法在通信消耗上出现了瓶颈。

过程

分层结构如下:

客户端的更新参数不是直接发送至云中心,而是发送至边缘服务器,然后边缘服务器再发送至云中心。

原因如下:

  1. 云中心比边缘服务器能够处理更多的用户连接,能够处理大量数据进行模型聚合。
  2. 客户端与边缘服务器的通信延时更低。
阅读更多
[论文笔记] Gossip Learning

提出 Gossip Learning,与 Federated Learning 做比较,实验表明使用 Gossip Learning 训练的模型在一定时间过后与Federated Learning 表现相当。

原文地址

Hegedűs I, Danner G, Jelasity M. Gossip Learning as a Decentralized Alternative to Federated Learning[C]//IFIP International Conference on Distributed Applications and Interoperable Systems. Springer, Cham, 2019: 74-90.


特色

传统的 Federated Learning 是 master-worker 架构(master 节点负责模型聚合,worker 是边缘设备,不同于参数服务器架构)

Gossip Learning 同样主张将数据保留在边缘设备上,但是它没有负责聚合的服务或者任何的中心组成部分,也就是说它是去中心化的。

文章通过实验表明了这两种方法训练出的模型变现相当,在高压缩率(采样率低)情况下,Gossip Learning 表现更佳。


阅读更多
分布式机器学习: 通信机制

分布式机器学习单机版的机器学习最大区别在于,它利用了多个工作节点同时训练、相互合作来加速学习过程。既然需要相互合作,那么通信就成为必不可少的环节。不过,分布式系统中的网络传输速度往往受限,导致通信常常成为分布式系统的瓶颈。举一个简单的例子:如果某个任务中计算与通信的时间占比为 1:1, 那么根据阿姆达尔定律(Amdahl’s law),无论使用多少台机器做并行运算,其加速比都不会超过两倍。因此,分布式机器学习的关键是设计通信机制,从而降低通信与计算的时间比例,更加高效地训练出高精度的模型。

一、通信的内容

通信的内容与并行方式有关。但是无论是数据并行还是模型并行,都需要在各个工作节点之间进行相互通信。总体而言,通信的内容可以分为参数(或参数的更新)和计算的中间结果两类。

1.1 参数或参数的更新

在基于数据并行的分布式机器学习中,工作节点各自完成本地的学习任务,然后互相交流各自对模型的修改,或者直接同步各自的模型。因此,在此情形下通信的内容是模型的参数或者参数的更新。在很多机器学习任务中,参数以及参数的更新是稀疏的同时在训练过程中,随着模型趋于收敛,参数的更新也会越来越少,这都会使得通信量相对较少(或越变越少)。因此进行通信以获取参数和参数更新是一个比较高效的选择。


阅读更多
LeetCode Weekly Contest 157

1217.Play with Chips

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

  • Move the i-th chip by 2 units to the left or to the right with a cost of 0.
  • Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

1
2
3
Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Constraints:

  • 1 <= chips.length <= 100
  • 1 <= chips[i] <= 10^9

题解

简单题,因为数据范围很小,可以考虑暴力,时间复杂度为 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int n = chips.size();
int mina = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
int temp = 0;
for (int j = 0; j < n; j++) {
if (j != i) {
temp += abs(chips[i]-chips[j])&1;
}
}
mina = min(mina, temp);
}
return mina;
}
};


阅读更多
贪吃蛇小游戏--SFML实现

经典游戏 —— 贪吃蛇。游戏的实现很简单,只要理清需要用什么数据结构表示蛇以及更新逻辑就好。这里使用 SFML 实现。

一、蛇的表示

我们可以将蛇身体每一部分存储起来,这里只需要储存每一部分的坐标值。如下

1
2
3
4
5
6
7
8
9
struct SnakeSegment {
int x, y;

SnakeSegment(int xx, int yy): x(xx), y(yy) {}

bool operator == (const SnakeSegment& other) {
return this->x == other.x && this->y == other.y;
}
};

</br>

二、更新逻辑

这里的话,我们需要考虑的逻辑有:

  • 在每一步的更新中,蛇的每一部分的坐标都在变化
  • 如果撞到自身,那么游戏重新开始
  • 判断是否吃到了食物
  • 边界处理

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void update() {
int n = snake.size();

for (int i = 0; i < n-1; i++)
snake[i] = snake[i+1];

if (dir == 0) snake[n-1].x--; if (dir == 1) snake[n-1].y++;
if (dir == 2) snake[n-1].x++; if (dir == 3) snake[n-1].y--;

if (std::find(snake.begin(), snake.end()-1, snake[n-1]) != snake.end()-1)
init();

if (snake[n-1].x == fruit.x && snake[n-1].y == fruit.y) {
fruit.x = rand() % (windowWidth-2)+1;
fruit.y = rand() % (windowHeight-2)+1;
snake.push_back(snake[n-1]);
}

if (snake[n-1].x >= windowWidth-1) snake[n-1].x = 1;
if (snake[n-1].x < 1) snake[n-1].x = windowWidth-2;

if (snake[n-1].y >= windowHeight-1) snake[n-1].y = 1;
if (snake[n-1].y < 1) snake[n-1].y = windowHeight-2;
}

</br>

三、其他东西

剩下的就是世界的绘制键盘事件的处理,这两部分实现比较简单,这里就不贴代码了。完整代码可以参见这里

游戏展示:

</br>

四、后续

作为展示,贪吃蛇游戏的代码实现过程较为简单,很多小细节没有去处理。例如,吃到食物之后蛇的身体没有立马更新、食物的随机生成没有考虑与蛇冲突、没有分数的展示等等,感兴趣的小伙伴可以动手去实现自己的贪吃蛇小游戏。😃


贝尔曼方程

本文将使用贝尔曼方程推导强化学习中的 State value functionQ function

1、一些概念

1.1、回报(Return)

智能体的目标是最大化回报。通常,回报需要定义一个折扣因子 $\gamma$,回报函数如下:

1.2、策略(Policy)

描述的是在某一状态 $s$ 下采取何种动作 $a$ 的概率,显然有:

1.3、State value function

State value function描述的是在策略 $\pi$ 下该状态 $s$ 下有多好。

1.4、Q function

Q function 描述的是在策略 $\pi$ 下,在状态 $s$ 采取动作 $a$ 有多好。

阅读更多
高斯分布下方差估计的推导

考虑一组独立同分布的样本 $\{x^{(1)},…,x^{(m)}\}$ 服从高斯分布 $p(x^{(i)})=\mathcal{N}(x^{(i)};\mu,\sigma^2)$,其中 $i \in \{1,…,m\}$ 。

</br>

样本方差(sample variance)

样本方差定义为

其中 $\hat{\mu}_{m}$ 是样本均值。

那么它的偏差为:$bias(\hat{\sigma}^{2}_{m})=\mathbb{E}[\hat{\sigma}^{2}_{m}]-\sigma^2$

以知的条件有:

  • $\mathbb{E}(x^{(i)})=\mu$
  • $D(x^{(i)})=\sigma^2$
  • $D(x^{(i)})=\sigma^2=\mathbb{E}[(x^{(i)})^2]-\mathbb{E}[x^{(i)}]^2$
  • $\mathbb{E}(\hat{\mu}_{m})=\mu$
  • $D(\hat{\mu}_{m})=D(\frac{1}{n}\sum_{i=1}^{m}x^{(i)})=\frac{1}{n^2}D(\sum_{i=1}^{m}x^{(i)})=\frac{\sigma^2}{n}$

那么有:

因此前面的偏差为$bias(\hat{\sigma}^{2}_{m})=-\frac{\sigma^2}{m}$


无偏样本方差(unbiased sample variance)

因此,下面这种估计是无偏的:

可以知道 $\tilde{\sigma}_m^2=\sigma^2$


用C++和SFML写游戏-2D 摄像机的使用(7)

本文将会介绍怎么在程序中使用摄像机和 OpenGL 。对摄像机将会深入的介绍,而对于 OpenGL,我们这里只做简单的介绍。OpenGL 是一个很大的主题,一篇文章根本就不能够将它完全介绍清楚。

本文将会介绍以下内容:

  • 什么是摄像机
  • sf::View 操作摄像机
  • 什么是 OpenGL
  • SFML 中使用 OpenGL
阅读更多
用神经网络思想实现 Logistic 回归

这是 吴恩达 的课程《神经网络与深度学习》第一个编程练习作业。

在这个作业中我们将不会使用任何循环(for/while),除非它明确说明要显式的使用循环。

将会学习到:

  • 建立一个学习算法的基本结构,它包括:
    • 初始化参数
    • 计算成本函数(cost function)以及它的梯度
    • 使用优化算法 — 梯度下降法(gradient descent)
  • 将上面提到的三个函数放入我们的主函数 model 中
阅读更多
用C++和SFML写游戏-让我们的精灵动起来(6)

在游戏中使用动画效果的话能够使我们的对象更加栩栩如生。例如,在有一个篝火精灵,如果它仅仅是一张静态的火焰图片,那么我们看到的火焰似乎没有在燃烧。然而,我们可以通过多张图片让它动起来,这也是我们这篇文章将要介绍的。这里,将会讲到:

  • 获取时间
  • 动画精灵
  • 创建动画基类
阅读更多