intellectual stimulation
Mar. 23rd, 2007 01:21 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslEvery day this week has been filled with intellectual stimulation.
Tuesday, I gave a talk to the generalists on Rhythm in Language and Rhythm in Music. I basically improvised an 8-slide presentation. I found the audience warm and easy to please. I got some interesting feedback about ways in which songs in syllable-timed languages are easier or harder to change lyrics than songs in stress-timed languages. 3 people (out of 5?) gave me positive feedback, and one of the remaining ones laughed a lot, so that's a success any way you look at it. The last time I gave a talk to an audience was my thesis defense 15 months ago.
Wednesday morning, Machine Learning covered learning Bayesian networks. Then I managed to meet with Peter to talk about ICA.
The next step I need to do is integrate matrix permutations with real data (i.e. real simulated data), i.e. make big multivariate simulations, choose a set of observed variables, run ICA to get the coefficients, do permutations to determine which coefficients are non-zero, and see how much of the graph we can reconstruct correctly / how much data is needed. After the row & column permutations, we have a lower-triangular matrix representing the coefficients in the causal DAG.
I designed 3 improvements to my current O(n^2) method for calculating loss, i.e. non-lower-triangularity. First, memoize the squares. Second, only look at the entries that would be swapped in and out of the lower-left triangle O(n): use the current cost to get the new cost. Third, "integrate" vertically and horizontally to create a memoization (actually two), so now you only need to look at 4 entries: this is O(1).
Even though Shimizu is greedy and needs lots of random restarts, (or maybe because of it), I feel this urge to optimize the hell out of it. I'm now wondering about a variation that looks deeper (k levels instead of 1) and chooses the best one out of those.
Since there are n(n-1) swaps are any given time, naively, this would be (n(n-1))^k choices. In practice, however, some (most?) of the swaps will commute as long as k << n... so you can divide that number by k! ... but first we need to be able to iterate through= each of those permutations only once, which seems like an interesting problem on its own. To simplify, let's only consider column-swaps.
total# permutations
# swaps= n(n-1) / 2
# sequences of 2 swaps=(n(n-1)/2)^2
How many of these commute? Assume each name denotes a different column.
There are 3 cases:
Case #1: (a b) and (c d) commute.
Case #2: (a b) and (a b) commute.
Case #3: (a b) and (b c) don't commute
How many Case #1?
After picking the first swap, there are (n-2)(n-3)/2 swaps available.
(n(n-1)/ 2)*((n-2)(n-3)/2)
How many Case #2?
After picking the first swap, There is one swap available.
(n(n-1) / 2)*1.
How many Case #3? After picking the first swap, there are 2 choices of b and n-2 choices of c.
(n(n-1)/ 2)*2*(n-2)
This better add up to (n(n-1) / 2)^2.
For > 2 swaps at once, the analysis might be difficult. I don't know.
Went to the 4th floor CS lounge to look for some algorithms geeks. Lots of them there, but they were all busy. Eventually,![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
mdinitz listened to my problem, and gave me how to treat approximation algorithms are analyzed, how to convert this into a decision problem, etc. He told me about the Aladdin blog, to which I should post the problem.
Today, I went to John Harrison's survey talk "Formalized Mathematics". That deserves its own post.
Tomorrow I do my taxes.
Saturday, I'll be attending a conference. Friday they have a party, so I might miss CtFwS.
Tuesday, I gave a talk to the generalists on Rhythm in Language and Rhythm in Music. I basically improvised an 8-slide presentation. I found the audience warm and easy to please. I got some interesting feedback about ways in which songs in syllable-timed languages are easier or harder to change lyrics than songs in stress-timed languages. 3 people (out of 5?) gave me positive feedback, and one of the remaining ones laughed a lot, so that's a success any way you look at it. The last time I gave a talk to an audience was my thesis defense 15 months ago.
Wednesday morning, Machine Learning covered learning Bayesian networks. Then I managed to meet with Peter to talk about ICA.
The next step I need to do is integrate matrix permutations with real data (i.e. real simulated data), i.e. make big multivariate simulations, choose a set of observed variables, run ICA to get the coefficients, do permutations to determine which coefficients are non-zero, and see how much of the graph we can reconstruct correctly / how much data is needed. After the row & column permutations, we have a lower-triangular matrix representing the coefficients in the causal DAG.
I designed 3 improvements to my current O(n^2) method for calculating loss, i.e. non-lower-triangularity. First, memoize the squares. Second, only look at the entries that would be swapped in and out of the lower-left triangle O(n): use the current cost to get the new cost. Third, "integrate" vertically and horizontally to create a memoization (actually two), so now you only need to look at 4 entries: this is O(1).
Even though Shimizu is greedy and needs lots of random restarts, (or maybe because of it), I feel this urge to optimize the hell out of it. I'm now wondering about a variation that looks deeper (k levels instead of 1) and chooses the best one out of those.
Since there are n(n-1) swaps are any given time, naively, this would be (n(n-1))^k choices. In practice, however, some (most?) of the swaps will commute as long as k << n... so you can divide that number by k! ... but first we need to be able to iterate through= each of those permutations only once, which seems like an interesting problem on its own. To simplify, let's only consider column-swaps.
total# permutations
# swaps= n(n-1) / 2
# sequences of 2 swaps=(n(n-1)/2)^2
How many of these commute? Assume each name denotes a different column.
There are 3 cases:
Case #1: (a b) and (c d) commute.
Case #2: (a b) and (a b) commute.
Case #3: (a b) and (b c) don't commute
How many Case #1?
After picking the first swap, there are (n-2)(n-3)/2 swaps available.
(n(n-1)/ 2)*((n-2)(n-3)/2)
How many Case #2?
After picking the first swap, There is one swap available.
(n(n-1) / 2)*1.
How many Case #3? After picking the first swap, there are 2 choices of b and n-2 choices of c.
(n(n-1)/ 2)*2*(n-2)
This better add up to (n(n-1) / 2)^2.
For > 2 swaps at once, the analysis might be difficult. I don't know.
Went to the 4th floor CS lounge to look for some algorithms geeks. Lots of them there, but they were all busy. Eventually,
mdinitz listened to my problem, and gave me how to treat approximation algorithms are analyzed, how to convert this into a decision problem, etc. He told me about the Aladdin blog, to which I should post the problem.Today, I went to John Harrison's survey talk "Formalized Mathematics". That deserves its own post.
Tomorrow I do my taxes.
Saturday, I'll be attending a conference. Friday they have a party, so I might miss CtFwS.