Thursday, April 28, 2011

Soft Margin one-norm Bias Calculator

function [ bias ] = GetSoftBiasUno( weights, kernel, labels, C)
[xm xn] = size(kernel);
counter = 0;
bias = 0;

for i = 1:xm
    if weights(i) > (10^-10) && weights(i) < (C - 10^(-10))  %calculate first <w xi>
        sgnLastY = labels(i) > 0;
        partialSum = 0;
        for j = 1:xm
            partialSum = partialSum + labels(j) * kernel(i,j) * weights(j);
        end
       
        %reset partial sum
        wXi = partialSum;
        partialSum = 0;
       
        for j = i:xm
            if weights(i) > (10^-10) && weights(i) < (C - 10^(-10)) && sgnLastY ~= (labels(j) > 0)
              for j = 1:xm
                 partialSum = partialSum + labels(j) * kernel(i,j) * weights(j);
              end
             
              %save second <w xj>
              wXj = partialSum;
              bias = bias + -(wXi + wXj) / 2;
              counter = counter + 1;
            end
        end
    end
end

bias = bias / counter;

Soft-Margin 2-norm Bias Calculator

function [ bias ] = GetSoftBiasDos( weights, kernel, labels, C)
[xm xn] = size(kernel);
counter = 0;
bias = 0;

for i = 1:xm
    if weights(i) > (10^-10)  %calculate first <w xi>
        sgnLastY = labels(i) > 0;
        partialSum = 0;
        for j = 1:xm
            partialSum = partialSum + labels(j) * kernel(i,j) * weights(j);
        end
       
        %reset partial sum
        wXi = partialSum;
        partialSum = 0;
       
        for j = i:xm
            if weights(i) > (10^-10) && sgnLastY ~= (labels(j) > 0)
              for j = 1:xm
                 partialSum = partialSum + labels(j) * kernel(i,j) * weights(j);
              end
             
              %save second <w xj>
              wXj = partialSum;
              bias = bias + -(wXi + wXj) / 2 - (labels(i) * weights(i) - labels(j) * weights(j)) / (2 * C);
              counter = counter + 1;
            end
        end
    end
end

bias = bias / counter;

Hard Margin Bias Calculator

function [ bias ] = getHardMarginBias(weights, kernel, labels)
%returns the bias
[xm xn] = size(kernel);
counter = 0;
bias = 0;
for i = 1:xm
    if weights(i, 1) > 0.000000000001
        partialSum = 0;
        for j = 1:xm
            partialSum = partialSum + label(j) * kernel(i,j) * weights(j);
        end
        bias = bias + labels(i) - partialSum;
        counter = counter + 1;
    end
end

bias = bias / counter;

end

Gaussian Kernel

function [ result ] = GaussKernel( x, y, sigma )
result = norm(x - y)^2;
result = result / sigma;
result = exp(-result);

end

Default Kernel

function [ result ] = defaultKernel(x, y, A)
%One of many kernel functions.  Takes vectors x and y, returns kernel
%function as a dot product using a positive definite matrix A
[xm xn] = size(x);
[ym yn] = size(y);
[R isPosDef] = chol(A);
if isPosDef ~= 0 || xm ~= ym || xn ~= yn || xn == 1
    disp('sorry, this function is idiot proof.  Please enter in a positive definite matrix A');
    result = -1;
    return;
end

result = x * (A * y');

Kernel Creator

function [ K H ] = KernelKreator( training, labels, scale, toggle)

[xm xn] = size(training);
[ym yn] = size(labels);


if xm ~= ym || toggle < 0
    display('Sorry, this is an idiot proof function. Try feeding in valid parameters next time, doof!');
    return;
end

K = zeros(xm, xm);
H = zeros(xm, xm);
iter = 0;
%build kernel based on toggle used
if toggle == 0 %use regular dot product
    for i = 1:xm
        for j = i:xm
            K(i,j) = (defaultKernel(training(i, :), training(j, :), eye(xn))) / scale;
            K(j, i) = K(i,j);
            H(i,j) = (K(i,j) * labels(i) * labels(j));
            H(j,i) = H(i,j);
            iter = iter + 1;
        end
    end
%put other toggles here for other kernels
elseif toggle == 1
    for i = 1:xm
        for j = i:xm
            K(i,j) = (defaultKernel(training(i, :), training(j, :), eye(xn))) / scale;
            K(i,j) = (K(i,j) + 1)^2;
            K(j, i) = K(i,j);
            H(i,j) = (K(i,j) * labels(i) * labels(j));
            H(j,i) = H(i,j);
        end
    end
elseif toggle == 2
    for i = 1:xm
        for j = i:xm
            K(i,j) = (defaultKernel(training(i, :), training(j, :), eye(xn))) / scale;
            K(i,j) = (K(i,j) + 1)^3;
            K(j, i) = K(i,j);
            H(i,j) = (K(i,j) * labels(i) * labels(j));
            H(j,i) = H(i,j);
        end
    end
elseif toggle == 3
    for i = 1:xm
        for j = i:xm
            K(i,j) = GaussKernel(training(i, :), training(j, :), scale);
            K(j,i) = K(i,j);
            H(i,j) = (K(i,j) * labels(i) * labels(j));
            H(j,i) = H(i,j);
        end
    end
end

Support Vector Machines

For our Applied Topics in Mathematics class we had to code up some basic versions of support vector machines.  One of my classmates and I coded the following 3:  A hard margin, one-margin maximal weight SVM and 2 soft-margin maximal margin SVMs (one-norm & two-norm versions).  The next few posts will be the MATLAB code of those machines.  Feel free to comment on them and offer any suggestions where appropriate.

Monday, January 31, 2011

Math: Discovered or Invented


            According to the dictionary definition function on google (which in this case accesses a dictionary put together by Princeton university) discovery is either “the act of discovering something” or merely “a productive insight.”  From the same source, invention is either “the creation of something in the mind” or “a new device or process resulting from study and experimentation.”  Which of these definitions best suits Mathematics?  Maybe a better question is whether invention and discovery are even mutually exclusive – that is, could it be the case that Mathematics involves both?  Let us work towards answering this question by first discussing the semantics of “discovery” and “invention” in more depth.  From there it would behoove us to contemplate the historical development of Mathematics, using David M. Burton’s textbook “The History of Mathematics” (which I will admit may be a fruitless effort, given that our knowledge of ancient civilizations is surprisingly limited).  Lastly we ought to discuss the larger philosophical theories and their logical consequences concerning whether Mathematics is discovered or invented – Platonism and Nominalism.  Naturally, I will follow this analysis up with my own concluding remarks.
            So, on to semantics!  If we are to take Princeton’s word for it, discovery can be merely “a productive insight” and invention “a new device or process resulting from study and experimentation.”  But then, where do we get insight if not from experimentation?  And if we decide upon a certain process based on trial and error, is the criterion used to judge its usefulness devoid of any productive insight?  It would seem from this line of reasoning that invention and discovery, while not perfect synonyms, are in many ways difficult to differentiate.  Therefore, let us decide upon some more useful definitions particular to the discovery or invention of Mathematics.  If we say “Mathematics is discovered” let us agree that this entails Mathematic principles and truths existing independent of whether or not any intelligent being thought about them or described them in a particular language.  (This is essentially Mathematical Platonism, but we will get to that later).  Likewise, “Mathematics is invented” would mean that the notion of performing Mathematical processes is entirely the product of human imagination (Nominalism is the primary philosophical theory associated with this belief).  A via media approach would be piecewise, stating that some parts are invented and some are discovered.  With our terminology clarified, let us move on to examining the relevant history.
            The oldest objects of Mathematical note mentioned by Burton are sticks and bones which he postulates were used as a primitive means to count.  A trek further along the timeline brings us to Egyptians and Babylonians, who apparently have developed more advanced Mathematical concepts such as adding and subtracting more than one at a time, multiplication, doubling, fractions, and even geometry.  Spin the globe and we arrive in the ancient Mayan culture which had evidently come up with a representation for zero.  A little further south and we would encounter Incans with complicated rope schemes for keeping track of taxes, among other things.  In one light, it seems that multiple cultures came to relatively similar beliefs about certain Mathematical concepts in a fairly independent manner.  This would support the idea that Mathematical truths and principles are totally independent of who is thinking about them and what their socio-cultural belief structure might be.  On the other hand, if one is to assume the stance of some evolutionists (that all humans originated in Africa with the same language) it would not be a far stretch to find early trade of ideas feasible.  This would serve to give some weight to the argument for invention over discovery.  Even the Biblical conjecture of a general confusion and dispersal after the Tower of Babel indicates the possibility that many Mathematical ideas could have been transferred at that time or prior; eliminating the necessity of independent discovery.  Which is it then – discovered or invented?  This line of inquiry, barring further archeological evidence, seems to be bereft of conclusive evidence to justify any particular stance.  Perhaps waxing philosophic will prove more fruitful.
            Mathematical Platonism, as a philosophical theory, consists of the following three theses:  existence, abstractness, and independence.  That is to say, it is the theory that there exist certain abstract Mathematical objects, whose existence is totally independent of whether or not humanity knows them and understands them.  Furthermore, it supposes that Mathematics, as a scientific process, is the observance of certain of these truths as axioms and definitions.  Theorems would then follow, using logic to determine their truth based upon accepted axioms and definitions.  If the chosen axioms and definitions are “true,” then the resulting system should accurately model the real world.  Naturally, Platonists allot some degree of invention to the divining of the proper axioms and definitions, but there is something of an implied assertion that there is a right “answer” to be found – a set of Mathematical laws that are perfectly consistent internally and work in perfect tandem with the natural laws of other branches of science.  It is worth noting that Mathematical Platonism does not come from Plato per se, but since it invests in the idea of abstract ideals existing to be discovered, it is related to Plato’s philosophy about physical forms versus metaphysical ideas.
            By contrast, Nominalism argues that abstract objects do not exist.  Or rather, they only exist in the mind of the particular Mathematician.  It would follow that any principles inferred from a given set of ideas would be limited to the Mathematician himself and would require exposition to others of the same profession (or, at least, would require similar circumstances and research to derive).  An important consequence of this view is that there is no “correct” Mathematical system to construct which would reflect all of reality accurately.  The necessity of experimental scientists to deny certain Mathematical truths, in practice, to attain correct results from their experiments would seem to lend credence to this conjecture.  Though, usually such considerations are taken based upon the limitations of the devices used (many such instances come to mind from Computer Science involving round-off errors that arise when representing infinite items in a discrete form).  Furthermore, under Nominalism, any Mathematics past a certain level of abstraction are in certain senses useless, since we remove it farther away from provability using empiricism.  Even internal consistency is no longer as much an issue since general Mathematical theories are no longer in vogue (only particular cases, since there are no universals).  Now that the two major philosophical theories on the subject have been elucidated, it is time to express where I stand
            Finding, from the historical perspective, that it seems much more plausible for significant Mathematical ideas to be developed later rather than sooner; that these ideas were apparently developed independently of one another; and that the Mayans’ use of zero predated the use of zero in western civilization by a few millennium, I endorse Platonism.  A more concrete answer is to say that while I do believe there is some creativity involved in coming up with the correct approach to certain axioms and definitions, the idea that multiple cultures in multiple eras, which had a relatively tiny possibility of meeting to share ideas, ended up with essentially the same concepts and processes seems somewhat absurd.  If such cultures came up with the same idea without contact between each other, it seems far more likely that they were simply looking at the same problems and coming up with the same math to solve the given problem.  That is, that the principles were there for the discovering, and would necessarily always give the same conceptual answer.  In addition (and while this may be something of a return to the earlier discussion of semantics) it would seem odd to call the Mathematical process from axiom to theorem anything but a “discovery process.”  Lastly, I am of the belief that the existence of abstract Mathematical objects is logically equivalent to the existence of abstract natural laws, such that the denial of the one is the denial of the other.  That is not to say that our current representations of said abstract objects in Mathematics and other sciences are free from all error, but rather such abstract objects must exist, and all of science is our journey to discover and properly describe them.

Tuesday, January 11, 2011

On Political Jargon: A Somewhat Immodest Proposal

Fellow denizens of the net:

     I move we realign a lot of terminology in our country's political vernacular to be more consistent through history.  Specifically, the following jargon needs to be addressed:

Liberal -- We ought to use this term only in respect to the liberal tradition present in English and American history, typically dated back to Edmund Burke (though really present in society at least as far back as King John was forced to sign the Great Charter).  This consists of a trend towards more freedom of speech and religion.  If any current political movement can be said to express the ideals of this tradition it would be the Libertarian Party.  The term has nothing to do historically with Democratic Socialism, and it would be inadvisable to continue using it in a manner that suggests a relation.

Moonbattery -- This term could potentially refer to a Lunar weapon emplacement, which is far too awesome to leave it as a derogatory term referring to those who believe that criminals follow laws, that government is a wealth creator, and/or those who simply suffer from BDS (Bush Derangement Syndrome).

Reform -- We ought to only apply this particular term when a plan of action demonstrably improves a specific program, either by decreasing costs or improving efficiency or effectiveness.  Making only cosmetic changes, or making changes which will obviously worsen the situation should not be considered as reform.

The Political Spectrum / The Right-Left Axis -- In regards to this, it really is an overgeneralization, and always has been.  I would recommend dropping it altogether from our vernacular.  If we must continue its use, it should refer to the classic distinction between the party of the court and the party of the country, republicans versus monarchists, or in the US, federalism versus states' rights.  If I were to put this in terms of modern pundits, think Bill O'Reilly as your typical lefty, Rush Limbaugh as probably dead center, and Nick Gillespie as your typical righty.  Such a spectrum would more accurately be in line with our history.

Grassroots/Astroturf -- I'm in favor of throwing both terms out, because while it ought to be seen as pathetic when you have to pay people to agree with you, I think we're intelligent enough to view _any_ idea thrown out in the public venue abstractly (regardless of who/where it came from).  It does not seem useful to make a distinction between opinions based on what occupation the person comes from.  Bad ideas are bad ideas, and good ideas are good ideas no matter who came up with them.

Expert -- There are certain subjects which require such specific layers of knowledge and understanding that I think most people implicitly understand that the person involved really does deserve to be taken credible.  Then there's everything else:  history, sociology, political science, economics, literature, art, psychology, business, marketing, etc.  The only expertise involved in this list of topics is what we all learned in high school -- the ability to analyze information and report on it.  I'm not sure even a differentiation between professional and amateur would be in order for any of the aforementioned "skills."

Welfare -- Basically, this ought to return to referring to infrastructure that maintains, promotes, and/or improves public well-being.  It should not refer to any private goods or services given to a specific individual.

Global Warming -- Either make this term refer only to the kind of pseudo-science Al Gore endorses, or use it only in the sense of a layman's term for the Greenhouse Effect.  I get tired of having to explain that I think AGW is a hoax, not trying to claim the aforementioned scientific phenomena doesn't happen.

And that's it...for now.  I may think of some more later, but readjusting this stuff would make politics a lot clearer and more consistent not only for us now, but in keeping a consistent historical context for progeny's sake.

Monday, January 10, 2011

Some MATLAB functions to create matrices representing steps in Gaussian Elimination

function interchangeRows = interchangeRows(i, j, n, m)
A = eye(n,m);
A(i,i) = A(j,j) = 0;
A(i,j) = A(j,i) = 1;
interchangeRows = A;

function multiplyRowbyScalar = multiplyRowbyScalar(j, alpha, n, m)
A = eye(n,m);
A(j, j) = alpha;
multiplyRowbyScalar = A;

function multiplyRowIbyScalarAddRowJ = multiplyRowIbyScalarAddRowJ(i, j, alpha, n, m)
A = eye(n, m);
A(j, i) = alpha;
multiplyRowIbyScalarAddRowJ = A;