In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Q: In this paper, we present algorithms that perform gradient ascent of the average reward in a partially observable Markov decision process (POMDP). These algorithms are based on GPOMDP, an algorithm introduced in a companion paper (Baxter & Bartlett, 2001), which computes biased estimates of the performance gradient in POMDPs. The algorithm’s chief advantages are that it uses only one free parameter 2 [0; 1), which has a natural interpretation in terms of bias-variance trade-off, it requires no knowledge of the underlying state, and it can be applied to infinite state, control and observation spaces. We show how the gradient estimates produced by GPOMDP can be used to perform gradient ascent, both with a traditional stochastic-gradient algorithm, and with an algorithm based on conjugate-gradients that utilizes gradient information to bracket maxima in line searches. Experimental results are presented illustrating both the theoretical results of Baxter and Bartlett (2001) on a toy problem, and practical aspects of the algorithms on a number of more realistic problems.

A: Experiments with Infinite-Horizon, Policy-Gradient Estimation
****
Q: Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for the sign function. Firstly, the “polynomial regression” algorithm of Kalai et al. (SIAM J. Comput. 2008) shows that halfspaces can be learned with respect to log-concave distributions on Rn in the challenging agnostic learning model. The power of this algorithm relies on the fact that under log-concave distributions, halfspaces can be approximated arbitrarily well by low-degree polynomials. We ask whether this technique can be extended beyond log-concave distributions, and establish a negative result. We show that polynomials of any degree cannot approximate the sign function to within arbitrarily low error for a large class of non-log-concave distributions on the real line, including those with densities proportional to exp(−|x|0.99). This impossibility result extends to multivariate distributions, and thus gives a strong limitation on the power of the polynomial regression algorithm for halfspaces. Secondly, we investigate the derandomization of Chernoff-type concentration inequalities. Chernoff-type tail bounds on sums of independent random variables have pervasive applications in theoretical computer science. Schmidt et al. (SIAM J. Discrete Math. 1995) showed that these inequalities can be established for sums of random variables with only O(log(1/δ))-wise independence, for a tail probability of δ. We show that their results are tight up to constant factors. These results rely on techniques from weighted approximation theory, which studies how well functions on the real line can be approximated by polynomials under various distributions. We believe that these techniques will have further applications in other areas of theoretical computer science. Harvard University, School of Engineering and Applied Sciences. Supported by an NDSEG Fellowship and NSF grant CNS-1237235. Harvard University, School of Engineering and Applied Sciences. Supported by NSF grant CCF-1116616 and the Lord Rutherford Memorial Research Fellowship.

A: Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
****
Q: The human perceptual system can make complex inferences on faces, ranging from the objective evaluations regarding gender, ethnicity, expression, age, identity, etc. to subjective judgments on facial attractiveness, trustworthiness, sociability, friendliness, etc. Whereas the objective aspects have been extensively studied, less attention has been paid to modeling the subjective perception of faces. Here, we adapt 6 state-of-the-art neural networks pretrained on various image tasks (object classification, face identification, face localization) to predict human ratings on 40 social judgments of faces in the 10k US Adult Face Database. Supervised ridge regression on PCA of the conv5 2 layer in VGG-16 network gives best predictions on the average human ratings. Human group agreement was evaluated by repeatedly randomly splitting the raters into two halves for each face, and calculating the Pearson correlation between the two sets of averaged ratings. Due to this methodology, the models correlations with the average human ratings can exceed this score. We find that 1) model performance grows as the consensus on a face trait increases, and 2) model correlations are always higher than human correlations with each other. These results illustrate the learnability of the subjective perception of faces, especially when there is consensus, and the striking versatility and transferability of representations learned for object recognition. This work has strong applications to social robotics, allowing robots to infer human judgments of each other.

A:
Learning to see people like people
****