| Name: | Amanda Wang |
|---|---|
| Email: | aw4309@princeton.edu |
| Home Institution: | Princeton University |
| Project: | Truth Learning in a Social and Adversarial Setting |
| Mentor: | Professor Jie Gao |
| Collaborators: | Julia Krizanova, Rhett Olson, Filip Uradnik |
I did some background reading to refresh my memory on sequential social learning models, information cascades, and voting rules. I worked on a presentation that would introduce my project to the rest of the REU participants next week.
I read some more recent papers on several possible directions to explore for the summer. I mostly focused on a paper proving NP-hardness for computing full Bayesian updates to agent beliefs in a slightly relaxed setting. This paper actually proved a stronger claim (PSPACE-hardness) and used a reduction from 3-SAT which was a little convoluted. Filip found an earlier paper by the same authors proving NP-hardness for the same problem using a reduction from VERTEX-COVER, which was much neater. We hope to use a similar reduction to show NP-hardness for determining if a given network permits truth learning under some (equivalently, a best-case) decision ordering.
This week I worked on constructing a reduction to show NP-hardness. Early in the week, Rhett suggested a revised version of the statement for the decision problem, which omitted the use of a family of graphs for the asymptotic part the definition. This proved to be the right claim to formulate the reduction with, and later in the week, Filip proposed a reduction from 3-SAT. His reduction gave a construction for a digraph that encoded variable assignments. Each clause was then represented by a single clause node, which were connected to literal nodes in such a way so that clauses that weren't satisfied had a lower probability of predicting the ground truth, which would hopefully correspond to a lower network learning rate if the formula wasn't satisfiable.
Filip and I then did a morning of algebra. This turned out to not work, because the best-case non-satisfiable formula did not necessarily have a lower learning rate than the worst-case satisfiable formula, especially as the number of clauses increased.
I then spent a day thinking about reductions to other NP-hard problems, like MAX-INDEPENDENTSET or VERTEX-COVER. But I felt that neither of these problems were actually easier to work with. As far as I know, evaluating the learning rate under the best ordering can't just be boiled down to finding some characterizing property of the network (like size of the largest independent set/clique), and the structure of the VERTEX-COVER reduction in the last paper didn't seem varied enough to give separable learning rates.
Toward the end of the week, I thought about adjusting Filip's reduction to separate the satisfiable and non-satisfiable learning rates. After a little trial and error, I fairly quickly came up with an idea. It wasn't clear if it worked and the probabilities at this point were pretty unmanageable, so I went ahead and had Mathematica grind it out for me. Based on the plots produced, this seemed like it would work for formulas with arbitrarily large number of clauses, although there were still some loose ends to tie up - but overall, I was pretty optimistic that the adjustments I needed to make wouldn't affect the final result too much, and we'd have a working reduction fairly soon!
I produced a preliminary informal writeup to try to more clearly communicate the reduction with some loose ends resolved. Then, Filip and I began working on writing it up more formally. This took us the whole week, partly due to the construction being sort of difficult to clearly express and the probabilities being incredibly messy. We tried to make things cleaner by using bounds when possible and also fixed some errors I made when initially computing the probabilities.
Meanwhile, I thought a little bit about proving that Bayesian aggregation always does at least as well as majority dynamics for achieving truth learning, but it seemed difficult to approach without some kind of stronger technique than just basic induction. It felt like something sort of coupling-ey could be useful, but I didn't really have any ideas, especially given whatever I did would have to apply to any graph.
At the start of this week, I completed the writeup for the reduction and Filip and I "finalized" (tentatively) it together. During our Monday meeting, Prof. Gao brought up another paper she'd found about learning from crowds in which the private signals of participants are biased against the ground truth, rather than towards it (as we'd previously been considering). This setting is actually fairly reasonable, since we may still want to learn from crowds in scenarios where misconceptions are widespread. We discussed adapting this setting for network learning.
I continued thinking a bit about coupling and Bayesian vs. majority dynamics. I found some literature on using coupling to analyze interacting particle systems, which felt somewhat similar to our setting, albeit much more structured and with simpler update strategies. At this point, I'm not sure a coupling argument would be feasible, since our update strategies are pretty complex and only probabilistic through the current agent's private signal. So even modelling our network learning as a Markov process would seem somewhat not straightforward.
After some feedback from Prof. Gao, Filip and I worked on removing the directed/double edges from our reduction. I thought pretty extensively about getting rid of double edges, but I really don't see a way to do it without making the optimal ordering intractable. Filip figured out a way to remove double edges, though, which was pretty nice. It took a while to check, but it seemed to work.
Filip and I worked on writing up the updated reduction.
Kevin came up with some progress on the Bayesian vs. majority vote problem in the special case where at every timestep under the optimal ordering, the neighbors of the current node were independent. This was still pretty cool and I thought for a while about extending it to the general cases where neighbors were not necessarily independent. I didn't get anywhere, but I still think there should be something that we can do with this.
I checked that our original reduction worked (as I had hoped/expected) for the Bayesian setting. Our group also prepared and gave our final presentation.
I participated in the Midsummer Combinatorial Workshop in Prague, and worked on writing up the reduction for the Bayesian setting. We turned in our final reports and wrapped up the program.