application/x-www-form-urlencoded

这是比较常用的提交数据的方式,在项目中也使用的是这一种,在MockMvc测试的参数准备时可以这样使用:

1
2
3
4
5
6
7
8
9
UrlEncodedFormEntity form = new UrlEncodedFormEntity(Arrays.asList(
new BasicNameValuePair("参数1", value1),
new BasicNameValuePair("参数2", value2),
), "utf-8");
MvcResult result = mvc.perform(MockMvcRequestBuilders.post("/test")
.contentType(MediaType.APPLICATION_FORM_URLENCODED)
.content(EntityUtils.toString(form))
)
.andExpect(status().isOk()).andReturn();

主要使用的是UrlEncodedFormEntity类,要注意的是需要设置字符集否则传参的时候中文会变成???.

application/json

我使用的是用阿里开源的fastjson直接转换的形式:

1
2
3
4
5
6
7
8
9
Parm parm = new Parm(); //你要传的参数的对象
//设置参数对象的值
String requestJson = JSONObject.toJSONString(parm);
MvcResult result = mockMvc.perform(post("/softs")
.contentType(MediaType.APPLICATION_JSON)
.content(requestJson)
)
.andDo(print())
.andExpect(status().isOk()).andReturn();

multipart/form-data

这个没有使用过,就借鉴Stack Overflow上的一个答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MockMultipartFile file = new MockMultipartFile("data", "dummy.csv",
"text/plain", "Some dataset...".getBytes());

MockMultipartHttpServletRequestBuilder builder =
MockMvcRequestBuilders.fileUpload("/test1/datasets/set1");
builder.with(new RequestPostProcessor() {
@Override
public MockHttpServletRequest postProcessRequest(MockHttpServletRequest request) {
request.setMethod("PUT");
return request;
}
});
mvc.perform(builder
.file(file))
.andExpect(status().ok());

get请求传参

这个虽然不是POST也很简单,但是也记录一下

1
2
3
4
5
MvcResult result = mvc.perform(MockMvcRequestBuilders.post("/v4/address/deleteAddress")
.param("参数1", value1)
.param("参数2", value2)
)
.andExpect(status().isOk()).andReturn();

也可以使用params的方式使用Map来传参,但是我还是习惯这样来初始化,因为毕竟每个参数还是需要自己设置的,这样看起来也清晰一点.

前言

国庆回来之后算是正是开始了Spring Boot的工作,而Java组里因为没有写任何的单元测试,每次测试都是靠Swagger的web页面自己填参数来测试,于是在这次新版本的迭代中我变成了第一个被要求贯彻实施每个controller都要写测试的人,不过单元测试,从我做起,真的很重要啊.

然后在选择的时候发现了MockMvc这个Spring自带的测试利器,个人认为主要的优势就在于可以直接在Java中模拟HTTP请求,而且对于模拟请求和参数的解析也是一把好手,当然就是选择它啊!,我当然是赞成的.然后在寻找资料的时候因为一开始没有看官方文档也是被搞懵了很久,在看了官方文档之后才豁然开朗,于是就为了自己,翻译一下记录一下,以防健忘的自己以后重复找轮子.

这里是文档地址:https://docs.spring.io/spring/docs/current/spring-framework-reference/testing.html#testing-introduction,因为这次只测试和服务器端的单元测试,所以文档也就翻了这部分.

Spring MVC Test Framework

Spring MVC Test框架为使用流畅的API测试Spring MVC代码提供了最高级的支持,你可以使用JUnit,TestNG或者其他任何的测试框架.它被构建在spring-test模块的Servlet API mock 对象之上,因此不使用运行中的Servlet容器.它使用DispatcherServlet来提供完整的Spring MVC运行时的行为并且除了独立的模块之外还提供了使用TestContext框架来加载实际的Spring配置的支持,也就是说你可以手动执行Controller的实例并且一次测试一个.

Spring MVC Test还使用RestTemplate来提供客户端的代码测试.客户端的测试模拟服务端的响应所以也不会使用正在运行的服务.

Spring Boot提供了一个选项来写一个完整的,端到端的包含运行中服务的集成测试.如果这是你的目标,查看Spring Boot reference page.获取更多关于容器外和端到端集成测试的区别的信息,查看Differences Between Out-of-Container and End-to-End Integration Tests

Server-Side Tests

你可以使用JUnit或者TestNG为Spring MVC controller编写一个普通的单元测试.如果要这么做的话,实例化conreoller,使用mocked或者stubbed依赖注入,然后使用它们的方法就行了(例如:MockHttpServletRequest,MockHttpServletResponse,和其他有必要用到的).然而,当你这样来写单元测试的时候,很多东西是测试不到的,例如:RequestMapping,数据绑定,类型转换,数据的合法性验证等等.此外,其他的controller方法,例如@InitBinder,@ModelAttribute@ExceptionHandler也会作为请求过程生命周期中的一部分被请求到.

Spring MVC Test的目标是提供一个高效的方式来测试controller通过执行请求和生成response通过实际的DispatcherServlet.

Spring MVC Test构建在熟悉的spring-test模块的“mock” implementations of the Servlet API之上.这也就允许我们不需要运行一个Servlet容器就可以模拟请求和生成response.在大部分情况下,一切都会像真实环境一样工作但是也有几个例外:[Differences Between Out-of-Container and End-to-End Integration Tests](### Differences Between Out-of-Container and End-to-End Integration Tests).下面的代码是基于JUnit Jupiter使用Spring MVC Test的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.*;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.*;

@SpringJUnitWebConfig(locations = "test-servlet-context.xml")
class ExampleTests {

private MockMvc mockMvc;

@BeforeEach
void setup(WebApplicationContext wac) {
this.mockMvc = MockMvcBuilders.webAppContextSetup(wac).build();
}

@Test
void getAccount() throws Exception {
this.mockMvc.perform(get("/accounts/1")
.accept(MediaType.parseMediaType("application/json;charset=UTF-8")))
.andExpect(status().isOk())
.andExpect(content().contentType("application/json"))
.andExpect(jsonPath("$.name").value("Lee"));
}
}

上面的测试依赖于TestContext框架提供支持的WebApplicationContext来从位于相同的package的xml配置文件中加载Spring的配置,基于Java和Groovy的配置文件也是支持的.看这里

MockMVC实例模拟了一个GET请求了/accounts/1并且验证response的结果状态码是200,content-type是application/json,并且response body有一个JSON属性名name的key值是Lee.jsonPath的语法通过JaywayJsonPath project提供支持.更多其他的关于验证结果和模拟请求的选项在后面的文档中会讨论.

Static Imports

上面例子代码中的API需要几个静态的imports,例如MockMvcRequestBuilders.*,MockMvcResultMatchers.*MockMvcBuilders.*.下面导包操作就省略了.

Setup Choices

你有2种主要的方式来创建MockMVC实例.第一种是通过TestContext框架加载Spring MVC配置文件,这样会加载Spring的配置信息并且通过注入WebApplicationContext到测试中来构建一个MockMVC实例.下面是示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@RunWith(SpringRunner.class)
@WebAppConfiguration
@ContextConfiguration("my-servlet-context.xml")
public class MyWebTests {

@Autowired
private WebApplicationContext wac;

private MockMvc mockMvc;

@Before
public void setup() {
this.mockMvc = MockMvcBuilders.webAppContextSetup(this.wac).build();
}

// ...

}

第二种选择是手动创建一个controller实例而不加载Spring的配置信息.相对的,通过大致比较MVC JavaConfig或者MVC namespace来自动的创建一个默认的配置.你可以在一定程度上自定义.下面是实例代码:

1
2
3
4
5
6
7
8
9
10
11
12
public class MyWebTests {

private MockMvc mockMvc;

@Before
public void setup() {
this.mockMvc = MockMvcBuilders.standaloneSetup(new AccountController()).build();
}

// ...

}

你会选择哪一种方式呢?#反正我是第二种hhh

webAppContextSetup会加载你实际的Spring MVC配置信息,导致一个更完整的集成测试.自从TestContext框架缓存加载Spring配置信息之后会让测试运行的更快,甚至在你引入了更多的测试的时候.此外,你可以通过Spring configuration注入mock service到你的controller以便于专注地在web层进行测试.下面的例子声明了一个mock service使用Mockito:

1
2
3
<bean id="accountService" class="org.mockito.Mockito" factory-method="mock">
<constructor-arg value="org.example.AccountService"/>
</bean>

然后你可以把mock service注入到测试中并且配置成你想要的样子.下面是示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@RunWith(SpringRunner.class)
@WebAppConfiguration
@ContextConfiguration("test-servlet-context.xml")
public class AccountTests {

@Autowired
private WebApplicationContext wac;

private MockMvc mockMvc;

@Autowired
private AccountService accountService;

// ...

}

这种单独的设置,从另一个方面看更接近一个单元测试,每次只测试一个controller.你可以使用mock依赖手动注入controller,并且这不涉及到加载Spring配置信息.这种测试更加关注于”style”并且让看到哪个controller正在被测试变得更容易,是否需要特定的Spring MVC配置文件才能运行,等等.这种单独设置的方式也是一种便利的写ad-hoc测试来验证具体的行为或者debug一个issue的方式.

在集成和单元测试的争论下,没有对的或者错的答案.然而使用单独设置就意味着需要额外的webAppContextSetup测试来验证你的Sring配置文件.或者你也可以用webAppContextSetup来写你的所有的测试,这样可以始终测试你的Spring配置信息.

Setup Features

无论你使用那种方式来构建MockMVC,所有的MockMvcBuilder实现都提供了一些常见并且很实用的特性.例如,你可以为所有的请求声明一个Accept头并且对于所有的response希望返回200的状态码和Content-Type头.下面是示例代码:

1
2
3
4
5
6
7
// static import of MockMvcBuilders.standaloneSetup

MockMvc mockMvc = standaloneSetup(new MusicController())
.defaultRequest(get("/").accept(MediaType.APPLICATION_JSON))
.alwaysExpect(status().isOk())
.alwaysExpect(content().contentType("application/json;charset=UTF-8"))
.build();

此外,第三方框架(和应用)可以预先打包设置声明,比如在MockMvcConfigurer.Spring框架有一个内置的实现可以通过请求来保存和重用HTTP session.你可以像下面一样使用:

1
2
3
4
5
6
7
// static import of SharedHttpSessionConfigurer.sharedHttpSession

MockMvc mockMvc = MockMvcBuilders.standaloneSetup(new TestController())
.apply(sharedHttpSession())
.build();

// Use mockMvc to perform requests...

查看Javadoc for ConfigurableMockMvcBuilder,列出了所有MockMvc内建的特性或者使用ide来查看.

Performing Requests

你可以使用任何的HTTP方法来模拟请求:

1
mockMvc.perform(post("/hotels/{id}", 42).accept(MediaType.APPLICATION_JSON));

你也可以使用MockMultipartHttpServletRequest内的模拟文件上传请求,这样就不会实际的解析一个多部分的请求.

1
mockMvc.perform(multipart("/doc").file("a1", "ABC".getBytes("UTF-8")));

你可以添加一个请求参数使用URI template风格:

1
mockMvc.perform(get("/hotels?thing={thing}", "somewhere"));

你还可以添加Servlet请求参数不管是请求参数还是表单参数.

1
mockMvc.perform(get("/hotels").param("thing", "somewhere"));

如果应用的编码依赖于Servlet请求参数并且没有明确检查请求的字符串,你使用那个选项都没关系.但是请记住,提供的请求参数使用URI template的时候被编码,在请求参数经过param()方法的时候是预计已经被编码的.

在大多数的情况下,最好是把context path和Servlet path放在请求的URI外面.如果你必须要在完整的URI下测试,确定设置了contextPathservletPath,request mapping才能正常工作.

1
mockMvc.perform(get("/app/main/hotels/{id}").contextPath("/app").servletPath("/main"))

在上面的例子里,给每个模拟请求设置contextPathservletPath是很笨重的.你可以设置默认的请求参数来代替:

1
2
3
4
5
6
7
8
9
10
11
public class MyWebTests {

private MockMvc mockMvc;

@Before
public void setup() {
mockMvc = standaloneSetup(new AccountController())
.defaultRequest(get("/")
.contextPath("/app").servletPath("/main")
.accept(MediaType.APPLICATION_JSON)).build();
}

上面的设置会影响所有通过这个MockMvc实例模拟的请求.如果相同的属性也在给定的请求里出现了,会覆盖默认的值.这也就是为什么HTTP方法和URI在默认的请求下没有影响,因为必须在每个请求中指定它们.

Defining Expectations

你可以定义预计的结果通过添加一个或者更多的.andExpect(..)在模拟请求之后:

1
mockMvc.perform(get("/accounts/1")).andExpect(status().isOk());

MockMvcResultMatchers.*提供了大量的expectations,其中一些嵌套了更详细的expectations.

Expectations分为两大类,第一类断言验证响应的属性,这些都是最重要的结果断言.

第二类断言超出了response的范围,这些断言可以让你检查Spring MVC的特定方面,例如哪个controller的方法处理了请求,是否一个异常被抛出和处理,模型的content是什么,哪个view被选择,哪些属性被添加,等等..他们也运行检查Servlet的特定方面,例如请求和会话属性.

下面的测试断言绑定或者验证失败:

1
2
3
mockMvc.perform(post("/persons"))
.andExpect(status().isOk())
.andExpect(model().attributeHasErrors("person"));

很多时候,当你在写测试,打印出模拟请求的结果是很有帮助的,可以使用MockMvcResultHandlers的静态方法print()来做到:

1
2
3
4
mockMvc.perform(post("/persons"))
.andDo(print())
.andExpect(status().isOk())
.andExpect(model().attributeHasErrors("person"));

只要请求过程没有造成一个没有处理的异常,print()方法就会打印出所有可得到的结果数据到System.out.Spring Framework 4.2引入了一个log()方法和两个附加的变种的print()方法,一个接收OutputStream一个接收Writer.例如,请求print(System.err)打印结果到System.err.当请求print(myWriter)的时候会打印数据到规定的地方.如果你想要使用结果数据日志来代替打印,使用log()方法,会把数据使用DEBUG打到org.springframework.test.web.servlet.result配置下.

在某些情况下,你也许想直接访问并且不想验证其他结果可以在后面加.andReturn():

1
2
MvcResult mvcResult = mockMvc.perform(post("/persons")).andExpect(status().isOk()).andReturn();
// ...

如果所有的测试有使用相同的expectations,你可以设置一个公共的expectations构建在MockMvc实例里面:

1
2
3
4
standaloneSetup(new SimpleController())
.alwaysExpect(status().isOk())
.alwaysExpect(content().contentType("application/json;charset=UTF-8"))
.build()

注意公用的expectations总是会被使用并且无法被覆盖.

当JSON响应内容包含使用Spring HATEOAS创建的超媒体链接时.你可以使用JsonPath表达式来验证结果连接:

1
2
mockMvc.perform(get("/people").accept(MediaType.APPLICATION_JSON))
.andExpect(jsonPath("$.links[?(@.rel == 'self')].href").value("http://localhost:8080/people"));

当xml被包含的时候可以使用xpath表达式来验证:

1
2
3
Map<String, String> ns = Collections.singletonMap("ns", "http://www.w3.org/2005/Atom");
mockMvc.perform(get("/handle").accept(MediaType.APPLICATION_XML))
.andExpect(xpath("/person/ns:link[@rel='self']/@href", ns).string("http://localhost:8080/people"));

Filter Registrations

当设置一个MockMvc实例的时候,你可以注册一个或多个Servlet Filter实例:

1
mockMvc = standaloneSetup(new PersonController()).addFilters(new CharacterEncodingFilter()).build();

注册过滤通过spring-testMockFilterChain来调用,并且把最后一个过滤器委托给DispatcherServlet.

Differences Between Out-of-Container and End-to-End Integration Tests

就像之前提到的,Spring MVC Test构建在spring-test的Servlet API mock objects之上并且没有使用运行中的Servlet容器.因此,这和在客户端和服务器运行的完整的端到端的集成测试有一些很重要的区别.

最简单的方式就是从思考一个空白的MockHttpServletRequest开始.在这里面你添加什么,请求就会变成什么样.令你吃惊的也许是这里没有完整的上下文路径在默认情况下,没有jsessionid的cookie,没有转发,错误或是异步调度并且因此,没有实际的JSP转义.与此相对的,转发和重定向URL被保存在MockHttpServletResponse里并且可以使用表达式来断言它.

这也就意味着,如果你使用JSP,你可以验证请求转发到的JSP页面,但是没有HTML被呈现.换句话说,JSP不会被调用.但请注意,所有其他不依赖转发的渲染技术,例如Thymeleaf和Freemarker,会在response body里像期待的那样呈现HTML内容.相同的,JSON,XML和其他一切通过@ResponseBody注解传递的格式都可以.

另外,你也可以考虑通过使用Spring Boot的@WebIntegrationTest来实现完整的端到端的集成测试.查看Spring Boot Reference Guide.

每种方法都有利弊.Spring MVC Test提供的选项和传统的单元测试的完整集成测试所停留的面是不一样的.可以肯定的是,Spring MVC中没有任何属于传统单元测试的选项,但是有一点接近它.例如,你可以通过把mock service注入到controller中的方式来隔离web层,在这种情况下你测试web层只需要通过DispatcherServlet但是实际上你是使用了Spring配置信息的,就像你可以隔离掉数据访问层之上的层面来测试数据访问层一样.当然,你也可以使用单独的配置,每次只关注一个controller并且手动提供使其运行所必须的配置文件.

使用Spring MVC的另一个重大的区别是,从概念上讲,这些测试是服务端的,所以你可以检查哪个Handler被使用了,如果一个异常被HandlerExceptionResolver处理了,这时候模型的内容是什么,绑定的是什么错误和其他的信息(可以很轻松的获取).这也就意味着写expectations会变得简单,因为server这时候就不是一个黑盒了,就像是通过实际的HTTP客户端去测试一样.传统的单元测试的优势是:易于编写,推理和调试但是不能完全取代完整的集成测试.同时,重要的是不要忽略了最重要的是要去检查response这件事.简而言之,即使在一个项目中,也存在多种的测试的风格和策略(条条大路通罗马).

Further Server-Side Test Examples

这个框架自己的测试包含了很多测试的例子为了展示如何使用Spring MVC Test.你可以打开这些例子来寻找更多的灵感.同时,spring-mvc-showcase项目覆盖了完整的基于Spring MVC Test的测试.

在度过了今年的最爽假期也是最后假期之后的星期六,又看到了qsc更新视频的我是很欣喜的,但是看完之后的我是懵逼的:怎么难度一下从天堂到了地狱~~,当然了,最后卿学姐也说了,这是一个导论性质的介绍,那么就让我再总结一下吧.

先放上视频的地址:机器学习算法讲堂(4):Explore and exploit算法 LinUcb《Bandits in Recommendation》

从老虎机开始

让我们来想象这样一个情景:

一个赌徒,要去摇老虎机,走进赌场一看,一排老虎机,外表一模一样,但是每个老虎机吐钱的概率可不一样,他不知道每个老虎机吐钱的概率分布是什么,那么每次该选择哪个老虎机可以做到最大化收益呢?

这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB),也就是我们需要在有限的回合内找出一个系统的最大收益,而之所以用MAB问题来举例的原因也是因为,这个问题的抽象可以套在很多推荐系统的问题之上,例如:

  • 假设一个用户对不同类别的内容感兴趣程度不同,那么我们的推荐系统初次见到这个用户时,怎么快速地知道他对每类内容的感兴趣程度?
  • 假设我们有若干广告库存,怎么知道该给每个用户展示哪个广告,从而获得最大的点击收益?是每次都挑效果最好那个么?那么新广告如何才有出头之日?
  • ….

可以发现,这些问题都跟老虎机是一样的:我们需要在有限的回合内找到老虎机的最大收益==>我们需要在有限次数内找到推荐广告的最大收益

而在推荐系统领域对于这类问题有一个统一的说法,叫做Explore-Exploit问题,也就是如何来最大化探索和利用的价值的问题,比如:

  • Explore(探索):我们需要探索用户的兴趣点而且需要不断地探索新的兴趣来保证用户对系统的新鲜度,这是一个长期的,挖掘潜在价值的,成长型的需求
  • Exploit(利用):当我们探索出最大价值的时候我们需要利用,这是一个贪婪的,短期的,需要奖励来反馈激励的需求

就像是在玩老虎机:我们发现一个老虎机吐钱很多,那肯定需要用它来赚钱啊,但是我们也不能保证它就是最赚钱的,我们也得去探索其他的老虎机的赚钱能力,而如何来协调探索和利用的关系来使得我们的系统产生出最大的价值,也就是需要研究的地方了.

Bandits in Recommendation

知识准备-累积遗憾

当然这一点在qsc的视频中没有着重讲,但是在看其他博客的时候还是觉得需要补充一下.

累积遗憾也就是Bandits算法中用来量化一个策略好坏的指标,用公式写出来是这样的:
$$
R_A(T) = E\left[\sum_{t=1}^Tr_t,a_t^*\right]-E\left[\sum_{t=1}^Tr_t,a_t\right]
$$

这里t表示轮数,r表示回报.公式右边的第一项表示第t轮的期望最大收益,而右边的第二项表示当前选择的arm获取的收益,把每次差距累加起来就是总的遗憾.显然的,累积遗憾越小,算法的效果也就越好.

$\epsilon$-greedy algorithm(贪心策略)

我们来看一种最简单的贪心的策略,方法如下:
在每一步:

  • 使用一个我们选择的概率$\epsilon$,随机的选择一个手臂去摇老虎机(探索)
  • 其他的(1-$\epsilon$)概率下,我们选择当前最赚钱的老虎机摇一下(利用)

然后我们观察最后的回报来调整概率达到最优解,然而这个算法的问题在于:我们的选择是随机的,但是实际上,我们在摇了很多下老虎机之后是知道哪些比较赚钱那些不怎么赚钱,而这个信息没有被利用起来.我们的改进思路也就变成了从随机选择去寻找更加聪明的选择方法.

Thompson sampling

Beta Distribution(Beta分布)

关于beta分布几乎是没有了解的,但是在这只需要知道它是一种概率分布就可以了,这里先给出分布的公式:
$$
f(x;\alpha,\beta) = constant \cdot x^{\alpha-1}(1-x)^{\beta-1}=\frac {1} {B(\alpha,\beta)} x^{\alpha-1}(1-x)^{\beta-1}
$$

这里我们需要关注的是beta分布的方差的计算(实验的次数越少方差就越大):
$$
var(X)=E[(X-\mu)^2]=\frac {\alpha\beta} {(\alpha+\beta)^2(\alpha+\beta+1)}
$$

算法解释

而这个方差的特征正是我们所希望的,比如我们摇了一个老虎机10000次,它赚的钱是500块而另一个老虎机我们只摇了100次赚的钱是5块,如果我们在这两个老虎机之间做抉择的话,肯定会选择后一个,因为它的上限比前者高,因为前者我们几乎以及可以肯定它就是10000次赚500,而后者可能比它更赚钱,虽然现在来看它们的平均收益是一样的.下面是ppt中对beta分布的可视化:

item-b和item-c就是上面的摇了10000次的老虎机和摇了100次的老虎机.
而Thompson sampling算法的思路就和上面的想法一样,假设每个老虎机的吐钱概率符合beta分布,跟随机选择手臂的贪心算法比起来,优化的地方就在于:用每个手臂的beta分布生成一个随机数,选择这些随机数中最大的那个手臂摇一下.下面给出贪心算法和Thompson sampling算法伪代码的比较:

UCB:Upper Confidence Bound(置信区间上界)

在之前我们也提到了,贪心算法的缺点就在于没有利用前面已经摇了的老虎机的信息,上面的Thompson sampling算法给出了一种利用的思路,而UCB(置信区间上界)则是另一种利用的方式.
大致的思路是:我们假设每一个老虎机的吐钱概率
$$
Q(a)\leq \hat{Q_t}(a)+\hat{U_t}(a)
$$
这里的$\hat{Q_t}(a)$就是每个老虎的收益的均值,而$\hat{U_t}(a)$可以认为是这个老虎机的赚钱潜力,而这个潜力也能够使得很少被摇到的但是很赚钱的老虎机被发掘出来.那么现在的问题就是要对$\hat{U_t}(a)$来确定一个上界,也就是它的极限赚钱能力是多少,而这个上界在1963年被Hoeffding找到了并且命名为Hoeffding Inequality,其中的上界的解是:
$$
\hat{U_t}(a) = \sqrt{\frac {-\log p} {2N_t(a)}}
$$
其中的p是我们假设的概率,$N_t(a)$则是实验的次数

Bayesian UCB

虽然我们已经可以通过上面的公式来计算每个老虎机的置信区间上界从而选择摇那个老虎机,但是缺陷是这个上界太大了,也就是说实际的效果并不会很好,而其中的一个解决方案就是假设$Q(a)$服从贝叶斯分布,这样我们就可以直接根据公式来算出上界,至于效果的话,直接引用paper中的一个比较,可以看到优化的效果是比较好的.

这是上面提到的几种算法的效果的比较图:

LinUCB–UCB算法的一次进化

算法的优化还在继续,上面的UCB算法的最大问题在于它是context-free(上下文无关)的,这怎么行呢(滑稽),所以我们的算法优化的下一步就是给UCB算法插上特征的翅膀.也就是我们给每一个手臂都加上一个上下文的特征,当然这里再举老虎机似乎不是很贴切了,可以把手臂变成替用户挑选商品的手臂.那么与此对应的,我们给每个手臂能够获得的期望收益一个定义:
$$
E[r_{t,a}|x_{t,a}] = x_{t,a}^\top \bf {\theta}_{a\cdot}^*
$$
假设手机到了m次反馈,特征向量可以写作Da(维度为md),假设我们收到的反馈为Ca(维度为m1),那么通过求解下面的loss,我们可以得到当前每个手臂的参数的最优解:
$$
loss = (C_a-D_a\theta_a)^2+\lambda\begin{Vmatrix} \theta_a \end{Vmatrix}
$$
然后我们可以使用ridge-regression(岭回归)得到explicit solution(闭式解):
$$
\theta_a = (D_a^TD_a+I)^-1D_a^Tc_a
$$
而根据UCB方法,我们除了需要一个均值之外,还需要找到一个置信上界,而这个置信上界也被人找出来了.反正最后我们需要训练的函数就可以确定下来,就是下面这一坨了(实在不行了,mathjax真难写):

给出LinUCB算法的伪代码:

优点

  • 是上下文相关的
  • 上下文特征的回报函数是线性的
  • 是一个岭回归==>是有解析解的
  • 服从高斯分布==>有UCB上界
  • 是一个在线的算法(个人认为是:有新的数据进来不需要重新训练模型)

优化方向

下面就是一些比较简短的优化的方向了

  • CoLin:协同过滤,引入了用户之间的关系(这个还是挺重要的特征)
  • hLinUCB:加入了hidden-feature(隐向量)
  • FactorUCB=hLinUCB+CoLin

最后的最后,放上一个Bandit算法的进化路径的图吧:

可以看到进化的方向就是从随机选择到更加聪明的选择,从上下文无关到上下文相关,也是越来越能够贴近推荐系统的核心需求了.

参考博客

专治选择困难症——bandit算法
UCB算法升职记——LinUCB算法
推荐系统遇上深度学习(十三)–linUCB方法浅析及实现
推荐系统遇上深度学习(十二)–推荐系统中的EE问题及基本Bandit算法

论文引用

LinUCB
CoLinUCB
CLUB
hLinUCB
FactorUCB

总结

因为是一个导论性质的小讲堂所有内容还是有点多的,消化起来也有点慢也有点吃力,但是还是很开拓眼界的.

吾尝终日而思矣,不如须臾之所学也

0%