# Question
Title: Solving the quadratic equation using only integer arithmetic
Like the title says, I am trying to solve the quadratic equation while avoiding floating point arithmetic. More specifically, I will be coding this algorithm in C.

I have integer values for a, b, and c. The result can be formatted in any way, though integers would be best. I would also like to avoid losing precision when compared to a traditional floating point solution.

Note this does not have to do with speed or optimization, I don't mind if it takes a little longer, though I would prefer reasonably fast algorithms. Most solutions I have come across are based on multiplying variables by powers of 10.

Answers would be best in pseudocode or C. Thanks

# Answer
You could just apply the rational roots theorem and this involves checking a finite number of possibilities. This will only find rational roots.

How do you propose to represent something like the square root of 2? You need a struct or class to do this.
> 3 votes

# Answer
If you want an infinite precision solution to the equation:

$$ f(x) = ax^2 + bx + c = 0 $$

Then you use Newton's method (or something better) to find:

$$ x\_{next} = x - \frac{ax^2 + bx + c}{2ax + b} = \frac{2ax^2 - ax^2 + bx - bx - c}{2ax + b} = \frac{ax^2 - c}{2ax + b} $$

Based on your comments, it would be *very* difficult (I would think) to find the *best* possible (i.e. highest precision) value using approximation methods (and you have to realize that virtually *every* floating point computation *is* an approximation--even multiplication and *even* addition).

In my opinion, the solution is to "cheat". Use a higher precision structure to calculate the value then round to your lower precision. For instance in C you could use Newton's method with doubles and require a higher precision than float could possibly offer, then cast your answer to a float--this will give the closest float or more precisely, one of the two closest floats--which one will depend on the compiler (I think the compiler chooses the rounding method, but I may be wrong--it might be the architecture).

If you want to find the closest *double* value then you need to use something with more precision than a double which would probably require either assembly or, worse, programmatically creating a higher precision value (that would be extremely slow).
> 3 votes

---
Tags: algorithms
---


title: Deadlock prevention by killing a victim

text:
# Question
Title: Deadlock prevention by killing a victim
In our operating systems class, the teacher told us about deadlocks prevention methods. One of them is that to select as a victim the process which requires the CPU time or one that requires a lot of resources, and remove this process. The next time the algorithm is called, it may be possible that again the same process becomes the victim. This causes **starvation**.

I'm confused: if the victim process is terminated, then how can it again become part of the deadlock?

# Answer
> 4 votes
The idea is that the process is not terminated: only the current operation is cancelled. The process reacts to the cancellation by trying again. In this model, it is assumed that each process runs something like the following pseudocode:

```
begin_transaction:
    try:
        acquire(lock_1);
        acquire(lock_2);
        …
        release(lock_2);
        release(lock_1);
    with Cancelled:
        goto begin_transaction

```

Without any form of deadlock prevention, the processes would get stuck forever. Cancelling one of the processes (in a way that releases its locks) prevents that.

This form of deadlock prevention only works if processes are written in the expected way and can cope with cancellation. It does not generalize to arbitrary programs.

---
Tags: concurrency, deadlocks
---


title: Grammar for a language with 1/3 of a's

text:
# Question
Title: Grammar for a language with 1/3 of a's
I have this language: $$ L = \left\\{ w \in \\{a,b,c\\}^\* \\;\big|\\; |w| / |w|\_a = 3 \right\\} $$ where $|w|\_a$ is the number of occurrences of $a$.

How can I find a grammar that generates it?

# Answer
> 7 votes
The proportion of $a$'s has to be $1/3$. This means that every $a$ encountered in the word creates a debt that must be compensated by two non-$a$'s. This way of looking at the language rather directly leads to a pushdown automaton. With a bit more reasoning, it also leads to a language.

If the word starts with $a$, that $a$ must be compensated by two non-$a$'s. These two compensating letters might not come immediately: the word can start with multiple $a$'s. But eventually the $a$ debt has to be reduced back to the starting $a$, and then a non-$a$ takes the debt down. Each $a$ can be said to have two matching non-$a$'s: the ones that take the debt down from the level where that $a$ put it. In other words, an initial $a$ can be followed by any number of elements of $L$ (each element of $L$ leaves the $a$ debt constant), then a compensating non-$a$, then more elements of $L$, then the second compensating non-$a$, and finally more elements of $L$.

The same principle applies if the word starts with a non-$a$. The trio of $a$, non-$a$ and non-$a$ can come in any order: the $a$ could be either second or third if it isn't first.

$$ \begin{align} S &\to \\ S &\to a \\, S \\, B \\, S \\, B \\, S \\ S &\to B \\, S \\, a \\, S \\, B \\, S \\ S &\to B \\, S \\, B \\, S \\, a \\, S \\ B &\to b \mid c \\ \end{align} $$

It's clear by induction on the length of the word that any word generated by this grammar is in $L$. (Write it down.) Conversely, the reasoning above shows that all words in $L$ can be decomposed according to the grammar above, again by induction on the length of the word. (Again, write it down.)

# Answer
> 0 votes
Suppose that you are given a word $w$ in the language. You can extend it by taking any word in the language and inserting it anywhere in $w$. The following rule generates the smallest non-empty words in the language:

$S \to \text{ a T T } | \text{ T T a } | \text{ T a T }$

$T \to b\text{ }|\text{ }c$

The first paragraph suggests that the grammar is given by:

$S \to \text{ S a S T S T S } | \text{ S T S T S a S } | \text{ S T S a S T S } | \text{ }\epsilon$

$T \to b\text{ }|\text{ }c$

---
Tags: formal-languages, context-free, formal-grammars
---


title: How do I prove theta(log n)=o(log n)?

text:
# Question
Title: How do I prove theta(log n)=o(log n)?
I'm solving a question from CLRS where we need to prove that (ceil(lg lg n))! is polynomially bounded.

```
Let g(n)=(ceil(lg lg n))!
lg(g(n))=lg((ceil(lg lg n))!)
        =theta(ceil(lg lg n) * lg (ceil(lg lg n))) [since lg(n!)=theta(n * lg n)
                                                    and replacing n by ceil(lg lg n) here.]
        =theta((lg lg n) * (lg lg lg n))  ----(1)  [since ceil(n)=theta(n)
                                                    and replacing n by (lg lg n) here.]

```

**Now if I can prove that theta(lg n)=o(n)**

```
=>theta(lg lg lg n)=o(lg lg n)
=>theta((lg lg n) * (lg lg lg n))=o((lg lg n) * (lg lg n))
                                 =o((lg lg n)^2)
                                 =o(lg^2(lg n))
                                 =o(lg n)  ----(2) [Polylogarithmic functions grow
                                                    slower than
                                                    polynomial functions.
                                                    =>log^b(n)=o(n^a)
                                                    =>log^2(log n)=o(logn^1)
                                                    =>log^2(log n)=o(log n)]

From (1) and (2) we have log(g(n))=o(log n)
=>g(n)=o(n^a) that is g(n) is polynomially bounded.

```

**The only problem I'm facing is to prove that theta(lg n)=o(n). Please help!**

# Answer
Hint: take derivatives on both sides and show that the derivative on the left tends to 0 (i.e. is smaller than any constant for n big enough). The derivative on the right is constant. Use that to show that the right side will always outgrow the left side for n big enough.
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


title: Neural Network Design Challenge

text:
# Question
Title: Neural Network Design Challenge
i'm studying for PHD Entrance Exam on Stanford. one of previous material exam designed very challenging.

i want to design a NN for classifying following 2-class problem.

1) output should be -1 or 1.

2) output should be 0 or 1.

for sove this question i think using XOR neural network for following problem for above dataset? i'm not sure because one point under the X-axis in this picture and above data all is above X-axis? can anyone help me ?

i want to draw a NN for two case mentioned above and find minimum number of node (without input node). for example i think for 0 or 1 output we have following NN with (5 nodes and 2 input node)

# Answer
> 1 votes
Artificial Neural Network design is as much art as it is science. Art in the sense that many problems have varying approaches and designs which may **not** be uniquely characterized.

After this simple prologue, this is a generalisation of the ANN XOR problem which multi-level ANNs have been shown to solve eficiently.

It can also be seen as transformation of the original XOR problem (simply rotate the data by $\pi/4$) and *explosion* by a factor.

Usually ANNs employ 3 layers (1-input 1 -intermediate and 1-output), of course more layers can be added. This simply illustrates a trade-off between computational power versus computational complexity.

By the universal approximation theorem arbitrary (compact) mappings can be approximated by a (sufficiently complex) MLP ANN .

A further approach is to use a hidden layer with $2n$ or $2^n$ neurons (by symmetry of the problem) and experiment with that.

UPDATE:

As per the OP's further comments regarding transformations between variables $\in \\{0,1\\}$ to variables $\in \\{-1,1\\}$, a link for an MLP ANN for the XOR problem using -1,1 values

---
Tags: computability, machine-learning, artificial-intelligence, neural-networks, pattern-recognition
---


# Question
Title: Are all undecidable/uncomputable problems reducible to the Halting problem?
Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an algorithm which solves the problem.

Many problems that are undecidable seem to have a reduction to the Halting problem: Matyasevich's proof of the undecidability of Diophantine equations uses the Halting problem, the machine equivalence problem uses the Halting problem as well...

The question is: are all undecidable problems (in the sense of Turing) reducible to the Halting problem?

If so, is there a proof of this? If not, is there a counterexample of such a problem that provably cannot be reduced or mapped to the Halting problem.

# Answer
No. As I recall a practical example can be made out of a *function inequivalence* statement. More abstractly, there is something called *Turing-degree* in undecidability and infinite levels of "hardness". Each level has it's own Halting Problem strictly harder than those at every level lower. Check out the first section of this Scott Aaronson lecture and what he calls a "Super Halting Problem".
> 7 votes

# Answer
The halting problem is recursively enumerable, but not co-recursively enumerable. That is, it is recognizable, but it's compliment is not. You are sure to halt on a string in the language, but not on a string that is not in the language.

Implication of **not** $r.e.$ and **not** $co\text{-}r.e$ propagate from left to right over a reduction. Implication of $r.e.$ and $co\text{-}r.e$ propagate from right to left over a reduction.

Because the halting problem is $r.e.$, any problem that reduces to it is $r.e.$ So if all undecidable languages reduced to the halting problem, then all undecidable languages would be $r.e.$, but some undecidable languages are neither $r.e.$ nor $\text{co-r.e.}$, and some are $co\text{-}r.e$ but not $r.e.$

An example of an undecidable language that doesn't reduce to $\text{HALT}$ is $\text{EMPTY} = \\{ \<M\> : \text{M is a Turing machine and } L(M) = \emptyset\\}$

$\text{EMPTY}$ is a language which is $co\text{-}r.e$, but **not** $r.e.$. This is because as soon as you find a string that $M$ accepts, you know that L(M) is not empty, and if a string is in $L(M)$ it is guaranteed to be accepted and therefore halt, in a finite amount of time. But if $M$ doesn't accept any strings, you may never know that as the machine may diverge or go into an infinite loop on a string and never halt.

Another language that doesn't reduce to $\text{HALT}$ is $ FINITE = \\{\<M\> : M \text{ is a Turing machine and L(M) is finite } \\}$, which is neither $r.e.$ nor $\text{co-r.e.}$
> 4 votes

# Answer
The proof that the halting problem is undecidable relativizes, that is, it still works if the Turing machine is given access to an oracle. In particular, the halting problem for Turing machines with oracle access to the (usual) halting problem isn't solvable by Turing machines with oracle access to the (usual) halting problem. This implies that this generalized halting problem cannot be many-one reduced to the (usual) halting problem.

More generally, we can construct a scale of problems, each one harder than the previous one, by adding the appropriate oracle. This is the classical "jump" operator of recursion theory. If you're interested in this sort of thing, find a textbook or lecture notes on recursion theory.
> 2 votes

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Implement "from" function for AVL Tree java
I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time.

Question:

I am completely lost for this question. I absolutely CANNOT figure out a way to get an algorithm that run in O(log(n)) time. The ONLY algorithm I can think of is to do an in-order traversal, store values in an array and then return the ith smallest key greater than k if it exists but obviously this is worst case O(n). I have been working on this problem for the past 2 days and I simply cannot come up with a solution. The hint my professor gave me was to add a size field to the node which will tell me the number of nodes at subtree v including itself. My thinking was to try to use a relative\_rank function (gives me the rank of node value k with respect to a node v) somehow but I cannot think of a way to do it in O(log(n)) time. Any help would be appreciated.

# Answer
If $i$ is bounded by a constant, simply search for $k$ and then do BST-successor $i$ times.
> 1 votes

---
Tags: algorithms, search-algorithms, search-trees
---


# Question
Title: Intersection and partial quantity decidability
I'm still insecure in the section decidability (no proof needed, I want to divine it):

X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable?

X is decidable and Y is a partial quantity of X. Is Y decidable, too or not?

Thanks!

# Answer
> 2 votes
For your first question, the answer is that $X\cap Y$ will not necessarily be decidable. Let $Y$ be an undecidable language over an alphabet $\Sigma$ and let $X=\Sigma^\*$. Then obviously $X$ will be decidable and $X\cap Y=Y$ will be undecidable. On the other hand, the intersection may be decidable, as we could show by letting $X=\emptyset$.

For your second question, I assume that by "$Y$ is a partial quantity of $X$" you mean that $Y$ is a subset of $X$ (i.e., $Y\subseteq X$). Then we can do a similar construction, letting $X=\Sigma^\*$, and $Y$ be undecidable, so again, $Y$ may or may not be decidable.

It's worth mentioning that this latter result frequently trips up students. Very few properties of languages are closed under subset/superset: there's no guarantee that a subset of a regular language will be regular, for example.

---
Tags: complexity-theory, turing-machines, undecidability
---


# Question
Title: What is the difference between LRU implemented for a cache and for page replacement?
I have read that true LRU page replacement requires significant hardware support, so only approximation of LRU is implemented for page replacement.

So I wanted to contrast LRU that is implemented for cache, and that for page replacement. Like - Is LRU properly implemented for cache?

# Answer
> 6 votes
LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each set.)

For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier to analyze for worst-case execution time. Binary tree pLRU is relatively simple to implement because an access to a given way will always merely set/clear specific bits.

For associativities higher than eight, FIFO, random, and Not Recently Used have been used. E.g., the Itanium 2 6M used NRU that is similar to the clock page replacement algorithm in that a bit is set when accessed and all the bits are cleared when they have all been set.

An interesting exception is the use of true LRU in the 32-entry fully-associative L1 TLBs for several Itanium implementations. For a fully associative TLB, true LRU is less expensive because there is only one set, so storage and control logic can be bundled together.

It should also be remembered that LRU is really just an estimate of relative reuse distance; approximation of a conceptually-derived heuristic can be roughly as effective as the ideal heuristic. (Even reuse distance may not be ideal for replacement because not all entries have the same cost/benefit.)

---
Tags: operating-systems, cpu-cache, paging
---


title: Concept used in the proof

text:
# Question
Title: Concept used in the proof
In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4:

The concept that I am referring to is:

> Then $\mathit{\Phi}$ is false if and only if there exists a clause $\phi \in N^+\_\mathit{\Phi}$ or $\phi \in N\_\mathit{\Phi}$ such that $\forall x\_1\exists y\_1\cdots y\_{k-1}\forall x\_k(P\_\mathit{\Phi} \land \phi)$ is false.

# Answer
An unquantified CNF formula consisting of clauses containing a single positive literal plus any number of negated literals is always satisfiable. To produce a satisfying assignment, you simply set all the positive literals to true, satisfying all the clauses. If you existentially quantify the variables associated with the positive literals and allow arbitrary quantification of the remaining variables, the formula is still satisfiable, and for the same reason. In the proof of the theorem, $P\_\mathit{\Phi}$ is the subset of such clauses from the Horn formula $\mathit{\Phi}$. Thus $P\_\mathit{\Phi}$ by itself is always satisfiable. It follows that $\mathit{\Phi}$ can only be unsatisfiable if, out of the sets of remaining clauses (denoted $N^+\_\mathit{\Phi}$ and $N\_\mathit{\Phi}$), a clause requires one of the previously set positive literals in $P\_\mathit{\Phi}$ to be set false and there is no other way to satisfy the previously satisfied clause.
> 5 votes

---
Tags: algorithms, np-complete, logic, proof-techniques, correctness-proof
---


# Question
Title: Contrast Enhancement For An Image Using A Gaussian Function
I am working on a program that involves detecting faces in photos, i am reading a paper that someone has wrote and they said that they had more success detecting faces once he they applied some enhancements to the image, one of these being a contrast enhancement. The exact words are...

> Contrast enhancement improves the overall quality of the image. Gaussian convolution using the Gaussian function G(x, y) is first applied with the input value channel image in the HSV space. The convolution process can be expressed as follows

They then give you Equation 3: $V\_{con} = V\_1(x,y) \oplus G(x,y)$ NOTE: $V\_1$ is the original value

> $V\_{CON}$ in Eq. 3 denotes the convolution result, which contains the luminance information from the surrounding pixels. The center pixel value is now compared with the Gaussian convolution result in order to find the amount of contrast enhancement of that center pixel. This process is described by the following equation

Equation 4: $V\_{ce}(x,y) = 255V\_{le}(x,y)^{E(x,y)}$ NOTE: $V\_{le}$ is the result of another enhancement done previously.

> where $V\_{CE}(x, y)$ is the result of contrast enhancement and $E(x, y)$ is given by the following relation

$E(x,y) = (V\_{con}(x,y)/V\_1(x,y))^g$

> Here g is the image dependent parameter determined by using the standard deviation of the input value channel image. If the center pixel is brighter then the surrounding pixels, the contrast of the pixel is pulled up. On the other hand, if the center pixel is darker then the neighboring pixel then the contrast of the pixel is lowered.

The problem is that with my understanding of maths (NCEA Level 3, Last year at collage) i don't understand how to do the first part, any help would be much appreciated

The full paper is here: http://jips-k.org/dlibrary/JIPS\_v09\_no1\_paper9.pdf

# Answer
> 3 votes
Convolution is a relatively simple operation to perform, but to make it fast involves a little extra work (Wikipedia article on convolution theorem). In general, if you convolve a discretized function F by a different discretized function G, you are simply performing the following operation:

$$(F\otimes G)(x) = \displaystyle\sum\_{i=0}^NF(x-i)\*G(i)$$

Where N is the number of discrete values of G. Notice this is effectively just summing the product of F and G "centered" around $x$.

In 2D (which is what an image is), this looks like:

$$(F\otimes G)(x,y) = \displaystyle\sum\_{i=0}^N\displaystyle\sum\_{j=0}^MF(x-i,y-j)\*G(i,j)$$

The paper you're reading tells you that F is the V channel of the image in HSV space, and G is a 2D gaussian function. Code-wise, the above form should translate very simply into a double-nested for loop.

The paper should also tell you what the mean/variance of the gaussian function is as well as the number of samples it contains, but sometimes that information is omitted.

---
Tags: computer-vision
---


# Question
Title: Policy function π in Reinforcement learning unclear
I have one question about policy function in Reinforcement learning.

> > in fact this function indicates which action should be done in each state? Or
> >
> > this function indicate for get the specific reward in each state, which action shoud be selected?
> >
> > or something else?

# Answer
> 1 votes
A policy $\pi$ maps each state to an action. Generalizations of this allow for a stochastic mapping (each state to an action with given probability). Given a policy you can estimate or compute the expected reward (or cost) at any state. An optimal policy is simply one that produces the most reward overall.

---
Tags: machine-learning, artificial-intelligence, data-mining, pattern-recognition, learning-theory
---


title: Rice's theorem vs Turing completeness

text:
# Question
Title: Rice's theorem vs Turing completeness
I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.

This is the problem:

In building an *Universal Turing Machine* to emulate another *Turing Machine*, how can we be sure that we are indeed simulating it? ('sure' in the sense of being computationally verified by an algorithm). So I get confused, the problem I found is that Rice's theorem apparently tell us that we can not verify this computationally.. Is not "to emulate" an extensive property?.This lead me to think we could not prove the Universal Turing Machine is doing what it's supposed to do..

**EDIT**

**To expand the topic**

I want to expand this point, what I understood from given answers, is you can state that a *specific* Machine is Universal but not that an *arbitrary* machine is (nor a family of machines are universal), ok, but I don't ask for arbitrary!, nor a family, but to test algorithmically a single fixed machine. Test, like measuring, is against something, It's hard to think a computer concept without having something to compare with, and according to answers, completeness of a machine seems as something that can't be compared.

How universality is proven? let's say by showing 'look mom I am simulating a TM', so, as she believes TM are universal, then your machine *is* also universal, but, she can't verify it!, she must believe you because she can't test that single machine you made, not by an algorithm, so that's why I see Rice's theorem rubs against completeness, there is no algorithm to test *two* fixed machines are doing the same computation.

So what can "universal" mean?, it's seems like saying, your software is doing what you mind, because is written in a Turing Complete language!. 'This *is* emulating a machine because it *can*'. I think that's not enough.

# Answer
Your misunderstanding is:

> 'sure' in the sense of being computationally verified by an algorithm

We are not, and we can not be . The question,

> Is this given Turing machine $M$ a universal one?

can not be generally and algorithmically decided for the reasons you state.

However, we can prove for a *fixed* Turing machine that it is universal -- and that is quite enough.
> 11 votes

# Answer
I'm not sure I understand your confusion (feel free to expand, if you are still confused), but there two issues that might give you better intuition:

1. Given a Specific TM $M$, we can know \`\`for sure'' what it does for all inputs. This is not "sure" in an algorithmic way, but sure in an absolute (mathematical) way.

Example: Consider the TM that has one state, which is non-accepting. We know **for sure** what it does: it does nothing. We can prove it mathematically. Same goes for universal TM: we can prove mathematically, that for any (well-defined) input $M',x$, the output will be exactly $M'(x)$. If this is true in an absolute way, what does it mean to be sure of it by a computationally verified algorithm?
2. There is a difference between knowing what a *specific* machine does, and deciding, for *any* arbitrary machine $M'$, what it does. Rice's theorem talks about family of machines that have the same property, so it fits the latter notion. Similarly, "being sure in an algorithmic way that a universal machine simulates a machine $M$" means that we have some decider TM that decides, for **any** $M'$, if it is a universal machine or not. This is very different then knowing thath one specific machine is universal.

Maybe to demonstrate this last issue, note that we know that $$ L\_{HP} = \\{ \langle M,x\rangle \mid M \text{ is a TM that halts on }x\\}$$ is undecidable. But for a given specific $M'$ and input $x$, the language $$ L\_{HP-M'-x} = \begin{cases}1 & \text{if $M'$ halts on $x$} \\0& \text{otherwise}\end{cases}$$ is very much decidable! (even if we don't know which specific machine decides it :)
> 5 votes

# Answer
I think you are stumbling on the *building* of an universal Turing machine, that process is (implicitly) a proof that the result is universal, by the way the machine is put together. You probably haven't seen any complete construction of such, only (more or less) handwavy explanations that it can be done. The complete constructions (and their proofs) are long, involved, and terminally boring.

Just as an interpreter for e.g. Python is something magical. Yes, I can explain in rough outline how it works, but for you to get really convinced the `python` program on your computer does the job you'd have to read the program's source and understand it. You can even write a Python interpreter in Python itself, mimicking the "TM that simulates TMs" above. To find out if some random Python program is in fact a Python interpreter is another kettle of fish altogether.
> 1 votes

---
Tags: computability, simulation, turing-completeness, church-turing-thesis, rice-theorem
---


title: Matching training with Neural Network

text:
# Question
Title: Matching training with Neural Network
I have a matching algorithm that is based on making an comparison score. This score is divided into parts. Example:

5 - Points for attributes (lets say they have 3 common attributes, would the score be ((3/5)\*5) = 3 Points

5 - Points for location

10 - Points for content

Theses points are just something i have set though guessing, and they work well. But to find what values would be best would i like to implement a kind of AI to test this, i have created 20+ test cases where i know what the correct matching is, so i though that i will be able to train my algorithm to have better values for the different value. I am no expert in AI, i have only have one course about it, but would a neural network be able to help me here, or should i go with another AI?

# Answer
I would suggest you use linear regression, or simply grid search (you can search over all possible number of points for each category, from 1..20; that's only $2^{13}$ possibilities, all of which can be easily tested one-by-one).

Make sure to use cross-validation: split the data set into training and test, and use the training data to derive the best parameters, then evaluate it on the test part.
> 1 votes

---
Tags: artificial-intelligence, neural-networks
---


title: VC Dimension Calculation for Intervals

text:
# Question
Title: VC Dimension Calculation for Intervals
As i See in ML Course a VC dimension calculation is very theoretical.

What is the VC-dimension of intervals in R?

The target function is specifieed by an interval, and labels any example positive i it lies inside that interval.

Answers:

VC-dim = 2. A set of two points can be shattered, since there's only a single block of positive examples that could lie within the interval. But no set of 3 points can be shattered, because it can not be labeled in alternating +; - ; + order.

so i'm get stuck with meaning of interval.

for example, it means {(a, b) | "a is lower than b", a,b is real number} has VC-dim = 2?

Any idea or solution would be highly appreciated.

# Answer
> 3 votes
Yes, an open interval in $\mathbb{R}$ is defined as $(a,b) = \]a,b\[ = \left \\{ x \in \mathbb{R}|\\,a\<x\<b\right \\} $. It has two parameters $a$ and $b$. The sets of all open intervals, i.e. $\left \\{ \left \\{ x \in \mathbb{R}|\\,a\<x\<b\right \\} | a,b \in \mathbb{R}\right\\}$ has a VC dimension of 2 for the reason you mention. Keep in mind that the VC dimension of a hypothesis set $H$ is **the most points** $H$ can shatter.). To put it graphically:

(image from CalTech's free machine Learning online course by Yaser Abu-Mostafa Learning from Data)

---
Tags: machine-learning, artificial-intelligence, data-mining, pattern-recognition, vc-dimension
---


# Question
Title: Difference between data duplication and data redundancy
My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in particular why the third normal form is important: because it eliminates data duplication and redundancy. But as far as I can see, both of these terms relate to data appearing more than once in a database. Yes, I asked my teachers, but I didn't understand the explanation and it was a group revision session that I didn't want to hold up.

# Answer
**(1) Duplication**

When you create tables in a database, you may want to create duplication:

```
CREATE TABLE user (name TEXT, id INTEGER);
CREATE TABLE friends (name TEXT, friend_of_id INTEGER);

```

Here you would duplicate the name of the user in both tables. That way when you display the list of friends, you do not have to access the user table to read the name. This is a simple example, but it shows what we call data duplication.

Duplication means YOU are responsible for also updating the name parameter in the friends table, when you change the name in the user table. If you do not do that consistently, then your data becomes inconsistent and users start seeing "strange things happening."

**(2) Redundancy**

In case of redundancy, you do not yourself have two copies of any piece of data. The database can though. This is useful for safety. For example, you can place your database on two separate computers. If one computer goes down, the same data is available on the other computer.

Redundancy is definitively a copy, but the access to either version of the data is 1 to 1 exactly the same to you. The RDBM may choose one or the other based on different parameters such as how fast or whether the other computer network connection is down.

The RDBM manages the copies in very consistent ways, the same problem I just mentioned about user names. If the RDBM is asked to update the user name, it has to update all the versions (all copies). The good thing is it does not have to do it at the time you do the INSERT or UPDATE, it can delay the update on the copy computer. So... the implementers of the database do exactly the opposite of what they were told and make duplicates of the data! (which is probably the main source of confusion in this realm.)

You may want to read about Cassandra for fun things in that respect. Cassandra is the type of database used by Google which update data in a ring of computers with possibly heavy redundancy.

**(3) Even More Duplication**

Since you asked, I'll also let you know that RDBMs make use of what we call Indexes... And Indexes duplicate your data further. To continue with the user example, the name of the user could be used in an index. The Index would then look like this, for example:

```
Alexis
Henri
Margarette
Phyllis
...

```

When you do an UPDATE of the users table, the RDBM needs to also update its index and move the name to the new position, and all of that with maintaining consistency (SQL warrants that the data is always 100% consistent...)

So, renaming Alexis as Tristan would give a new index:

```
Henri
Margarette
Phyllis
Tristan
...

```

And here we see that the duplication is actually necessary. And if you see how you can handle that properly, without ever losing any existing data, you understand why duplication is difficult to deal with.
> 6 votes

---
Tags: databases, normal-forms
---


# Question
Title: How do I apply patch sized features to larger images?
I've been trying to teach myself some machine learning, and I wanted to ask what seems a simple question, but I've not been able to find any resources that explain the next step.

Let's say I am doing semi-supervised learning, and have a few hundred sparsely distributed feature extractors, trained on random 32x32 regions (the unsupervised part of the process).

I now want to take the larger images in my training set, and do some supervised learning based on the feature extractors I now have. In this case, multi-label classification.

The bit I'm not clear on is what I do with the full sized image from my training set:

* Take random samples from it? -- seems like it would be pot luck if it picks an area needed to identify appropriate labels
* Take overlapping tiles with a sliding window? -- seems like I'd end up with absurd dimensionality, since for each tile, I get a whole vector of features
* Take adjacent tiles? -- dimensionality still nonsensical, and probably translation sensitive as well

It's a hypothetical example, but let's say my inputs are 800x600 photographs, i.e. the input is about 100-1000 times bigger than the samples I used in the unsupervised learning stage.

# Answer
> 2 votes
The options are various.

If you want a naive and easy workaround simply resize your image (shrink it) and trust that the interpolation would preserve information.

If not, you might want to use Gaussian Pyramids or Spatial Pyramid Match Kernels:

http://www.ifp.illinois.edu/~jyang29/papers/CVPR09-ScSPM.pdf http://www.vision.caltech.edu/Image\_Datasets/Caltech101/cvpr06b\_lana.pdf

Other options are a bit untidy. For example, you might take overlapping samples from it, apply some sort of feature extraction and if those features are still big for you, apply a PCA or LDA for dimensionality reduction. (There are more clever sampling strategies such as farthest point sampling : http://webee.technion.ac.il/people/zeevi/papers/17-00623193.pdf

Also taking a look at the covariance matrices might provide you relevant information. Why don't you also check:

http://static.googleusercontent.com/external\_content/untrusted\_dlcp/research.google.com/en/us/pubs/archive/36416.pdf

Cheers,

# Answer
> 2 votes
I understand that you are trying to build a scene analysis algorithm based on patch based feature extractors. Apart from tbirdal's suggestions, take a look at literature on feature pooling, that is crucial for building higher level information from the output of low level features.

Take this paper for example:

A Theoretical Analysis of Feature Pooling in Visual Recognition

http://www.icml2010.org/papers/638.pdf

---
Tags: machine-learning, image-processing, pattern-recognition
---


# Question
Title: Complexity of edit distance with block operations
Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$. The operations are:

* Insert a single character into $P$
* Delete a single character from $P$
* Substitute a single character in $P$ for another one
* Move an entire substring of $P$ to another location in $P$

What is the time complexity of this problem?

# Answer
> 2 votes
What it looks like you are after is the Block Swap edit distance. Here is a paper outlining a polynomial time solution to this problem, An Edit Distance Algorithm with Block Swap. I cant recall the exact time complexity they give in the paper, however it is outlined in there.

---
Tags: complexity-theory, time-complexity, strings, string-metrics
---


# Question
Title: Training Error & Convergence to True Error
I Take some online class for Machine Learning. one of teacher say this sentence.

if we have m data points, the training error converges to the true error as m → ∞.

i thought, this sentence not always correctly. i think when we assume that the data points are i.i.d this sentence becomes true. but in general it's false.

any tutorial for clarity on my thought and Real ML ?

# Answer
> 0 votes
Statistical machine learning always assumes that the data points all come from the same distribution and are i.i.d.

If they weren't, the machine learning task would be hopeless. Imagine if there were some crazy correlation where the 1000th data point has a crazy different distribution (maybe correlated to all 999 prior data points in a crazy way). Now imagine trying to train a model on the first 999 points, and then use the learned model to classify the 1000th data point. There would be no hope of success.

So machine learning can only be used when all of the points have the same distribution, iid.

---
Tags: machine-learning, artificial-intelligence, data-mining, pattern-recognition, learning-theory
---


title: Over-fitting Always Occurs?

text:
# Question
Title: Over-fitting Always Occurs?
i get stuck in one sentence in machine learning.

i read tom Mitchel book on ML, and some other materials.

if we have small training set, always over-fit can occurs? or is likely to occurs?

i read lots of material but i'm not sure that which of my fact will be correct.

any solution or idea?

# Answer
> 9 votes
Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, that is to say when the size of the training data is to small in comparison with the model complexity.

Examples:

* if your data is in two dimensions, you have 10000 points in the training set and the model is a line, you are likely to *under*-fit.
* if your data is in two dimensions, you have 10 points in the training set and the model is 100-degree polynomial, you are likely to *over*-fit.

From a theoretical standpoint, the amount of data you need to properly train your model is a crucial yet far-to-be-answered question in machine learning. One such approach to answer this question is the VC dimension. Another is the bias-variance tradeoff.

From an empirical standpoint, people typically plot the training error and the test error on the same plot and make sure that they don't reduce the training error at the expense of the test error:

I would advise to watch Coursera' Machine Learning course, section "10: Advice for applying Machine Learning".

# Answer
> 0 votes
Overfitting occurs whenever there is noise, because the definition of overfitting is (more or less) fitting a model to the noise, instead of to the signal.

Since noise always exists in real data, overfitting always happens when working with real data.

# Answer
> 0 votes
Overfit is usually characterized by high variance in the estimation of the classifier performance. When having very little data one tends to fall in this regime. It is in this case where techniques like bootstrapping become useful.

The idea is that your measurements are inherently unstable due to the lack of data, because the system to be solved is undetermined. Hence you observe high variance.

You need to introduce some smoothing that gets you closer to the task data. Bootstrapping and generating new samples by adding small amount of noise usually help in this regime.

---
Tags: machine-learning, artificial-intelligence, pattern-recognition, learning-theory
---


# Question
Title: Finding number not in list with wildcards
I have a list like this:

```
1*0*0
1**0*
0*0**
001**

```

Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time algorithm that can determine if there exists an $n$-bit number that does not equal any of the rows. Does anyone know of an algorithm that could do this? I've been thinking about evaluating the total number of possible solutions for each row and subtracting from $2^n$ but I can't figure out how to delete duplicates in polynomial time.

# Answer
> 7 votes
Reduce from SAT. Consider a CNF formula $\phi = C\_1 \land C\_2 \land \ldots \land C\_m$ over a set of variables $\\{x\_i\\}\_{i=1}^n$. Construct an instance of your problem as follows:

For each clause $C\_i$, create a row (i.e. binary string) $B\_i = b\_1 b\_2 \ldots b\_n$, where

$$ b\_k = \begin{cases} 1 & \text{if }\overline x\_k \in C\_i \\ 0 & \text{if } x\_k \in C\_i \\ * & \text{if } x\_k, \overline x\_k \notin C\_i \end{cases}$$

We can preprocess $\phi$ to remove any clauses that contain both a literal and its negation, as these will of course always be satisfied and do not affect the result.

Any binary string $S$ that solves your problem also yields a satisfying assignment to $\phi$, using the reduction that sets $x\_i$ to the value of $S\_i$.

Thus your problem is $NP$-hard. Since it is also clearly in $NP$, it is also $NP$-complete.

---
Tags: algorithms, polynomial-time, lists
---


# Question
Title: Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak
The book *Computational Complexity: A Modern Approach* by Arora/Barak provides the following:

**Theorem 1.10** There exists a function $UC: \\{0,1\\}^\* \to \\{0,1\\}$ that is not computable by any TM.

**Theorem 1.11** HALT(The halting problem) is not computable by any TM.

**Table 1.7** that shows how Theorem 1.10 can be proved using diagonalization. Essentially this table says that there exists an uncomputable function UC that can always reverse the output of any TM, therefore, *function* UC is uncomputable.

The proof of Theorem 1.11 essentially creates a TM $M\_{UC}$ that computes UC by assuming that HALT is computable and also by using a universal TM to simulate $M\_{UC}$ and thus contradicts Theorem 1.10 and concludes that HALT is uncomputable.

My question is this: Since $M\_{UC}$ is a TM, it already exists as a part of Table 1.7. In this case (as explained by the note attached to this table), function UC will (by definition) reverse the output of $M\_{UC}$. Thus the $M\_{UC}$ does not compute function UC even if we assume that HALT is computable.

Also, it seems that $M\_{UC}$ will go into a type of recursion when the input to $M\_{UC}$ is a bit representation of $M\_{UC}$, i.e., each simulation on a universal TM will lead to another call on the universal TM and thus lead to a type of loop. Perhaps this is the reason the proof of Theorem 1.11 invokes a call to the HALT function (which is assumed to be computable).

# Answer
> 5 votes
Since neither HALT nor UC is computable, the machine $M\_{UC}$ actually does not exist. The proof by contradiction *assumes* that HALT is computable and then constructs a machine $M\_{UC}$, which contradicts the preceding theorem. This machine is hypothetical, and the proof of Theorem 1.10 indeed shows that it doesn't exist. That's why HALT cannot be computable.

---
Tags: computability
---


title: Dijkstra Counter Example

text:
# Question
Title: Dijkstra Counter Example
I an brushing up on Dijkstra (specifically Wikipedia's pseudocode) and can't resolve this counter example. I want the shortest path between A and E. I would move from A to C to D, where D would have a cost of 105. Once I mark D as visited I no longer have an opportunity to find the correct path A to B to D to E. What am I missing?

# Answer
> 4 votes
initially you have: Q={A, B, C, D, E} dist(A)=0, dist(B)=dist(C)=dist(D)=dist(E)=inf previous(A)=previous(B)=previous(C)=previous(D)=previous(E)=undefined

from Q the vertex with min distance is A. Therefore you choose A and you do (dist(A)+length(A,B)

your remove A from Q, now you have Q={B, C, D, E} In Q the vertex with the min dist is C with dist(C)=5, so you pick C the only vertex adjacent to C is D so you have (dist(C)+length(C,D)

you remove C from Q, now you have Q={B, D, E} the vertex with the min dist in Q is B so you pick B (dist(B)+length(B,D)

you remove B from Q, now you have Q={D, E} the vertex with the min dist in Q is D so you pick D (dist(D)+length(D, E)

you remove D from Q, now you have Q={E} the vertex with the min dist in Q is E so you pick E No neighboors remove E from Q Q is empty and the algorithm terminates previous(E)=D previous(D)=B previous(B)=A so this is your shortest path from A to E

I skipped the distance checking for the previous vertex for simplicity (it is always equal), the algorithm performs this check. I think you confuse picking a vertex from the set Q and changing the distance of a vertex. They are two different things. The fact that you are assigning a distance at some point to a vertex does not mean that it will be final. It will be final only when this vertex have the minimum distance in the set Q and it will be the one to be picked next and removed. I hope I am clear.

# Answer
> 1 votes
D would not yet have become the current node. A node can only be marked as visited if all of its connections have been explored, to explore it must be the current node selected. To be selected it must have the lowest weight assigned to it, B would have already been visited and d's value updated to reflect that since b has a value of 10 and D is a value of 105, Its a priority queue, not a regular queue that you use.

---
Tags: algorithms
---


# Question
Title: What is the algo used for Phonetic Search
I am new to the field of text mining. Could not figure out what to search on google so am here for the same help. When we talk of approximate / fuzzy string match. searching for RAT would give RAAT too. i have used utl\_match.edit\_distance in oracle. searching for BAAT would give BAT. but if i search for RAT. it would return BAT, CAT, etc. How does google bring the phonetically same rhyming / sounding words eg if some one does'nt know spelling of 'Schwaznegger', even then correct data is brought by google. For 'levenshtein distance', cat and bat are pretty close but for google. closest to cat is kat not bat. Please tell me what we call such a search and what algorithms are used for it. Thanking you in advance for patience.

# Answer
Take a look at Soundex, Levenshtein edit distance, and related ideas.
> 1 votes

---
Tags: search-algorithms
---


# Question
Title: Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?
On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the **software application** of that concept.

I'd like to write a simulation of Japanese Multiplication to get benchmarks on large calculations utilizing the shortcut vs traditional CPU multiplication. **I'm curious as to whether it makes sense to try this.**

**My Question:** I'd like to know whether or not a software math shortcut, as described above is actually a shortcut at all.

This is a question of programming concept. By utilizing the simulation of Japanese Multiplication, **is a program actually capable of improving calculation speed? Or am I doomed from the start?**

---

**The answer to this question isn't *required* to determine whether or not the experiment will succeed**, but rather whether or not it's logically possible for such a thing to occur in any program, using this concept as an example.

---

**My theory** is that since addition is computed faster than multiplication, a simulation of Japanese multiplication may actually allow a program to multiply (large) numbers faster than the CPU arithmetic unit can. I think this would be a very interesting finding, if it proves to be true.

If, in the multiplication of numbers of **any immense size**, the shortcut were to calculate the result via less instructions (or faster) than traditional ALU multiplication, I would consider the experiment a success.

# Answer
> 4 votes
When considering algorithms for multiplying large numbers, the first think to keep in mind is the asymptotic complexity. Generally speaking, algorithms with better (smaller) asymptotic complexity are faster, though this only goes so far. So the first thing to do to find out whether Japanese multiplication is "worthwhile" is to calculate its asymptotic complexity. You have to be careful with respect to the model of computation, but in your case it probably won't make a big difference; probably your algorithm has "bad" asymptotic complexity.

The second thing to notice is that the multiplication logic is already there in the CPU, and no code that you can write will be faster than calling the built-in multiplication instruction. Of course, this is only good for multiplying machine words (or multiwords, in some cases). That means that your algorithm had better take advantage of the multiplication capabilities of your processor. While not affecting the asymptotic complexity, it does considerably affect the constants. All fast multiplication algorithms use machine multiplication instructions.

The best way to know whether the algorithm is any good in practice is to program and optimize it. Use a language like C which produces fast code, and then you can compare it to libraries such as GMP. This is the only convincing way to claim that your algorithm is better than existing ones, though you should expend some effort on optimization.

Finally, you claim that Japanese multiplication is better than CPU multiplication algorithms since it only uses addition. Textbook multiplication algorithm also only use addition, since everything is in binary. But probably this can be optimized further at the expense of using more gates, by having logic for small multiplications. You can look up what algorithms CPUs use, perhaps they're similar to Japanese multiplication.

# Answer
> 2 votes
The method shown in the picture is essentially the same as the standard algorithm (long multiplication) taught in many schools. Since this way of doing multiplication is common knowledge, I don't expect it would help you speed up multiplications on a computer... unless you think the idea of performing small multiplications with overlapping lines would somehow be faster than normal circuit design.

To see why this method is the same as long multiplication, let's say we're multiplying abc * def. With Japanese multiplication, you compute five numbers: cf, bf+ce, af+be+cd, ae+bd, and ad. Then you add them together, adding the tens digit of each to the ones digit of the next, to produce the sum cf + 10(bf+ce) + 100(af+be+cd) + 1000(ae+bd) + 10000ad.

Compare this to long multiplication. You first compute the three numbers cf+10bf+100af, ce+10be+100ae, and cd+10bd+100ad. But the second number is shifted to the left by one digit, and the third number by two. So when you add them, you get (cf+10bf+100af)+10(ce+10be+100ae)+100(cd+10bd+100ad), which is equivalent to the answer we got from Japanese multiplication.

---
Tags: arithmetic, binary-arithmetic, mathematical-programming
---


title: Is 2**x faster to compute than exp(x)?

text:
# Question
Title: Is 2**x faster to compute than exp(x)?
Forgive the naïveté that will be obvious in the way I ask this question as well as the fact that I'm asking it.

Mathematicians typically use $\exp$ as it's the simplest/nicest base in theory (due to calculus). But computers seem to do everything in binary, so is it faster on a machine to compute `2**x` than `Math::exp(x)`?

# Answer
Since this is CS and not Stackoverflow, I'm going to assume that you're asking a question about numeric analysis, and (to keep things simple) IEEE-754 floating point in particular. In that case, the answer to your question partly depends on what you mean by "easier", and partly on the details of the system.

No modern CPUs that I'm aware of have an instruction built in which does exactly what you'd expect either for either the $e^x$ operation (which henceforth we will call `exp`, its usual name in C) or $2^x$ (`exp2`). They are both implemented using library functions.

As is the case with all numeric methods for transcendental operations, there are a few special cases to consider:

```
exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

```

However, there is another thing that makes the problem slightly less complicated: the useful domain is quite small. For binary32, `exp(x)` underflows if $x \< -104$ or so, and overflows if $x \> 88.7$ or so. Unusually for transcendental operations, we can also ignore the subnormal case, since `exp(x)` is indistinguishable from `1.0` if `x` is subnormal. All of the above is also true for `exp2`, except that the domain is slightly different.

Your intuition is right in that most implementations compute $e^x = 2^{x/\ln 2}$. However, the cost of that multiplication by $\frac{1}{\ln 2}$ is trivial compared to the rest of computing `exp2`. A typical method uses a precomputed table with $K$ elements:

$$\hbox{exp2}(x) = 2^n \times T\[j\] \times P(y)$$

where $n$ is the integer part of $x$, the table $T$ contains values of $2^{j/K}$ for all $j$ in the range $\[0,K)$, and $P$ is some polynomial approximation to $2^x$ (quartic is sufficient for binary32) in the range $\[0,\frac{1}{K})$. The $2^n$ part is cheap, since it's just manipulating the exponent. $T$ is a lookup table. So $P$ is likely to be the expensive part of the operation.

I should point out for completeness that Intel x86 FPUs include an instruction called `f2xm1`, which computes $2^x-1$ for $x$ in the range $\[-1,1\]$. However, on a modern CPU, this is a fairly expensive and non-pipelined instruction, and you are highly discouraged from using it. As the Intel Optimization Reference Manual Section 3.8.5 rightly notes:

> Although x87 supports transcendental instructions, software library implementation of transcendental function can be faster in many cases.

**Edit:** It's been pointed out in the comments that I should explain some of the new terminology used in IEEE 754-2008. Some of the language has changed since 1985 and 1987, and most people are far more familiar with the old jargon.

The terms "binary32" and "binary64" are the new names for 32-bit and 64-bit binary floating-point numbers, which the old standard called "single" and "double" respectively.

The term "subnormal number" replaces the previous term "denormal number" or "denormalized number".
> 19 votes

# Answer
If by `2**x` you mean $2^x$, then yes. We can use the left-shift operator `<<`, i.e. we compute `1 << x`. This is lightning-fast as it is a primitive machine instruction in every processor I know of. This can not be done with any base other than 2. Moreover, integer exponentiation will always be faster than real exponentiation, as floating point numbers take longer to multiply.
> 7 votes

# Answer
If `2**x` is a function on integers, then I agree with Stephen's answer, shift is cheaper. But I typically see that as `2^x` and `**` to indicate floating point exponentiation. For this case, I would expect similar performance between `**` and `^` since both `exp` and `pow` (the underlying operation for `**`) are both transcendental approximation operations.
> 2 votes

# Answer
Since 2^x = e^(x * ln 2) and e^x = 2^(x * log2 (e)), you wouldn't expect much difference.

For x close to zero, one would usually use a polynomial e^x = 1 + x + x^2/2 + x^3/6 ..., nicely optimised to cut off as soon as possible while keeping the rounding error small. Clearly 2^x is a tiny, tiny bit slower to calculate. "x close to 0" would usually be values of x where sqrt (1/2) \<= e^x \<= sqrt (2). Restricting the range of x makes sure that the polynomial degree need not be chosen too high.

For larger x, one would usually calculate 2^x by letting x = x' + x'', where x' is an integer and -0.5 \<= x'' \<= 0.5. 2^x' would then be calculated by constructing a floating point number with the right bit pattern, and 2^x'' by using the e^x method for small x. Here, 2^x is a tiny bit faster. Moreover, if x is largish (say x = 100.3), just multiplying x by log2 (e) would introduce an unacceptable rounding error (because there are many fewer fractional bits), so more care needs to be taken.

And hopefully a good library function would take care that whenever x \<= y, e^x \<= e^y and 2^x \<= 2^y, no matter what the rounding errors are. Achieving that kind of thing can be tricky.

Important to notice: If you want to calculate one function, and the other has a faster implementation, you can bet that multiplying your argument with a suitable constant and calling the faster function will not gain you any speed, and may lose substantial precision.
> 1 votes

# Answer
You've got to understand that math on a computer is done in different ways by different software, hopefully coming up with consistent answers. Looking at most software I think computers behave like well - computers and will calculate the answer the long way around even for like 0^0. The problem is that special cases involve "recognition" which doesn't occur for free in digital computers. This means that only in those cases where having the answer will speed things up "the most" will optimization occur. But in those cases it will occur extremely well. Also note that several different recognitions may have to be done to get the right answer. This is called speed optimization levels and this has occurred to the maximum professional extent in the basis of most software called GNU "C". This is because here minute differences in run time from software to software and machine to machine is used there as quality acceptance figures. In other interpreters usually only if a "zero flag" occurs as a side effect of previous calculations will speed up recognition be performed. such as 0 * x =\> C0.
> 0 votes

---
Tags: binary-arithmetic, numerical-analysis, numeral-representations
---


title: Number of phrases of LZ compression

text:
# Question
Title: Number of phrases of LZ compression
It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon\_n)\log\_2 n}$$ With $\epsilon\_n\to 0$ for $n\to\infty$.

The proof is made in Thomas & Cover: Elements of Information Theory (Lemma 12.10.1, page 320 in the linked chapter).

I tried to generalize it to an alphabet of size $k$ by adjust the proof step by step, but I failed. So, my question:

How can I prove that the number $c(n)$ of phrases / tupel of the LZ compression is bounded by $$c(n)\leq\frac{n}{(1-\epsilon\_n)\log\_k n}$$ for all words of length $n$ over an alphabet of size $k$ with $\epsilon\_n\to0$ for $n\to\infty\\;?$

# Answer
> 4 votes
You don't need to redo the proof for this, simply note that $n$ symbols of an alphabet of size $k$ can be represented with $n \log\_2(k)$ bits. The Lempel-Ziv bound is then:

$\mbox{# phrases} \leq \frac{n log\_2 k}{(1-\epsilon\_{n \lg k})log\_2(n \log\_2 k)}$

Dividing numerator and denominator by $\log\_2 k$ then gives:

$\mbox{# phrases} \leq \frac{n}{(1-\epsilon\_{n \lg k})\left(log\_k(n) + \log\_2(\log\_2(k))/log\_2(k)\right)}$

Since $\epsilon\_n \longrightarrow 0$ as $n \longrightarrow \infty$, the result follows.

---
Tags: information-theory, data-compression, lempel-ziv
---


title: Word classification algorithms

text:
# Question
Title: Word classification algorithms
I am looking for algorithms to classify words in a paragraph of text. I am particularly interested in a classification to determine if a certain word is noun, verb, etc., but also looking for any kind of word-classification algorithms. I am given a smaller input (e.g. 200 words) so there is no many options for machine learning but I would really appreciate algorithms involving machine learning.

# Answer
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 history of the last 2 tags you have assigned to the 2 previous words in the sentence as well as the list of all the words in your sentence.
* Let $t$ be the tag you assign to the current word.
* You defined many features $f\_i(h, t)$, typically some indicator functions like $f\_i(h, t)=1$ if current word ends with 'ing\`, $f\_i(h, t)=0$ otherwise.
* $v$ is a parameter vector with the same number of elements of the number of features $f\_i(h, t)$. $v$ is used to weight the features.
* You define $p(t\_i|t\_{i-1},t\_{i-2},w\_1,...,w\_n) = \frac {\exp \left( \sum\_{i} v\_i f\_i(h, t) \right)\ }{\sum\_{t'} \exp \left(\sum\_{i} v\_i f\_i(h, t') \right)\ }$ (this is named multinomial logistic regression, a.k.a. maximum entropy (MaxEnt) classifier, multiclass logistic regression, polytomous logistic regression, softmax regression.)
* Use Markov assumption: $p(t\_1...t\_n|w\_1...w\_n) = \prod\_{i=1}^{n} p(t\_i|t\_{i-1},t\_{i-2},w\_1,...,w\_n)$ (that's the probability that your sentence $w\_1,...,w\_n$ has tags $t\_1,...,t\_n$)
* You find the $t\_1,...,t\_n$ that maximizes $\prod\_{i=1}^{n} p(t\_i|t\_{i-1},t\_{i-2},w\_1,...,w\_n)$ using the Viterbi algorithm: that's the final tagging of your sentence.
* You train the model ($v$) so that it maximizes the likelihood of your training set (and add some regularization to improve generalization)

Most of the work to improve this main idea is about:

* Finding better features
* Do some reranking (e.g. Global Linear Models, which allows to define global features that take as inputs the entire tagging history, and not just the last 2 tags as before, whose feature weights are trained with some gradient descent like algorithm)

As usual, the more data, the better.

For more details see Coursera's Natural Language Processing by Michael Collins (Coursera's Natural Language Processing by Dan Jurafsky and Christopher Manning is great too).

Note that the task to locate and classify elements in text into pre-defined categories such as the names of persons, organizations, locations, expressions of times, quantities, monetary values, percentages, etc. is called Named-entity recognition.
> 5 votes

# Answer
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 some sort of machine learning approach and will probably require a large training set (200 words won't be enough).
> 5 votes

# Answer
Sadly, the English language has denied even the most brilliant Scientists a way to answer this question. I have been working in the area of geometric representations of the English Language for Memory Modelling and I've (maybe somewhat prematurely) come to the conclusion that the unbalanced laws of the English language allow it to mutate continuously with often contradictory and logically infeasible states.

Still the game is great to play and I can see no reason that with the right direction a computer of an imaginable amount of muscle could possibly implement learning algorithms to properly understand the nature of the English Language.

....Quantum Mechanics does provide some interesting leads though :-)
> 0 votes

---
Tags: machine-learning, natural-language-processing, classification, computational-linguistics
---


# Question
Title: Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

# Answer
Your language is equivalent to the language $a^ib^ib^{2k}c^k$, and since concatenation is associative, this is equivalent to $(a^ib^i)(b^{2k}c^k)$.

A PDA for the first of these parts pushes an $a$ for each $a$ it sees and pops an $a$ when it sees a $b$. If the topmost stack symbol after this is $Z\_0$, transition to the second PDA, which pushes a $b$ for every two $b$s it sees and then pops a $b$ for every $c$ it sees, accepting if, after this, you end up with no input and $Z\_0$ as the topmost symbol.
> 7 votes

# Answer
Hint: The PDA has three phases: an $a$ phase, a $b$ phase and a $c$ phase. Your goal in the $a$ phase is to "compute" $i$ by strong an appropriate load on the stack. Your goal in the $b$ phase is to compute $j-i$. Finally, your goal in the $c$ phase is to compare $j-i$ to $2k$.
> 6 votes

# Answer
Hint: find a PDA for the language $\\{a^kb^k:k\ge 0\\}$ and apply it twice.

The other approach is to find a grammar for the language and convert it to an equivalent PDA. Here is the grammar version:

$S \to AB \mid \epsilon$

$A \to aAb \mid ab$

$B \to bbBc \mid bbc$
> 5 votes

# Answer
I think the best solution would be to form the CFG first and convert it to the equivalent PDA. the CFG can be constructed as follows: there are 2 cases:
1\> an a for a b
2\> a c for 2 b's

so when you add up, you make it equalized.

i.e.,
S -\> AB
A -\> aAb / epsilon
B -\> bbBc / epsilon
> 0 votes

---
Tags: pushdown-automata
---


# Question
Title: Is a supercomputer more powerful than the total of all the world's computers in 2004?
The supercomputer I am researching has 2.2 petaflops and boasts total memory of 1000 terabytes and disk space of 23.5 petabytes.

Is this more computing power than the total of the entire worlds computing power 10 years ago (2004)?

# Answer
No, and not by a long way.

Take 25,000,000 ordinary desktop PCs from 2004. To exceed the supercomputer you're talking about, each would need an 88megaflop CPU, 40Mb of memory and a 940Mb hard disk. In 2004, CPU clock frequencies were already in the GHz range, RAM in the hundreds of megabytes and hard drives in the gigabyte range. And there were many more than 25,000,000 computers in the USA, let alone the world.
> 9 votes

# Answer
EDIT: I realize my answer is a bit off-topic, but I let it anyway, it could interest the OP.

I cannot tell you if the most powerful supercomputer today is more powerful than the sum of all computers 10 years ago (I don't think so), but I can tell you that the most powerful supercomputer today is about **30 times** more powerful than the sum of the **best 500 supercomputers in the world** 10 years ago: http://top500.org/statistics/perfdevel/
> 1 votes

# Answer
Here's another way to think about it that might help your intuition a bit. Moore's Law states that transistor density double every 1 to 2 years (you'll find varying numbers here). Let's be optimistic and assume that this correlates to a doubling of computing power every year. In 10 years we should expect supercomputers to be roughly $2^{10}$ (1024) times as powerful as they are now.
> 0 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Why is Mixed Quantified Horn SAT in PSPACE?
I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE?

My study: To prove QSAT to be in PSPACE: Generate a boolean tree or circuit and evaluated it in O(n) space. Similarly, it has been done for the "Geography " problem and "GO" problem. SO, I think it should be possible to do for the mixedQhorn problem in the same way.

# Answer
To show that a problem is in PSPACE is quite straightforward: you show that it can be solved by a deterministic Turing Machine using polynomial space.

So basically you just write an algorithm solving the problem. You can use as much time as you like, as long as you only ever use a polynomial amount of memory.
> 2 votes

---
Tags: complexity-theory, algorithm-analysis, logic, satisfiability, space-complexity
---


# Question
Title: generate possible inputs valid for automata
I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not.

Can we do the reverse ?

I am looking for solution which generates few possible inputs (not all) accepted by automata(NFA/DFA).

One of the Brute-force approach can be to randomly select inputs and validate with automata if passes then consider those as desired .

But really don't want that . What really am i looking for here, can we use automata itself for produce possible inputs which are accepted by automata.

Any approach also would be helpful.

# Answer
> 6 votes
Just do a BFS from the start state, and at every node keep track of what transitions you took to get there. Obviously this will only generate a finite number of words, as it doesn't follow cycles.

# Answer
> 3 votes
A way to generate strings accepted by a given DFA is to start at the initial state, and follow a random transition out of the current state at each step, recording the symbol(s) that would give this transition. Output the result each time you reach a final state, backtrack when you hit a dead state. Collect a few strings each run, and start over to get another path through the DFA.

I'd minimize the DFA beforehand to make this more efficient.

# Answer
> 3 votes
Another way to think of the process described in the other answers is as follows:

1. Convert the DFA into a Regular Grammar (use the one that puts the nonterminal on the right, for convenience)
2. Assign $L\_0 = \\{S\\}$ where $S$ is the start symbol for your grammar.
3. Iteratively compute $L\_{i+1}$ from $L\_i$. All sentences in $L\_i$ will end with a single nonterminal; they are of the form $\alpha X$ where $\alpha$ consists only of terminals (maybe empty). Now, for each $\alpha X \in L\_i$, consider all $\alpha \beta$ where your grammar has a production of the form $X \rightarrow \beta$. If $\alpha \beta$ consists only of terminals, it's a string in the language accepted by the DFA; otherwise, it belongs in $L\_{i+1}$. If $L\_{i}$ is ever empty, then your DFA accepts a finite language.

This might be a bit more natural, since grammars are typically thought of as generating languages anyway (whereas automata are usually thought of as recognizing or accepting strings).

---
Tags: formal-languages, automata, finite-automata
---


title: Moore's law and Clock Speed

text:
# Question
Title: Moore's law and Clock Speed
This figure says according to moore's law number of transistors doubles about two years. but clock speed, power flattening after given stage. can anyone describe the reasons this flattening in clock-speed. Why can't we increase the clock speed more and more?

# Answer
> 3 votes
Here is a link to a similar discussion in another stack exchange where the causes are explained.

# Answer
> 8 votes
There are two different "laws" being graphed here, *Moore's law*, and *Dennard scaling*. Moore's law is an economic observation, made by Gordon Moore in 1965, that predicts that the number of transistors on a die will tend to double about every two years. It does not seem to be slowing down (yet). While there are reasons to believe that transistors will stop scaling down soon (14nm is 140 Angstroms (about the width of 140 hydrogen atoms)) it may be possible to continue Moore's law scaling for some time, either by making bigger chips (what Moore originally predicted) or by stacking multiple layers of transistors in the 3rd dimension.

Dennard Scaling, on the other hand, is an observation, made by Robert Dennard in 1974 that every time you scale down the width of a CMOS gate by a factor of 2, you can reduce both supply voltage and the threshold voltage by a factor of 2, the clock frequency can improve by a factor of 2, and the power density will stay constant. (Or you can scale down the voltage by less than 2, and you'll get a *better* than 2x clock frequency boost, but an increase in power.) When Dennard's observation was made a CMOS transistor was about 5 micron = 5000 nm wide. (So we've scaled transistor widths by a factor of about 360 in about 40 years.)

The limit that showed up in the early 2000s has to do with threshold voltage. Clock frequency (at a particular transistor size) is at best proportional to $V\_{dd} - V\_{th}$ (supply voltage minus threshold voltage), but as you scale $V\_{th}$ down leakage current (and power) increases exponentially. That was fine from 1974 to about 2000 because $V\_{dd}$ was much larger than $V\_{th}$. (In 1974 $V\_{dd}$ was usually about 12V.) So we could hold $V\_{th}$ at around a volt or so, and just change $V\_{dd}$. But now with $V\_{dd}$ around 1.3V and $V\_{th}$ around .5V, we can't scale voltage much anymore (without dramatically increasing leakage power.)

# Answer
> 1 votes
the topic of semiconductor scaling is very complex and multidimensional but basically, performance gains in clock speed could come with increased power applied to the chip. but when the gate widths and gate densities get very small (which is not graphed above but is roughly closely related to gate counts which is graphed) the power dissipation (heat) is much more challenging. essentially there is a ceiling where heat cannot be removed any more effectively or faster from the chip except with very expensive and increasingly impractical (unviable) systems eg liquid cooling. some of this heat is due to the following current leakage issue into the chip at a certain gate width reached mid 2000s:

> This expanded version of Moore’s law held true into the mid-2000s, at which point the power consumption and clock speed improvements collapsed. The problem at 90nm was that transistor gates became too thin to prevent current from leaking out into the substrate.

the quote comes from this basic summary of the issues:

---
Tags: computer-architecture
---


# Question
Title: if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$
I'm looking for a proof to the claim stated in the title:
if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$.
I read the proof from my professor's recitation, but couldn't understand it, and I was hoping to find more easy-to-understand version of that proof.
It goes something like that:
Let $L\in NP\cap Co-NP$ be an $NPH$ problem, and let $L'\in Co-NP$, our goal is to first show that $L'\in NP$.
We know that there exist a **Cook** reduction from $L'$ to $\bar{L'}$ (any problem can be reduced to its complement with Cook reduction), and since $\bar{L'}\in NP$, we also know that there exist a **Karp** reduction from $\bar{L'}$ to $L$.
So by transitivity, we have a reduction from $L'$ to $L$.
The only problem is, $NP$ is not closed under Cook reduction (if a problem $A$ can be reduced to a problem $B\in NP$ with Cook reduction, that doesn't mean that $A\in NP$...)
So define the relation $R\_{L'}$, associated with $L'$ (meaning $R\_{L'}$ is the search problem of $L'$) as follows:
$R\_{L'}=\left\\{(x,\[(z\_1,\sigma\_1,w\_1),(z\_2,\sigma\_2,w\_2),...(z\_t,\sigma\_t,w\_t)\]) \right\\}$
Now if we can prove that $R\_{L'}$ can be decided with a deterministic polynomial verifier, and that for all $(x,y)\in R\_{L'}$, $|y|\leq p(|x|)$ for some polynomial $p$, we're done, and that will prove that $L'\in NP$...
Now comes the part where I really lost him, he starts to rattle on and on about "questions" and "answers", and I completely lost track.
Can anyone provide a link that explains the rest of that proof more clearly?

# Answer
> 8 votes
Suppose $L$ is an NP-hard problem in coNP, and let $M$ be any problem in NP. Since $L$ is NP-hard, there is a polytime reduction $f$ such that $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$: given an input $x$, compute $f(x)$ and apply the coNP algorithm for $L$. This shows that $M$ is in coNP. In other words, NP is a subset of coNP. The same argument also shows the reverse inclusion, and so NP equals coNP.

The key idea is to avoid Cook reductions, for the reasons you mention.

---
Tags: np-hard, np
---


# Question
Title: Iterative Byzantine consensus in directed graphs with unbounded malicious nodes
I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or http://arxiv.org/pdf/1203.1888v1.pdf) but they all assume that a fraction of the peers aren't faulty or malicious.

Are there procedures to reach consensus among honest peers when there is an unbounded amount of faulty peers, but such faulty peers are only very sparsely connected to the cluster of honest peers?

A typical example would be a web of trust where it is trivial for an attacker to create millions of peers, but hard to receive trust from the main cluster.

I realize that, as such, the problem isn't very well defined. The honest cluster may have sub clusters, and it's unclear why they should be able to influence each other's consensus, while clusters of dishonest nodes may not. Typically, a solution would exhibit a threshold effect depending on connectedness.

# Answer
As you are probably well aware, it is provably impossible to reach consensus if a majority of the peers are faulty, malicious, or dishonest, if we assume they are all fully connected (as is typically the assumption for distributed systems).

If you are imagining that for some reason honest peers are better-connected than faulty/malicious peers, well, there are two problems with that model:

* The first problem is that the model is not realistic. In practice, faculty/malicious peers are typically just as well-connected as honest ones. In the case of unintended software faults, there is no reason to expect that connectivity will be at all correlated to software failure rates. In the case of malice (e.g., peers that are compromised or dishonest), well, attackers can typically arrange to be as well-connected as the honest peers, and can often arrange to be even better-connected.
* The second reason is that if we really did have such a separation, the problem would become trivial. For instance, we could just pick a threshold and ignore all peers whose connectivity is below that threshold. If this ensures that a 2/3 majority of the remaining peers are honest and non-faulty, then this reduces to the standard Byzantine consensus problem.

But ultimately I think it is the first problem that is the big one. It would only make sense to even think about such a setting if we had some sample application where there is evidence that your assumption is valid. Lacking that, there is not a clear reason to study such a model.

---

The web of trust doesn't actually seem to meet your assumptions, unless you are very careful about how you define them. An attacker can create one dishonest node $x$ (that is connected to a few honest peers), and then create lots of additional dishonest nodes $y\_1,y\_2,\dots,y\_n$ and have $x$ endorse all of the $y\_i$'s. The $y\_i$'s can also endorse lots of honest nodes. Now, at least by some measures, the $y\_i$'s are well-connected. There is also the risk of Sybil attacks, where the attacker creates many fake identities ("Sybils") and gets them connected to many honest nodes.

In the cryptographic world, you could look at the research directions under the catch-phrases "reputation systems" and "trust metrics". Some of them *are* designed to estimate the amount of trust one can have in a node, based upon its connectivity and the endorsements that nodes make in each other. However, academic research hasn't had a ton of impact in practice, because it is hard to make them work well in practice, and because Sybil attacks are hard to stop.
> 2 votes

---
Tags: algorithms, graphs, cryptography, fault-tolerance
---


# Question
Title: How to obtain a trilateration ordering in a graph?
In a sensor network graph $G = (V,E)$
$V = \\{1,2,...,n\\}$ is the set of sensors and the edge $(i,j)$ denotes that sensor $i$ and sensor $j$ are inside each other's sensing range. The weight of that edge denotes the Euclidean distance between the corresponding sensors.
The problem is in 2D.

Our goal is to fix the positions of three sensors and find the positions of the remaining.
Starting from 3 nodes (seed nodes), we first start the localization by finding a common adjacent of those 3 nodes.
Determining the position of a fourth node using three already localized node is called trilateration.

We expand the localization using trilateration. We have a localized node set, and each time we search for three nodes from that set that has a common unlocalized adjacent.

When we find such node, it does not mean it is localizable.

A trilateration ordering is: starting from three nodes, the list of vertices denoted by $a \rightarrow i, j, k$ so that when followed, the localization process is completed unless there can be no improvement.

For instance:
$1 \rightarrow 5, 6, 7$
$2 \rightarrow 5, 6, 7$
$4 \rightarrow 5, 6, 7$
$8 \rightarrow 1, 2, 4$

Is a trilateration ordering.

My question is:

How to obtain such ordering, starting from three seeds, without checking the same node triplet twice and without skipping any node triplet.

# Answer
> 3 votes
## Focus on the right problem

I suspect you will find that the most important challenge is not finding a trilateration ordering, but rather choosing a strategy that minimizes the localization error.

It is easy to find a trilateration ordering, as I will describe below. In contrast, minimizing the error is more challenging. Trilateration might actually not be the best way to minimize the error. For instance, when trying to localize a node, it is possible that you might get better accuracy by using four neighbors (e.g., doing multiple trilaterations) and averaging. Also, the order in which you do the localization might matter. If you choose a bad order, errors might accumulate.

So, I suspect you might not be focusing on the right problem.

## Answering your question as posed

I'm going to answer your problem as posed, even though I'm not sure it is the right problem.

There is a trivial, straightforward algorithm to solve your problem. You simply enumerate all possibilities. That can be done as follows:

* Let $S$ denote the set of nodes that are currently localized. Initially, $S$ includes just the three seed nodes.
* Repeat the following, until $S$ includes all nodes (i.e., until $S=V$):

+ For each node $v \in V\setminus S$, for all triples $s,t,u \in S$ of three nodes in $S$:

    - If $s,t,u$ are all adjacent to $v$, then append $v \to s,t,u$ to your trilateration order. Assuming localization of $v$ doesn't fail, add $v$ to $S$, and continue to the next iteration of the outermost loop.

The running time is $O(n^5)$, i.e., polynomial in the size of the graph.

With standard optimizations, the running time can be reduced significantly. For instance, you can use a worklist $W$ of nodes that are adjacent to some element of $S$ but not in $S$ themselves (i.e., $W= \\{w \in V \setminus S : \exists s \in S . w \in N(s)\\}$). You can update this worklist efficiently. You can also use a priority queue to sort the elements of $W$ by their "degree" (i.e., the number of nodes in $S$ they are adjacent to), and you can update this ordering efficiently.

But since you didn't list any specific running time requirements, this should be sufficient.

## A better approach

I suspect that a better approach is to try to use statistical methods to estimate a global best-fit for the location of all sensors, simultaneously. For instance, you might use least-squares methods.

Let me illustrate what I mean. Suppose that you perform a bunch of measurements of the distances between pairs of sensors; create a graph $G=(V,E)$, where there is an edge $(v,w)$ if you have measured the distance between sensor $v$ and sensor $w$. Let $m(v,w)$ be the measured distance between $v$ and $w$.

Now our goal is locations of all the sensors that best fit these measurements. In particular, we are looking for a map $L : V \to \mathbb{R}^2$, where $L(v)$ represents the location of sensor $v$. We are given the locations of three seed nodes, say $v\_1,v\_2,v\_3$. Also, we are given approximate distance measures between pairs of nodes that are connected by an edge in $G$. We want to find a location map $L$ that minimizes the total error of the measurements. Thus, the *cost* of a location map $L$ might be given by the total squared error:

$$\text{cost}(L) = \sum\_{(v,w) \in E} (d(L(v),L(w)) - m(v,w))^2.$$

Here $d(p,q)$ represents the Euclidean distance between the two points $p,q \in \mathbb{R}^2$.

Now we want to find the location map $L$ that minimizes $\text{cost}(L)$, subject to the requirement that $L(v\_1),L(v\_2),L(v\_3)$ have their given values (the locations of the three seed nodes).

This is an optimization problem that can be readily solved using standard methods, e.g., least-squares fitting.

Your problem then decomposes into two parts:

1. Select a set of measurements to perform.
2. Solve the optimization problem, e.g., using least-squares best fit, to find the location of all sensors.

A simple approach to decide on a set of measurements might be: each sensor looks at the set of other sensors that are within in its range, and selects 5 of them at random (and ensures that each sensor has its distance measured against at least 3 other sensors, to ensure its location can be uniquely determined; hopefully most will be measured against more than 3 other sensors). Of course, you could adjust the parameter 5 based upon empirical accuracy/performance tradeoffs.

You could also imagine more sophisticated methods, e.g., where you perform a series of measurements, solve the optimization, look at the average error for each sensor (as a crude measure of how accurate its location might be), then perform a few additional measurements (e.g., only for sensors who average error in its location is too high), and solve the optimization problem again with the additional data.

I think you might find that this is a more effective and robust way to solve your localization problem.

I also encourage you to look at the literature on localization in sensor networks. There is *lots* of prior work on this problem. You know the saying: a month in the field can save you a week in the library. So, spend the week in the library, and first inform yourself about what has already been tried in the literature.

---
Tags: algorithms, graphs
---


# Question
Title: Training given pairs of similar values, not labels
I have pairs of "similar" values $(x\_i, y\_i)$ drawn from a space $x\_i, y\_i \in S$, and want to train a neural network $N$ such that $N(x\_i)$ would be "close" to $N(y\_i)$ for all $i$, yet, to make it useful, the overall image of $N$ would be as spread apart as possible. Note that the training data says which values are similar, but does not imply that values from different pairs are necessarily different (i.e. these aren't labels).

Defining a cost function to be something like $\frac{1}{2} \sum\_i \\| N(x\_i) - N(y\_i) \\|^2$ doesn't work, because $N(x) = 0$ would then be a trivial solution. Another option I considered is to require that, assuming the inputs are distributed with zero mean and unit variance, say, the outputs would be distributed with zero mean and unit variance too. I don't know how to efficiently enforce it though, or whether it would even give good results.

I see it as a kind of unsupervised learning with some "hints" provided.

So, my question is: what kind of problem is this? How to approach it? Can you direct me to any previous similar research?

# Answer
> 1 votes
I'm not convinced that a neural network is necessarily the right tool for this. When you have a hammer, it's tempting to think that everything looks like a nail... but sometimes the answer is "No, you dummy, that's a screw, use a screwdriver, not a hammer."

So, I'll comment on several kinds of methods you could explore, for your problem. I suggest you look into them all and see which works best in your specific application.

## Clustering

It looks like your problem is basically a clustering problem. There are many standard algorithms for clustering data. For instance, if your space is $S=\mathbb{R}^n$, many clustering algorithms are known. There are also many clustering algorithms known that can work on any metric space. I recommend you take a look at https://en.wikipedia.org/wiki/Cluster\_analysis to familiarize yourself with some of the standard methods, and look to see whether any of them might suit your application well.

## Neural networks and autoencoders

If you are set on using a neural network (which, again, might not be the right attitude), an alternative approach might be to learn an auto-encoder for the data. This is a standard way to use neural networks for unsupervised learning. This basically asks the neural network to find a way to project high-dimensional data down to some lower-dimensional space, in a way that preserves as much as possible of the structure of the original data. Empirically, it often seems to be an effective way to do unsupervised learning.

You could train a neural network in this way, and then use it to project your inputs to the lower-dimensional space and measure distances in the projected space. There are standard training algorithms to fit an autoencoder.

See also https://en.wikipedia.org/wiki/Neural\_network#Unsupervised\_learning and https://en.wikipedia.org/wiki/Autoencoder.

## Metric space embeddings

You might also want to look into the literature on metric space embeddings. A metric space embedding is a map $f:S \to \mathbb{R}^n$ from a metric space $S$ to $\mathbb{R}^n$, such that $f$ approximately preserves the distance metric on $S$. In other words, we seek to find $f$ such that

$||f(x)-f(y)||\_2 \approx d\_S(x,y)$$

for all or most $x,y \in S$. This is an embedding into $\mathbb{R}^n$ with the Euclidean norm (or into $\ell\_2$ if we don't care about the dimension $n$).

There's been a lot of work on this subject, including the computational aspects of learning/finding such embeddings. See, e.g.,

I'm not an expert on this subject, so there's probably more relevant work out there (e.g., in the machine learning or systems community).

---
Tags: machine-learning, neural-networks
---


# Question
Title: Convert $\lnot(x \oplus y \oplus z\oplus a)$ to CNF
How to convert the below formula to CNF?

> $\lnot(x \oplus y \oplus z\oplus a)$

# Answer
Use the Tseitin transform. It is a standard way to convert to CNF. It introduces additional variables, but keeps the number of clauses and variables relatively small.

You can also use very simple methods using De Morgan's laws (or Karnaugh maps or the Quine–McCluskey algorithm) to find an equisatisfiable CNF that does not introduce any new variables, but in general this will cause an exponential increase in the size of the CNF, which usually is undesirable.
> 6 votes

# Answer
## Step 1

Find all the cases that makes the function to be false. In our case we can just find all the *truth* of that formula:

> $x \oplus y \oplus z\oplus a$

I will write it down from left to write, from $x$ - $a$, 1 for *true* 0 for *false*.

```
0 0 0 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

```

Those will be the false cases for the main formula.

## Step 2

Now to get the **CNF** all what you have to do is to write them down with *not*. Because all the laterals connected with or signs, if we didn't wrote it down it will be true. So this is the **CNF** for that expression.

* $(\lnot x \lor \lnot y \lor \lnot z \lor a)$
* $(\lnot x \lor \lnot y \lor z \lor \lnot a)$
* $(\lnot x \lor y \lor \lnot z \lor \lnot a) $
* $(\lnot x \lor y \lor z \lor a) $
* $(x \lor \lnot y \lor \lnot z \lor \lnot a) $
* $(x \lor \lnot y \lor z \lor a) $
* $(x \lor y \lor z \lor \lnot a)$

In general this trick will work if all the variables appear in all the clauses.
> 1 votes

---
Tags: logic, normal-forms
---


# Question
Title: Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds
From Wikipedia, a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$, so that it satisfies

The two definitions should be equivalent. Do we need the augmentation property, for the following to be true:

> a set system $(E,F)$ is nonempty and has the hereditary property, if and only if it is an accessible system, and has the Interval Property without Lower Bounds?

Without assuming the augmentation property, it is simple to see that the "only if" part is true, but I wonder if the "if"part is also true? Thanks and regards!

---

Note:

A set system $(E,F)$ that is nonempty and has the hereditary property is also called an independence system.

---

The aforementioned properties are defined as follows:

* The empty set is in $F$. (nonempty property)
* if $X \in F$, then every subset of $X$ is also in $F$. (The hereditary property)
* for all $X,Y ∈ F$ with $|X| \> |Y|$, there is some $x ∈ X-Y$ such that $Y∪{x} ∈ F$. (The augmentation property)
* Every nonempty $X \in F$ contains an element $x$ such that $X-\\{x\\} \in F$. (I.e. $(E,F)$ is an accessible system)
* If $B, C ∈ F$ with $B ⊆ C$, then, for all $x ∈ E-C$, $C∪\\{x\\} ∈ F$ implies $B∪\\{x\\} ∈ F$. (the Interval Property without Lower Bounds)

# Answer
> 2 votes
Suppose that a set system $F$ is accessible and satisfies the interval property. We show that it is hereditary. Let $C = \\{x\_1,\ldots,x\_n\\}$ be any set. Without loss of generality, by accessibility we can assume that for all $t \in \\{0,\ldots,n\\}$, $\\{x\_1,\ldots,x\_t\\} \in F$. We show by induction that all subsets $B$ of $C$ are in $F$. If $|B| = 0$ then $B = \emptyset \in F$ (the case $t = 0$ above). Now suppose $B = \\{x\_{i\_1}, \ldots, x\_{i\_k}\\}$, where $i\_1 \< i\_2 \< \cdots \< i\_k$. By assumption, $A = \\{x\_{i\_1},\ldots,x\_{i\_{k-1}}\\} \in F$. Now $A \subseteq \\{x\_1,\ldots,x\_{i\_k-1}\\}$ and both $\\{x\_1,\ldots,x\_{i\_k-1}\\},\\{x\_1,\ldots,x\_{i\_k}\\} \in F$, and so by the interval property, $B = A \cup \\{x\_{i\_k}\\} \in F$.

---
Tags: combinatorics, sets
---