m8ta
you are not logged in, login. new entry
text: sort by
tags: modified
type: chronology
{1408}
hide / edit[0] / print
ref: -2018 tags: machine learning manifold deep neural net geometry regularization date: 08-29-2018 14:30 gmt revision:0 [head]

LDMNet: Low dimensional manifold regularized neural nets.

  • Synopsis of the math:
    • Fit a manifold formed from the concatenated input ‘’and’’ output variables, and use this set the loss of (hence, train) a deep convolutional neural network.
      • Manifold is fit via point integral method.
      • This requires both SGD and variational steps -- alternate between fitting the parameters, and fitting the manifold.
      • Uses a standard deep neural network.
    • Measure the dimensionality of this manifold to regularize the network. Using a 'elegant trick', whatever that means.
  • Still yet he results, in terms of error, seem not very significantly better than previous work (compared to weight decay, which is weak sauce, and dropout)
    • That said, the results in terms of feature projection, figures 1 and 2, ‘’do’’ look clearly better.
    • Of course, they apply the regularizer to same image recognition / classification problems (MNIST), and this might well be better adapted to something else.
  • Not completely thorough analysis, perhaps due to space and deadlines.

{661}
hide / edit[3] / print
ref: -0 tags: computational geometry triangulation ocaml kicadocaml zone fill edge date: 01-26-2009 01:47 gmt revision:3 [2] [1] [0] [head]

I have been working hard to add zone support to kicadocaml since the implementation in kicad's PCBnew is somewhat borken (at least for my boards). It is not a very easy task!

Roughly, the task is this: given a zone of copper pour, perhaps attached to the ground net, and a series of tracks, vias, and pads also on that layer of the PCB but not on the same net, form cutouts in the zone so that there is an even spacing between the tracks/vias and zone.

Currently I'm attacking the problem using triangles (not polygons like the other PCB softwares). I chose triangles since I'm using OpenGL to display the PCB, and triangles are a very native mode of drawing in OpenGL. Points are added to the triangle mesh with an incremental algorithm, where the triangles are stored as a linked-mesh : each triangle has a pointer (index#) to the triangle off edge ab,bc,ca. This allows finding the containing triangle when inserting a point a matter of jumping between triangles; since many of the points to be inserted are close to eachother, this is a relatively efficient algorithm. Once the triangle containing a point to be inserted is found, the triangle is split into three, the pointers are updated appropriately, and each triangle is tested to see if flipping with it's pair would result in a net larger smallest interior angle between the two. (This is not the same as Delaunay's criteria, but it is simpler, and it produces equally beautiful pictures.)

The problem is when two triangles are allowed to overlap or a gap is allowed - this makes the search algorithm die or get into a loop, and is a major major problem of the approach. In Guibas and Stolfi's paper, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", they use an edge data structure, rather than a triangle data structure, which I suppose avoids this problem. I was lazy when starting this project, and chose the more obvious triangle-centric way of storing the data.

The insertion of points is actually not so hard; the big problem is making sure the edges in the original list of polygons are represented in the list of edges in the triangle mesh. Otherwise, triangles will span edges, which will result in DRC violations (e.g.g copper too close to vias). My inefficient way of doing this is to calculate, for all triangles, their intersections with the polygon segments, then adding this to the mesh until all segments are represented in the list. This process, too, is prone to numerical instability.

Perhaps the solution is to move back to an edge-centric data representation, so that certain edges can be 'pinned' or frozen, and hence they are guaranteed to be in the triangle mesh's edge list. I don't know; need to think about this more.


Update: I got most of it working; at least the triangulation & making sure the edges are in the triangle mesh are working. Mostly there were issues with numerical precision with narrow / small triangles; I rewrote the inside triangle function to use the cross product, which helped (this seems like the simplest way, and it avoids divisions!):

ocaml
let insidetri a b c d = 
	cross (sub b a) (sub d a) > 0.0 &&
	cross (sub c b) (sub d b) > 0.0 &&
	cross (sub a c) (sub d c) > 0.0 
	;;

as well as the segment-segment intersection algorithm:

ocaml
let intersect a b c d = 
	(* see if two line segments intersect *)
	(* return the point of intersection too *)
	let ab = sub b a in
	(* a prime is the origin *)
	let bp = length ab in
	let xx = norm ab in
	let yy = (-1.) *. (snd xx) , (fst xx) in
	let project e = 
		(dot (sub e a) xx) , (dot (sub e a) yy)
	in
	let cp = project c in
	let dp = project d in
	let cd = sub dp cp in
	let m = (fst cd) /. (snd cd) in
	let o = (fst cp) -. m *. (snd cp) in
	let e = add (scl ab (o /. bp)) a in
	(* cp and dp must span the x-axis *)
	if ((snd cp) <= 0. && (snd dp) >= 0.) || ((snd cp) >= 0. && (snd dp) <= 0.) then (
		if o >= 0. && o <= bp then ( true, e )
		else ( false, e )
	) else ( false, e )
	;;

Everything was very sensitive to ">" vs. ">=" -- all must be correct. All triangles must be CCW, too, for the inside algorithm to work - this requires that points to be inserted close to a triangle edge must be snapped to that edge to avoid any possible CW triangles. (Determining if a triangle is CW or CCW is as simple as measuring the sign of the smallest cross product between two segments). I tried, for a day or so, to include a specialized function to insert points along a triangle's edge, but that turned out not to matter; the normal flipping routine works fine. I also tried inserting auxiliary points to try to break up very small triangles, but that really didn't affect the stability of the algorithm much. It is either correct, or it is not, and my large board was a good test suite. I have, however, seeded the triangularization with a grid of (up to) 20x20 points (this depends on the aspect ratio of the region to be filled - the points are equally spaced in x and y). This adds (max) 800 triangles, but it makes the algorithm more stable - fewer very narrow triangles - and we are working with sets of 10,000 triangles anyway for the large zones of copper.

Some corrections remain to be done regarding removing triangles based on DRC violation and using the linked-mesh of triangles when calculating edge-triangle edge intersection, but that should be relatively minor. Now I have to figure out how to store it in Kicad's ".brd" file format. Kicad uses "Kbool" library for intersection polygons - much faster than my triangle methods (well, it's in C not ocaml) - and generates concave polygons not triangles. Would prefer to do this so that I don't have to re-implement gerber export. (Of course, look at how much I have re-implemented! This was originally a project just to learn ocaml - Well, gotta have some fun :-)