2016 年 2 月

第 31 卷,第 2 期

此文章由机器翻译。

Microsoft Azure - Azure Service Fabric、Q-Learning 和井字棋

通过 Jesus Aguilar

云计算减少屏障条目为分布式计算和机器学习应用程序从利基技术要求为商品提供任何软件开发人员或解决方案架构师的专业知识且昂贵的基础结构方面的创新。在本文中,我将介绍学习技术,利用 Azure 服务结构中,Azure 平台为的服务产品的下一个迭代的分布式计算和存储功能强化的实现。为了演示这种方法的可能性,我将介绍如何可以充分利用服务结构和其可靠参与者编程模型来创建可以预测下一个智能后端移动 tic-tac-toe 游戏中。战争游戏的任何人?

输入 Q 学习

现在我们看到创新数据驱动的解决方案,如建议,面临着无处不在识别和欺诈行为检测。软件工程团队使用监督和无人监督的学习技术来实现这些解决方案。这些方法广泛的功能,尽管一些情形下它们是难应用。

高效性学习是处理的方案可表示为一系列状态和转换的方法。与其他机器学习方法,不同强化学习不会尝试通过从标记信息 (受监管的学习) 或未标记的数据 (无监督学习) 为模型定型通用化模式。相反,它主要关注问题可以建模为状态和转换的序列。

假设您有可以表示为导致 (称为一部分状态) 的最终状态的状态的一串的方案。考虑机器人制定决策以避免的障碍或在游戏中设计为击败了对手的人工智能 (AI)。在许多情况下,特定的情形会导致状态的序列才是决定最佳的下一步代理/机器人/AI 的字符。

问: 学习是学习迭代奖励机制用于在状态机模型; 中查找最佳过渡途径的技术强化它们都运行不寻常的是正常的状态和它们的转换数是有限时。在本文中,我将介绍如何使用服务结构构建端到端 Q 学习解决方案并显示如何创建一个"学习"玩法 tic-tac-toe 的智能后端。(请注意,状态机方案也称为 Markov 决策过程 [Mdp])。

问: 学习有关的第一个、 一些基本理论。请考虑的状态和转换中所示 图 1。假设您想要在任何状态,查找处的状态的代理需要用来转换到下一步到达金牌状态,同时最小化的转换的数量。要解决此问题的一种方法是将奖励值分配到每个状态。这种回报提供建议的值转换为向您的目标状态: 正在获取金牌。

通向金牌状态的状态的序列
图 1 一个序列的状态为金牌状态前导

非常简单,是不是? 问题就成了如何识别为每个状态奖励。问: 学习算法通过循环并将奖励分配给导致的一部分 (金色) 状态的状态以递归方式来标识奖励。该算法将计算的折扣的奖励值从后续状态的状态奖励。如果状态具有两个奖励 — 这是当多个路径中存在一种状态 — 最高有效。折扣具有对系统产生重要影响。通过折扣回报,该算法可减少这种回报远离金牌的状态的值,将更多的权重分配给与金牌最接近的状态。

例如,算法将如何计算积分,看一看状态图 图 1。如您所见,有三种途径金牌:

1-> 5-> 4-> G

1-> 5-> 3-> 4-> G

1-> 5-> 3-> 2-> 4-> G

在运行使用暴力攻击的算法后强制转换 (遍历关系图中的所有可能路径),该算法计算并将分配奖励方案以供有效路径。奖励 0.9 的折扣系数计算。

1(R=72)-> 5(R=81)-> 4(R=90)-> G (R = 100)

1(R=64)-> 5(R=72)-> 3(R=81)-> 4(R=90)-> G(R=100)

1(R=58)-> 5(R=64)-> 3(R=72)-> 2(R=81)-> 4(R=90)-> G(R=100)

由于某些州具有多个奖励,将盛行的最大值。图 2 描绘了最终奖励分配。

最终奖励
图 2 最终奖励

使用此信息,代理可以通过转换到带最高奖励状态标识为在任何状态的金色的最佳路径。例如,如果代理处于状态 5,它可以对状态 3 或 4,转换选择和 4 便成为的选择,因为这种回报是更高版本。

Azure 服务结构

服务结构中,Azure 平台为的服务产品的下一个迭代使开发人员可以创建分布式应用程序使用两种不同的顶级编程模型: 可靠的参与者和可靠的服务。通过这些编程模型允许您以最大化分布式平台的基础结构资源。该平台处理与维护和运行分布式应用程序相关联的最困难任务 — 从故障中的恢复,服务以确保高效的资源使用率,滚动更新和向并行版本控制,说一些分发。

服务结构提供与群集中,为您提供更高级别的抽象,若要使用,而不是无需担心底层基础结构也是如此。您的代码运行的服务结构群集节点上,可以托管多节点群集出于开发目的的一台计算机上或为生产工作负荷的多个服务器 (虚拟或物理计算机) 上。平台管理您的使用者和服务以及从基础结构故障中的恢复的生命周期。

服务结构引入了具有有状态的语义的可靠参与者和服务。此功能会转换成可以在其中开发分布式且因此高度可用的方式保存数据,而无需包括外部存储层 (例如,在外部存储设备上获取依赖关系或缓存层) 的应用程序的完全集成的开发人员体验在您的体系结构中。

通过为服务结构中的服务实现 Q 学习算法,您可以受益于使用分布式计算和低延迟状态存储功能,使您能够执行算法、 保存结果,并将整件事情公开为客户端能够访问的可靠终结点。所有这些功能一起在单个解决方案中使用统一的编程和管理堆栈。没有必要将附加组件添加到您的体系结构,如外部存储、 缓存或消息传送系统。简单地说,您有一个驻留在其中计算、 数据和服务在同一个集成平台内的解决方案。这是在我的书是最好的解决方案!

问: 学习和可靠的参与者

使用者模型简化了大规模并行应用程序的设计。在使用者模型中,参与者是最基本的计算单位。参与者表示的功能和状态的边界。可以参与者看作生活在分布式系统中的对象实体。服务结构管理的参与者的生命周期。出现故障,服务结构都自动重新实例运行正常的节点中的参与者。例如,如果由于某种原因或正在发生故障的节点 (如 VM) 崩溃有状态的参与者,参与者是状态的自动在所有它 (数据) 保持不变的另一台计算机上重新创建。

服务结构还管理如何访问参与者的一个实例。该平台可以保证,在任一时间点,只有一个方法在特定的主角上执行一次。如果有对相同的参与者的两个并发调用,服务结构将其中一个进行排队,让其他继续。也就是说,参与者在您的代码无需担心争用条件、 锁或同步。

如我前面所述,Q 学习算法将循环访问其目标查找一部分状态和状态的增加,奖励的状态。一旦该算法所标识的一部分的状态与奖励,它将计算奖励方案以供导致一部分状态的所有状态。

使用使用者模型,我可以建模作为参与者表示 Q 学习算法 (如整体的关系图中的各个阶段) 的状态的上下文中此功能。在我的实现,参与者表示的类型,这些状态是 QState。后转换到包含奖励 QState 参与者,QState 参与者将为每个路径中的 QState 演员创建另一类型 (QTrainedState) 的另一个参与者实例。QTrainedState 参与者维护的最大回报值和后续产生回报的状态的列表。该列表包含后续状态的状态标记 (它唯一地标识在图中的状态)。

图 3, ,描绘了非常简单的方案,其中状态标记 3 的状态是一部分状态、 包含为 100,奖励,具有只能有一个路径,带有两个以前的状态 (状态令牌 1 和 2) 使用参与者,该算法的逻辑。每个圆圈表示的参与者,以蓝色 QStates 实例和 QTrainedStates 显示为橙色。转换过程到达后使用状态令牌 3 QState,QState 参与者将创建两个 QTrainedStates,分别针对每个以前 QStates。QTrainedState 主角表示状态标记为 2,(对于 90 奖励) 建议的转换是状态令牌 3 和 QTrainedState 参与者,它表示状态令牌 1,建议 (适用于的 81 回报) 转换为状态令牌 2。

确定和保持奖励
图 3 确定和保持奖励

很可能多个状态会产生相同的奖励,,因此 QTrainedState 参与者仍然存在子状态作为状态标记的集合。

下面的代码演示 QState 和 QTrainedState 参与者,名为 IQState 和 IQTrainedState 接口的实现。QStates 有以下两种行为: 过渡到其他 QStates 和启动转换进程没有以前的转换存在时:

public interface IQState : IActor
{
  Task StartTrainingAsync(int initialTransitionValue);
  Task TransitionAsync(int? previousStateToken, int transitionValue);
}
public interface IQTrainedState:IActor
{
 .Task AddChildQTrainedStateAsync(int stateToken, double reward);
 .Task<List<int>> GetChildrenQTrainedStatesAsync();
}

请注意 IQTrainedState 的实现公开方法 GetChildrenQTrainedStatesAsync。此方法是如何 QTrainedState 参与者将公开定型的数据包含在系统中使用的任何状态的最高奖励值的状态。(请注意服务结构中的所有参与者都必须都实现从 IActor 派生接口)。

QState 参与者

定义接口之后,我可以移到参与者的实现。首先使用 QState 参与者和 TransitionAsync 方法,它是该算法的基础,并且大部分的工作所在的位置。TransitionAsync 通过创建 QState 参与者的新实例,然后再次调用同一个方法,使过渡到另一种状态。

您可能想知道是否通过调用方法以递归方式将避免调用通过另一个参与者实例方法的开销。递归方法调用是在单个节点的计算密集型操作。与此相反,通过实例化另一个参与者,您会通过允许将处理分散到水平的计算资源的平台来采用 advantange 服务结构的功能。

若要管理的奖励分配,我将注册提醒。提醒都是在参与者的编程模型中引入的可用于安排异步工作,而不会阻止执行方法的新结构。

提醒都是仅适用于有状态的参与者。对于无状态和有状态的参与者,该平台提供了启用相似的模式的计时器。一个重要考虑因素是,当使用者时,垃圾收集进程已延迟;不过,该平台不使用考虑计时器回调。如果垃圾回收器会介入,将停止计时器。参与者不会进行垃圾回收时执行方法。若要确保定期执行,使用提醒。处找不到的详细信息 bit.ly/1RmzKfr

目标,因为它与该算法是执行奖励分配而不会阻止转换过程。通常情况下,计划中使用回调的线程池的工作项就足够了;但是,在参与者编程模型中,这种方法不是一个不错的主意,将丢失该平台的并发利益。

该平台可保证只有一个方法在任何时间执行。此功能,您可以编写代码,而无需考虑并发;也就是说,不带无需担心线程安全。如您所料,还有一个折中方案: 必须避免创建任务或线程来包装在参与者方法内的操作。提醒,可以实现与该平台的并发性保证的后台处理方案中所示 图 4

图 4 TransitionAsync QState 类中

public abstract class QState : StatefulActor, IQState, IRemindable
{
  // ...
  public Task TransitionAsync(int? previousStateToken, int transitionValue)
  {
    var rwd = GetReward(previousStateToken, transitionValue);
    var stateToken = transitionValue;
    if (previousStateToken != null)
        stateToken = int.Parse(previousStateToken.Value + stateToken.ToString());
    var ts = new List<Task>();
    if (rwd == null || !rwd.IsAbsorbent)
      ts.AddRange(GetTransitions(stateToken).Select(p =>
        ActorProxy.Create<IQState>(ActorId.NewId(),
        "fabric:/QLearningServiceFab").TransitionAsync(stateToken, p)));
    if (rwd != null)
      ts.Add(RegisterReminderAsync("SetReward",
        Encoding.UTF8.GetBytes(JsonConvert.SerializeObject(rwd))
        , TimeSpan.FromMilliseconds(0)
        , TimeSpan.FromMilliseconds(-1), ActorReminderAttributes.Readonly));
      return Task.WhenAll(ts);
  }
  // ...
}

(请注意,将 dueTime 设置为 TimeSpan.FromMilliseconds(0)) 指示立即执行。)

若要完成 IQState 的实现,下面的代码实现 StartTransitionAsync 方法,其中我使用提醒来避免阻止的长时间运行调用:

public Task StartTrainingAsync(int initialTransitionValue)
  {
    return RegisterReminderAsync("StartTransition",
      Encoding.UTF8.GetBytes(JsonConvert.SerializeObject(new { TransitionValue =
      initialTransitionValue })), TimeSpan.FromMilliseconds(0),
      TimeSpan.FromMilliseconds(-1),
      ActorReminderAttributes.Readonly);
  }

若要完成 QState 类的实现,我将介绍 SetRewardAsync 和中显示的 ReceiveReminderAsync 方法的实现 图 5。SetReward 方法创建或更新有状态参与者 (IQTrainedState 的实现)。若要查找操作者在后续调用中,我使用的状态标记为参与者 id — 是可寻址的参与者。

图 5 SetRewardAsync 和 ReceiveReminderAsync 方法

public Task SetRewardAsync(int stateToken, double stateReward, double discount)
  {
    var t = new List<Task>();
    var reward = stateReward;
    foreach (var pastState in GetRewardingQStates(stateToken))
    {
      t.Add(ActorProxy
        .Create<IQTrainedState>(new ActorId(pastState.StateToken),
          "fabric:/QLearningServiceFab")
        .AddChildQTrainedStateAsync(pastState.NextStateToken, reward));
      reward = reward * discount;
    }
    return Task.WhenAll(t);
  }
public async Task ReceiveReminderAsync(string reminderName,
  byte[] context, TimeSpan dueTime, TimeSpan period)
  {
    await UnregisterReminderAsync(GetReminder(reminderName));
    var state = JsonConvert.DeserializeObject<JObject>(
      Encoding.UTF8.GetString(context));
    if (reminderName == "SetReward")
    {
      await SetRewardAsync(state["StateToken"].ToObject<int>(),
        state["Value"].ToObject<double>(),
        state["Discount"].ToObject<double>());
    }
    if (reminderName == "StartTransition")
    {
      await TransitionAsync(null, state["TransitionValue"].ToObject<int>());
    }
  }

QTrainedState 参与者

在解决方案中的第二个参与者是 QTrainedState。QTrainedState 参与者中的数据必须为持久,因此我实现了有状态参与者作为此参与者。

在服务结构中,通过从 StatefulActor 或 StatefulActor < T > 基类派生您的类实现有状态参与者而从 IActor 实现接口派生。T 是状态实例,它必须是可序列化的类型和引用类型。平台调用时从 StatefulActor < T > 派生的类的方法,从状态提供程序,加载此状态并在调用完成后,该平台将其保存自动。对于 QTrainedState,我构建了状态 (持久数据) 使用以下类:

[DataContract]
public class QTrainedStateState
{
  [DataMember]
  public double MaximumReward { get; set; }
  [DataMember]
  public HashSet<int> ChildrenQTrainedStates { get; set; }
}

图 6 显示 QTrainedState 类,该类实现 IQTrainedState 接口的两种方法的完整实现。

图 6 QTrainedState 类

public class QTrainedState : StatefulActor<QTrainedStateState>, IQTrainedState
{
  protected async override Task OnActivateAsync()
  {
    this.State =
      await ActorService.StateProvider.LoadStateAsync<QTrainedStateState>(
      Id, "qts") ??
      new QTrainedStateState() { ChildrenQTrainedStates = new HashSet<int>() };
    await base.OnActivateAsync();
  }
  protected async override Task OnDeactivateAsync()
  {
    await ActorService.StateProvider.SaveStateAsync(Id, "qts", State);
    await base.OnDeactivateAsync();
  }
  [Readonly]
  public  Task AddChildQTrainedStateAsync(int stateToken, double reward)
  {
    if (reward < State.MaximumReward)
    {
      return Task.FromResult(true);
    }
    if (Math.Abs(reward - State.MaximumReward) < 0.10)
    {
      State.ChildrenQTrainedStates.Add(stateToken);
      return Task.FromResult(true);
    }
      State.MaximumReward = reward;
      State.ChildrenQTrainedStates.Clear();
      State.ChildrenQTrainedStates.Add(stateToken);
      return Task.FromResult(true);
  }
  [Readonly]
  public Task<List<int>> GetChildrenQTrainedStatesAsync()
  {
    return Task.FromResult(State.ChildrenQTrainedStates.ToList());
  }
}

公开参与者

此时,解决方案必须启动定型过程中并保留数据所需的一切。但我还没有论述如何与这些参与者客户端进行交互。在高级别中,这种交互组成启动定型过程和查询所保留的数据。每个这些交互进行与 API 操作,可以很好地关联并 RESTful 实施方便了与客户端集成。

除了有两种编程模型,服务结构是一个全面的业务流程和进程管理平台。存在参与者和服务的故障恢复和资源管理器也可为其他进程。例如,您可以运行 Node.js 或 ASP.NET 5 的进程,由服务结构和受益于这些功能而无需进一步的工作。因此我可以仅使用标准的 ASP.NET 5 Web API 应用程序并创建一个公开相关参与者功能的 API 控制器中所示 图 7

图 7 API 控制器

[Route("api/[controller]")]
public class QTrainerController : Controller
{
  [HttpGet()]
  [Route("[action]/{startTrans:int}")]
  public  async Task<IActionResult>  Start(int startTrans)
  {
    var actor = ActorProxy.Create<IQState>(ActorId.NewId(),
      "fabric:/QLearningServiceFab/");
    await actor.StartTrainingAsync(startTrans);
    return Ok(startTrans); 
  }
  [HttpGet()]
  [Route("[action]/{stateToken}")]
  public async Task<int> NextValue(int stateToken)
  {
    var actor = ActorProxy.Create<IQTrainedState>(new ActorId(stateToken),
      "fabric:/QLearningServiceFab");
    var qs = await actor.GetChildrenQTrainedStatesAsync();
    return qs.Count == 0 ? 0 : qs[new Random().Next(0, qs.Count)];
  }
}

和 Tic-Tac-Toe?

现在剩下是必须使用与具体方案的解决方案。为此,我将使用一个简单的游戏: tic-tac-toe。

目标是要训练 QTrainedStates 可以查询来预测下一步移动 tic-tac-toe 游戏中的一组。思考一下这个的一种方法是该计算机是作为两个玩家和经验教训结果。

回到实现的更多信息,请注意 QState 是一个抽象类。其理念是封装该算法的基本情况并将特定方案的逻辑放在派生类中。一种方案定义了三个部分的算法: 状态间的转换方式 (策略);一部分和具有初始的回报; 什么状态和状态该算法将会分配有折扣奖励。对于每个这些部件,QState 类有一个方法可以在其中实施这些语义,解决特定的方案。这些方法是 GetTransitions、 GetReward 和 GetRewardingQStates。

这样的问题就是: 如何为的状态和转换序列模型 tic-tac-toe 的游戏?

请考虑中所示的游戏 图 8, ,其中每个单元格都有分配的编号。您可以将从一个状态转换到另一个在其中的转换值是播放机正在播放的单元格作为每个打开。每个状态标记为则上一轮 (单元格) 和转换值的组合。例如,在 图 8, ,从 1 转换到 14,再到 142,以此类推,模型这里播放机播放第一个打开 wins 游戏的步骤。而且,在这种情况下,必须将导致 14273 (入选和一部分状态) 的所有状态都分配奖励: 1,142。

Tic-Tac-Toe 方案
图 8 Tic-Tac-Toe 方案

追溯到 Q 学习,我需要提供列出所有的最终 (一部分) 状态,每个都有初始奖励。对于 tic-tac-toe,三种类型的状态将都会产生奖励: win、 一次或块 (指一个点时您的对手赢得了,因此您会被迫使用现在轮到您来阻止他)。一种的成功和一次是一部分,这意味着游戏结束;一个块,但是,并不游戏将继续下去。图 9 显示 tic-tac-toe 游戏 GetReward 方法的实现。

图 9 GetReward 方法

internal override IReward GetReward(int? previousStateToken, int transitionValue)
{
  var game = new TicTacToeGame(previousStateToken,transitionValue);
  IReward rwd = null;
  if (game.IsBlock)
  {
    rwd = new TicTacToeReward() { Discount = .5, Value = 95, IsAbsorbent = false,
      StateToken = game.StateToken};
  }
  if (game.IsWin)
  {
    rwd = new TicTacToeReward() { Discount = .9, Value = 100, IsAbsorbent = true,
      StateToken = game.StateToken };
  }
  if (game.IsTie)
  {
    rwd = new TicTacToeReward() { Discount = .9, Value = 50, IsAbsorbent = true,
      StateToken = game.StateToken };
  }
  return rwd;
}

接下来,一旦奖励标识一种状态,则我需要提供该算法与导致将状态与初始奖励,因此无法分配折扣的奖励的状态。Win 或块的情况下,这些状态是所有以前的状态 (播放) 的入选或正在阻塞的播放机。对于版本号,所有状态 (播放) 的两个玩家必须都分配奖励:

internal override IEnumerable<IPastState> GetRewardingQStates(int stateToken)
{
  var game = new TicTacToeGame(stateToken);
  if (game.IsTie)           
    return game.GetAllStateSequence();           
  return game.GetLastPlayersStateSequence();
}

最后,我需要实现一个确定如何将算法遍历状态的过渡策略。对于游戏,我将实现其中探讨所有可能组合的转换策略:

internal override IEnumerable<int> GetTransitions(int stateToken)
{
  var game = new TicTacToeGame(stateToken);
  return game.GetPossiblePlays();
}

针对计算机播放

此时,我可以将解决方案发布并开始调用 REST API 通过培训并提供初始转换: 1 到 9。

一次培训完成时,您可以使用 API 创建的应用程序只需传递状态令牌并收到的建议的值。这篇文章的源代码包含一个使用该后端的通用 Windows 平台应用。图 10 显示游戏。

Tic-Tac-Toe 游戏
图 10 场 Tic-Tac-Toe 游戏

总结

通过使用 Q 学习和服务结构,我就能够创建利用了一个分布式的平台,用于计算和保持数据的端到端框架。为了展示这种方法,我使用 tic-tac-toe 游戏创建了解到如何玩游戏时,并且这样做了在可接受级别通过唯一的该值指示 win、 一次或块时出现并允许计算机了解通过玩游戏的后端。


Jesus Aguilar是技术推广和开发团队他与在云中,出生的令人惊叹公司合作,并可以帮助他们在 Microsoft 的高级云架构师在规模较大提供极具吸引力的体验。他是热衷于软件工程和解决方案设计,并将通过使用诸如"预测分析功能,""可伸缩性,""的并发程度,"之类的术语捕获注意力"设计模式"和"< 选择的任何字母 > aaS。" 您可以关注他的 Twitter: @giventocode 和签出他的博客 giventocode.com

感谢以下的微软技术专家对本文的审阅: Rob bagby 在其中简要、 Mike Lanzetta 和 Matthew Snider
Rob 是 sr。Microsoft 的云架构师。在此角色中,Rob 配合工作有影响力的 Isv,帮助他们在 Azure 中实现他们的软件。在之前此角色中,Rob 曾顾问构建松耦合,更易于管理、 可伸缩系统。

Mike Lanzetta 是在 Microsoft,合作伙伴 Catalyst 小组合作,致力于机器学习、 大数据和系统编程的开发者。他在从华盛顿大学的 CSE 中有一个由 MS,已经在行业 20 年多家公司,范围从新手到 Amazon 和 Microsoft。

Matt Snider 加入 Microsoft 在 2008 年,从事.NET 的一小部分。.NET 4 运送后,他加入了服务结构工作组,作为第一个技术 PM,处理所有不同的功能区域,已经与团队从那时起。这些天他主要适用于群集资源管理器 (Orchestrator)、 可靠的集合和在堆栈中的故障转移/复制部分。当不使用分布式系统,他喜欢啤酒、 徒步旅行和音乐。