tag:blogger.com,1999:blog-97499602024-03-08T05:35:24.532+00:00Research on SearchMy study of machine learning, data mining, computational linguistics and information retrieval, towards the grand goal of developing the "perfect search engine" that "understands exactly what you mean and gives you back exactly what you want" (Larry Page).Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.comBlogger137125tag:blogger.com,1999:blog-9749960.post-72397723067423121082012-08-21T16:11:00.000+01:002012-08-21T16:11:10.893+01:00New-style Python classesWith Python 2.2 a new type of classes, named <a href="http://docs.python.org/reference/datamodel.html#newstyle">new-style classes</a>, was introduced. New-style classes add some convenient functionality to classic classes. New-style classes are recognized by having class object as base class.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-19797198797293286512012-08-09T17:18:00.000+01:002012-08-09T17:18:08.859+01:00Python caching decoratorsImplementing a <a href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic programming</a> algorithm is made much easier in Python by using a <a href="http://codecereal.blogspot.co.uk/2011/06/optimizing-functions-with-python.html">caching/memorization decorator</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-81895712649755590062012-05-11T13:15:00.000+01:002012-05-11T13:17:15.227+01:00Python's handling of default parameter values<a href="http://docs.python.org/reference/compound_stmts.html#function">Python's handling of default parameter values</a> becomes tricky when one uses a mutable object (e.g., list or dictionary) as a default value.
<blockquote>Default parameter values are evaluated when the function definition is executed. This means that the expression is evaluated once, when the function is defined, and that the same "pre-computed" value is used for each call. If the function modifies the object (e.g. by appending an item to a list), the default value is in effect modified. </blockquote>
This has to be borne in mind when writing recursive Python programs.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-73142444995305255382012-05-11T10:47:00.001+01:002012-05-11T10:47:10.865+01:00Python's splat operatorPython actually has the splat operator (as in Perl or Ruby) that can <a href="http://docs.python.org/tutorial/controlflow.html#unpacking-argument-lists">unpack the arguments out of a list, tuple, or dictionary</a>: func(*args), or func(**kwdargs).Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-22605646110514065782011-09-07T11:21:00.002+01:002011-09-07T11:28:34.086+01:00The Hungarian algorithm in clustering evaluation<a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">The Hungarian algorithm (aka Kuhn–Munkres algorithm or Munkres assignment algorithm)</a> can solve the assignment problem in polynomial time O(n^3). It can be used to find the optimal mapping from discovered clusters to the ground-truth categories which serves as the basis for some performance measures of <a href="http://en.wikipedia.org/wiki/Cluster_analysis">clustering</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-42895736359621900102011-08-28T16:14:00.003+01:002011-08-28T16:19:47.790+01:00Fastest membership test in PythonWhat is the most efficient method to check whether an item is in a given group or not? In Python, it seems that <a href="http://labs.kortina.net/2010/10/13/list-dict-set-and-frozen-set-performance-in-python/">set (or frozenset) would be slightly faster than dict and much much faster than list</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-69727145368655894312011-08-26T20:02:00.002+01:002011-08-26T20:14:56.364+01:00Submodular functionsIntuitively, a <a href="http://en.wikipedia.org/wiki/Submodular_function">submodular function</a> over the subsets demonstrates "<span style="font-style:italic;">diminishing returns</span>", which is related to the concept of <a href="http://en.wikipedia.org/wiki/Marginal_utility">marginal utility</a> in economics. Its usefulness for machine learning is well explained and illustrated by the <a href="http://submodularity.org/">Beyond Convexity</a> tutorial. There is <a href="http://www.cs.caltech.edu/~krausea/sfo/">a Matlab toolbox for submodular function optimization</a> available that is developed by <a href="http://las.ethz.ch/krausea.html">Andreas Krause</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-44171350165451966002011-08-26T15:24:00.004+01:002011-08-26T20:02:46.722+01:00L1 regularisation Is efficient for selecting relevant features<a href="http://ai.stanford.edu/~ang/">Andrew Ng</a> has proven in his <a href="http://ai.stanford.edu/~ang/papers/icml04-l1l2.pdf">ICML-2004 paper</a> that sample complexity grows linearly in the number of irrelevant features when using L2 regularisation (in logistic regression, support vector machine, and back-propagation neural network), but only logarithmically when using L1 regularisation (in logistic regression).Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-27160341721547683682011-07-03T13:44:00.002+01:002011-07-03T13:57:59.061+01:00New linear-time algorithm for suffix array constructionJuha Kärkkäinen, Peter Sanders , and Stefan Burkhardt: <a href="http://portal.acm.org/citation.cfm?id=1217858">Linear Work Suffix Array Construction</a>, Journal of the ACM (JACM), Volume 53 Issue 6, November 2006.<br />As the authors have said, this algorithm narrows the gap between <a href="http://en.wikipedia.org/wiki/Suffix_tree">suffix tree</a> and <a href="http://en.wikipedia.org/wiki/Suffix_array">suffix array</a>, which are widely used and largely interchangeable index structures on strings and sequences. Usually theoreticians prefer the former due to linear-time construction algorithms and more explicit structure while practitioners prefer the latter due to its simplicity and space efficiency. Now there is one more reason for practitioners to stick with suffix array.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-86379535121082752562011-07-01T09:01:00.006+01:002011-07-01T09:10:17.939+01:00Research Impact for REFThe British government's emphasis on the practical <span style="font-weight:bold;">impact</span> of research in <a href="http://en.wikipedia.org/wiki/Research_Excellence_Framework">REF</a> reminds me of Feynman's following words.<br /><blockquote><span style="font-style:italic;">Physics [research] is like sex: sure, it may give some practical results, but that's not why we do it.</span></blockquote>Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-16561288335759646232011-06-17T23:32:00.002+01:002011-06-17T23:39:00.642+01:00DiveRS'11<a href="http://www.eps.uam.es/~castells">Pablo Castells</a>, <a href="http://www.cs.ucl.ac.uk/people/J.Wang.html">Jun Wang</a>, <a href="http://ir.ii.uam.es/~rlara">Ruben Lara</a>, and <a href="http://www.dcs.bbk.ac.uk/~dell">Dell Zhang</a> are organising an ACM <a href="http://www.recsys.acm.org/2011/">RecSys-2011</a> workshop on <a href="http://ir.ii.uam.es/divers2011/">Novelty and Diversity in Recommender Systems (DiveRS)</a>. A special issue of <a href="http://tist.acm.org/">ACM TIST</a> in the scope of the workshop will be announced after the conference. Authors of accepted papers will be invited to submit an extended version.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com1tag:blogger.com,1999:blog-9749960.post-55082173514145452102011-06-17T23:19:00.002+01:002011-06-17T23:30:59.601+01:00A couple of metricsIt is often desirable to measure the dissimilarity or distance between items using a proper <a href="http://en.wikipedia.org/wiki/Distance_function">metric</a>.<br /><ul><li><a href="http://en.wikipedia.org/wiki/Jaccard_index">Jaccard coefficient</a> can be converted to a metric by by subtracting the Jaccard coefficient from 1. </li><li><a href="http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence">Kullback–Leibler divergence</a> can be converted to a metric by taking the square root of its symmetric version <a href="http://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence">Jensen–Shannon divergence</a>.</li></ul>Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-21418581578107123562010-10-04T00:18:00.003+01:002010-10-04T00:29:48.709+01:00A Poor Man's Parallel ProcessingA very crude, but often good enough, method to achieve parallel processing (e.g., on multi-core computers) is to partition the large input data file into small chunks, run the program to process each of them in parallel, and then merge the output results file back. Fortunately, this process can be done easily with the wise iterative usage of two Unix utilities: <a href="http://en.wikipedia.org/wiki/Split_(Unix)">split</a> and <a href="http://en.wikipedia.org/wiki/Cat_(Unix)">cat</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com2tag:blogger.com,1999:blog-9749960.post-38397077940644666292010-09-10T21:28:00.003+01:002010-09-10T21:35:59.251+01:00nDCGThe choice of the gain and discount function for the popular IR performance measure <a href="http://en.wikipedia.org/wiki/Discounted_cumulative_gain#Normalized_DCG">normalised Discounted Cumulative Gain (nDCG)</a> has been discussed and empirically justified in <a href="http://portal.acm.org/citation.cfm?id=1645953.1646032">a CIKM-2009 paper</a> through <a href="http://en.wikipedia.org/wiki/Analysis_of_variance">analysis of variance (ANOVA)</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-79382743217229923932010-08-11T15:09:00.002+01:002010-08-11T15:13:12.663+01:00LNREHere is a good tutorial with Matlab examples about <a href="http://www.ling.upenn.edu/courses/cogs502/LNRE.html">Statistical Estimation for Large Numbers of Rare Events (LNRE)</a>.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-83622162678237199562010-06-18T21:56:00.002+01:002010-06-18T22:10:13.860+01:00VLFeat - a computer vision toolboxThe <a href="http://www.vlfeat.org/">VLFeat</a> open source computer vision library that implements popular<br /><ul><li><span style="font-weight: bold;">feature extraction</span> algorithms (such as <a href="http://www.vlfeat.org/overview/sift.html">SIFT</a>, <a href="http://www.vlfeat.org/overview/mser.html">MSER</a>, and <a href="http://www.vlfeat.org/overview/quickshift.html">quick shift</a>),<br /></li><li><span style="font-weight: bold;">clustering</span> algorithms (such as <a href="http://www.vlfeat.org/overview/ikm.html">integer k-means</a>, <a href="http://www.vlfeat.org/overview/hikm.html">hierarchical k-means</a>, and <a href="http://www.vlfeat.org/overview/aib.html">agglomerative information bottleneck</a>), and<br /></li><li><span style="font-weight: bold;">matching</span> algorithms (such as <a href="http://www.vlfeat.org/overview/kdtree.html">randomized kd-trees</a>).<br /></li></ul>It is written in C for efficiency and compatibility, with interfaces in MATLAB for ease of use, and detailed documentation throughout.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-65956650103989392852010-06-01T09:24:00.002+01:002010-06-01T09:33:56.666+01:00Bloom filters and Locality Sensitive Hashing<a href="http://en.wikipedia.org/wiki/Locality_sensitive_hashing">Locality Sensitive Hashing (LSH)</a> of <span style="font-style:italic;">l</span>-bits is achieved by carrying out <span style="font-style:italic;"> l</span> independent random cuts of the Euclidean space: if two data points are in the same side of all these cuts, they are very likely to be nearest neighbours. In this sense, I think <a href="http://en.wikipedia.org/wiki/Bloom_filter">Bloom filters</a> (that also relies on a number of independent hashing functions) can be conceptually considered as the extreme case of LSH: each of its cuts tries to separate one data point from the rest.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-63820785207422476012010-05-31T10:22:00.004+01:002010-06-01T09:23:57.595+01:00An application of Bloom filtersIt is said that Google's <a href="http://en.wikipedia.org/wiki/BigTable">BigTable</a> uses <a href="http://en.wikipedia.org/wiki/Bloom_filter">Bloom filters</a> to reduce the disk lookups for non-existent rows or columns.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-71685427093930457122010-05-04T00:00:00.005+01:002010-05-04T00:34:54.858+01:00A suffix tree implementation with Unicode supportIt seems that there is currently no <a href="http://en.wikipedia.org/wiki/Suffix_tree">suffix tree</a> implementation with Unicode support publicly available online. So I adapted <a href="http://www.daimi.au.dk/~mailund/suffix_tree.html">Thomas Mailund's suffix tree implementation in C with a Python binding</a> and put it <a href="http://www.dcs.bbk.ac.uk/~dell/code/suffix_tree_unicode.zip">here</a>. The changes that I made to the code were mainly to make it support Unicode text and be compatible with new version Python. It also includes an example program all_comsubstr.py that illustrates the extraction of common substrings from two Chinese strings (encoded in UTF-8).Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com6tag:blogger.com,1999:blog-9749960.post-3887172780648742812010-05-03T22:53:00.002+01:002010-05-03T23:01:56.651+01:00Longest Common SubstringGiven two strings, <span style="font-style:italic;">S</span> of length <span style="font-style:italic;">m</span> and <span style="font-style:italic;">T</span> of length <span style="font-style:italic;">n</span>, their <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem">longest common substrings</a> can be found in O(<span style="font-style:italic;">m</span>+<span style="font-style:italic;">n</span>) time using a <a href="http://en.wikipedia.org/wiki/Generalised_suffix_tree">generalised suffix tree</a>, or in O(<span style="font-style:italic;">m</span><span style="font-style:italic;">n</span>) time through <a href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic programming</a> (e.g., the Python code <a href="http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#Python">here</a>).Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-47832431302988997102010-03-28T22:53:00.005+01:002010-03-28T23:31:41.381+01:00Bayesian inference for the GaussianGiven the prior probability <br />$p(\mu) = \mathcal{N}(\x_0,\sigma_0^2)$ <br />and the likelihood <br />$p(x_1|\mu) = \mathcal{N}(\mu,\sigma_1^2)$, <br />the expectation of the posterior probability <br />$p(\mu|x_1)$ <br />has a very simple and elegant form:<br />$(\alpha \x_0 + \beta x_1) / (\alpha + \beta)$<br />where <br />$\alpha = 1/(\sigma_0^2)$ and $\beta = 1/(\sigma_1^2)$ <br />are the precisions.<br /><br />Please refer to Bishop's PRML book section 2.3.6.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-81618841150714194972010-02-03T14:56:00.002+00:002010-02-03T15:03:32.388+00:00Comparing Data Analysis PackagesA succinct comparison of data analysis packages including R, Matlab, SciPy, Excel, SAS, SPSS and Stata, can be found <a href="http://anyall.org/blog/2009/02/comparison-of-data-analysis-packages-r-matlab-scipy-excel-sas-spss-stata/">here</a>. I recently tried Stata, but found its language syntax ugly and awkward.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com1tag:blogger.com,1999:blog-9749960.post-70072926147507031942009-11-11T11:58:00.004+00:002009-11-11T12:13:13.283+00:00The myth about the Internet<a href="http://www.research.att.com/viewInnovator.cfm?id=109">Walter Willinger</a> et al. recently published a <a href="http://faculty.nps.edu/dlalders/docs/Internet-AMS-Notices-May2009.pdf">paper</a> in which the <a href="http://en.wikipedia.org/wiki/Scale-free_network">scale-free network</a> model of the <a href="http://en.wikipedia.org/wiki/Preferential_attachment">preferential attachment</a> type for Internet is said to be a myth, as it is based on fundamentally flawed traceout data. Furthermore, they criticize the currently popular <span style="font-style:italic;">data-fitting</span> approach to <a href="http://en.wikipedia.org/wiki/Network_science">network science</a> and argue that it should be replaced by the <span style="font-style:italic;">reverse-engineering</span> approach.Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-60894370430825358012009-08-12T23:24:00.008+01:002009-08-23T17:20:21.853+01:00Large networks are not modularA pretty striking finding in <a href="http://www2008.org/papers/fp569.html">the WWW'08 paper from Leskovec etc.</a> is that in nearly every network dataset they examined, there are tight but almost trivial communities at very small scales (up to around 100 nodes), while at larger scales, the best possible communities gradually "blend in" with the rest of the network and thus become less "community-like".Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0tag:blogger.com,1999:blog-9749960.post-72710823700855893512009-07-30T23:52:00.005+01:002009-07-31T00:41:40.002+01:00Spectral Graph PartitioningThere are a number of methods in the family of Spectral Graph Partitioning, including the traditional <span style="font-style:italic;">min-cut</span> and various balanced cut criteria (such as <span style="font-style:italic;">ratio-cut</span>, <span style="font-style:italic;">average-cut</span>, <span style="font-style:italic;">normalized-cut</span> and <span style="font-style:italic;">minmax-cut</span>). Each method uses a different objective function and consequently a different definition of partition (cluster) indicator vector. The following two tutorials on Spectral Clustering both contain a good summary of these methods.<br />[1] <a href="http://ranger.uta.edu/~chqding/Spectral/">Spectral Clustering, ICML 2004 Tutorial by Chris Ding</a><br />[2] <a href="http://www.kyb.tuebingen.mpg.de/bs/people/ule/publications/publication_downloads/Luxburg07_tutorial.pdf">A Tutorial on Spectral Clustering by Ulrike von Luxburg</a>Dell Zhanghttp://www.blogger.com/profile/14810903698038676929noreply@blogger.com0