tag:blogger.com,1999:blog-39450752375011909112017-09-14T21:18:54.153-07:00Jedd's Computer (Science) ForaysJedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3945075237501190911.post-5858376486129591002017-09-14T21:17:00.003-07:002017-09-14T21:18:54.162-07:00Learning vs InferenceIn machine learning, the terms "learning" and "inference" are used often and it's not always clear what is meant. For example, is "variational inference" and neural network "inferencing" the same thing? Usually not!<br /><br />When the deep learning crowd says "inference", what they mean is "perform a prediction." When the bayesian crowd says "inference", what they really mean is "compute the posterior distribution of a latent variable model"; e.g., for a model p(x, z) = p(x | z)p(z) and data x, compute p(z | x).<br /><br />When someone says learning, they mean their model has a set of parameters and they need to find a good setting of those parameters; e.g. their model is actually p(x, z) = p(x | z; theta)p(z) and they want to find theta. For frequentists, this means finding a point estimate of the parameters. For a bayesian, learning is inference because the parameters are treated as latent, random variables, so they can use normal variational inference or MCMC to compute a distribution over the parameters. Note that for 99% of deep learning practitioners, training is synonymous with learning as the practitioner will likely only be computing a single set of values (aka point estimate) for their weights.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-75331344438590337932017-09-10T23:30:00.002-07:002017-09-11T01:21:11.605-07:00Why is the ELBO difficult to optimize?<br />The task of bayesian inference is to compute the posterior p(z | x) of the model p(x, z) = p(x|z)p(z) where z is a latent variable. This is often intractable, so a bayesian may resort to approximating it with some easier distribution q(z) — this method is called variational inference . Usually the approximating distribution is chosen from a parameterized family of distributions. Thus q(z) is really the variational distribution q(z; lambda) for some chosen value lambda. How is this parameter lambda chosen?<br /><br />A common method is to minimize the KL-divergence between the variational distribution and the true posterior, KL[q(z; lambda) || p(z | x)]. Of course, the posterior isn’t actually known, but if we break down this KL divergence, we see the following:<br /><br />KL[q(z) || p(z | x)] = E_q(z)[log(q(z)) - log(p(z|x))]<br />= E_q(z)[log(q(z)) - log(p(x, z)/p(x))]<br />= E_q(z)[log(q(z)) - log(p(x, z)) + log(p(x))]<br />= E_q(z)[log(q(z)) - log(p(x, z))] + log(p(x))<br />= E_q(z)[log(q(z)) - log(p(x|z)) - log(p(z))] + log(p(x))<br /><br />The KL divergence can be minimized up to a constant (the marginal likelihood) wrt the variational parameters since we know how to compute p(x, z) per the model’s definition. This term that we want to minimize — E_q(z)[log(q(z)) - log(p(x|z)) - log(p(z))] — is the negative evidence lower bound (ELBO). So, back to the original title question — why is the ELBO difficult (but not impossible) to optimize?<br /><br />It actually isn’t difficult to optimize for certain classes of models. If all the latent variables are chosen to be independent in the variational distribution (i.e. the mean-field assumption) and the model is conditionally conjugate, then one can use coordinate ascent variational inference. This method is fast to compute. Unfortunately, the restrictions it places on the model are also quite limiting. It is when the model is unconstrained is optimizing the ELBO difficult. But again, why?<br /><br />If nothing is known about the model p(x|y)p(y) except a method to evaluate it, we are relegated to optimizing the ELBO by gradient descent. This entails computing the gradient of the ELBO (excuse my abuse of notation):<br /><br />Gradient of E_q(z)[log(q(z)) - log(p(x|z)) - log(p(z))]<br />= gradient of (integral of q(z)*(log(q(z)) - log(p(x|z)) - log(p(z)))dz)<br />= gradient of (integral of q(z)*log(q(z))*dz) - (integral of q(z)*(log(p(x|z)) - log(p(z))*dz))<br />= integral of (gradient of q(z)*log(q(z))*dz)) - (integral of (gradient of q(z))*(log(p(x|z)) - log(p(z))*dz))<br /><br />where the I've shortened q(z; lambda) to q(z) and the gradient is wrt lambda.<br /><br />When I first saw this equation, I wasn’t sure what the big deal was. This is because I wasn’t accustom to staring at math equations all day, but to any (applied) mathematician it should be obvious. I’ll put in bold font: computing the gradient of the ELBO *requires computing some likely high-dimensional, likely intractable integral.* Why is it intractable? Well, you may get lucky and the integral has an analytic solution, but in general that won’t be true. Also, because this quantity no longer takes the form of an expectation, it can’t easily be estimated by Monte Carlo. It may be possible to do so if z is discrete and its sample space is small (as you could exhaustively evaluate the integrand at all z), but that implies z is very low dimensional which may not be true either.<br /><br />Luckily there exist some methods to side-step these issues by placing mild(ish) constraints on either the variational family of distributions or both the variational family and the model. These methods are the score function gradient and reparameterization gradient, but I won’t be discussing them in this post — they’re best left to be explained another day (or by Google)..Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-49437295216426648492017-09-07T00:24:00.000-07:002017-09-07T00:36:07.073-07:00Expectation Maximization vs Variational Bayes I constantly find myself forgetting the details of the EM algorithm, variational bayes, and what exactly the difference is between the two. To avoid confusion in the future, I wrote the following note.<br /><br /><b>Q:</b> What is the difference between EM and Variational Bayes (aka "Variational Bayesian EM")?<br /><b>A:</b> Both are iterative methods for learning about the parameters theta and the posterior p(z | x, theta) in a latent variable model p(x, z | theta) by trying to a maximize a lower bound to the marginal likelihood p(x) (or p(x | theta) when using EM). The difference between the two techniques lies in following:<br /><br /><ol><li>VB assumes that, even when given a setting of the parameters theta, it is not tractable to compute the posterior p(z | x, theta). Thus, it must be approximated by some variational distribution q(z). On the other hand, EM makes the opposite assumption - given a setting of the parameters theta, it will compute the exact posterior p(z | x, theta). In this sense, VB is a relaxation of EM.</li><li>VB is a bayesian technique while EM is a frequentist technique. As such, VB treats theta as a latent, random variable and computes a distribution q(theta) that approximates the posterior distribution p(theta | x). EM, a maximum likelihood technique, computes a point estimate to the parameters theta instead of a full distribution.</li></ol>With these differences in mind, we can describe the two algorithms using a similar framework.<br /><br /><u>Objective:</u><br />EM’s objective is to maximize a lower bound to p(x | theta), E_q(z)[log(p(x, z | theta))].<br />VB’s objective is to maximize a lower bound to p(x), E_q(z, theta)[log(p(x, z, theta))].<br /><br /><u>E-step:</u><br />EM first maximizes the objective by fixing theta and then finding an <i>optimal</i> setting of q(z). This optimal setting is always calculated to be the posterior p(z | x, theta).<br />VM first maximizes the objective by fixing q(theta) and finding a <i>better</i> setting of q(z) (often by some gradient method).<br /><br /><u>M-step:</u><br />EM maximizes the objective by fixing q(z) to the posterior from the previous E-step, and then calculates a maximum likelihood point estimate of the parameters theta.<br />VM maximizes the objective by fixing q(z) and then finding a better setting of q(theta) (again, often by some gradient method).<br /><br />The E and M step are then repeated until convergence (i.e. until the point at which the log marginal likelihood no longer improves).<br /><br />One last point: there is another algorithm called "Variational EM". This algorithm is just the E-step of VB combined with the M-step of EM. Since parameters are not treated as random variables, it is not a bayesian technique.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-64897113960469435762016-05-02T23:32:00.001-07:002016-05-02T23:32:07.875-07:00Frequentists vs BayesiansA really wonderful aspect of learning about machine learning is that you can't help but learn about the field statistics as well. As a computer scientist (or really, a software engineer -- I have a hard time calling myself a computer scientist), one of the joys of the field is that many interesting problems require expertise from other fields and so computer scientists tend to be exposed to a great many of ideas (even if only in a shallow sense)!<div><br /></div><div>One of the major divides among statisticians is in the philosophy of probability. On one hand there are frequentists who like to place probabilities only on data; there is some underlying process that the data describes, but one doesn't have knowledge of all data, so there only exists uncertainty about what unknown data the process could generate. On the other hand there are bayesians who, like the frequentists, place probabilities on data for the same reason, but who also place probabilities on the models they use to describe the underlying process and on the parameters of these models. They allow themselves to do this because they concede that, although there does exist one true model that could perfectly describe the underlying process, as the modeler they have their own uncertainty about what that model may be.</div><div><br /></div><div>I think this is an interesting divide because it highlights two different sources of uncertainty. Some uncertainty exists because there exists true randomness in the world (or so physicists believe), while other uncertainty exists solely due to our own ignorance -- the quantity in question may be completely determined! We are just forced to work with incomplete information. I think it is fascinating that there exists a unified framework that allows us to manage both sources of uncertainty, but it does make me wonder: do these two sources of uncertainty warrant their own frameworks?</div>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-78979278707790605152016-04-02T15:16:00.003-07:002016-04-02T15:17:41.699-07:00An intuition of Newton's methodDuring my lazy weekend afternoons (and all the other days of the week) I've been going through Nando de Freitas' undergraduate machine learning course <a href="https://www.youtube.com/playlist?list=PLE6Wd9FR--Ecf_5nCbnSQMHqORpiChfJf" target="_blank">on youtube</a>. In lecture 26 he introduces gradient descent, an iterative algorithm for optimizing (potentially non-convex) functions. I'll refrain from explaining gradient descent more than that as there are many good explanations on the internet (including Professor de Freitas'), but I do want to discuss gradient descent's learning rate parameter and why intuitively Newton's method, also introduced in lecture 26, is able to side-step the learning rate.<br /><br />As described in the video lecture, a common difficulty with gradient descent is picking the learning rate hyper-parameter. Pick too small of a learning rate and gradient descent will come to crawl and make very little progress or even eventually stop making progress due to floating point underflow. Pick too large of a learning rate and gradient descent will oscillate around the minimum/maximum, bouncing around, very slowly making progress. In an ideal world, as the gradient vanishes, the gradient descent algorithm would be able to compensate by adjusting the learning rate so to avoid both underflow and oscillation. This is exactly what Newton's method does.<br /><br />Compare gradient descent<br />$$\boldsymbol\theta _{k+1} = \boldsymbol\theta _{k} - \eta_{k}\nabla f(\boldsymbol\theta_{k})$$<br />to Newton's method<br />$$\boldsymbol\theta _{k+1} = \boldsymbol\theta _{k} - H_{k}^{-1}\nabla f(\boldsymbol\theta_{k})$$<br /><br />The only difference is that Newton's method has replaced the learning rate with the inverse of the <a href="https://en.wikipedia.org/wiki/Hessian_matrix" target="_blank">Hessian matrix</a>. The lecture derived Newton's method by showing that \(f(\boldsymbol\theta)\) can be approximated by a second-order Taylor series expansion around \(\boldsymbol\theta_{k}\). If you're familiar with Taylor series, then this explanation may be sufficient, but I prefer to think about it differently.<br /><br />What is this Hessian matrix we've replace the learning rate with? Just as the gradient vector is the multi-dimensional equivalent of the derivative, the Hessian matrix is the multi-dimensional equivalent of the second-derivative. If \(\boldsymbol\theta_{k}\) is our position on the surface of the function we're optimizing at time step \(k\), then the gradient vector, \(\nabla f(\boldsymbol\theta_{k})\), is our velocity at which we're descending towards the optimum, and the Hessian matrix, \(H\), is our acceleration.<br /><br />Let's think back to the original problem of choosing the learning rate hyper-parameter. It is often too small, causing underflow, or it is too big, causing oscillation, and in an ideal world we could pick just the right the learning rate at any time step, most likely in relation to the rate at which the gradient vector vanishes, to avoid both these problems. But wait, now we have this thing called the Hessian matrix that measures the rate at which the gradient vanishes!<br /><br />When starting the algorithm's descent we will quickly gain acceleration as we starting going downhill along the function's surface (i.e. the Hessian matrix will "increase"). We don't want to gain too much velocity else we'll overshoot the minimum and start oscillating, so we'd want to choose a smaller learning rate. As the algorithm nears the optimum, the geometry of the function will flatten out and we will eventually lose acceleration. We don't want to lose too much velocity else we'll underflow and stop making progress. It is precisely when we lose acceleration (i.e. the Hessian matrix "decreases") that we want to increase our learning parameter.<br /><br />So we have observed that heir is an inverse relationship between the magnitude of the acceleration at which we descend towards the minimum and the magnitude of the most desirable learning parameter. That is to say, at greater accelerations we want smaller learning rates and at smaller accelerations we want larger learning rates. It is precisely for this reason why Newton's method multiplies the gradient vector (the "velocity") by the inverse Hessian matrix ("the inverse acceleration")! At least, this is how I intuitively think about Newton's method. The derivation involving Taylor series expansions is probably the <i>actual</i> precise reason, but I like thinking about it in terms of velocities and accelerations.<br /><br />Finally, I'd like to end with one cautionary note. I'm an amateur mathematician. I like to think my intuition is correct, but it may not be. By sharing my intuition, I hope to help others who are looking to gain intuition, but if you need anything <i>more</i> than an intuitional understanding of Newton's method or gradient descent (because perhaps you're an actual mathematician in training), please consult a textbook or your favourite professor :-).<br /><br /><br />Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-5570463975674972502015-12-09T00:06:00.002-08:002015-12-12T12:23:09.473-08:00On optimizing high-dimensional non-convex functionsExcuse me for the (in)completeness of this post. What follows is merely a thought, inspired by two independent statements, about a domain of science (or math, really) with which I am barely initiated. Let me give you these two statements first.<br /><br />In the book <a href="http://www.cs.cornell.edu/jeh/bookMay2015.pdf" target="_blank">Foundations of Data Science</a>, the very first paragraph of the book says<br /><blockquote class="tr_bq"><span style="font-family: "cmr12"; font-size: 12pt;">If one generates </span><span style="font-family: "cmmi12"; font-size: 12pt;"><i>n</i> </span><span style="font-family: "cmr12"; font-size: 12pt;">points at random in the unit </span><span style="font-family: "cmmi12"; font-size: 12pt;"><i>d</i></span><span style="font-family: "cmr12"; font-size: 12pt;">-dimensional ball, for sufficiently large </span><span style="font-family: "cmmi12"; font-size: 12pt;"><i>d</i>, </span><span style="font-family: "cmr12"; font-size: 12pt;">with high probability the distances between all pairs of points will be essentially the same. Also the volume of the unit ball in </span><span style="font-family: "cmmi12"; font-size: 12pt;"><i>d</i></span><span style="font-family: "cmr12"; font-size: 12pt;">-dimensions goes to zero as the dimension goes to infinity. </span></blockquote>That is statement one. Statement two is an assertion given in this year's <a href="http://www.iro.umontreal.ca/~bengioy/talks/DL-Tutorial-NIPS2015.pdf" target="_blank">Deep Learning Tutorial</a> at the Neural Information Processing Systems (NIPS) conference. They claim that "most local minima are close to the bottom (global minimum error)."<br /><br />The second statement is significant for training (deep) neural networks. Training a neural network always uses a variant of a gradient descent, a method for minimizing the neural network's error by iteratively solving for when the gradient (i.e. the derivative) of the function that gives the error is 0. Ideally gradient descent will approach the global minimum error (the point where the neural network will give the most desirable approximations of the training data), but that is only guaranteed when the error function is convex (there are no hills when the function is plotted). Unfortunately, a neural network almost never has a convex error function. Hence, during gradient descent, one might find a local minimum that is nowhere near as low as the global minimum. The second statement however says we shouldn't be so concerned -- all local minima will be close to the global minimum!<br /><br />But why?<br /><br />My thought is that somehow the first statement can be used to prove the second statement. The training data of modern neural networks is high dimensional. It will also often be normalized as part of feature scaling. Given those two properties, the high-dimensional hills and valleys of a neural network's error function then (roughly) form unit hemispheres. This (possibly) implies that that local minima are close to the global minimum because the volumes of every valley nears zero, making all the valleys increasing similar to each other as the dimensionality of the training data increases.<br /><br />I want to stress though, this is a half-baked idea. It's probably rubbish. It might also be redundant! Perhaps the second statement already has a proof and I've missed it. Either way, I would love to see if others find my intuition plausible or, even better, to be pointed in the direction of a proof for the second statement.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-83821959106711313302015-10-03T10:52:00.000-07:002015-10-03T10:52:43.074-07:00TIL: premultiplied-alpha colorsAlpha is the measure of how translucent an object is. An alpha of 0.0 means the object is entirely transparent, an alpha of 1.0 means the object is entirely opaque, and an alpha in the middle means a fraction of the total light may passthrough the object. Traditionally, a color is represented by 4 constituent components: a red contribution, a green contribution, a blue contribution, and the alpha. When compositing two colors together, one on top of the other, the alpha acts as a modulus of the colors, indicating how much of the top color and how much of the bottom color contribute to the new composited color. The traditional compositing operation is as follows, where <i>A</i> is being composited over top <i>B</i>:<br /><br /><center style="text-align: center;"><img src="http://latex.codecogs.com/gif.latex?\inline&space;\\&space;A&space;=&space;\begin{bmatrix}&space;r_{a}&space;&&space;g_{a}&space;&&space;b_{a}&space;&&space;a_{a}&space;\end{bmatrix}&space;\\&space;B&space;=&space;\begin{bmatrix}&space;r_{b}&space;&&space;g_{b}&space;&&space;b_{b}&space;&&space;a_{b}&space;\end{bmatrix}&space;\\&space;C_{rgb}&space;=&space;a_{a}\cdot&space;A_{rgb}&space;+&space;(1&space;-&space;a_{a})\cdot&space;B_{rgb}" title="\\ A = \begin{bmatrix} r_{a} & g_{a} & b_{a} & a_{a} \end{bmatrix} \\ B = \begin{bmatrix} r_{b} & g_{b} & b_{b} & a_{b} \end{bmatrix} \\ C_{rgb} = a_{a}\cdot A_{rgb} + (1 - a_{a})\cdot B_{rgb}" /></center><br />Alternatively, we may wish to premultiply the red, green, and blue components by the alpha: <br /><br /><center><img src="http://latex.codecogs.com/gif.latex?C&space;=&space;\begin{bmatrix}&space;a\cdot&space;r&space;&&space;a\cdot&space;g&space;&&space;a\cdot&space;b&space;&&space;a\end{bmatrix}" title="C = \begin{bmatrix} a\cdot r & a\cdot g & a\cdot b & a\end{bmatrix}" /></center><center style="text-align: left;"></center><center style="text-align: left;"></center><center style="text-align: left;"><br /></center><center style="text-align: left;">With this representation we get a new compositing equation:</center><center style="text-align: left;"><br /></center><center style="text-align: left;"></center><center style="text-align: left;"></center><center><img src="http://latex.codecogs.com/gif.latex?C&space;=&space;A&space;+&space;(1&space;-&space;a_{A})\cdot&space;B" title="C = A + (1 - a_{A})\cdot B" /></center><center style="text-align: left;"></center><center style="text-align: left;"><br /></center><center style="text-align: left;">This new form is interesting for a couple reasons.</center><center style="text-align: left;"><ol><li>It is computationally more efficient. It requires one less vector multiplication.</li><li>It is a closed form. Compositing a premultiplied-alpha color over top a premultiplied-alpha color yields another premultiplied-alpha color. The same cannot be said of non-premultiplied-alpha colors. Compositing two non-premultiplied-alpha colors yields, interestingly, a premultiplied-alpha color.</li><li>When filtering (<i>aka</i> downsampling), it produces more visually accurate results. A <a href="http://15462.courses.cs.cmu.edu/fall2015/lecture/pipeline/slide_031" target="_blank">picture</a> is worth a thousands words.</li></ol><div>And that's it. Premutliplied-alpha colors are nifty.</div></center>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-22787021942293068192015-10-02T21:58:00.002-07:002015-10-02T21:58:47.384-07:00TIL: The column space and null spaceA vector space is a set of vectors that is closed under addition and scalar multiplication. In other words, given two vectors, <b>v</b> and <b>w</b>, a vector space is formed by the set of all linear combinations formed between <b>v</b> and <b>w</b>, namely <i>c</i><span style="font-weight: bold;">v</span> + <i>d</i><b>w</b> for arbitrary coefficients <i>c</i> and <i>d.</i><br /><i><br /></i>Columns spaces and null spaces are special categories of vector spaces that have interesting properties related to systems of linear equations, <i>A</i><b>x</b> = <b>b</b>. The column space of the matrix A, C(<i>A</i>), is simply the linear combinations of <i>A</i>'s column vectors. This implies that <i>A</i><b>x</b> = <b>b</b> may only be solved when <b>b</b> is a vector in A's column space. Finally, the null space of matrix <i>A</i> is another vector space formed by all the solutions to <i>A</i><b>x</b> = <b>0</b>.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-32926143843545052482015-10-01T16:23:00.000-07:002015-10-01T16:24:24.527-07:00TIL: a principled approach to dynamic programmingDynamic programming has always been a topic I understood at a surface level (<i>it's just memoization, right?!)</i>, but ultimately feared for lack of real-world experience solving such problems. I read today a superb <a href="http://sites.fas.harvard.edu/~cs124/sections/section7_sol.pdf" target="_blank">explanation</a> of a principled approach to solving dynamic programming problems. Here it is:<br /><br /><ol><li>Try to define the problem at hand in terms of composable sub-problems. In other words, ask yourself what information would make solving this problem easier?</li><li>Define a more rigorous recurrence relation between the sub-problems and the current problem. What are the base-cases and how do the sub-problems answer the current problem?</li><li>Build a solution look up table (up to the point of the current problem) by first initializing it for the base cases and then for the sub-problems in a bottom-up approach. The bottom-up approach is the defining characteristic of a dynamic programming solution. Alone, the look up table is just memoization. <i>Note</i>: building the solution table bottom up will often look like a post-order depth-first search.</li></ol><div><a href="https://gist.github.com/jhaberstro/c4fd6fdf8d20f9f4bfed" target="_blank">Here is an implementation (in Scala)</a> to the following problem:</div><blockquote class="tr_bq">Given a general monetary system with M different coins of value {c1, c2, . . . , cM}, devise an algorithm that can make change for amount N using a minimum number of coins. What is the complexity of your algorithm?</blockquote>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-86193417715462165852015-10-01T13:12:00.000-07:002015-10-01T13:19:30.414-07:00TIL: Alpha-to-coverage for order-independent transparencyAlpha-to-coverage is a computer graphics technique, supported by most (all?) modern GPUs, for rendering translucent multi-sampled anti-aliased primitives. Given an alpha value in the range of [0.0, 1.0] and <i>N</i> samples of color stored per pixel, the alpha channel will be discretized into a coverage-mask of the <i>N</i> samples. An alpha of 0 will generate an empty coverage-mask (no samples take on the new color), an alpha of 1 will result generate a full coverage-mask (all samples take on the new color), and values in between will generate a partial coverage-mask (between 1 and <i>N</i>-1 samples take on the new color).<br /><div><br /></div><div>It's not alpha-to-coverage itself that I learned today however, but rather it's implication; <b>Alpha-to-coverage is a form of order-independent transparency!</b> In the naïve case, one benefits from <i>N</i>-layers of transparency. I suppose this is the whole point of alpha-to-coverage, but I never put two-and-two together*.</div><div><br /></div><div><br /><span style="font-size: x-small;">* I blame my experience. Being a GPU driver engineer, but never a rendering engineer, I'm exposed to large cross-section of rendering techniques and low-level graphics implementation details, but never to the greater-picture of real-time rendering but by word of mouth and self-study.</span></div>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-68768855995862589102015-10-01T12:47:00.000-07:002015-10-01T12:47:31.825-07:00TIL: Today I learnedIt has been a long time since my last appearance. I've written a couple of unfinished posts in that time, but I've realized that writing a detailed essay that's up to a satisfactory standard of quality is actually quite time consuming (<i>who would have thought!</i>). In an attempt at more productive writing, I will try to publish one post per day expounding on something new I've learned that day. Nothing more than a paragraph or two. My hope is that this will be burden-free enough not to require extraneous effort, yet valuable enough that it's worth recording. Equally, this will serve as a nice personal journal of my educational journey post-schooling.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-28157948412554511422014-05-21T21:37:00.002-07:002014-05-21T21:37:38.730-07:00Encapsulation == ParameterizationMartin Odersky recently made the interesting observation that encapsulation is equivalent to parameterization. He demonstrated this by showing how abstract types are used (in their natural fashion) for encapsulation in Scala, and then equivocated parameterized types (aka generic classes) to corresponding types where the original type parameters had been transformed into abstract type members.<br /><br />Intuitively this observation makes sense. Encapsulation's goal is to <i>hide</i> information: don't let me muck with the internals of an implementation. Parameterization's goal on the contrary is to defer, or put another way <i>abstract</i>, implementation details (i.e. abstract what types or values make up the data structure or algorithm that I'm building). Logically, as we increase the amount of parameters, the less we can know. That is to say, by restricting our knowledge we've abstracted, or <i>hidden</i>, implementation details from ourselves! (albeit, in a somewhat inverse manner than traditional encapsulation, but that's besides the point)<br /><br />As we can see clearly now, encapsulation and parameterization are equivalent; both hide implementations and both abstract interfaces. Put another way, hiding implementations is equivalent to abstracting interfaces.Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-33975878755309409352013-09-18T17:40:00.000-07:002013-09-18T17:41:38.601-07:00"Is President Obama Really A Socialist? Let's Analyze Obamanomics" -- ReactionsI wrote this in response to a post of a Facebook friend the other night. It was never meant to be more than some casual thoughts, and still really, it's only that. However, seeing as I'm awful at staying current on my blog, I thought I might as well not let this digital hunk of "ideas to paper" go to complete waste. So, here it is, a reaction to silly political Forbes article, (almost) completely unedited.<br /><br /><hr /><br />There is a lot wrong (or perhaps misguided, in my opinion) in <a href="http://www.forbes.com/sites/peterferrara/2012/12/20/is-president-obama-really-a-socialist-lets-analyze-obamanomics/" target="_blank">this article</a>. It's hard to know where to start. However, let me start by saying that what follows is simply to point out the holes of Ferrara's arguments from a factual standpoint, as it is presented; In no way am I asserting that if we accept what he says to be wrong, then the logical implication is that Obama's solutions are automatically right. In fact, I'm not going to talk to Obama's policies at all. So, let's begin.<br /><blockquote class="tr_bq"><i>the top 1% of income earners paid 39% of all federal income taxes, three times their share of income at 13%. Yet, the middle 20% of income earners, the true middle class, paid just 2.7% of total federal income taxes on net that year, while earning 15% of income. </i></blockquote>His line of reasoning here only works if you agree that every dollar has equal worth (which, they don't[1]). In that case, what he puts foward does suggest that there is a flaw *somewhere* in the system; I don't think anyone is denying that. However, what is more startling are the ratios between percentage of income to percentage of income earners. The difference between (13/1) and (15/30) means that the top 1% is making 1700% more than the middle 20%! And that's only with the conservative bounds that Farrara has chosen. That gap will certainly expotentially increase as you widen the bounds to include the lower class and the upper class (1% is what I would call "elite upper class").<br /><blockquote class="tr_bq"><i>Any normal person would say that such an income tax system is more than fair, or maybe that “the rich” pay more than their fair share.</i></blockquote>Yes, perhaps so, but "any normal person" isn't qualified to make these judgements (we like to think we are, though). Economics, like any other science, is non obvious; that's why we have economists and trained professionals. Anyways, point is: the "any normal person would..." card is a straw-man's argument.<br /><blockquote class="tr_bq"><i>The answer is that to President Obama this is still not fair because he is a Marxist. To a Marxist, the fact that the top 1% earn more income than the bottom 99% is not fair, no matter how they earn it, fairly or not. So it is not fair unless more is taken from the top 1% until they are left only with what they “need,” as in any true communist system. Paying anything less is not their “fair” share. __That is the only logical explanation of President Obama’s rhetoric__, and it is 100% consistent with his own published background.</i></blockquote>No it's not. Like most things in this world, there isn't a binary right or wrong, yes or no, "this way or that way answer" solution or answer to everything (or most things for that metter). Following that, his jump to "Obama is a Marxist" is a long leap to make and equally ignorant (I actually doubt this man is ignorant, but rather knows his readers well).<br /><blockquote class="tr_bq"><i>Good tax policy is not guided by “need.” It is guided by what is needed to establish the incentives to maximize economic growth.</i></blockquote>Says who? (no, seriously) There's a lot of debate about this, but I hardly think what he suggests here is a "good thing"(™). A tax policy that optimizes only for "economic growth" doesn't speak at all to economic distribution. In my book (okay, I'm interjecting an opinion here), a good tax policy would ensure the largest amount of people are living comfortable, with small but noticeable degrees of variance -- the variance allowing for the opportunity to achieve greater economic success (i.e. to ensure that the motivation to "rise the ranks" still exists, a key component of the "American Dream").<br /><blockquote class="tr_bq"><i>The middle class, working people and the poor are benefited far more by economic growth than by redistribution. That is shown by the entire 20th century, where the standard of living of American workers increased by more than 7 times, through sustained, rapid economic growth.</i></blockquote>This is blatantly false. Our initial economic booms were due to labor exploitation (child labor, poor working conditions, no minimum wage, etc.) and the military industrial complex. Secondly, if you look at the tax rates through the 50s and 60s, some of the argueably better economics years of the 20th century, you will see that what Farrara is arguing about tax is completely contrairy to the actual statistics (which, at the very least suggests that there is no causitive relationship between tax rates and economic health, and at the best suggests that high taxes that essentially scale with your income are causitive to the economy's health. In reality, it suggests something in between). For example, take these statistics of incomes adjusted for inflation vs marginal tax rates[2]: in 1960, a single person making $1,163,483 dollars was taxed at the rate of 90% and a head of house making $100,000 was taxed at 36%.<br /><blockquote class="tr_bq"><i>But President Obama’s tax policy of increasing all tax rates on savings and investment will work exactly contrary to such economic growth. It is savings and investment which creates jobs and increases productivity and wages. Under capitalism, capital and labor are complementary</i></blockquote>These are unsubstantiated assertions. He gives no reason why I should believe what he says.<br /><br />Anyways, I must admit, I don't have the energy to persist in my writing. I'm tired and still have homework to do (which involves much, much denser, drier reading than that of Farrara's… :)). I'll just conclude in saying that although there are some claims that Farrara makes that seem to be substantiated (however, I'm skeptical that real substantiation can be provided in a Forbes article), the large majority of his claims aren't sufficiently (or at all) substantiated. For that reason alone, I would take everything that this man writes in such Forbes-like articles with a grain of salt.<br /><br /><br />[1] Think about the value of $50 to someone making minimum wage to a multi-millionaire or billionaire. If each person respectively were to lose a $50 bill, the so decrease in so called "opportunity cost" between the two is hugely different (i.e. A minimum wage worker will "get a lot more" out of that $50 bill). Ideally "fairness" needs to be judged upon an adjusted scale of relative value.<br /><br />[2] http://taxfoundation.org/article/us-federal-individual-income-tax-rates-history-1913-2013-nominal-and-inflation-adjusted-bracketsJedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-85340529618294011212012-11-14T12:28:00.001-08:002012-11-14T12:30:49.749-08:00In Good CompanyRegarding my last post, I'm glad to see I'm <a href="https://plus.google.com/101960720994009339267/posts/hoJdanihKwb" target="_blank">in good company</a> in feeling that object-oriented programming is not the be-all, end-all to software design (nor is it always a good design). Now if only I could get my school's Software Engineering department to agree...<br /><br /><i>I should also note, I have a lot more to my opinion than what I crudely wrote in my last post. I just don't feel particularly motivated to expand upon them because religion is religion is religion and I doubt anyone reading this (if there is anyone reading this) will alter their views based on what I have to say.</i>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-68204972548269011462012-10-18T12:08:00.001-07:002012-10-18T12:08:52.286-07:00On the Harm of Object-Oriented ProgrammingThis is an excerpt of an essay that I wrote for a class, prompted by Dijkstra's famous goto letter. I must admit that it was written in a very "stream-of-conscious" type of way, so it may not be elegant writing, but I think it's worth putting down anyways.<br /><br /> <blockquote class="tr_bq"><span class="s1">I believe today that the reach of computer science (which I should probably refer to as software engineering as the discussions of goto is more a practical than a theoretical) is sufficiently widespread that is has divided the industries of programming so much that it is not useful or plausible to talk of a single language feature or programming practice being useful or harmful. What is useful for a web application could be considered harmful for an embedded software application, and vice-versa. So I would limit my response to the area that I most familiar: desktop application development.</span></blockquote><br /><blockquote class="tr_bq"><span class="s1"></span>In my opinion, one of the most harmful programming features is single-paradigm object-oriented programming. Object-oriented programming has been advocated, pushed, and taught so strongly for the past 20 years that it is almost universally used to model any problem we need to tackle as programmers. However, like any tool, there are strengths and weaknesses. At the heart of object-oriented programming, the idea is to model every piece of the program as realistically as possible to a noun that as humans we can understand (which implies that we are attempting to draw a parallel between real life objects and our programs). The consequence is that we group pieces of data that compose that noun together in memory. This has significant downsides on modern desktop computers though. This grouping of data that object-oriented programming encourages is essentially the memory layout referred to as “array of structures” (AOS). Consider an AOS layout for a list of particles being used to model an explosion effect in a video game. In this setup, you may have a geometric vector for a position, velocity, force stored in this object. Presumably, since the particle has these attributes, you need to perform a numerical integration of these attributes over time. This is a loop over your particles where at each iteration you access each attribute, perform the necessary computation, and store the result. In the AOS layout, these properties are stored contiguously in memory and further each particle is stored contiguously in memory. That means on current desktop PCs, where memory access is expensive and the hardware has a lot of builtin mechanisms to reduce the costs, the particle array will only utilize one cache line. On the contrary, let’s reconsider the system we’re building. We designed our program so that each particle is an object. But when will there only exist one particle? The answer is never. The program can be better redesigned to account for the fact that particles are only ever used in mass. So the solution is to split each attribute of a particle into an array of each attribute (the so called “structure of array” layout), and now when iterating over the particle data there will be a cache line utilized by each array, significantly reducing the amount of cache miss and increasing the performance of the application. Arguably you can still have a “ParticleManager” object, so all hope isn’t lost for object-oriented programming; but the point is that single paradigm object-oriented programming languages are so taught and widely used that the mindset we’ve learned has lead us to design our particle system blindly, thinking about real-world abstraction instead of an abstraction that makes sense for both us and the computer. On a final note, I talk of <i>single paradigm</i> object-oriented programming because it is those languages that force us to think in terms of object and don’t allow us to escape the paradigm when it no longer makes sense. </blockquote>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-536197481522299802012-05-27T17:46:00.000-07:002012-05-27T17:46:19.843-07:00Animating NSSplitViewA couple of days ago I set out to come up with an emulation of Mail.app's "Mail Activity" panel. For the most part, it was a straight forward implementation. Create a horizontal NSSplitView in IB, set the top view to my source list (or whatever else you want -- it doesn't matter), set the bottom view to a custom view whose drawRect: method have been overridden to draw a background color matching the source list background color.<br /><br />Okay, that's fine and dandy. All that's left is to implement the "Show/Hide" toggle functionality. There were two constraints I wanted to make sure I abided by:<br /><ol><li>When toggling from hidden to shown, I want to restore the panel's height to it's previous height when it was last shown.</li><li>I want the toggle to animate like in Mail.</li></ol>Neither criteria are complicated, but neither get any help from NSSplitView provided functionality either.<br /><br /><h3> Restoring the previous height</h3>I can't fathom why, but NSSplitView has a method to set a divider's position (setPosition:ofDividerAtIndex:), but doesn't have a method to query a divider's position. The implementation is trivial, but that just makes me wonder all the more why NSSplitView doesn't have it. Maybe I'm overlooking something, and my implementation is horribly broken; I'm not really sure! But let's assume and hope that I'm not too far off :). Here's my implementation:<br /><br /><pre class="prettyprint">- (CGFloat)positionForDividerAtIndex:(NSInteger)idx<br />{<br /> NSRect frame = [[[self subviews] objectAtIndex:idx] frame];<br /> if (self.isVertical) {<br /> return NSMaxX(frame) + ([self dividerThickness] * idx);<br /> }<br /> else {<br /> return NSMaxY(frame) + ([self dividerThickness] * idx);<br /> }<br />}<br /></pre><br />This can be added as either a category extension or in a subclass. To actually restore the panel to it's previous height is dead simple once you have this. Upon hiding you call positionForDividerAtIndex: on the panel's parent split-view and save the value, and then upon unhiding you use the saved value to set the divider's new position.<br /><br /><h3> Animating the panel</h3><div>My initial reaction was to animate the frame of the panel view using NSView's animator proxy object. However, that just felt messy to me. There were to many unknowns in my mind -- how would changing the frame of subview interact with the rest of NSSplitView? My guess it that I'd most likely need to animate all subviews of the NSSplitView and do some additional magic in the NSSplitView's delegate methods. I quickly dismissed this option.</div><div><br /></div><div>My second thought was to somehow animate the split view's divider itself (which you might of guessed by the previous section on restoring a divider's position). This should correctly size the subviews and obey any constraints imposed by the NSSplitView's delegate. The problem is that Core Animation relies on key-value coding to animate arbitrary properties of a class. And although conceptually each divider's position kinda-sorta feels like a property, they aren't. But that was my inspiration! </div><div><br /></div><div>Before I get into the implementation, let me briefly describe how Core Animation can animate arbitrary properties. The first requirement for the class whose properties you want to animate is for the class to implement the NSAnimatablePropertyContainer protocol. To my knowledge, NSView and NSWindow are the only classes in AppKit that implement this protocol, and there isn't a way to implement this yourself without Apple's SPI. Part of NSAnimatablePropertyContainer is the animator method. It returns a proxy object responsible for initiating animations (the proxy object can also be treated and passed around just like the original object because it will respond to any method the original object responds to). The magic works by checking whether messages sent to the animator proxy conform to a property's key path on the original object. If it does, it will check with its animationForKey: to see if there exists an animation associated with that property, and there does then it will do magic, private CoreAnimation operations to perform the animation using a series of setValue:forKey: method calls for each sample along the animation. If the sent message either doesn't have an associated animation or doesn't represent a proper key-value compliant property, then the proxy will just forward the method to the original object.</div><div><br /></div><div>So, to animate custom properties that don't have default animations (such as frame or position do) we have to create and associate an animation of our choosing with the property, and then send the appropriate method to the animator proxy object. Here's a quick example to check out.</div><br /><pre class="prettyprint">@interface MyCustomView : NSView<br /><br />@property (assign) float customAnimatableProperty;<br /><br />@end<br /><br />@implementation MyCustomView<br /><br />@synthesize customAnimatableProperty;<br /><br />- (void)testAnimation<br />{<br /> // Add a custom animation to the animations dictionary<br /> CABasicAnimation* animation = [CABasicAnimation animation];<br /> NSMutableDictionary* newAnimations = [NSMutableDictionary dictionary];<br /> [newAnimations addEntriesFromDictionary:[self animations]];<br /> [newAnimations setObject:animations forKey:@"customAnimatableProperty"];<br /> [self setAnimations:newAnimations];<br /> <br /> // initiate the animation<br /> [[self animator] setCustomAnimatableProperty:10.0f];<br />}<br /><br />@end<br /></pre><br />Okay, so that does it for my explanation of Core Animation. Know the kicker: how so animate something that isn't associated with a property (such as setPosition:ofDividerAtIndex:)? My solution? Create a faux key path! By overriding animationForKey:, valueForUndefinedKey: and setValue:forUndefinedKey: and creating setPosition:ofDividerAtIndex:animate: to initiate the animation, I can trick the view into thinking properties exist for each divider. The faux key path is a series of key paths, one for each divider (which I call "dividerPosition0", "dividerPosition1", "dividerPosition2", etc..) and a catch-all key "dividerPosition" that all dividers can use if the user doesn't provide an animation specific to that divider.<br /><br />setPosition:ofDividerAtIndex:animate: is straightforward. It calls the original setPosition:ofDividerAtIndex: if animate is false, else it calls setValue:forKey on the animator proxy with the appropriate dividerPosition key.<br /><br /><pre class="prettyprint">- (void)setPosition:(CGFloat)position ofDividerAtIndex:(NSInteger)dividerIndex animate:(BOOL)animate<br />{<br /> if (!animate) {<br /> [super setPosition:position ofDividerAtIndex:dividerIndex];<br /> }<br /> else {<br /> [[self animator] setValue:[NSNumber numberWithFloat:position] forKey:[NSString stringWithFormat:@"dividerPosition%i", dividerIndex, nil]];<br /> }<br />}<br /></pre><br />The other three methods are small also, but share in common the need to parse the key to check whether the key is a valid "dividerPositionN" key, and if so extract that 'N' suffix integer value for use. animationForKey: will first check whether an animation all ready exists for the key, and if an animation doesn't it will return the defaultAnimation for the "dividerPosition" key.<br /><br /><pre class="prettyprint">- (id)animationForKey:(NSString *)key<br />{<br /> id animation = [super animationForKey:key];<br /> NSInteger idx;<br /> if (animation == nil && [self _tryParsingDividerPositionIndex:&idx fromKey:key]) {<br /> animation = [super animationForKey:@"dividerPosition"];<br /> }<br /> <br /> return animation;<br />}<br /></pre><br />And finally, valueForUndefinedKey: and setValue:forUndefinedKey: are just wrappers around positionForDividerAtIndex: and setPosition:ofDividerAtIndex:<br /><br /><pre class="prettyprint">- (id)valueForUndefinedKey:(NSString *)key<br />{<br /> NSInteger idx;<br /> if ([self _tryParsingDividerPositionIndex:&idx fromKey:key]) {<br /> CGFloat position = [self positionForDividerAtIndex:idx];<br /> return [NSNumber numberWithFloat:position];<br /> }<br /> <br /> return nil;<br />}<br /><br />- (void)setValue:(id)value forUndefinedKey:(NSString *)key<br />{<br /> NSInteger idx;<br /> if ([value isKindOfClass:[NSNumber class]] && [self _tryParsingDividerPositionIndex:&idx fromKey:key]) {<br /> [super setPosition:[value floatValue] ofDividerAtIndex:idx];<br /> }<br />}<br /></pre><br />And that's it! I stick this code in a NSSplitView subclass, and animate a divider by calling [mySplit setPosition:pos ofDividerAtIndex:divIndex animate:YES].<br /><br />I hope you've enjoyed this post and find the code useful. However, this code is young and not well-tested. If you come across any problems or have suggestions I'd love to hear them in the comments section. Until next time.. :)<br /><br /><script src="https://raw.github.com/gist/1522901/" type="text/javascript"></script>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com2tag:blogger.com,1999:blog-3945075237501190911.post-74361064645206159252012-03-21T22:00:00.001-07:002012-03-21T22:00:13.558-07:00Never do this:Rename libc++.1.dylib (in /usr/lib) to something other than libc++.1.dylib. I wanted to install a fresh svn build of libc++ on my home computer. I figured I wanted to keep the original dylib file around just incase anything went horribly wrong (TM). The irony? Renaming libc++.1.dylib basically made my whole machine fail. Internet stopped working, Finder stopped working, spotlight stopped working, launchd crashed on reboot causing my computer to hang, and who know what else was broken because of it.<br /><br />In hindsight, I guess it makes sense that renaming libc++.1.dylib would cause a lot of stuff to crash since libc++ is a dynamically loaded library. Though I always thought that when a dylib was loaded, it was somehow copied into the resident memory of the application. I guess not.<br /><br />It does make me wonder though... what IS the correct way to install libc++ if not to replace the file? libc++'s website suggests creating links in /usr/lib but goes on to say "either way to should work" (and then never goes on to say what that other way is..). Hum.<br /><br />And just to document what I did to fix it:<br /><br /><ol><li>Booted into single user mode (held command-s during reboot).</li><li>Saw a diagnostic message saying that stuff crashed because libc++.1.dylib was missing. This is when I realized that renaming libc++.1.dylib did have such catastrophic effects. </li><li>Rebooted into recovery mode (held command-r during reboot).</li><li>cd up several directories until I found "Volumes"</li><li>cd into Volumes/Macintosh\ HD/usr/lib</li><li>renamed the file to libc++.1.dylib (using the 'mv' command).</li><li>Rebooted normally, and prayed that this would fix it</li><li>And it did!</li></ol>Hopefully I can now figure out the correct way to install libc++ >.<<br />Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0tag:blogger.com,1999:blog-3945075237501190911.post-7935565405903716292012-03-11T12:52:00.001-07:002012-03-11T23:03:15.424-07:00Matrix-Vector MultiplicationI'm finishing up my spring break this week (I know - not much of a "spring" break, but you take what you can get) and I decided to start going through the MIT OpenCourseWare course on Linear Algebra. I want to be a graphics guy when I get out of school and I haven't taken a single linear algebra course yet! Shame on me.<br /><br />Gilbert Strang is a great lecturer. He teaches linear algebra in a such a way that even the small points he makes makes you go "aha!" I'd never had matrix-vector multiplication explained to me; it was just something I memorized and had to take a leap of faith for. In his lectures, Strang really hits home the importance of this idea of "linear combinations."<br /><br />Linear combinations are simple. If you have a bunch of vectors and a scalar coefficient for each vector, the linear combination is just the addition of each vector multiplied by its scalar.<br /><br />As it turns out, that's exactly what matrix-vector multiplication is, too. Each column in your matrix is one of the vectors and each component in your vector is one of the coefficients (the first component of the vector is the coefficient to the first column, the second component of the vector is the coefficient to the second column, etc.).<br /><br />The typical way to think of matrix-vector multiplication is to just consider your vector as a matrix and do the standard "take a row from the first matrix, take a column from the second matrix, perform the dot product" matrix multiplication.<br /><br />With the linear combination concept, matrix-vector multiplication becomes much more intuitive (for me at least) because it's just a normal linear combination:<br /><br /><center><a href="http://www.codecogs.com/eqnedit.php?latex=\begin{bmatrix}%20c1_{1}%20&%20c2_{1}%20&%20c3_{1}%20\\%20c1_{2}%20&%20c2_{2}%20&%20c3_{2}%20\\%20c1_{3}%20&%20c2_{3}%20&%20c3_{3}%20\end{bmatrix}\begin{bmatrix}%20x_{1}\\%20x_{2}\\%20x_{3}%20\end{bmatrix}%20=%20x_{1}\begin{bmatrix}%20c1_{1}\\%20c1_{2}\\%20c1_{3}%20\end{bmatrix}%20@plus;%20x_{2}\begin{bmatrix}%20c2_{1}\\%20c2_{2}\\%20c2_{3}%20\end{bmatrix}%20@plus;%20x_{3}\begin{bmatrix}%20c3_{1}\\%20c3_{2}\\%20c3_{3}%20\end{bmatrix}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\begin{bmatrix} c1_{1} & c2_{1} & c3_{1} \\ c1_{2} & c2_{2} & c3_{2} \\ c1_{3} & c2_{3} & c3_{3} \end{bmatrix}\begin{bmatrix} x_{1}\\ x_{2}\\ x_{3} \end{bmatrix} = x_{1}\begin{bmatrix} c1_{1}\\ c1_{2}\\ c1_{3} \end{bmatrix} + x_{2}\begin{bmatrix} c2_{1}\\ c2_{2}\\ c2_{3} \end{bmatrix} + x_{3}\begin{bmatrix} c3_{1}\\ c3_{2}\\ c3_{3} \end{bmatrix}" title="\begin{bmatrix} c1_{1} & c2_{1} & c3_{1} \\ c1_{2} & c2_{2} & c3_{2} \\ c1_{3} & c2_{3} & c3_{3} \end{bmatrix}\begin{bmatrix} x_{1}\\ x_{2}\\ x_{3} \end{bmatrix} = x_{1}\begin{bmatrix} c1_{1}\\ c1_{2}\\ c1_{3} \end{bmatrix} + x_{2}\begin{bmatrix} c2_{1}\\ c2_{2}\\ c2_{3} \end{bmatrix} + x_{3}\begin{bmatrix} c3_{1}\\ c3_{2}\\ c3_{3} \end{bmatrix}" /></a></center>If you work this out, you'll see this is equivalent to the dot-product technique.<br /><br />The linear combination repurposing of matrix-vector multiplication makes a lot of sense if you imagine the matrix to be a rotation matrix where each column is an axis that forms a basis/coordinate system, and the vector to be a point in space. If you visualize vector addition using the "head-to-tail" concept, you can almost visualize why multiplication of a rotation matrix and a point works!Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com2tag:blogger.com,1999:blog-3945075237501190911.post-33055817401063846702012-03-02T16:32:00.002-08:002012-03-11T23:05:07.653-07:00Computability and the Underpinnings of Computer ScienceThis week I concluded a <a href="http://www.cs.rit.edu/usr/local/pub/jeh/courses/380/" target="_blank">course</a> I took this quarter that covered the theory behind computer science. How comprehensive the course's coverage of a whole field's underpinnings was, I'm not qualified to speculate (but my guess would be: not very). With that said, it did cover a lot of interesting material. The course covered:<br /><br /><ul><li>The Chomsky hierarchy of formal languages.</li><ul><li>Regular languages/(non-deterministic and deterministic) finite state automata/regular expressions/left-linear and right-linear context-free grammars.</li><ul><li>Pumping lemma for proving non-regularity of languages</li></ul><li>Deterministic push-down automata (and whatever class of languages these are equivalent to)</li><li>Context-free grammars/push-down automata</li><ul><li>Ambiguity</li><li>Griebach Normal Form</li><li>Chomsky Normal Form and membership test Cocke-Younger-Kasami (CYK) algorithm.</li><li>Pumping lemma for proving language to be not context-free.</li></ul><li>An offhand mention of context-sensitive language</li><li>Recursively enumerable languages/Turing Machines.</li></ul><li>Computability (unfortunately we were not able to solve does P=NP and win that new car).</li><ul><li>P time</li><li>NP time</li><li>NP-hard vs. NP-complete vs. NP</li><li>Decidability vs. intractability</li></ul></ul>Overall I enjoyed the class a lot. I felt the course was not rigorous in its mathematical treatment of a lot of topics, but the professor did provide an alternative practical viewpoint which I appreciated (he was a compiler's guy, so he found grammars to be particularly interesting and snuck in a few question about LL parsers).<br /><div><br /></div><div>What I was disappointed about was the treatment of computability and exactly what the heck it means to be P or NP. I came away feeling only a little less confused about the problem than I was when I started the class. </div><div><br /></div><div>As always, I went to google. I found a great explanation on <a href="http://stackoverflow.com/questions/210829/what-is-an-np-complete-problem" target="_blank">stackoverflow</a> (scroll to grom's answer) that was a good balance between layman's terms and formal terms I learned in class. </div><div><br /></div><div>From my understanding now:</div><div><ul><li><b>P problems </b>are a class of problems where there is a known algorithm that can provide an answer/solution to the problem in polynomial time. Polynomial time can be O(1), O(n), or O(n^100000000). It doesn't matter.</li><li><b>NP problems</b> are a class of problems where we can guarantee there exists a solution, but we can't compute it in polynomial time; it can only be computed in non-deterministic polynomial time. What that means is that there exists a finite, polynomial amount of steps to find the solution but we can't describe a polynomial algorithm to reach it. We have to resort to an exhaustive, "brute-force" search for the solution. This is a problem because some NP problems are intractable which means even though it's possible to find an answer it may take so long it's not even worth it.</li><li><b>NP-complete problems</b> are problems that are NP but have the special property that all other NP problems can be reduced to them in polynomial time. This "simply" means any NP problem can be transformed into the NP-complete problem using a polynomial time algorithm. </li><li><b>NP-hard problems</b> are problems that are at least as difficult to solve as the hardest NP problem(s). Note, this class of problems includes problems that are harder than any NP problem (which means they may not even be solvable in non-deterministic polynomial time).</li></ul>So the big question is: does P=NP, meaning are all P problems equivalent to NP problems? If this is true, that means a lot of hard problems we haven't been able to reasonably compute would be solvable in an amount of time that's worthwhile. An example of this type of problem would be breaking cryptography and security codes which could be a severely good thing or bad thing (depending who you are). And so I guess that's why the <a href="http://www.claymath.org/millennium/" target="_blank">Clay Mathematics Institute</a> is willing to give any person who solves whether P=NP $1 million for their efforts.</div>Jedd Haberstrohttps://plus.google.com/114880443833205151313noreply@blogger.com0