# Tag Info

55

I do not want to sound condescending, but the math you are studying at the undergraduate and even graduate level courses is not advanced. It is the basics. The title of your question should be: Is "basic" math needed/useful in AI research? So, gobble up as much as you can, I have never met a computer scientist who complained about knowing too much math, ...

14

I think you are asking about two different things. The ability of a programming language to represent all its programs as data. Reasoning about programs as data. For analytical purposes it's useful to keep them apart. I will focus on the former. The ability of a programming languages to represent, manipulate (and run) its programs as data goes ...

12

Levin's universal algorithm is an algorithm such that $t(U,A) < s_V t(V,A) + t_V$. By modifying the algorithm (see for example Hutter's The Fastest and Shortest Algorithm for All Well-Defined Problems), you can make $s_V$ a universal constant, though definitely not $1$ as you require. For related work, consult work by Hirsch, Itsykson and their students, ...

9

See Tic-Tac-Toe by Randall Munroe.

6

Max, here is a (necessarily) partial list : Basic linear algebra and probability are needed all over the place. I suppose you don't need references for that. To my knowledge, Fourier analysis has been used in some learning-theory related investigation. Check out this paper, for instance. The concept of manifold learning is getting popular, and you can ...

6

No there is no current system that does all four steps in your system. If you want to design a system one of the first requirements is homoiconic language. At minimum you would want your core programming language that you have as small as possible so that when you enter the system and start to make it interpret itself it will work. So therefore you want a ...

5

I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E. But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive. And I am afraid that you will probably ...

5

There is no efficient universal problem solver. Intuitively, U should have the (almost) optimal runtime for any decidable decision problem; while the speedup theorem says that there are decidable decision problems that have no optimal algorithm (not even in a very mild sense). To formalize this: The time speed-up theorem (see for example [1])): For every ...

5

As @user217281728's answer mentions there are a type of machines related more to inference and AI, called Gödel Machines A Gödel machine is a self-improving computer program invented by Jürgen Schmidhuber that solves problems in an optimal way. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new ...

4

Antenna design has already been mentioned, and it is an extremely rich domain. (It is, very directly, what started my motion from electrical engineering to computer science (in the late 90's) and more specifically to bio-inspired computation and artificial intelligence (in the last five years or so.)) In the same vein, I'll add antenna array optimization, ...

3

What do you mean by "should have"? In principle you could train a neural network (a multi-layer perceptron, I assume) to perfectly classify the training set (provided that it doesn't contain conflicting examples), however doing so might require a long time (exponential in the size of the training set) and more importantly will usually impair the neural ...

3

The first question can be solved by googling integer logic programming. http://en.wikipedia.org/wiki/Constraint_logic_programming The second question is called the theory of expert programming. I was also able to google this. http://en.wikipedia.org/wiki/Expert_system There is a practical need for expert systems and rule based systems. They are used in ...

3

recently there was a question about using GAs to evolve wind turbine blade designs using fluid dynamics simulations of physical power generated as the fitness function.[1] This video shows the use of a genetic algorithm to develop VAWT wind turbine blades. One of the resulting blades is quite different and seems to simulate well. The breeding software was ...

3

By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits. What you are trying to calculate in part (1) is: $$T = \sum_{A | T(A) < \infty} \frac{1}{2^{|A|}}T(A)$$ Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ ...

3

there is some research into using GAs for wine classification. it accurately classifies the variety of wine and the production place ("origin denomination").[1] this is a subset of use of GAs in Agricultural Systems of which there are many applications. [2] [1] Feature selection algorithms using Chilean wine chromatograms as examples by N.H.Beltran et al [...

3

It would be interesting to know what litterature you have read. As far as I know, Bayesian filters were working very well. That's because the learning is based on the words used, and a Bayesian filter is quick to understand that an email containt "Viagra" is likely spam. But spammers are not so stupid, and they quickly introduced mispelled word. "VI4GRA" ...

3

As for the question of what characteristics make a problem amenable to bandit-based approaches, this paper describes the behaviour of UCT in various search spaces: http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf Regards, Cameron

3

This paper by Jurgen Schmidthuber might be of interest: http://arxiv.org/pdf/cs/0309048.pdf

3

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function. That said, the source of your problem is a confusion about which choices are available to each player when it is their turn. Consider the left-hand side of your first example: writing this in matrix form, each player gets to choose ...

3

In stats I think they'd say "imputation". CS theorists might model this as "matrix completion" (if you make it a matrix), "collaborative filtering" (like in the Netflix challenge). Maybe others know of more keywords.

2

This recent survey paper lists the application of MCTS to a number of search and optimisation problems other than games, in Section 7.8: http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622 As for domains that are totally resistant to bandit-based methods, I'm not aware of ...

2

Yes, T>0. I am not sure I correctly get all your conditions, so I suppose that each $A_i$ is an algorithm and each of them contains an upper bound for its running time. A constant fraction of the algorithms will be the following type: "Run U on This'' program and if it stops in less then k steps, then output something different from its output, otherwise ...

2

Depends on your definition of advanced, and what sort of AI you want to study. Many problems in AI are provably intractable-- optimal solutions to POMDPs are provably NP-Complete, optimal solutions to DEC-POMDPs are provably NEXP-Complete, etc. So, absent some unexpected breakthrough in complexity theory, the more one knows about approximation algorithms ...

2

This is a very soft question and AI is not my field, but I wanted to clarify about the halting problem. It is not generally accepted that humans can tell if a program will halt. This is also more of a question of philosophy than of CS Theory - you might check out this post, and you may find discussions more to your liking on other Stackexchanges (I'm ...

2

The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon >0$ and a loss class $L$ and a data distribution $D$, one cannot use algorithms of type $A$ to find a member of $L$ whose generalization error is below $\epsilon$ unless running time is $f(\epsilon)$"... . One such lower ...

2

Your question is underspecified. If you just want to fill the gaps, put some fixed arbitrary value there. To make the question interesting you have to specific some condition for preferring one way of filling the gaps vs. another one. Essentially what metric are you trying to optimize? E.g. are you assuming that your data is a sample coming from some ...

1

John Sowa (probably the foremost expert on knowledge representation) gives a thorough discussion of the subject here: Sowa

1

You are probably speaking about something like a process ontology. Lately, that research has focused (moved?) on semantic workflows, e.g. to model processes in science, related with reproducibility. Similarly, we can also find the application of ontologies to business processes. For more classical (lower level?) approaches, you may be interested in the ...

1

Let's assume all possible paths are finite to make the discussion simpler. This is the case for the vast majority of game actually played such as Chess (because of the 50-move rule) or Go (assuming superko is forbidden). The idea you have about chosing the move maximizing the minimum path is actually an instance of the following more general idea. A proof ...

1

I don't think this question is related at all with approximation algorithms, or theoretical CS. Please take the following as some free, non-exhaustive, thoughts on your question. It seems to me that what you want is just the probability that a given sequence of words contains only valid words. Let me assume that each word is chosen independently (which it ...

Only top voted, non community-wiki answers of a minimum length are eligible