There are two things in world: (i) scalars (ii) vectors. Scalars have only one value i.e. only one dimensions, examples are numbers, boolean values, intensity of emotions etc. Vectors have multiple values i.e. multiple dimensions, examples are points, multi-column tables etc.
Its easy to compare scalars. Given a list of numbers its straightforward to tell which one is the largest or one among the largest ones. Vector analysis is very hard. A thing can be good in one aspect but bad in another aspect, how to tell that the goodness in one aspect is more important than the badness in the other aspect?
Lets have a situation. Suppose you are manager of three subordinates in a business organization. The organization have these four basic functions: production, accounting, marketing and customer interaction. Every subordinate provide some service in each of these functions but they are not equally good in any of these functions. Some employee is good in two things, average in the third thing and bad in the fourth thing. Another employee is good in some other set of functions, average in some other and bad in some other. How to tell which subordinate is the best among the three subordinates?
I have created this situation as a four dimensional vector analysis. The four dimensions are the four functions of the organization, in which each employee has some value. Each employee is a vector, so we have three vectors. To have an intuition about vectors, consider them as points in n-dimensional space.
The above situation is one of the knapsack problems. The classical knapsack problem has only two dimensions: weight and value (in dollars). You have a bag to fill with objects (vectors) where each object has a weight and a value (in dollars). The bag has a maximum capacity so total weight of all the objects that you put in the bag must be less than or equal to that capacity. The task is to fill the bag with as much cummulative value of objects as you can.
There is a long way to solve this problem which is quiet complicated. Infact the easiest solution that I can find is here on stackoverflow (please scroll down on that link to read the last comment). I really cannot understand why people do not offer a simpler solution, May be nobody has thought about it. Anyways, my solution is below and I think I am the first one to make it this simple.
Here is my algorithm to solve the knapsack problem:
Step 1: For each object, divide value with weight, so you get one number for each object. Lets call this number Efficiency Factor. Put these values in an array so we have one element in array for each object.
Step 2: Sort the Efficiency Factors array in descending order.
Step 3: For each element in array, put the element in the bag, till either the bag is full or the array exhausts.
The big O notation for the stackoverflow solution is O(nW) where n is number of items and W is the capacity of bag. The big O notation of my solution is, well lets see, we have to visit each object once to calculate the Efficiency factor, so we have a n there in our big O notation. Then we have to sort the array, so we have a log n there. Then we have to run through the Efficiency Factor array, which is of same length as number of objects. So its O(2nlogn). Since we remove co-efficients in big O notations, so its O(nlogn). Actually we might not have to visit every element in the last loop because the bag might be filled before the array exhausts.
This is great and I think more efficient than normally available algorithms. Its also quiet simple so score some points there too. The core of the algorithm is to reduce the vectors into scalars. Works great but what if the vectors are of more than 2 dimensions. In case of 2 dimensions we can use divisions but what to divide with what when there are more than 3 dimensions. Also in more general vector analysis i.e. in non-knapsack problems, like comparison of employees above, the division approach makes no sense and this algorithm of mine do not work. We cannot divide performance in one field by performance in another field because the result is meaningless. In two equally important fields A and B, if employee 1 scores 7 and 5, and employee 2 scores 5 and 7, then actually the two employees should have equal grading. But if we divide A by B, then the first employee gets a score 1.4 whereas the second employee gets score 0.714, wrongly grading the employee 1 better than the employee 2. If we swap place of A and B in the division then we see opposite result. Since fields are equal, so we cannot decide which field to go in nominator and which to do in denominator.
To solve this problem of employees grading in particular and vector analysis in general, lets use the analogy of points. Lets consider each employee a point in 4 dimensional space. Since that is hard to visualize lets first consider only two dimensions. Following is the performance of each employee in the four functions of the organization, lets call these functions A, B, C, D in the order given above (means A for production, B for accounting, 3 for marketing, 4 for customer interaction). Lets call each of our vectors (employees) Vi.
V1(7, 8, 5, 1)
V2(1, 9, 10, 4)
V3(4, 7, 4, 6)
Lets suppose we have only two employees to consider. The first one scores 5 in field A and 5 in field B. The second one scores 10 in field A and 0 in field B. A naive approach of summing the points (the same approach use in grading students in marks sheet) says that both employees are equal. However its easy to see that the first employee is an average performer whereas the second one is a specialist. We have two choices here: (i) Reward the specialist (ii) Reward the mediocre.
If we want to reward the specialist, which is generally the case in big organizations and govt institutes, which can afford to have specialists and where quality is more important than flexibility, we can use the following algorithm that I created:
The algorithm is to simply reward the employee who go farthest from the origin. In case of the first employee, the mediocre. who is at point x=5, y=5, we can use pythagorous theorem to find out that the distance from the origin is root(5*5 + 5*5) = root(25 + 25) = root(50) = 7.14. So thats the score of the first employee. For the second employee the score is root(10*10 + 0*0) = root(100 + 0) = root(100) = 10. So if the employees are enemy planes moving in two dimensional space and we have our anti-aircraft guns at origin, we have to have a range of 7.14 for our guns to hit the plane of the first employee but to hit the second employee we need far better guns of range 10. Therefore, where we reward the specialists, the solution is to simply use the phythagorous theorem. Every science person knows the phythagorous theorem of two dimensions, but the phythagorous theorem of three dimension is root(x*x + y*y + z*z) and for four dimensions it is root(A*A + B*B + C*C + D*D).
If we do not want to reward the specialists, but want to reward the mediocres, a strategy good for small organizations where flexibility and jack-of-all-tradeness is more desirable than specialism or intense knowledge of a very few things, we simply have to take the reciprocal of the length of diagonal calculated above. So in that case, for the first employee the score would be 1/7.14 = 0.14 and for the second employee the score would be 1/10 = 0.10. Here, the first employee scores more indicating that he is more valuable for the organization than the second employee. Unlike the diagonal approach, there is no way to easily visualize which employee is good, meaning no aircraft like story exists, other than saying that being closer to origin is desirable (consider both the planes and aircraft guns to be friendly and the planes are now going on bombing missions on enemy territories under the cover of our own anti aircraft guns so the enemy fighter planes cannot destroy our bombers, we do not want our planes to go very far from the origin).
Now to solve our employee situation, assuming that our organization is big and therefore reward specialists:
V1: root(7*7, 8*8, 5*5, 1*1) = root(49 + 64+ 25 + 1) = root(139) = 11.79
V2: root(1*1, 9*9, 10*10, 4*4) = root(1 + 81+100+16) = root(198) = 14.07
V2: root(4*4, 7*7, 4*4, 6*6) = root(16 + 49+ 16 + 36) = root(117) = 10.81
So the middle one is the best employee. A few things to note:
(1) We are assuming all values to be positive. For negative values where negation is undesirable, subtract instead of adding, after taking square of the value i.e. root(x*x + y*y - z*z) if z has a negative value. If negation is not undesirable then do not subtract but add as usual.
(2) We do not really have to take the root because the value before the roots is also reliable for grading. Its however not reliable for precise grading where we do not just have to tell which employee is best but also have to tell the margin of goodness. Suppose an organization has only three functions, and an employee has 5,5,5 value and another employee has 10, 10, 10 value. We know that the second employee is better than the first employee, but by how much. Can we say double, actually we can, because if the second employee has value 10,5,5 then that employee is obviously not twice as good as the first employee. To get the right grading, we do have to take root. Its because before taking roots, the values are (5*5 + 5*5 + 5*5 = 25 + 25 +25 = ) 75 vs (10*10 + 10*10 + 10*10 = 100 + 100 + 100 = ) 300 which wrongly says that the second employee is 4 times as good as the first employee. After taking roots the values become root(75) = 8.66 vs root(300) = 17.32, a difference of 2 times
(3) All we are doing is converting vectors into scalars. We humans are not capable of vector comparison, we can only compare scalars.
(4) We are assuming that each of the fields or functions of organization are equally important. If they are not, then we have to multiply each value with weight before taking square. Suppose the weights are as follows:
production: 5
accounting: 2
marketing: 3
customer interaction: 4
The scores of the employees would be as follows:
V1(7, 8, 5, 1) => (7*5, 8*2, 5*3, 1*4) => (35, 16, 15, 4)
V2(1, 9, 10, 4) => (1*5, 9*2, 10*3, 4*4) => (5, 18, 30, 16)
V3(4, 7, 4, 6) => (4*5, 7*2, 4*3, 6*4) => (20, 14, 12, 24)
No comments:
Post a Comment