Weekly summary 2016-10-22

Threads

• PMI - get some results!
• SoS - chapters 2 and 3
• DL: do experiments suggested in DL generalization (Mon, Tue)
  • (*) NN learns DL. (Mon, Tue) - Wrote up progress so far, where I am stuck.
• Papers
  • [HM16] on unsupervised learning (went through 1st half, Tue)
  • [HMR16] on dynamical system learning (read blog post Tue)
• Come up with a class of MDPs on exponential space that is interesting and tractable. Thoughts
  • Understand provable guarantees on MDP’s first
• Alexa references

Analyze Arora and Ge’s NMF algorithm in the presence of noise. Exactly how much noise can it tolerate?

Other papers

• TODO Read this paper: [CFP16] Assessing significance in a Markov chain without mixing

Talk with Arora 10/19 (Wed)

Dynamical systems + MDP!

Wonderings

• Can we generalize the random walk of the context vectors? There’s no reason to think that context vectors just drift on the sphere. (p. 139)
  • Make it a RBM. Say with bounded degree. (There are ways to learn - see the factored MDP paper. We don’t care about MDP here, so it’s easier.)
  • For example, one node (dimension) could simply control output of common words.
  • Given the observations, whose probs are \(\propto e^{w^TAc}\), learn the RBM. (Note we can replace \(w\) by \(A^Tw\)… but if \(c\) is in larger space, then it’s not obvious how to learn the \(A\)! Can we modify the word embeddings to deal with this? Beware of difficulties… HMMs usually assume full column-rank observations, violated here. Look at the proper hard instance for HMM. - the version I saw with noisy parity wasn’t quite a HMM)
  • Prereq: given \((x,h)\) how to learn RBM or Bayes net? (When \(W\)’s entries are small enough, can do via MCMC estimation of partition function and optimization of log-likelihood. Otherwise, is hard worst-case.)
    • I’m confused! There seems to be a line of work on factorial MDP’s. However, where are the basic results about learnability of Bayes nets? Learning the model for FMDP’s is strictly harder—why so much work on this (with too much assumptions, or weak results) without results on learning Bayes nets?
    • Bresler.
  • cf. work on continuous HMM’s. Work on factored HMMs? Any bounds when hidden state has larger dimension? Also, adapt HMM learning to vector observations. (Is the natural generalization a factored prob model rather than a dynamical system? Note probabilistic linear dynamical system IS straightforward generalization of HMM, but the factored prob model is not. Weird generalization though, because only having states \(\{e_1,\ldots, e_n\}\) seems decoupled - can couple together any way you want.) @Andrej on this.
    • When state has larger dimension, need overcomplete tensor factorization.
  • Start with: given an HMM with both transitions and observations being RBMs (say of degree at most 2), observations don’t “lose info” (analogue of full column rank), infer RBM. (Z is over words that exist). Breaks symmetries - the various dimensions are important now?
• Dictionary learning experiment
  • The kernel DL I want is different from in the literature. There they want \(\Phi(Y) \approx \Phi(A)X\), here we want \(\Phi(Y) \approx \Phi(AX)\). I.e. we want to maximize \(K(Y,AX)\) where \(X\) is restricted to be sparse. Usual algorithms break down here, but can still consider \(K(Y,AX) + \ve{X}_1\). (137)
  • Use kernel in PMDH16.
• RL questions (135)
  • Given a (continuous) space of policies, converge to a local min in the space of policies.
  • Find some measure of complexity of a class of policies. Branching is important. (Getting limited info from other policies…) Get a bound independent of number of states, involving this complexity.
    • Example to keep in mind: \(2^n\) strategies all branching off into different rewards at end of their paths.
    • Alternatively, complexity of class of models of environment.
  • What is the VC dimension bound for contextual (expert) bandits? Also look at the contextual MDP paper, cf. EXP4.
  • [ALA16] open question
  • Scraps
    • Right \(\la\), how do well without learning model?
    • SoS, minimax, etc.
    • EXP3:Scrible:EXP4::UCB1:?:? (LinUCB? RUCB?)
  • Increasing \(\ga\) towards 1 (simulated annealing, temperature schedule…)