Finding the first 1 in a binary set using optimization

Hello everybody,

Assume that a binary set V is given and the task is to find the first 1 in V. Note that

1) V is not sorted (so, we cannot benifit from binary search)

2) Although V is binary it is not known beforehand. It would be computationally expensive to tell

whether an element of V is 0 or 1. If I would know V then I could simple use the command find(V,1)

Therefore, I need to search efficiently. It seems that optimization is one efficient way to solve this problem. But,

unfortunately, it seems that the underlying optimization problem is not that easy to tackle. For instance, In

bellow, you see an example where I used genetic algorithm (I used this algorithm since it can tackle integer optimization problems)

clc;
A=[zeros(1,10^4) 1 zeros(1,100) 1 1 zeros(1,10^3)];
cost=@(i) i+10^8*(1-A(i));  % Here, in theory instead of 10^8, we should use 'infinity'
options = optimoptions('ga','Display','iter');
[x,f] = ga(cost,1,[],[],[],[],1,length(A),[],1,options)

Unfortunately, it often always fails to find the true solution which is x = 10^4+1. Rather it finds x = 1 as the

solution which is clearly wrong.

Any idea?

Thanks for your kind help in advance!

Babak

[Matt J]

First, it is confusing that you use A in your code, but V in your test.

Second, it appears that A=V is known beforehand, contrary to what you stated. At least, it is treated as known in your example optimization code.

[Mohammad Shojaei Arani]

I apologize to use different letters. I should have used V in my code.

Please note that, the code I wrote was only and only a test. Even for this easy case, when

we know the set V beforehand, the optimization fails to find the correct solution.

Further, with a simple manipulation, it is possible to convert this code to a one where the set V is not known in advance (I could write a more complex objective function (the function 'Cost') ) so that it first finds A(i) and then proceeds. It could be as follows

cost=@(i)Cost(i);

function cost=Cost(i)

% Calculate V(i) % In my actuall problem this is a length code

cost = i+10^8*(1-V(i));

end

[Sam Chak]

Hi @Mohammad Shojaei Arani

I'm attempting to visualize your situation as the quest for searching the first Calculus book relative to the first call number order at the George Peabody Library. Ordinarily, you would peruse the library's catalogue, and after pinpointing the book, you would employ the call number to find it.

Let's assume that the library's homepage is inaccessible, and the digital catalogue is unavailable as well. Consequently, you engage with multiple librarians to aid you in physically locating the book. Is the metaheuristic optimization approach you're utilizing comparable to this scenario?

Image by Matthew Petroff / CC BY-SA.

Answer 1

[Walter Roberson]

Imagine that you had a case where location P is set, that all positive integer multiples of P were also set. Then suppose you examine location #60. If it is not set then you can rule out locations 1, 2, 3, 4, 5, 6, 10, 15, 20, 30 -- so in this hypothetical situation in which information about the value of one V entry could give you definitive information about the value of an earlier V entry, then there would be the potential for strategies that are better than linear search.

However, in your description about your matrices, it is not obvious to us that information about a particular V entry gives you definite information about any other V entry.

Let us think for the moment about the possibility that knowing (say) V(10) is 1 gives you the probabilistic result that V(1) has only (say) 1e-10 probability of being 1. Can you skip examining V(1) in that case? No! If your accumulated information so far gave V(1) only a 1 chance in 2^64 of being 1, then you would still need to examine V(1), because the task is not to find a "good approximation" or a "bounded cost best-effort" solution, but is instead to find the first entry in V with value 1. Knowing a probability distribution might help guide you in choosing upper bounds, but as long as there is any remaining probability in the first entry not yet examined, you still need to examine it.

Now let us consider the case where examining an entry cannot rule out an earlier entry. Suppose you have examined V(4) and found that it is 1, but you have not examine V(1) yet. Can you stop? There is nothing obvious to us in your description of your task that would allow you to stop without examining V(1): as best the volunteers have been able to make out, even knowing V(2) is 1 would not allow you to rule out V(1) being 1. So you always need to examine V(1) as best we can tell. There is a 100% probability that you will need to examine V(1) . If you were to examine V(2) before V(1) and found the value of V(2), would you be able to skip V(1) ? Not that we can tell: if V(2) == 1 then as far as well can see you would still need to examine V(1) . But examining V(2) first has a cost, and if V(1) turns out to be 1, you would have wasted the effort of examing V(2) first.

Likewise, suppose you examine V(3) first and determine it is 1. You examine V(1) and find it is 0. Can you skip examining V(2) and assume that V(3) is the first? It is not obvious to any of us that you could do that: as far as we can tell, you would still have to examine V(2), and if V(2) is 1 then the cost of examining V(3) first would have been wasted.

Yes, if you first examine V(10) and then examine V(5) and determine V(5) is 1 then you can skip V(6) through V(9) -- but you would have wasted the cost of evaluating V(10) first, and would have been better off examining V(5) first.

In any situation in which examining a latter entry cannot rule out an earlier entry, then by induction you can show that the most cost effective method is to examine V(1) then V(2) then V(3) and so on. A linear search, in other words. There is a 100% chance you will need to evaluate V(1). If V(1) == 0 then there is a 100% chance you need to examine V(2) . If V(2) == 0 there is a 100% chance you will need to evaluate V(3)... and so on.

[Mohammad Shojaei Arani]

Yes. Makes sense. Thanks!

Answer 2

[Image Analyst]

Why not simply do

V=[zeros(1,10^4) 1 zeros(1,100) 1 1 zeros(1,10^3)];
index = find(V == 1, 1, 'first')

index = 10001

???

[Bruno Luong]

" Although V is binary it is not known beforehand"

[Mohammad Shojaei Arani]

Thanks!

The problem with your solution is that you have assumed that you know the set V, beforehand. Assume that it takes 30 seconds to find whether each element of V is 1 or 0. That is why I try to avoid the command 'find' and seek to solve my problem via optimization.

[Image Analyst]

Obviously V has to exist or else you can't do anything at all. And if it exists, then you "know" it (all its values are defined). However my code does not depend on it being binary or floating point, though it has to be numerical (not a structure or cell array or some other class). So I'm not sure why you say there is a problem with it or why it takes 30 seconds.

V=[zeros(1,10^4) 1 zeros(1,100) 1 1 zeros(1,10^3)];
tic
index = find(V == 1, 1, 'first')

index = 10001

toc

Elapsed time is 0.016965 seconds.

See, 0.016 seconds, not 30.

[Mohammad Shojaei Arani]

Sorry, I believe my explanation was not clear.

Look, I said "it takes 30 seconds to find whether an element of V is 0 or 1". for instance, if you ask me what is A(27) then I cannot tell you imediately (takes 30 seconds).

Yes, V exists and its elements are defined, for sure. The issue is that finding its elements is expensive.

I hope I was clear this time?

[Image Analyst]

Not really. Is there any difference between A and V? And if you want to somehow access A(27), like assign it to a new variable, that is virtually instant. Even generating a logical vector telling if A or V is exactly equal to 1 is virtually instant (unless A or V is hundreds of millions of elements long).

But it looks like your responses to @Bruno Luong that you don't really want find() regardless because you are trying to learn/use optimization, like a genetic algorithm or something: "I want to tackle it (via optimization) " and so are not interested in using standard, traditional functions.

[Mohammad Shojaei Arani]

Yes, A and V are the same (I should have always used V. Sorry)

Next, you did not get what I meant. Yes, if the set V is known beforehand then an operation like x = V(27) is super fast. But, what if V is not known beforehand? Do you want me to tell you my actual problem? Then it is long and deviates us from the core of the problem. But, to give you an example consider the following example:

Assume that the matric X is given. Assume further that we have a dynamical system and consider an equilibrium of this system. The task is to see whether each column of X being used as initial condition for the dynamical system eventually converges to the equilibrium E or not (for instance, it can converge to another equilibrium or it can diverge to infinity). Now, define the set V as: V(i) = 1, if the i-th column of X (used as initial condition for our dynamical system) ends up into E, otherwise V(i) = 0. How to know that i-th initial consition ends up into the equilibrium E? It either einds up into E or it wont. The only way we can determine V(i) is to simulate our dynamical system and see where it ends up. This is time conssuming. So, here, I gave you asn example where we have a binary set V but determining its elements is expensive.

Was this clear?

You are wroing to think that "I do not want to use the command 'find' because I am trying to learn/use optimization". By the example I gave you you will clearly see that the use of 'find' command is not practical. That is why I intend to use optimization. Is this clear?

Answer 3

[Bruno Luong]

You ask the same question several time. Without any other a priori knowledge, scan your array until 1 is meet.

There is no miracle algorithm to find it since there is not other way to guess where 1 first appears.

[Mohammad Shojaei Arani]

Yes and No.

In spirit this is similar to the question I asked yesterday. But, the way I want to tackle it (via optimization) is fundamentally different. This idea did not come to my mind yeasterday and nobody also mentioned it. From this angle this is never a repetitive question.

Your way of tavkling the problem is linear search whose complexity os O(n). However, an optimization is orders of magnitude cheaper than linear search. But, my question is this: "How to solve this problem via optimization?" (therefore, it is not a repetitive question)

[Bruno Luong]

"Your way of tavkling the problem is linear search whose complexity os O(n)."

Incorrect this is the worse case complexity.

The average complexity is O(p*n) where p is probailty of 1 to appeas.

There is no miracle algorithm, you waste your time.

[Mohammad Shojaei Arani]

OK Bruno,

But, its complexity should be something like O(0.5 n), on average. Look, if V=[zeros(1,10^6) 1]; (I know this is worst case) then it takes ages. But, using optimization it is much cheaper. Why? because, using optimization there is no need to inspect all the elements of V. Right?

the example V=[zeros(1,10^6) 1]; was worst case complexity for the linear search. But, even when the first 1 appears earlier still optimization is much cheaper. For instance, V=[zeros(1,10^4) 1 zeros(1,10^6)]; should be cheaper to solve via optimization than to follow a linear search. If I follow you strategy then I need to calculate 10^4 elements of V (imagine it takes 30 seconds for each) but it is clear that an ptimization should typically use much less operations (function calls) for this problem. Right?

[Bruno Luong]

" because, using optimization there is no need to inspect all the elements of V. Right?"

Wrong if your array is random without autocorrelation the optimization willl fail. That is so simple to build a count example.

Let assume the first 1 found by your miracle algo is presumed to be at position x. If your optmization evalutes less than x, meaning there is a hole somewhere in 1:x that is NOT evalute. Then I put a 1 there. Your optimzation fail to detect it.

So any algorithm needs at least x evaluations to detect correctly the first 1 at position x.

[Mohammad Shojaei Arani]

I did not completely understand your example but I agree with you that if the set V does not have autocorrelation then the optimization often fails (note that V is not random, it is deterministic but inspecting its values is time conssuming).

But, the elements of set V, often, have some rather high degrees of correlation. Therefore, if I can use optimization it should be compoutationally cheaper.

[Bruno Luong]

Whatever until the lesson is learned...

Answer 4

[John D'Errico]

If V is given, then find(V,1) is perfect, and it will not be improved upon. And you say that V is given! So what is your question?

MAYBE, MAYBE, you mean that V is given, but unknown in a sense, that you cannot know the value of V unless you interrogate that element? That seems consistent with your comments.

Now, your goal is to somehow magically use optimization to find that first element. The problem is, suppose you sample element 100, this V(100), and you find that is is a 1. Is that the FIRST element of V that is 1? You can never know. And nothing will tell you that is the case, unless you evaluate EVERY element that precedes that element. This tells me if your goal is to find the FIRST element of this unknown binary vector that is a 1, then you need to simply start at the beginning, and test every element. Optimization cannot help you, since the unit elements of V are presumed to be random as far as we know. Optimization is meaningless in this case. I'm sorry, but it is.

Ok, is there anything we can do? Suppose V has length 1024. Evaluate V at some intermediate position., say V(512). If V(512) is a 1, then you know that the first element that is a 1 must lie no further than element 512. But if V(512)==0, then you know nothing. Again, this suggests your best scheme is to simply start at the very begnning.

It feels like it might help if we know the probability that any element of V is a 1. Now you could use probability theory to know the distribution of the first non-zero element, if any element has probability P of being a 1. That could tell you where to start looking, but does it really help? NO. In the end, you will always need to test the first element of V, and if is zero, then test the second element, and so on, because knowing if a later element of V is 1 does not tell you anything.

I'm sorry, but if you absolutely need to know the first element of V, then you need to start your search at element 1, and then proceed. This is the only way to know if you have found the first 1.

[Mohammad Shojaei Arani]

Hi John,

First, thanks for the kind response and brilliant ideas!

The set V is deterministic but expensive to find its elements. I already gave an example from dynamical system (am not sure if you read it). But, I would like to tell you in bellow:

Assume that the matric X is given. Assume further that we have a dynamical system and consider a specific equilibrium of this system, say E. The task is to see whether each column of X (being used as initial condition) for the dynamical system eventually converges to the equilibrium E or not (for instance, it can converge to another equilibrium, a limit cycle, can diverge to infinity, etc.). Now, define the set V as: V(i) = 1, if the i-th column of X (used as initial condition for our dynamical system) ends up into E, otherwise V(i) = 0. How to know that i-th initial consition ends up into E? It either einds up into E or it wont. The only way we can determine V(i) is to simulate our dynamical system and see where it ends up (assume that this is a complex dynamical system with complex basins of attraction which is deficult to calculate). This is time conssuming. So, here, I gave you an example where we have a binary set V but determining its elements is expensive.

Now, I go back to your answer. You say that optimization is not usefull since, anyway, we need to start form the begining. Look at the following example

V=[zeros(1,10^5) 1 zeros(1,100) 1 1 ones(1,10^3)];

cost=@(i) i+10^8*(1-V(i));

options = optimoptions('ga','Display','iter');

[x,f] = ga(cost,1,[],[],[],[],1,length(V),[],1,options)

% Please note that in practice the cost function should be defined as bellow (I just defined it for the case when V is known, for the sake of clarity)

function cost=Cost(i)

% First, Calculate V(i)

cost=i+10^9*(1-V(i));

end

For this example the true answer is x=10^5+1. This code often finds x=100102 as the true solution but sometimes correctly finds the true solution. The function calls is often less than 4000. If I want to start from the begining then I have to calculate 10^5 values of V. In practice, in my V vector the first 1 does not, often, appear to be very close to the begining of V.

Does this clarify my claim that optimization is the way to proceed?

[Bruno Luong]

"Does this clarify my claim that optimization is the way to proceed? "

No, because it will fail to find the first 1. This is bound to happen as I and John told to you with logical argument.

Now if you accept that occasional failure then it's OK.

But why ask the question then?

[John D'Errico]

No. It does not at all justify your claim. Not even remotely.

An optimization will evaluate the vector V at multiple points. That you don't see that happening is irrelevant. You are not a little child, where if you don't see something happen in front of your nose, it does not happen. Function evals called by GA are no less costly than function calls in a loop, but in fact more costly, since you now have the overhead of GA.

A simple loop would have been more efficient, and the ONLY possible way to know that you have found the first true element in V.

An optimizer like GA will not know that no earlier element is 1, UNLESS IT TESTS ALL PREVIOUS VALUES. GA stops sometimes early, because it got lucky. And as you have seen, often GA will get it wrong. If you are looking for a probabilistic scheme, that MIGHT be different. But even then, I see no better scheme than to start at the beginning.

[Mohammad Shojaei Arani]

Yes. If the optimization does not work well but gives me an answer which is not so far from the first 1 then still I would be happy.

Anyway, thanks for your kind helps.