• Mathematician Chat v. 3.999...
    1,232 replies, posted
[QUOTE=sltungle;48162764]It's a little bit harder than it would otherwise be to generalise because I'm also considering diagonal elements, and wrapping with diagonal elements is a bit tricky. For example, on an NxN grid EVERY element, i, has a ±1, ±N and ±(N-1) neighbour; the ±(N+1) case isn't quite so simple with only N(N-2) elements having such a neighbour; the remaining 2N elements have neighbours at sites which are scattered around in a fashion which hasn't yet clicked to me. This probably wouldn't be so difficult if I wasn't using Matlab to program, but oh well.[/QUOTE] Can you not use an N-dimensional array for this rather than one huge list? I haven't used MATLAB for years, so perhaps it's not as simple as that. Unless you need super-high performance I really recommend the extra level of abstraction.
[QUOTE=Joey90;48166141]Can you not use an N-dimensional array for this rather than one huge list? I haven't used MATLAB for years, so perhaps it's not as simple as that. Unless you need super-high performance I really recommend the extra level of abstraction.[/QUOTE] OH shit, he's actually using a 1D array, I couldn't even figure out what he was talking about in his post. sltungle, you should really consider using an n-dimensional array for this, calculating the indices for a linear array by yourself is a huge pain in the ass and will just lead you into unnecessary errors. With an n-D array, you can easily generate all possible neighbors of a cell by just generating all possible lists of length n with elements from {-1, 0, 1} (except for the one with only zeros), then just use those as offsets for the indices. You'll probably need to use the function sub2ind to actually index the array once you have the indices calculated.
Isn't Mat(rix)lab great with multidimensional arrays??
The issue with most of these solutions is that they require the use of for loops (which for large arrays are incredibly time consuming; something I unfortunately know from experience), or inbuilt functions which are hardly ever optimised properly. I have, however, just stumbled on a method for very rapidly building 2 dimensional adjacency matrices with wrapping from nothing more than the 1 dimensional adjacency matrix. I figured the possible set of movements in 2 dimensions is just the set of possible movements in two 1 dimensional spaces (obviously), plus a few adjacent sites (diagonal movements). So on a hunch, I tried the tensor product of two 1 dimensional adjacency matrices, but it didn't look quite right; that said, it did have a lot of the elements in common, so I decided to try adding to this both permutations of the tensor product with the identity matrix and holy shit it gives me a two dimensional adjacency matrix with wrapping. I'm working on making sense of this on pen and paper now and hopefully I'll more easily be able to generalise this to n-dimensions. [editline]12th July 2015[/editline] Ahha! I think I've just rediscovered the Cartesian or the tensor product of graphs!
[IMG]http://latex.codecogs.com/gif.latex?\dpi{120} \large A_n %3D (\mathbb{I}+A_1)^{{\otimes}{n-1}} - \mathbb{I}^{{\otimes}{n-1}}[/IMG] If I'm correct, I'm pretty sure this generates the adjacency matrix for an n-dimensional ring given the 1-dimensional adjacency matrix for a circle (i.e. line with wrapping), where the funky I symbol is meant to be a funky 1 (the identity matrix). Gotta test it out first, but it's going to take me a while to figure out how to code tensor powers.
[QUOTE=sltungle;48182957]The issue with most of these solutions is that they require the use of for loops (which for large arrays are incredibly time consuming; something I unfortunately know from experience), or inbuilt functions which are hardly ever optimised properly.[/QUOTE] Well, there's usually always a way to avoid using for loops in matlab. For example, if you want to know the neighbor of every cell in a particular direction, just circshift the array by an appropriate offset. If you want to know all the neighbors of every cell, you could then build an n+1 dimensional array containing all the possible circular shifts. Once you have that and want to know the number of live neighbors, you can just sum that array along the n+1th dimension.
[QUOTE=pebkac;48184071]Well, there's usually always a way to avoid using for loops in matlab. For example, if you want to know the neighbor of every cell in a particular direction, just circshift the array by an appropriate offset. If you want to know all the neighbors of every cell, you could then build an n+1 dimensional array containing all the possible circular shifts. Once you have that and want to know the number of live neighbors, you can just sum that array along the n+1th dimension.[/QUOTE] See above. I think I've determined how to obtain the directly adjacent cells for any 'square' graph of arbitrary dimensions; it spits out the correct adjacency matrix for 2 dimensions (checked by hand), it spits out the correct adjacency matrix for 3 dimensions (checked by hand), and it produces the correct number of neighbours for any dimension n. Unfortunately it's difficult to check if the elements are correct by hand for n>3 because the adjacency matrix in 4 or more dimensions is fucking huge, but I might give it a crack later and merely check one instance each of unique sites (corner elements, edge elements, face elements, volume elements, and finally elements buried in the hypervolume). The only for loop I had to use in the end was a tiny one to help build a tensor power function. Other than that, spdiags is the most complicated thing I've had to use.
[QUOTE=sltungle;48183669][IMG]http://latex.codecogs.com/gif.latex?%5Cdpi%7B150%7D%20%5Chuge%20A_n%20%3D%20%28%5Cmathbb%7BI%7D+A_1%29%5E%7B%5Cotimes%20n%7D%20-%20%5Cmathbb%7BI%7D%5E%7B%5Cotimes%20n%7D[/IMG] If I'm correct, I'm pretty sure this generates the adjacency matrix for an n-dimensional ring given the 1-dimensional adjacency matrix for a circle (i.e. line with wrapping), where the funky I symbol is meant to be a funky 1 (the identity matrix). Gotta test it out first, but it's going to take me a while to figure out how to code tensor powers.[/QUOTE] So that notation is just "tensor product these together n times"?
[QUOTE=JohnnyMo1;48184932]So that notation is just "tensor product these together n times"?[/QUOTE] Yup!
Who wants me to start dumping problems from an Olympiad book? Can post solutions too if needed.
And I'm pretty sure to get perpendicular nearest neighbours for an n-dimensional torus/'square' graph with wrapping or connections it's simply the sum of all permutations of: [IMG]http://latex.codecogs.com/gif.latex?\dpi{100} \huge \mathbb{I}^{\otimes (n-1)}\otimes A_1[/IMG] So like AIII + IAII + IIAI + IIIA for 4 dimensions.
What is this (X) about and what is it doing up here on power? I^(X) ? Anyway, I was looking at Neural networks, MLP, it's just bunch of scalar products and activation function, is that really so simple?
Calculating an output is indeed very simple. The learning algorithm is a bit more complicated. Figuring out the correct amount of layers & neurons is also pretty hard (what I got from it is that you just try to figure that out heuristically). One rule is that you can't have as much nodes as inputs because then you'll overfit your model.
[QUOTE=Fourier;48193618]What is this (X) about and what is it doing up here on power? I^(X) ? [/QUOTE] Tensor product: [url]https://en.wikipedia.org/wiki/Tensor_product[/url] The power and (n-1) I think means tensor product I with itself (n-1) times
I don't know algebra help
[QUOTE=Hollosoulja;48195638]I don't know algebra help[/QUOTE] Only school can save you [editline]13th July 2015[/editline] [QUOTE=Number-41;48193704]Calculating an output is indeed very simple. The learning algorithm is a bit more complicated. Figuring out the correct amount of layers & neurons is also pretty hard (what I got from it is that you just try to figure that out heuristically). One rule is that you can't have as much nodes as inputs because then you'll overfit your model.[/QUOTE] If I got this correctly, I could also other number types such as complex numbers or quaternions or matrices instead of reals? Weights should be same type of course. But you are correct, training those types of networks can become nightmare really soon.
[QUOTE=Fourier;48196669]Only school can save you [editline]13th July 2015[/editline] If I got this correctly, I could also other number types such as complex numbers or quaternions or matrices instead of reals? Weights should be same type of course. But you are correct, training those types of networks can become nightmare really soon.[/QUOTE] I guess so, but I think you have to be careful. Say you're working in Matlab, where everything in terms of variable types and predefined functions is taken care of for you, you could just enter an array of complex numbers. If your activation function is atan() though, you might stumble upon trouble, as the complex atan() function doesn't behave as an activation at all. Look at the plot for [URL="http://www.wolframalpha.com/input/?i=atan%28ix%29"]complex input[/URL]. It has poles, so you'll have to deal with that, possibly. You could deal with magnitudes at intermediate steps, maybe? Of course you could split a single complex input into the real and imaginary part, same for matrices. I think that's the easiest way. My AI course didn't really touch the question.
[QUOTE=Number-41;48207074]I guess so, but I think you have to be careful. Say you're working in Matlab, where everything in terms of variable types and predefined functions is taken care of for you, you could just enter an array of complex numbers. If your activation function is atan() though, you might stumble upon trouble, as the complex atan() function doesn't behave as an activation at all. Look at the plot for [URL="http://www.wolframalpha.com/input/?i=atan%28ix%29"]complex input[/URL]. It has poles, so you'll have to deal with that, possibly. You could deal with magnitudes at intermediate steps, maybe? Of course you could split a single complex input into the real and imaginary part, same for matrices. I think that's the easiest way. My AI course didn't really touch the question.[/QUOTE] It doesn't matter really, it's just my curiosity. Could also jut put magnitude since more closer to center -> more true/more truth.
Are there any major math specific forums any of you frequent?
Nope, sorry. You know anything good?
[QUOTE=Drakehawke;48214652]Are there any major math specific forums any of you frequent?[/QUOTE] Not really math-major specific, but /r/math. Not really "forums," but math stackexchange and mathoverflow.
I've been considering taking a discrete math class as part of some required math in my degree. Despite what I've researched about it, I still don't really know what it is and what to expect from a first-year level course in it. What exactly should I expect and what would I be doing in a discrete math course?
[QUOTE=Carlito;48251414]I've been considering taking a discrete math class as part of some required math in my degree. Despite what I've researched about it, I still don't really know what it is and what to expect from a first-year level course in it. What exactly should I expect and what would I be doing in a discrete math course?[/QUOTE] Discrete math is the bees knees! I've tutored it for 3 semesters now and marked ~300 exams a few weeks ago. First year discrete math usually covers the basics of: - Logic - Number Theory - Set Theory - Graph Theory - Proving Mathematical Statements - Functions and Relations - Counting If you want to know more about any of these either search it on wikipedia or ask this thread. (Which uni btw?)
[QUOTE=Wunce;48251853]Discrete math is the bees knees! I've tutored it for 3 semesters now and marked ~300 exams a few weeks ago. First year discrete math usually covers the basics of: - Logic - Number Theory - Set Theory - Graph Theory - Proving Mathematical Statements - Functions and Relations - Counting If you want to know more about any of these either search it on wikipedia or ask this thread. (Which uni btw?)[/QUOTE] Thanks for the info. I go to the University of Sydney.
Possibly more of an algorithmic problem, but perhaps someone recognizes it as a different problem and could point me in the right direction (is it some form of directed graph theory?). I'm sure this problem is commonplace in the financial world or accounting or something. It's based on the real life problem of buying festival supplies for your friends. Not everyone will come shopping, so only a few will pay for all of the supplies. If only one person buys all the supplies, dividing the cost fairly is easy. If multiple persons buy supplies, the problem becomes more complicated because you don't want dozens of bank transfers, it's a clusterfuck. So a bit more formally: There's a total cost of C that is acquired by some subset of a total of N people, and our goal is to divide this cost fairly over all N people. We calculate the average cost C/N and the amount that every person owes or is owed, which is the difference of the average cost C/N and the individual cost C_i they racked up. So far the easy part. What I have trouble with is figuring out a way to minimize the amount of transactions everyone has to do. You could divide the group in people who owe (call that set A) and people who are owed (B). You then let A pay group B. How does this happen exactly? You could let several people from A all pay the same person in B, but you have to be extremely lucky to have some subset of A owe exactly the amount someone in B is owed (this is guaranteed to happen if group B only has one person, so that's a trivial case). A solution to that problem is then to have some people in A split what they owe so they send their money to two people from B instead of one. The problem is that this leads to lots of bank transfers and it's also harder to coordinate. If I try to make it even more abstract I see two lines of equal length with a different partition and you have to find some image or sequence of images (~bank transfers) which lines up the partitions in the most elegant way: [IMG]http://i.imgur.com/kvOxHu7.png[/IMG] The first case is for B being one person, the second case illustrates the problem if B is more than one person. How do you link the set of line segments from A to B? The right side shows the practical solution I came up with, which is to let everyone from A give their money to the person in B who is owed the largest amount, and then have that person divide that money over the rest of the people in B. Is this the best solution? You have to try to keep the amount of transactions per person to a minimum. I'm not even sure if this really is a difficult mathematical problem or not. I do know I spent 3 hours in a spreadsheet calculating everything by hand and figuring out a way to make this foolproof and I don't feel like doing this again next year so I'd rather implement it in a program :v:
[QUOTE=Number-41;48261110]Possibly more of an algorithmic problem, but perhaps someone recognizes it as a different problem and could point me in the right direction (is it some form of directed graph theory?). I'm sure this problem is commonplace in the financial world or accounting or something. It's based on the real life problem of buying festival supplies for your friends. Not everyone will come shopping, so only a few will pay for all of the supplies. If only one person buys all the supplies, dividing the cost fairly is easy. If multiple persons buy supplies, the problem becomes more complicated because you don't want dozens of bank transfers, it's a clusterfuck. So a bit more formally: There's a total cost of C that is acquired by some subset of a total of N people, and our goal is to divide this cost fairly over all N people. We calculate the average cost C/N and the amount that every person owes or is owed, which is the difference of the average cost C/N and the individual cost C_i they racked up. So far the easy part. What I have trouble with is figuring out a way to minimize the amount of transactions everyone has to do. You could divide the group in people who owe (call that set A) and people who are owed (B). You then let A pay group B. How does this happen exactly? You could let several people from A all pay the same person in B, but you have to be extremely lucky to have some subset of A owe exactly the amount someone in B is owed (this is guaranteed to happen if group B only has one person, so that's a trivial case). A solution to that problem is then to have some people in A split what they owe so they send their money to two people from B instead of one. The problem is that this leads to lots of bank transfers and it's also harder to coordinate. If I try to make it even more abstract I see two lines of equal length with a different partition and you have to find some image or sequence of images (~bank transfers) which lines up the partitions in the most elegant way: [IMG]http://i.imgur.com/kvOxHu7.png[/IMG] The first case is for B being one person, the second case illustrates the problem if B is more than one person. How do you link the set of line segments from A to B? The right side shows the practical solution I came up with, which is to let everyone from A give their money to the person in B who is owed the largest amount, and then have that person divide that money over the rest of the people in B. Is this the best solution? You have to try to keep the amount of transactions per person to a minimum. I'm not even sure if this really is a difficult mathematical problem or not. I do know I spent 3 hours in a spreadsheet calculating everything by hand and figuring out a way to make this foolproof and I don't feel like doing this again next year so I'd rather implement it in a program :v:[/QUOTE] The simplest strategy would just be to do it in a circle. Person 1 gives/takes from Person 2 until they have paid C/N total. Then Person 2 does the same with Person 3, all the way until Person N-1 and Person N - at which point it should exactly resolve. This will always result in N-1 transactions. It seems likely at first glance that most* distributions will require this number of transactions... Certainly there are distributions that can be done in fewer, and it's probably much harder to determine exactly when this occurs.** I'd have to think about it a bit more to be sure, but that's my instinct. *for some definition of most **one condition would be having a subset that sums to zero, then you can just split your group into 2 parties - saving a single transaction. [editline]21st July 2015[/editline] See also: [url]https://en.wikipedia.org/wiki/Subset_sum_problem[/url]
Apparently without the axiom of choice, you can partition a set into more parts than there are elements in the original set. And people still whine about the Banach-Tarski paradox being unintuitive.
If we can partition to empty sets then yeah.
[QUOTE=Fourier;48313464]If we can partition to empty sets then yeah.[/QUOTE] Should have said nonempty. But yeah, even without.
But that doesn't make sense, unless we split set for example {2} into {1} and {1}? Also that Banach-Tarski paradox, professor told us about it many times.
Sorry, you need to Log In to post a reply to this thread.