Linear programming application in machine learning assignment solution

Integer linear programming is a technique applied in statistical problems in which variables are restricted to be integers. It is one of the easiest ways to perform optimization. The technique is applied in a variety of disciplines, the most common being machine learning. Here, integer linear programming is used to train neural networks to fit models of functions in order to label data and forecast unknown future values.

This question requests a look into multi-object tracking using 0-1 linear programming. Some understanding and assumptions before answering:

- The project is encased around a video, meaning that there are different time samples, each of which is a different time in the video.

- The detector is already given, meaning that the objects have already been detected and our program is only tasked with tracking these objects.

- “Tracking” refers to following one object over the time segments along one track.

In order to answer this question, we know that 0-1 linear programming needs binary variables that will be put into a linear function and either minimized or maximized. In this case, we look towards an object ifound in time kand make some variables that will help us determine where it has gone for time j

Variable 1: First, a variable is needed to know whether or not object i is on a track/path, namely:

V1(i)= {(1 if object i is on a [email protected] otherwise)┤

Variable 2: Then, a variable is needed to know whether object iat time kisimmediately followed by object i2at time j :

V2(i,i2)= {(1 if object i is immediately followed by object i2 on a [email protected] otherwise)┤

Variable 3: Then, a variable is needed to know whether or not a track starts at object i:

V3(i)= {(1 if trajectory begins at object [email protected] otherwise)┤

Variable 3: Finally, a variable is needed to know whether or not a trackends at object i:

V4(i)= {(1 if trajectory ends at object [email protected] otherwise)┤

To get professional assistance with homework revolving around this topic, take our linear programming assignment help.

The objecting for this 0-1 linear program is as expected of any linear program, to take a linear function and minimize with respect to the constraints built based on the situation. In this situation, with the given variables, we in fact want to maximize the probability that the object ifollow a specific track across time. Basically; we look at a set of detections across time and find the best tracks that explain these detections as best as possible.

Assume all detected objects are inset “O”, and “T” are all tracks, we need to find the T that best explains the detections, this is by maximizing the probability that this is in fact the track that the object will take.

Best T= maximum probability(T|O)

With basic probability in mind, assuming that the events are independent and following the law of conditional probability:

Best T= maximum probability(O│T)*probability(T)

Which translates to:

Best T= maximum∏_i〖 probability(O_i│T) 〗*probability(T)

From the given assumptions “detections can only be matched to a single track.”We know that these tracks can not overlap, one detection to one track. This assumption allows us to treat every track independently of the rest, and thus decompose the equation:

Best T= maximum∏_i〖 probability(O_i)〗*∏_(t ∈T)〖 probability(t)〗

To learn more about this topic, avail our professional probability assignment help.

The linear program will find the best chance that an object is on a path by checking the variables mentioned before, it will try to minimize the cost when assuming that the object is on a track. That this track is followed by another object immediately after, and it will check whether this track starts or ends.

 As stated in part B, the linear program will be trying to maximize probability with respect to the variables described in part A and using constraints. We now will insert these variables and their constraints into a linear function along with the cost functions for these variables (now use minimum as we want to reduce cost):

Best T= minimum∑_i〖C1V1(i)+ 〗 ∑_(i,i2)〖C2V2(i,i2)+ 〗 ∑_i〖C3V3(i)+ 〗 ∑_iC4V4(i) 

The constraints for this program are extracted from assumptions given and from variables formulated:

The first constraint, all variables must be either 0 or 1, as this is an NP-hard 0-1 linear program, and does not allow any leeway

Constraint: V ∈{0,1}

The second constraint, due to the assumption that “tracks cannot be assigned more than once.”, this means that any trajectory can not have a value of more than 1, which means that if there is an observation, this is either the start, end or middle

Constraint: V1(i)+V3(i)≤1

Constraint: V1(i)+V4(i)≤1

This means that if V1 is 1, the object is on the trajectory and therefore cannot be in the start or end, otherwise, there would be an overlap in trajectories.

Next Constraints, the sum of all succeeding objects (flow of track) must be equal to the input and output of the track

Constraint: V1(i)+V3(i)=∑_i2〖V2(i,i2)〗

Constraint: V1(i)+V4(i)=∑_i2〖V2(i2,i)〗

Essentially, what this constrain means is that ∑_i2〖V2(i,i2)〗 will only ever be equal to 1 once, due to the assumption that there are not track overlaps, and due to this constraint. This means that if the object is at the start of the node, i2 will be the succeeding object, and if the object is at the end, i2 will be the preceding object.