# Tag Info

12

The depth of a decision tree is the length of the longest path from a root to a leaf. The size of a decision tree is the number of nodes in the tree. Note that if each node of the decision tree makes a binary decision, the size can be as large as $2^{d+1}-1$, where $d$ is the depth. If some nodes have more than 2 children (e.g., they make a ternary ...

9

One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that ...

9

You have a small (but crucial) misunderstanding of what the VC dimension of a class is. The VC dimension is the maximal number $d$ such that there exists a set of $d$ points that is shattered by the class. It doesn't mean that every set is shattered. In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then ...

8

The true error of a classifier $h$ is \begin{align*} L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \begin{cases} \Pr[y \neq 0|x] & \text{if } h(x) = 0, \\ \Pr[y \neq 1|x] & \text{if } h(x) = 1. \end{cases} \end{align*} (All probabilities are with respect to $D$.) The ...

7

Although it performs poorly on text classification tasks, if you want a clear explanation of the classification reasoning, a decision tree would be your best option as it provides clear rules for how an instance is classified. A trace of the tree would provide the determining values and by analyzing the instances close to the root node, you might even be ...

7

Answering knowingly this question would require experiments. I am sure there is some data for natural languages, where it is a common problem. I recall from memory that one study gave ridiculously small figures for natural language, which is not too surprising. If you take 5 consecutive word in a sentence (the figure I recall, without being sure), there is a ...

6

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set. Think of this as projecting the highly dimensional space into a smaller dimensional space. For example, you could do principle component analysis and project it into a small space. This way things that are correlated together are projected into the same dimension and if one of ...

6

The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what you can do with every-day data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question. Some specific ...

5

As D.W. said, the task of classifying words as noun, verb, etc. is called part-of-speech tagging: The machine learning algorithm typically used for this purpose is the Log-Linear Model (aka. Maximum-Entropy, in short MaxEnt). It is actually pretty straightforward: Assume you read the sentence sequentially (left to right, or right to left) Let $h$ be the ...

5

This is a standard problem in Natural Language Processing (NLP). Classifying whether each word is a noun, verb, etc., is known as "part-of-speech tagging". Searching on that term should turn up a lot of information about how to do that. If you want to tag the words in some other way, you might be able to use other tagging algorithms. They generally use ...

5

Michael J. Flynn is one of the all-time great computer architects. He was the design manager of the IBM 360/91, and made numerous foundational contributions in the areas of pipelining, and in computer arithmetic. But the Flynn Taxonomy has not stood the test of time, and is no longer useful. The SI/MI part of the taxonomy is easy to differentiate on the ...

5

Flynn's taxonomy was defined by the great computer architect Flynn in 1960s. Though since that time there is an entire paradigm shift, so today it's better to understand these concepts with a different context. In modern world, parallel computing works by dividing large problems into smaller problems which are then solved at the same time. Now let's ...

4

It is not possible to consistently estimate $P(y \mid x)$ if you are learning with hinge loss. Strictly proper losses, also known as strictly proper scoring rules, are the subclass of loss functions that are consistent for probability estimation. There is now a comprehensive and rich theory of proper losses, the larger class containing strictly proper losses....

4

Genetellboost is developed to cope with labeling noise, i.e., when some samples are wrongly labeled. Though, it wasn't so successful in that respect, from my experience it is quite good in handling noisy features which are kind of outliers in dataset. That being said, there is no proof for neither of the things that you asked (nor the things that you ...

4

It's important that all of the training and test images have the same aspect ratio but it doesn't necessarily have to be the natural one. If you think about it for a while you can see why that is. For example, if you're making a face detector and you have altered the aspect ratio to make all the faces look abnormally tall and skinny then you have a tall and ...

4

The state of the art for digit recognition does not use collective recognition, competence areas, ensembles, or any of the other ideas you propose in your question. Instead, the state of the art for digit recognition uses convolutional neural networks. Just a convolutional neural network: no need for multiple of them, no need for any kind of other fancy ...

4

What you are looking for is called "on-line recognition". I have written my Bachelors thesis about this: Thoma, Martin. "On-line Recognition of Handwritten Mathematical Symbols." arXiv preprint arXiv:1511.09030 (2015). And I've created the online service write-math.com as a part of it. As a short introduction, you might be interested in my presentations....

3

Since your data are extremely sparse, using GMMs or a traditional SVM will result in an over-fit model. By employing methods that exploit the sparsity of the structure, you should get much better results. Regression methods typically add some penalty function as a measure of the amount of non-zero values. This is usually referred to as "regularization". ...

3

If you would be constrained by computational complexity, decision trees (Quinal, 1986) are hard to beat (especially when a framework offers direct conversion of DT model to a bunch of if statements - like Accord.NET). For high dimensional data the notion of distance, on which k-NN is based, becomes worthless (Kriegel, Kröger, Zimek, 2009) (also: Wikipedia ...

3

kNN is useful for large data samples However it's disadvantages are: Biased by value of k. Computation Complexity Memory Limitation Being a supervised learning lazy algorithm Easily fooled by irrelevant attributes. Prediction accuracy can quickly degrade when number of attributes increase. It's usually only effective if the training data is large, and ...

3

There is no universal answer. Instead, it depends on your application. What counts as useful for your application? That determines what should count as a useful or good-enough machine learning algorithm. What counts as useful will vary widely from application to application; some applications require 99.99% accuracy, others might be happy with 52% ...

3

You subsequently clarified that you are looking for a way to do multi-label classification in general, and the example in the question about wanting a cake was just an example. OK, here is one standard way to do multi-label classification. For each candidate label, you build a boolean classifier that outputs true or false: true means that the label applies,...

3

I vaguely recall that Peter Norvig had an implementation of MYCIN, a medical diagnosis expert system, written in LISP in his book Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, which did exactly this. Maybe that is a good place to start your research. You will find the source code online, together with a rule base, however, ...

3

Think of what different features the desert has compared to an urban environment. The desert is probably restricted the a limited set of colors/hues. It is limited to mostly smooth textures. It lacks "man-made" geometries such as straight lines from building edges etc. So you should be able to differentiate between desert and urban environment by looking at ...

3

I think you should have a fourth dataset where the images are in their natural environments because you will need information with white background when you will be testing the datasets.

3

This is a cascade classifier. Of course you can do that, but the main disadvantage (that you have to keep in mind) is that your error propagates along your cascade classifiers. So even if you have a very good classifier somewhere towards the end of your cascade, if you feed it with weak features (i.e., the output of the previous layer which was not so good) ...

3

Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books. One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point. Another approach might be to use ...

3

Try a common feed-forward neural network with one hidden layer and train it with error backpropagatin to find a coherence between your input (temperature values) and output (migration patterns). In order to train a neural network, you have to have pairs of input and output vecors, i.e. in your case, one temperature measurement position corresponds to one ...

3

This is the original paper: Gabriella Csurka, Christopher R. Dance, Lixin Fan, Jutta Willamowski, and Cédric Bray. Visual Categorization with Bag of Keypoints. Workshop on Statistical Learning in Computer Vision, ECCV, 2004.

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