# Tag Info

5

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project. ...

4

Precision and recall are the two basic measures and most of the other measures can be written in terms of them. If a model has both better precision and better recall, then it can be seen as strictly better than another model. If two models are incomparable in the sense that another has better precision and another has better recall, then it depends on the ...

4

My favorite is Understanding Machine Learning: From Theory to Algorithms. It’s presentation is very probability oriented and introduces concepts in a very concise, yet insightful way. It covers the foundations of a lot of Statistical Learning Theory and thanks to the rigorous introduction, I found it is easy to build on certain directions that interest me.

3

Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights. A simple example which requires exponential weights is the function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.

2

As a disclaimer, I didn't read that page, but I can certainly explain where the derivatives come from. The backpropagation algorithm is actually a variant of the gradient descent algorithm. Think about a single function for the moment. Suppose you have a function which responds to a single input and a single weight: $f(w, x)$. We want to adjust $w$ so that ...

2

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right). Machine learning ...

2

The energy usage will vary depending on the machine, but as long as all of your results are from the same setup there's a comparatively low-tech, simple solution: Hook up your computer to an electricity meter and take some measurements with the computer "at rest", to get a baseline of its energy consumption. Then, run several trials with each model you're ...

2

ML is not likely to be a good approach for these kinds of problems. It will probably perform far worse than a hand-designed algorithm. Current ML is not magic; it is just a form of pattern-matching.

2

$R(h)$ is not necessarily a number, it is a deterministic function of $h$. So, it would be a number if $h$ is deterministic, but if $h$ is a random variable, then $R(h)$ is also a random variable. We consider $S \sim D^m$, a dataset that consists of $m$ i.i.d. samples, assumed to be drawn with respect to $D$. Accordingly, $h_S$ denotes the function that we ...

2

(Not enough reputation to comment, so writing here.) Unless your algorithms are secret, please post your algorithms here. Maybe someone (not me though) can find a library for you. Maybe someone can tell how long does it take to implement it. Use Git and GitHub. You can rollback bad code with this. Always write tests. This helps against regressions as you ...

2

Detexify is a service that recognizes LaTeX symbols from handwritten figures. Their training dataset is freely available on Github.

2

I have not heard of recent work on this kind of thing, but there's a huge amount of literature and I know only a tiny slice of it. Today much of the work on neural networks is concerned with feedforward neural networks, which don't have a cyclical structure. The most common form is $$z(x) = L_n(\cdots (a(L_1(x))))$$ where $f:\mathbb{R}^n \to \mathbb{N}^k$, ...

2

To answer your question, I would to point you to the field of computational learning theory (CLT), which applies complexity theoretic approaches to analyse machine learning. An important concept in CLT is probably approximately correct (PAC) learning: in simple terms, a problem is PAC learnable if there exists an efficient algorithm which learns the data ...

2

That's a tough one. I don't know what could cause that. It can be hard to know why we see the results we do, when working with neural nets. Often the best we can do is form several hypotheses, and then devise experiments to try to test those hypotheses. Some possible explanations that you could try to test: Perhaps it is noise / random chance Perhaps the ...

2

In my opinion, this may be best approached as a sequence tagging problem, similar to part-of-speech tagging or named entity recognition. (So, this would be the seq2seq option, rather than regular classification). For example, think about it as trying to decide for each token, whether it is the start of a new verse or not. The advantage of the sequence ...

2

This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David. Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such ...

2

In modern papers, and unless stated otherwise, NP-hardness is one of the following: A decision problem is NP-hard if it is NP-hard with respect to many-one reductions. An optimization problem is NP-hard if its decision version is NP-hard. Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem ...

1

I usually recommend An Introduction to Statistical Learning if you're starting out and Elements of Statistical Learning if you're a bit more advanced. They are both equally pleasing and completely free.

1

Zhou Mashuq have shown that you can learn the structure of documents and recognize them even with different templates. It does this by grouping content into labels. See diffbot.com for a commercial example of this. While this recognizes the labels you still need to select the labels that interest you. This could be done by training a classifier, perhaps ...

1

It depends what to use on what you are doing. I divide this problem in two categories. 1.Site without changing structure Suppose, you are building a app which takes data from your national weather department site and normally which has same structure throughout decade. Here using AI for finding data is stupid thing. You should use conventional parsing ...

1

This depends heavily on the attribute you have in mind: I see no point in using ML for tree recognition for instance since we already have very practical exact algorithms for this. But sure, if you wanted to, nothing is stopping you from taking a bunch of graphs, representing them in some way and labeling them ("is a tree", "is not a tree") and training a ...

1

You can apply transfer learning. Leverage one of the existing datasets and deep learning networks that can classify faces e.g. celebrities. Add/remove layers on top of the feature extraction layers and use your small data set. Provided that the base dataset / network is large and rich enough you should be able to apply it to your dataset. See https://...

1

Given normalized top $k$ eigenvectors $v_1,\ldots,v_k$, you send a point $x$ to the tuple $(\langle x,v_1 \rangle, \ldots, \langle x,v_k \rangle)$. Alternatively, you put the eigenvectors as rows in a matrix $M$, and you map the column vector $x$ to $Mx$ (this is exactly the same thing as above). Multiplying vectors is an operation that doesn't have much ...

1

Let us prove the following general result: Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\{0,1\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$. Indeed, if $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \{0,... 1 What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized. 1 Let$X = |L_\mathcal{D}(h) - L_S(h)|$. The statement on the expectation of the supremum of$X$implies, in particular, that for some$M$, $$\mathbb{E}[X] \leq M.$$ Since$X \geq 0$, Markov's inequality implies that $$\Pr\left[X \geq \frac{M}{\delta}\right] \leq \delta.$$ This implies that $$\Pr\left[X \leq \frac{M}{\delta}\right] \geq \Pr\left[X < \... 1 Store the values in a priority queue. Typically, in each iteration you will update the value for only a single arm, so you need to change the key of a single value in the priority queue, which can be done in O(\log n) time, where n is the number of arms. You can also find the argmax in O(\log n) time. 1 Artificial Intelligence is a very broad area of Computer Science which is intertwined with many other fields, and someone might argue that its definition is the discipline that develops rationally acting systems. When it comes to Machine Learning, the generally accepted definition is programming computers to perform a specific task without specific ... 1 Many research projects use something called "hard negative mining": instead of training on all of the positive instances (e.g., "text" or "object") and all of the negative instance (e.g., "not text" or "not object"), they train on all of the positive instances and a carefully chosen subset of the negative instances. In particular, they omit many of the '... 1 A neural network is not a good choice for this. For this task, you can get a much better solution by analytically solving for the unknown radius of the sphere. In particular, if the radius of the sphere is s, then a slice at height z will have radius r, where these three variables satisfy the equation$$(s-z)^2 + r^2 = s^2.$\$ Re-arranging, we find ...

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