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


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.


3

There is no expectation that an Machine Learning (ML) system will perform perfectly. Not just in the practical sense that we obviously haven't yet figured out how to make a human-level chatbot, but in a more formal sense that ML systems, particularly neural nets, but this is true for many other ML algorithms, approximate functions and this approximation is ...


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

(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

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

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.


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

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


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


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

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

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


1

A plain CNN normally isn't used to produce an image as output; but if you combine it with deconvolution layers, then you can produce an image as output.


1

The readme file lists the following uses for the dataset: 1. Cyber Security 2. Machine Learning 3. Recommender System I believe that you already know point 3 since you specified that you want to use the dataset to build a recommender system. About Point 2: You can use the information in the dataset to train a machine learning algorithm. The former could,...


1

There is sadly very little theory that is useful for predicting the behavior of neural networks. Also, their effectiveness tends to be dependent on the particular workload/task you are trying to solve it. While I know it's not what you were hoping to hear, I suggest that you try it in empirical experiments.


1

The AlphaGo algorithm does not benefit from this kind of optimization. It's hard to share an intuition for why without diving into the details of the algorithm, but at a coarse level: a single small change to the board can make a dramatic change to the strategic nature of the position, so it's not clear that one can reuse calculations effectively. In ...


1

There are a few different ways. One way is to always give it a zero vector, or some other constant that means "new sequence". Another way is to train the initial state vector just like you train any other weight: initialize it randomly, then apply gradient descent during training. The former is easier and faster, but the latter can sometimes make the RNN ...


1

Actually, derivative methods such as random search shorten the time allocated for function evaluation if the problem is big. On the other hand, derivative-free methods take much time to complete function evaluation that leads to a dramatic increase in optimization time.


1

I have wondered something similar and failed to find much in the way of satisfying answers in the literature. Here is what I tentatively came up with. It seems perhaps what we need is some kind of regularization. If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the ...


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