m8ta
use https for features.
text: sort by
tags: modified
type: chronology
{517} is owned by tlh24.
{1506}
hide / / print
ref: -0 tags: asymmetric locality sensitive hash maximum inner product search sparsity date: 03-30-2020 02:17 gmt revision:5 [4] [3] [2] [1] [0] [head]

Improved asymmetric locality sensitive hashing for maximum inner product search

  • Like many other papers, this one is based on a long lineage of locality-sensitive hashing papers.
  • Key innovation, in [23] The power of asymmetry in binary hashing, was the development of asymmetric hashing -- the hash function of the query is different than the hash function used for storage. Roughly, this allows additional degrees of freedom since the similarity-function is (in the non-normalized case) non-symmetric.
    • For example, take query Q = [1 1] with keys A = [1 -1] and B = [3 3]. The nearest neighbor is A (distance 2), whereas the maximum inner product is B (inner product 6).
    • Alternately: self-inner product for Q and A is 2, whereas for B it's 18. Self-similarity is not the highest with inner products.
    • Norm of the query does not have an effect on the arg max of the search, though. Hence, for the paper assume that the query has been normalized for MIPS.
  • In this paper instead they convert MIPS into approximate cosine similarity search (which is like normalized MIPS), which can be efficiently solved with signed random projections.
  • (Established): LSH-L2 distance:
    • Sample a random vector a, iid normal N(0,1)
    • Sample a random normal b between 0 and r
      • r is the window size / radius (free parameters?)
    • Hash function is then the floor of the inner product of the vector a and input x + b divided by the radius.
      • I'm not sure about how the floor op is converted to bits of the actual hash -- ?
  • (Established): LSH-correlation, signed random projections h signh^{sign} :
    • Hash is the sign of the inner product of the input vector and a uniform random vector a.
    • This is a two-bit random projection [13][14].
  • (New) Asymmetric-LSH-L2:
    • P(x)=[x;||x|| 2 2;||x|| 2 4;....;||x|| 2 2 m]P(x) = [x;||x||^2_2; ||x||^4_2; .... ; ||x||^{2^m}_2] -- this is the pre-processing hashing of the 'keys'.
      • Requires that then norm of these keys, {||x||}_2 < U < 1$$
      • m3 m \geq 3
    • Q(x)=[x;1/2;1/2;...;1/2]Q(x) = [x;1/2; 1/2; ... ; 1/2] -- hashing of the queries.
    • See the mathematical explanation in the paper, but roughly "transformations P and Q, when normas are less than 1, provide correction to the L2 distance ||Q(p)P(x i)|| 2||Q(p) - P(x_i)||_2 , making in rank correlate with un-normalized inner product."
  • They then change the augmentation to:
    • P(x)=[x;1/2||x|| 2 2;1/2||x|| 2 4;...;1/2||x|| 2 2 m]P(x) = [x; 1/2 - ||x||^2_2; 1/2 - ||x||^4_2; ... ; 1/2 - ||x||^{2^m}_2]
    • Q(x)=[x;0;...;0]Q(x) = [x; 0; ...; 0]
    • This allows use of signed nearest-neighbor search to be used in the MIPS problem. (e.g. the hash is the sign of P and Q, per above; I assume this is still a 2-bit operation?)
  • Then the expand the U,M compromise function ρ\rho to allow for non-normalized queries. U depends on m and c (m is the codeword extension, and c is the ratio between o-target and off-target hash hits.
  • Tested on Movielens and Netflix databases, this using SVD preprocessing on the user-item matrix (full rank matrix indicating every user rating on every movie (mostly zeros!)) to get at the latent vectors.
  • In the above plots, recall (hah) that precision is the number of true positives / number of false positives as the number of draws k increases; recall is the number of true positives / number of draws k.
    • Clearly, the curve bends up and to the right when there are a lot of hash tables K.
    • Example datapoint: 50% precision at 40% recall, top 5. So on average you get 2 correct hits in 4 draws. Or: 40% precision, 20% recall, top 10: 2 hits in 5 draws. 20/40: 4 hits in 20 draws. (hit: correctly within the top-N)
    • So ... it's not that great.

Use case: Capsule: a camera based positioning system using learning
  • Uses 512 SIFT features as keys and queries to LSH. Hashing is computed via sparse addition / subtraction algorithm, with K bits per hash table (not quite random projections) and L hash tables. K = 22 and L = 24. ~ 1000 training images.
  • Best matching image is used as the location of the current image.

{1096}
hide / / print
ref: -3000 tags: DBS STN oscillations beta gamma research date: 02-21-2012 16:51 gmt revision:22 [21] [20] [19] [18] [17] [16] [head]

There seems to be an interesting connection between excessive grip force, isometric muscle contraction causing coherence between motor cortex and EMG, lack of inhibition on delayed response and go-no-go task, and experiments with STN lesioned rats, and the high/low oscillation hypothesis. Rather tenuous, I suppose, but let me spell it out. ( My personal impression, post-hoc, is that this is an epiphenomena of something else; evidence is contradictory.)

  1. PD patients, STN DBS impairs ability to match force characteristics to task requirements both in terms of grip force {88}, and when lifting heavy and light objects {88-2}. This is consistent with GPi function controlling the vigor or scaling of muscle responses
  2. Isometric force creation frequently engages the piper rhythm between cortex and muscles {1066}, which may be a means of preserving motor state {1066-4}.
  3. In PD patients there is marked increase in beta oscillation and synchronization {1064}, which decreases during movement {829}. Some suggest that it may be a non-coding resting state {969}, though beta-band energy is correlated with PD motor symptoms PMID-17005611, and STN DBS attenuates the power in the beta band {710-2},{753},{1073}, and DCS is likely to do the same PMID-21039949. Alternatively synchrony limits the ability to encode meaningful information. The beta band activity does not seem associated with rest tremor {1075}. Furthermore, beta band decreases prior and during movement, and with the administration of levodopa oscillation shifts to higher frequency -- the same frequency as the piper rhythm {1075}. Closed-loop stimulation with a delay (80ms) designed to null the beta oscillations is more effective than continuous high frequency DBS {967}.
  4. PD patients have deficits in inhibition on go-no-go and delayed response tasks that is exacerbated by STN DBS {1077-3}, as well as expedited decision making in conflict situations {1077} Lesioning the STN in rats has similar effect on delayed reward task performance, though it's somewhat more complicated. (and their basal ganglia is quite a bit different). {677}.
  5. The <30 Hz and >30Hz bands are inversely affected by both movement and dopamine treatment. {1069}

footnote: how much is our search for oscillations informed by our available analytical techniques?

Hypothesis: Impulsivity may be the cognitive equivalent of excess grip force; maintenance of consistent 'force' or delayed decision making benefits from Piper-band rhythms, something which PD abolishes (gradually, through brain adaptation). DBS disrupts the beta (resting, all synchronized) rhythm, and thereby permits movement. However it also effectively 'lesions' the STN, which leads to cognitive deficits and poor force control. (Wait .. DBS plus levodopa improves 40-60Hz energy -- this would argue against the hypothesis. Also, stroke in the STN in normal individuals causes hemiballismus, which resolves gradually; this is not consistent with oscillations, but rather connectivity and activity.)

Testing this hypothesis: well, first of all, is there beta-band oscillations in our data? what about piper band? We did not ask the patients to delay response, so any tests thereof will be implicit. Can look at relative energy 10Hz-30Hz and 30Hz-60Hz in the spike traces & see if this is modulated by hand position. (PETH as usual).

So. I made PETHs for beta / gamma power ratio of the spiking rate, controlled by shuffling the PETH triggers. Beta power was between 12 and 30 Hz; gamma between 30 and 75 Hz, as set by a noncausal IIR bandpass filter. The following is a non-normalized heatmap of all significant PETHs over all sessions triggered when the hand crossed the midpoint between targets. (A z-scored heatmap was made as well; it looked worse).

X is session number, Y time, 0 = -1 sec. sampling rate = 200 Hz. In one file (the band) there seems to be selective gamma inhibition about 0.5 sec before peak movement. Likely it is an outlier. 65 neurons of 973 (single and multiunits together) were significantly 'tuned' = 6.6%; marginally significant by binomial test (p=0.02). Below is an example PETH, with the shuffled distribution represented by mean +- 1 STD in blue.

The following heatmap is created from the significant PETHs triggered on target appearance.

80 of the 204 significant PETHs are from PLEX092606005_a. The total number of significant responses (204/1674, single units and multiunits) is significant by the binomial test p < 0.001, with and without Sept. 26 removed. Below is an example plot (092606005). Looks pretty damn good, actually.

Let's see how stable this relationship is by doing a leave-half out cross-validation, 10 plies, in red below (all triggers plotted in black)

Looks excellent! Problem is we are working with a ratio, which is prone to spikes. Fix: work in log space.

Aggregate response remains about the same. 192 / 1674 significant (11.5%)

In the above figure, positive indicates increased β\beta power relative to γ\gamma power. The square shape is likely relative to (negative lags) hold time and (positive lags) reaction time, though the squareness is somewhat concerning. Recording is from VIM.

{5}
hide / / print
ref: bookmark-0 tags: machine_learning research_blog parallel_computing bayes active_learning information_theory reinforcement_learning date: 12-31-2011 19:30 gmt revision:3 [2] [1] [0] [head]

hunch.net interesting posts:

  • debugging your brain - how to discover what you don't understand. a very intelligent viewpoint, worth rereading + the comments. look at the data, stupid
    • quote: how to represent the problem is perhaps even more important in research since human brains are not as adept as computers at shifting and using representations. Significant initial thought on how to represent a research problem is helpful. And when it’s not going well, changing representations can make a problem radically simpler.
  • automated labeling - great way to use a human 'oracle' to bootstrap us into good performance, esp. if the predictor can output a certainty value and hence ask the oracle all the 'tricky questions'.
  • The design of an optimal research environment
    • Quote: Machine learning is a victim of it’s common success. It’s hard to develop a learning algorithm which is substantially better than others. This means that anyone wanting to implement spam filtering can do so. Patents are useless here—you can’t patent an entire field (and even if you could it wouldn’t work).
  • More recently: http://hunch.net/?p=2016
    • Problem is that online course only imperfectly emulate the social environment of a college, which IMHO are useflu for cultivating diligence.
  • The unrealized potential of the research lab Quote: Muthu Muthukrishnan says “it’s the incentives”. In particular, people who invent something within a research lab have little personal incentive in seeing it’s potential realized so they fail to pursue it as vigorously as they might in a startup setting.
    • The motivation (money!) is just not there.

{660}
hide / / print
ref: -0 tags: perl one-liner search files cat grep date: 02-16-2009 21:58 gmt revision:2 [1] [0] [head]

In the process of installing compiz - which I decided I didn't like - I removed Xfce4's window manager, xfwm4, and was stuck with metacity. Metacity probably allows focus-follows-mouse, but this cannot be configured with Xfce's control panel, hence I had to figure out how to change it back. For this, I wrote a command to look for all files, opening each, and seeing if there are any lines that match "metacity". It's a brute force approach, but one that does not require much thinking or googling.

find . -print | grep -v mnt | \
perl -e 'while($k = <STDIN>){open(FH,"< $k");while($j=<FH>){if($j=~/metacity/){print "found $k";}}close FH;}' 
This led me to discover ~/.cache/sessions/xfce4-session-loco:0 (the name of the computer is loco). I changed all references of 'metacity' to 'xfwm4', and got the proper window manager back.

{409}
hide / / print
ref: bookmark-0 tags: optimization function search matlab linear nonlinear programming date: 08-09-2007 02:21 gmt revision:0 [head]

http://www.mat.univie.ac.at/~neum/

very nice collection of links!!

{18}
hide / / print
ref: notes-0 tags: SQL fulltext search example date: 0-0-2006 0:0 revision:0 [head]

SELECT * FROM `base` WHERE MATCH(`From`, `To`) AGAINST('hanson') ORDER BY `Date` DESC Limit 0, 100

  • you need to have a fulltext on the column set provided as a parameter to the MATCH() keyword. Case does not matter so log as the coalition is correct.

{31}
hide / / print
ref: bookmark-0 tags: job_search professional employment wisdom date: 0-0-2006 0:0 revision:0 [head]

http://www.tcnj.edu/~rgraham/wisdom.html