# Tag Info

59

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

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 ...

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 ...

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

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

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

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

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

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

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

I suppose the scientific consensus is that while we are very far from there, in principle a digital artificial intelligence could mimic a human intelligence. For some recent work on the Church-Turing thesis and the relation between physical computation and digital computation by Turing machines, see: Space Bounded Church-Turing thesis and computational ...

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 ...

1

Experiment. It depends on the topology of your problem domain. If you knew how to optimize more efficiently you wouldn't be throwing a GA at it.

1

The maths involved in AI are not advanced, and are taught at the undergrad level. AI training and inferencing algorithms are in the domain of advanced Computer Science. It is a bit of a word game. Some history should also be included when researching AI. For example, in the current nomenclature, Deep Learning seems to be a trending keyword in AI. Deep ...

1

Visualization of clusters. The same ordered display can be used for illustrating the clustering density in different regions of the data space. The density of the reference vectors of an organized map will reflect the density of the input samples [Kohonen, 1995c, Ritter, 1991]. In clustered areas the reference vectors will be close to each other, and in the ...

1

A baseline against which the performance of a classifier can be compared is a naive classifier that only exploits obvious biases in the data. The idea is that if your classifier doesn't do much better than a random biased guess, it is not a very good one. Or it might be that the data doesn't allow you to extract much information. In general, the answer as ...

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