<p>A PhD thesis should have references to the published literature and should be extending results in that literature.  So it is important to be able to say, these serious researchers did something but we do something they either were not able to do, or at least did not think of doing or did not have time to do, but would want to do. </p>

CC BY-SA 3.0
2014-04-20T22:23:39.163Z
Yes, of course. Right now, my ability to scour what has already been done in this direction is limited (Google doesn't really point to anything, or maybe I'm using it wrong and I don't have access to any journals). I would probably have references to neural networks and machine learning papers, exactly which I don't know yet. I am asking if 1. Someone has already done exactly this and there's nothing for me to do anymore and 2. If this is ambitious enough - a PhD should contribute something significant in some way, it can't be something trivial - this **feels** significant to me, but is it?
IVlad
CC BY-SA 3.0
2014-04-21T04:08:58.143Z
I think the significance depends on what your results are. What are you hoping to be able to conclude about this problem?
Thomas Steinke
CC BY-SA 3.0
2014-04-21T16:06:05.977Z
@Thomas - that there is a provably good (either mathematically or empirically - in the case that I build such a system, get people to use it and usage stats will prove it) way to implement such a system using the techniques and specs I mentioned.
IVlad
CC BY-SA 3.0
2014-05-23T13:58:53.573Z
Just building a system is arguably not a significant research contribution, and it is certainly not a _theoretical computer science_ research contribution.
Jeffε
CC BY-SA 3.0
2014-04-20T22:13:24.973Z
2014-04-20T22:13:24.973Z
Bjørn Kjos-Hanssen
<p>I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence. </p>

<p>I have an idea I've been tinkering with for a while, but some people have told me that it is not ambitious enough for Ph.D.-level research. I'm not sure if this is because the TCS community already knows all there is to know about it or because I have failed to express myself adequately (bad sales pitch). Based on what I could find online, not all that much has been done. </p>

<p>So, I am going to describe what I thought about doing and I would like to ask if you think this is a promising start idea and if it has the potential to lead to something graduate-level worthy.</p>

<p>I want to research efficient and reliable ways to implement a distributed system that can identify entities based on data collected from its users. To give a concrete example of this, I am going to use the <a href="http://en.wikipedia.org/wiki/Twenty_Questions" rel="nofollow">20 questions game</a>.</p>

<p>Existing implementations of this can be found at <a href="http://www.20q.net/" rel="nofollow">http://www.20q.net/</a> and <a href="http://www.akinator.com/" rel="nofollow">http://www.akinator.com/</a> however these are closed: no official details whatsoever on how they do it exist anywhere that I can find (<strong>subquestion</strong>: in general, if someone does something but does not publish how it's done, how worthy is (much) later research that explains how it can be done?). </p>

<p>There are also no details on the required processing power (performance can easily be seen to be very good, although also hard to quantify exactly - is this because they're smart about whatever it is they do or because they run the site on supercomputers?) and the reliability (how often they guess right, under what circumstances etc.) of these systems. </p>

<p>Of course, one can say "use neural networks", "use bayesian classifiers", "use KNN", "use this special form of decision trees: ____", but how well will these work (is it that obvious that they even will?), how exactly they need to be implemented to work efficiently and reliably, how they can be implemented in a distributed manner that is accesible and cheap (for example, if they could be implemented efficiently using widely-used relational databases such as MySQL, that would be great), how they can be tailored to learn from user inputs and probably other factors seem to be up for research.</p>

<p>The problem is more complicated than it seems I feel, because players can also lie, and you'll notice akinator will guess right in many of those cases as well - so it's not so easy as using a decision tree. As for the other approaches, many questions arise as well, such as scalability, reliability and exact mechanics that are provably best (or at least better than most others) for this specific problem.</p>

<p>At first, based on what I read online, the problem did not seem too complicated, but when I thought and learned more about what people were suggesting, I quickly started to find various flaws. Then I started to write code and noticed even more potential shortcomings, so now I feel that the problem has a lot more that can be learned from it than trivial implementations of various existing concepts.</p>

<p>Does this have any potential or should I start looking someplace else entirely?</p>

CC BY-SA 3.0
2014-04-21T02:48:19.087Z
There is a lot of interesting work in the theory community on search in the presence of errors. See for example this paper and the references in it: http://www.cs.bu.edu/~gacs/papers/liars.pdf.
Sasho Nikolov
CC BY-SA 3.0
2014-04-21T02:51:16.003Z
BTW do not take my comment above as an answer to your question in either direction.
Sasho Nikolov
CC BY-SA 3.0
2014-04-21T03:18:13.963Z
I think it would be good to extract the main points of the question and express it more generally so it can be useful for others also.
Kaveh
CC BY-SA 3.0
2014-04-21T03:42:49.207Z
I suspect the difficulty with building these 20q websites is getting enough data (i.e. descriptions of millions of things). The actual learning and computing is probably not that difficult once you have that.
Thomas Steinke
CC BY-SA 3.0
2014-04-21T03:59:06.793Z
This is the usual reason a Ph.D student has an advisor: to answer questions precisely of this form.
Suresh Venkat
CC BY-SA 3.0
2014-04-21T15:03:43.650Z
see also [20q](http://cs.stackexchange.com/questions/22872/) on cs.se. to build a reliable system seems too hard for Phd work but there are many related areas at Phd level research. related stuff with phd research: douglas lenat [Cyc project](http://en.wikipedia.org/wiki/Cyc), IBM [watson/jeopardy](http://en.wikipedia.org/wiki/Watson_(computer)) system, [expert systems](http://en.wikipedia.org/wiki/Expert_systems), [collective intelligence](http://en.wikipedia.org/wiki/Collective_intelligence)
vzn
CC BY-SA 3.0
2014-04-21T16:04:02.497Z
@SureshVenkat - one potential adviser told me this is not ambitious enough, but I also might not have provided enough details and didn't get a chance to provide more, so I thought I'd ask here.
IVlad
CC BY-SA 3.0
2014-04-22T20:37:57.307Z
Isn't the 20 questions game basically a fact database and a binary search? So you have objects and every object has attributes. You want to identify the object the questioner is talking about, so you ask the question that divides your dataset best. Interesting is: 1) how to get missing attribute values for single objects 2) how to get new attributes you could ask for 3)  synonym detection 4) error detection / correction
Martin Thoma
CC BY-SA 3.0
2014-04-22T21:30:16.450Z
@moose - I'm not sure what you mean exactly, but it's definitely a lot more complicated than a binary search if you want something that functions well with lies. "A fact database" is also an oversimplification - the implementation details of such a database are not exactly immediately obvious in my opinion.
IVlad
<soft-question><advice-request><research-practice>
Are aspects of the 20 questions game ambitious enough for graduate research?
IVlad
# Are aspects of the 20 questions game ambitious enough for graduate research?

(Asked by: username_0 on 2014-04-20)

I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence.

I have an idea I've been tinkering with for a while, but some people have told me that it is not ambitious enough for Ph.D.-level research. I'm not sure if this is because the TCS community already knows all there is to know about it or because I have failed to express myself adequately (bad sales pitch). Based on what I could find online, not all that much has been done.

So, I am going to describe what I thought about doing and I would like to ask if you think this is a promising start idea and if it has the potential to lead to something graduate-level worthy.

I want to research efficient and reliable ways to implement a distributed system that can identify entities based on data collected from its users. To give a concrete example of this, I am going to use the [20 questions game](http://en.wikipedia.org/wiki/Twenty_Questions).

Existing implementations of this can be found at <http://www.20q.net/> and <http://www.akinator.com/> however these are closed: no official details whatsoever on how they do it exist anywhere that I can find (**subquestion**: in general, if someone does something but does not publish how it's done, how worthy is (much) later research that explains how it can be done?).

There are also no details on the required processing power (performance can easily be seen to be very good, although also hard to quantify exactly - is this because they're smart about whatever it is they do or because they run the site on supercomputers?) and the reliability (how often they guess right, under what circumstances etc.) of these systems.

Of course, one can say "use neural networks", "use bayesian classifiers", "use KNN", "use this special form of decision trees: \_\_\_\_", but how well will these work (is it that obvious that they even will?), how exactly they need to be implemented to work efficiently and reliably, how they can be implemented in a distributed manner that is accesible and cheap (for example, if they could be implemented efficiently using widely-used relational databases such as MySQL, that would be great), how they can be tailored to learn from user inputs and probably other factors seem to be up for research.

The problem is more complicated than it seems I feel, because players can also lie, and you'll notice akinator will guess right in many of those cases as well - so it's not so easy as using a decision tree. As for the other approaches, many questions arise as well, such as scalability, reliability and exact mechanics that are provably best (or at least better than most others) for this specific problem.

At first, based on what I read online, the problem did not seem too complicated, but when I thought and learned more about what people were suggesting, I quickly started to find various flaws. Then I started to write code and noticed even more potential shortcomings, so now I feel that the problem has a lot more that can be learned from it than trivial implementations of various existing concepts.

Does this have any potential or should I start looking someplace else entirely?

**Tags:** soft-question, advice-request, research-practice

> **Comments:**
> **username_1**: There is a lot of interesting work in the theory community on search in the presence of errors. See for example this paper and the references in it: http://www.cs.bu.edu/~gacs/papers/liars.pdf.  
> **username_1**: BTW do not take my comment above as an answer to your question in either direction.  
> **username_2**: I think it would be good to extract the main points of the question and express it more generally so it can be useful for others also.  
> **username_3**: I suspect the difficulty with building these 20q websites is getting enough data (i.e. descriptions of millions of things). The actual learning and computing is probably not that difficult once you have that.  
> **username_4**: This is the usual reason a Ph.D student has an advisor: to answer questions precisely of this form.  
> **username_5**: see also [20q](http://cs.stackexchange.com/questions/22872/) on cs.se. to build a reliable system seems too hard for Phd work but there are many related areas at Phd level research. related stuff with phd research: douglas lenat [Cyc project](http://en.wikipedia.org/wiki/Cyc), IBM [watson/jeopardy](http://en.wikipedia.org/wiki/Watson_(computer)) system, [expert systems](http://en.wikipedia.org/wiki/Expert_systems), [collective intelligence](http://en.wikipedia.org/wiki/Collective_intelligence)  
> **username_0**: @SureshVenkat - one potential adviser told me this is not ambitious enough, but I also might not have provided enough details and didn't get a chance to provide more, so I thought I'd ask here.  
> **username_6**: Isn't the 20 questions game basically a fact database and a binary search? So you have objects and every object has attributes. You want to identify the object the questioner is talking about, so you ask the question that divides your dataset best. Interesting is: 1) how to get missing attribute values for single objects 2) how to get new attributes you could ask for 3)  synonym detection 4) error detection / correction  
> **username_0**: @moose - I'm not sure what you mean exactly, but it's definitely a lot more complicated than a binary search if you want something that functions well with lies. "A fact database" is also an oversimplification - the implementation details of such a database are not exactly immediately obvious in my opinion.  

---

## 1 answers

### Answer by username_7 on 2014-04-20. Score: 1

A PhD thesis should have references to the published literature and should be extending results in that literature. So it is important to be able to say, these serious researchers did something but we do something they either were not able to do, or at least did not think of doing or did not have time to do, but would want to do.

> **Comments:**
> **username_0**: Yes, of course. Right now, my ability to scour what has already been done in this direction is limited (Google doesn't really point to anything, or maybe I'm using it wrong and I don't have access to any journals). I would probably have references to neural networks and machine learning papers, exactly which I don't know yet. I am asking if 1. Someone has already done exactly this and there's nothing for me to do anymore and 2. If this is ambitious enough - a PhD should contribute something significant in some way, it can't be something trivial - this **feels** significant to me, but is it?  
> **username_3**: I think the significance depends on what your results are. What are you hoping to be able to conclude about this problem?  
> **username_0**: @Thomas - that there is a provably good (either mathematically or empirically - in the case that I build such a system, get people to use it and usage stats will prove it) way to implement such a system using the techniques and specs I mentioned.  
> **username_8**: Just building a system is arguably not a significant research contribution, and it is certainly not a _theoretical computer science_ research contribution.  

---

