Forem: Fulton Byrne

Trying out git submodules

Fulton Byrne — Sat, 02 Jan 2021 16:41:14 +0000

Organizing code into multiple git repositories remains one of the most charming organization methods available to developers. Multiple repositories work best when teams logically isolate their work together and away from others, but this system may break down when teams develop dependencies on each other's work.

Perhaps, a team writes helm charts and deploys them from one repository, but code that the helm chart deploys exists in another. Git submodules provide an oft overlooked method for mitigating cognitive load when managing dependent repositories.

When following this tutorial feel free to fork my example repository, git@github.com:Freyert/submodule_example.git, and follow along.

Getting started with submodules is actually fairly easy:

git submodule add git@github.com:left-pad/left-pad.git

NOTE: left-pad is no longer maintained.

This clones the remote repository into the current directory and adds configuration to .gitmodules at the git repository’s root. Git add and git commit these changes then push to the remote repository.

Now remove the cloned version of the repository and try cloning down the repository again. Notice that the submodule resources were not cloned down from the submodule’s repository. This may not make sense, but imagine a repository with hundreds of submodules. Pulling only the submodules required saves a lot of time. Here is one way to clone a submodule:

git submodule update --init

This initializes and updates the git submodule, therefore fetching the remote code. If the work environment generally requires all submodules when cloning the repository, more recent versions of git allow this command:

git clone git@github.com:Freyert/submodule_example.git --recurse-submodules

That should suffice for a quick taste of submodules to peak interest. Managing dependencies through submodules introduces its own complexity which is why almost every system today includes dependency management frameworks. Think NPM for nodejs or Ruby Gems for Ruby. When considering submodules weigh the cost of using submodules against the cost of introducing a dependency management system. Most of the time dependency management wins, but submodules do have some advantages that are worth learning about.

Notes on Dr. Andrew Ng's "Machine Learning" Week 5

Fulton Byrne — Sat, 01 Feb 2020 21:04:01 +0000

This week is definitely one of the more difficult to get through. The exercise has a high number of complex, moving parts that all need to move together in order to complete.

Often times when struggling with concepts I look for other explanations. I found Zeyuan Hu's write up on the math for the exercise a great aggregation of all the math for the week: Andrew Ngs ML Week 04 - 05.

I also discovered some jewels in the course forums. The course forums are generally a horror story of duplicated questions, but if you look hard enough you can find some serious help from the course mentors.

Programming Exercise Tutorial (List) will be my first stop before starting any exercises from here on out. The mentor provided tutorials typically provide a nigh step by step write up to completing any exercise.

Mistakes Were Made

The common errors I ran into were:

Incorrect Dimensions
Matrix Multiplication Caveats

Incorrect Dimensions

ex4 tutorial for nnCostFunction and backpropagation goes in depth on how each matrix dimension should match.

I also found these debugging tips to be extraordinarily helpful combined with knowing how to use the Octave Debugger.

Matrix Multiplication

I really prefer using the vectorized approach for any solution in the course. They are generally far easier to write, but you can also get really mixed up because matrix multiplication has a lot of rules and conditions.

The cost function with the double sigmas made me really want to use matrix multiplication to do summation, but I ended up using the easier element wise multiplication and summation.

However, the forum post Computing the NN cost J using the matrix product explains the intuition needed in order to correctly apply matrix multiplication in this case.

I'm writing mine out in Octave as a way to translate the material between two mediums. So we begin with the two mxK (m = 2 & K = 3) matrices:

A = [1 2; 3 4; 5 6]
B = [7 8; 9 10; 11 12]

We want the sum over the rows and columns of the element wise product:

sum(sum(A .* B))
ans =  217

Naively, I expect I can reach an equivalent answer by the matrix product of transpose A and B.

Surprise! its an mxm (2x2) matrix because when you multiply m x K and K x m you get an m x m matrix.

The cost function is supposed to reduce to a scalar value though. What's missing? As the mentor's article points out we just need to take the trace or the sum of the main diagonal of a square matrix for our answer:

trace(A' * B)
ans = 217

Does this always work? In this instance, where we want the sum of the columns and rows of two matrices of equal dimension: yes. This is not always the case though.

Matrix multiplication requires mxn * nxp dimensions. So only the columns of the first must match the rows of the second. You won't necessarily receive a square matrix.

The Hadamard Product a.k.a element wise multiplication only requires that the two matrices have the same dimensions. Again, not necessarily resulting in a square matrix.

Specifically to the above cost function though, this does always work because y and x are both mxK. Intuitively this makes sense. If X is a matrix of (instances) x (features) so that each row is an instance with columns for each feature then each row of y is an instance's "actual" value. That alone doesn't work because y is typically either a column vector or its columns correspond to the number of classes as in the case of digit recognition.

The reason this does always work for the cost function is we are not dealing with X, but h(X) which contains the "predicted values" for each instance in X therefore having the same dimensions as y. Therefore the formula can multiply h(X) and y because they have the same dimensions and we can sum the result using trace because their product is a square matrix.

I won't make guarantees here though as this really only applies to the double sigma part of the equation. Evaluating the terms inside the equation is another story, but I wager if I encountered this equation again in another exercise I could build the vectorized version now that I understand more of the rules.

It is also interesting to note that the mentor points out the vectorized implementation may not necessarily perform better due to a lot of wasted calculations that are thrown away after using trace. So if you built the element wise version like myself give yourself a pat on the back.

Those are my notes for the week! Best of luck!

Notes on Andrew Ng's "Machine Learning" Week 2

Fulton Byrne — Tue, 24 Dec 2019 23:43:39 +0000

The most difficult part of week 2 is taking the formulas and converting them into Octave. Especially, if you don't quite grasp the formula notations and Octave is new.

I will walk through some of the boiler plate code regarding Gradient Descent, the hypothesis function, cost function, and try to develop some intuition to move things forward. I will also point out my own gaps of understanding in the hopes that I can fill them in later.

Know Your Resources

As I was writing these notes I stumbled on the "Resources" section which has been immensely helpful and clarified quite a lot. I highly recommend reading the lecture notes for each week as they clarify the videos and other resources quite a lot.

The Shape of Matrices

The shapes of two matrices dictate whether or not you can compute the dot product of the two.

In Dr. Ng's slides on Vectorization he calculates the following hypothesis function using an iterative notation (summation) and a vectorized notation (transpose and dot product):

Note that in this case "x_j" (x subscript j) indicates the value of feature "j". The Week 2 Lecture Notes under resources is incredibly helpful here. "x" is a column vector of feature values. Perhaps its the square footage of each house in the data set or the number of floors for each house. Whereas the thetas represent "weights" for each feature such as the price per floor or price per square foot.

The week 2 notes expand this function like so:

hθ(x)=θ_0+θ_1x_1+θ_2x_2+θ_3x_3+⋯+θ_nx_n

This hypothesis function takes a row or instance from the data set, say a house, and takes each of its features x_y multiplied against their corresponding θ_y or weight. The value for theta is what we attempt to discover through Gradient Descent.

A part of the exercise I don't quite understand is that a column of ones is added to X. This column of ones will be paired with θ_0 when calculating the hθ(x) function. This is definitely a part I have confusion on.

Getting back to vectorization. Seeing that the summation form of the hypothesis function can be represented as hθ(x)=θ_0+θ_1x_1+θ_2x_2+θ_3x_3+⋯+θ_nx_n makes it a lot easier to connect this to matrix multiplication where you multiply each value of a row times each value of a column in two matrices and sum them to get a new value.

Since we know x and theta are column vectors lets see how the vectorized version of the hypothesis function would actually work.

% initialize column vector a. ; starts a new row.
octave:8> a = [ 1; 2; 3; 4; 5; 6 ]
a =

   1
   2
   3
   4
   5
   6

% initialize column vector b. ; starts a new row.
octave:9> b = [ 1; 2; 3; 4; 5; 6]
b =

   1
   2
   3
   4
   5
   6

% and voila a transpose dot product b returns a single value.
octave:10> a' * b
ans =  91

Continuing on the Programming Tips from Mentors has a really helpful clarification to reach a fully vectorized solution:

"h(x) = theta' * x" vs. "h(x) = X * theta?"

Lower-case x typically indicates a single training example.

Therefore X potentially has multiple "x" or single training examples. A training example in our case would be a row and each column in the row a feature for that training sample.

Remember the Σ(h(x_j) - y)? The sigma tells us we need to calculate this for all rows of X. Since X has a column for each row of theta we can multiply them together as we did theta' * x.

Calculating Cost

The programming exercise has this definition for the cost function:

The cost function J(θ) has a very minor detail where it plugs x^(i) into the hypothesis function. Meaning for a particular feature/column calculate the hypothesis over all training examples. The summation symbols to the left indicate that this should be done for each column in the data set. You could do this iteratively, but its a lot easier when you realize X * theta means the same thing. X * theta means multiply every training example (row) times every theta (column) aka θ_0 + θ_1x_1.

Instead of subtracting one x from one y we can now use the h(x) vector calculated above subtract the y matrix.

The interesting bit though is that originally y was a single column and so was X:

X = data(:, 1); y = data(:, 2);
disp(size(X))
disp(size(y))

% 97 1
% 97 1

However, X is reassigned to have two columns. Subtraction between these two matrices should not be possible, but Octave allows it via "broadcasting".

Since y has fewer dimensions Octave transforms it into a matrix consisting of [y, y] to match X dimension of 97 x 2. At this point the ones column on X is a throw away column used to provide proper shape. X[:,2] and y[:] have a relation recorded in the original dataset, but the arbitrary ones column should have no such relation. Perhaps their hint about dimensional analysis makes this make sense.

The next trick comes when trying to figure out how to take h(x) - y to the power of 2. Remember everything in the function definition is defined iteratively so what the function is telling us is to square each element of the matrix, not the entire matrix.

Your intuition might be to use Octave's broadcast exponentiation (x.^y or x.**y) provides this for us:

Element-by-element power operator. If both operands are matrices, the number of rows and columns must both agree, or they must be broadcastable to the same shape. If several complex results are possible, the one with smallest non-negative argument (angle) is taken. This rule may return a complex root even when a real root is also possible. Use realpow, realsqrt, cbrt, or nthroot if a real result is preferred.

(Broadcasting 19.2)

Which I think actually works since its an element-by-element power operation, but the vectorized version is described in the week 2 lecture notes as follows:

This preserves the iterative squaring of each term by multiplying each position in the matrix by itself. Pretty neat!

Conclusion

There is so much more I still don't quite understand, but at this point I have a framework for converting iterative solutions to vectorized solutions. Some of intuition behind the hypothesis function and the cost functions themselves are still beyond me. Why is understanding "dimensional analysis" important? Why is it OK to do broadcast subtraction of (X * theta) - y?

Parsing JSON with Circe

Fulton Byrne — Sat, 02 Nov 2019 16:02:53 +0000

I received some very good feedback on my last post: Scala has some popular libraries that should be avoided. Not only that, I learned a few libraries I considered before required more investigation. Today I want to look at Circe. After working in Scala a bit, I understand the problems it wants to solve and why the project makes the choices it does.

Cursors

Think about how you use JSON for a minute. Programs retrieve or assign to a single field at a time. Parsing the entire document when the program only needs one field wastes processing time and heap memory.

car["age"] = 23
console.log(car["age"])

When I wrote more NodeJS I would not bat an eye at parsing one document entirely, but when working with many documents or a large document I would use JSONStream to selectively parse items out of the document. This provides two benefits: it does not require storing the entire document into memory and only the pertinent fields parse.

Circe provides "cursors", an API to traverse raw JSON and project the values therein. Think about cursors the way you think about the blinking | cursor when writing an email or text. It keeps track of your place in the document, moves around the document to track the new current location, and even selects interesting text for modification.

Example

I'm assuming some sbt knowledge. Here's the build.sbt I used to run this project.

name := "basic_json"

version := "0.1"

scalaVersion := "2.12.2"

lazy val circeVersion = "0.12.2"


libraryDependencies ++= Seq(
  "io.circe" %% "circe-parser" % circeVersion,
  "io.circe" %% "circe-core" % circeVersion,
  "io.circe" %% "circe-generic" % circeVersion
)

This example iterates through a JSON document via a cursor to select and present the car's age the document describes.

import io.circe.parser._
object Main extends App {
  val rawJson: String =
    """
      |{
      |  "hello": "world",
      |  "car": {
      |    "type": "honda",
      |    "age": 23,
      |    "color": "blue",
      |    "used": true,
      |    "owner": {
      |       "name": "darwin",
      |       "age": 43
      |    }
      |  }
      |}
      |""".stripMargin

  val parsed = parse(rawJson) match {
    case Left(s) => s
    case Right(r) => r.hcursor.downField("car").get[Int]("age") match {
      case Right(age) => age
      case Left(l) => l
    }
  }

  println(parsed)

}

A lot going on, but focusing on the critical area simplifies things:

  val parsed = parse(rawJson) match {
    case Left(s) => s
    case Right(r) => r.hcursor.downField("car").get[Int]("age") match {
      case Right(age) => age
      case Left(l) => l
    }
  }

Circe's parse from import io.circe.parser._ ingests the raw JSON document and returns an Either. Left contains useful information about failures, while Right contains success values. I always return the unwrapped Left value since I just want to log results, but ideally Lefts would branch code into an error handling branch.

Finally, the important piece: actually retrieving the data.

r.hcursor.downField("car").get[Int]("age")

r represents the Right result of parse which contains an hcursor into the JSON document. HCursors maintain a cursor's history so relevant history may surface during an error indicating why the cursor operation failed.

downField("x") moves the cursor's position into the JSON object specified by "x". Very similar to how JavaScript accesses object via obj["x"]. get[Type]("field") performs a downField to the "field" key, parses the JSON object at that point, and then casts it to the type specified. In my case I cast the "age" field to an Int. Casting tells Scala to take an object it thought was text and convert it into a Scala object like an Int.

Conclusion

Scala definitely requires more thought when working with JSON. While Circe's techniques seem radically different from Javascript at first glance; these languages really have a lot in common. As an exercise try triggering different Left branches to see the messages they produce.

Easy JSON with Scala

Fulton Byrne — Sun, 20 Oct 2019 19:03:56 +0000

Update: I've been notified the json4s has some fairly severe and public DoS issues.

Andriy Plokhotnyuk

@aplokhotnyuk

@Fbyrne CAUTION: json4s is vulnerable under DoS/DoW attacks which exploit hash collision vulnerabilities of Scala's HashMap or parsing vulnerabilities of Java's BigInteger/BigDecimal values: github.com/json4s/json4s/…

19:46 PM - 20 Oct 2019

I'll make another post exploring this basic case using some of the libraries recommended in the thread.

I had been searching for an easy way to work with JSON in Scala. Most libraries expect the user wants to create advanced encoding and decoding functionality; therefore making them a bit difficult to jump into.

Fortunately I found this StackOverflow post that showed how to represent JSON using basic Scala data types such as Map, List, and String:

How to convert Scala Map into JSON String?

Jan 14 '15 Comments: Answers: 7

For example, I have this Map value in Scala:

val m = Map(
    "name" -> "john doe", 
    "age" -> 18, 
    "hasChild" -> true, 
    "childs" -> List(
        Map("name" -> "dorothy", "age" -> 5, "hasChild" -> false),
        Map("name" -> "bill", "age" -> 8, "hasChild" -> false)
    )
)

I want to convert…

Open Full Question

The really big takeaway is that json4s performs recursive JSON encoding/decoding with fundamental Scala types where most basic libraries will only encode/decode one level deep.

Getting started is fairly easy.

1. Follow the installation steps for json4s.

Add the following to your build.sbt file:

// Change 3.6.7 to whatever the latest version is on Maven Central
libraryDependencies += "org.json4s" %% "json4s-native" % "3.6.7"

2. Decode JSON

  import org.json4s._
  import org.json4s.native.JsonMethods._

  object DecodeJSON extends App {
    val jsonString =
      """
        |{
        |  "hello": "world",
        |  "data": {
        |   "number": 12,
        |   "lie": false
        |   }
        |}
        |""".stripMargin

    val decoded = parse(jsonString)
    println(decoded)
    // JObject(List((hello,JString(world)),(data,JObject(List((number,JInt(12)), (lie,JBool(false)))))))
  }

Notice the output uses special wrapper classes to represent the JSON data types and structure. The full list is found here.

3. Encoding JSON

Decoding recursively from Maps and Lists is possible as shown in the Stackoverflow post, but json4s provides a domain specific language (DSL) for creating JSON.

import org.json4s.JsonDSL._
import org.json4s.native.JsonMethods._

object Hello extends App {

// ~ is part of the json4s scala DSL
// it means these fields belong on the same Object level.
// It corresponds directly to a JSON comma (,).

  val jsonScala = ("hello" -> "world") ~
    ("data" ->
      ("number" -> 12) ~
        ("lie" -> false)
      )
  println(compact(render(jsonScala)))
  // {"hello":"world","data":{"number":12,"lie":false}}
}

Conclusion

There are many JSON libraries for Scala out there, but json4s excels for quick and dirty projects involving dynamic JSON and simple types. Also, I'm really new to Scala so if you have a library you enjoy for working with JSON please share!

Forem: Fulton Byrne

Trying out git submodules

More Reading

Notes on Dr. Andrew Ng's "Machine Learning" Week 5

Mistakes Were Made

Incorrect Dimensions

Matrix Multiplication

Notes on Andrew Ng's "Machine Learning" Week 2

Know Your Resources

The Shape of Matrices

Calculating Cost

Conclusion

Parsing JSON with Circe

Cursors

Example

Conclusion

Easy JSON with Scala

How to convert Scala Map into JSON String?

Conclusion