Meaningful Life

So exciting that I can download AudioBook from TCPL

2010-01-05T09:47:00.000-05:00

Thanks to information technology that I can download audiobook from my library without any extra fee. Haha, today's best thing! Enjoying~

Do you know what is X11?

2009-05-12T23:31:00.006-04:00

X11 for Mac OS X is an implementation of the X Window System that makes it possible to run X11-based applications in Mac OS X. Based on the X.org Foundation releases -- the leading reference implementation of X11 -- X11 for Mac OS X is compatible, fast, and fully integrated with Mac OS X. It features includes full X11R7 compatibility including an X window server, Quartz window manager, libraries, and basic utilities such as xterm. It is optional but installed by default on Mac OS X v10.5 Leopard. The X11 SDK headers are available as part of the Xcode Developer Tools.

review of SVM

2009-05-10T22:42:00.003-04:00

SVM(Support Vector Machine) is an classifying algorithm using for machine learning and regression. The basic idea is simple and powerful that find a hyperplane to classify different set of data.

Initially, there are 2 parameters need to optimize, w and b. How to decide the optimal solution? Maximizing margin between two sets. This goal is equal to minimize the(1/2)||w||^2[I am not very clear about this]. By adding Lagrangian constrain, through derivation of w and b, the optimal answer is gotten.

Then, considering more complicate cases, how can we do when the data are not linear? Recall above the solution is gotten in the linear situation, therefore, we can transform non-linear dataset to linear, then apply SVM on them. This is one key feature about SVM: kernel function.

Review of k-NN and k-means

2009-05-10T09:47:00.004-04:00

k-NN(k-Nearest Neighbor) and k-means are two totally different algorithm in pattern recognition, machine learning and data mining. Sometimes, there are confused that maybe because both algorithm's name are contain "k". Anyway, I believe I will clear after writing this article.

First of all, we have to emphasize that the basic differences: k-NN is used to classify but k-means is used to clustering.

In additionally, let me explain what's the meaning of "k" in both algorithms. As a classifying algorithm, we usually already knew the classes in k-NN, then an object is classified by a majority vote of its neighbors, with the object being assigned to the class most common among its k nearest neighbor. That is to say, if k=1, an object's label is determined by the only one nearest object, if k=3, the object will assigned to one class by voting the 3 nearest neighbors. On the other hand, k in k-means means that there are k clusters in the data, and the algorithm aims to partition n observations into k clusters with the nearest mean.

To be continuing...

PageRank and HITS in link analysis

2009-04-25T13:24:00.006-04:00

First of all, we have to emphasize that the link analysis in today's discussion mainly concerns the problem of how to give score to web page, that is to say, how to rank the pages in order to surfer's query.

Let's take a look at the PageRank. Based on the analysis of page's link with each other, we can get a graph to describe the webs. Since the links have direction, so does the graph. Recall that we have learn from the graphical model, the graph with directions can be viewed as Markov chain.

After getting the graph, we can give each edge in the graph a number between [0,1] to present the probability that the surfer will click the link. Typically, if web A has links to B, C, D, then the probability from A to B is assigned 1/3. This is reasonable that the surfer clicks the links with the same probabilities. So if A has N links to other pages, the probability on the edges to other pages will be 1/N.

Anyway, there is one possible situation we should consider. What the probability from page Z to page Y if there is no link between them? We can denote the edge with 0 but it is not very reasonable because the surfer can jumped from page Z to page Y by enter an URL. Therefore, we use a teleport operation to simulate this situation. There is a parameter \alpha to denote the probability from Z to Y.

Now we can generate a graph to present the web relations by assigned probabilities on edges.

Recall that the matrix of this graph is a Markov matrix, there exists an steady state if we perform random walk in this graph. In our link analysis, the steady state can be treated as the most visited pages as well as the score for each pages.

Above all, we get the score by doing eigenvalue decomposition of the Matrix for the graph. We can see that the score is static and independent with the query. There also some discussions about the Topic-specific PageRank which take consideration of surfer's preference to construct graphs and combine them together. I am not talk about that here since the basic idea is same.

The second algorithm that we will talk about today is HITS, stands for Hyperlink-Induced Topic Search. First of all, there are two very important concepts that we have to talk first, hub score and authority score. Say it simply, hub score estimates the value of its links to other pages. Authority score estimates the vale of the content of the page. If the hub score is high it seems that the links are good, while the authority score is high seems that the the contents in the page are good. A good hub page is one that points to many good authority pages. A good authority page is the one that is pointed by many good hub pages.

By the basic idea, we can compute the hub score or authority score by adding the score of all the good authority or good hub respectively. Usually, we initialize the score is 1. This is the method to update one web page, when there are many pages that construct a graph, we can generate an adjacency matrix A to update the hub score and authority score in the web subset.

h <- AA'h

a <- A'Aa

In this way, we can update the h and a vector of hub scores and authority score. The top-scoring hubs and authorities is our want for ranking pages.

File process with Java

2009-04-19T14:56:00.028-04:00

Summarize the methods of how to do file read and write with Java today. Start my programmer way.

1. Simple Ex. from "Big Java":

(1)import & source

import java.io.FileReader;

import java.io.FileNotFoundException;

import java.util.Scanner;

...

private FileReader reader;

private Scanner in;

...

reader = new FileReader(inFileName);

in = new Scanner(reader);

...

return in.nextFloat();//see more

(2)exception

FileNotFoundException

2. Get file length and the lines in the file:

(1)import & source

import java.io.FileReader;

import java.io.IOException;

import java.io.RandomAccessFile;

import java.io.LineNumberReader;

import java.util.Scanner;

...

/* get length */

RandomAccessFile randFile = new RandomAccessFile(filename, "r");

long fileLen = randFile.length();

randFile.close();

/* get the number of lines */

FileReader readForLine = new FileReader(filename);

LineNumberReader lineRead = new LineNumberReader(readForLine);

lineRead.skip(fileLen);

numberOfLines = lineRead.getLineNumber() + 1;

lineRead.close();

readForLine.close();

...

(2)exception

IOException

3. read and write for certain constant length

(1)import & source

import java.io.InputStream;

import java.io.OutputStream;

import java.io.BufferedInputStream;

import java.io.BufferedOutputStream;

import java.io.FileInputStream;

import java.io.FileOutputStream;

...

InputStream in = null;

OutputStream out = null;

byte[] buf = null;

int LEN = 4096;

int reallen = 0;

...

in = new BufferedInputStream(new FileInputStream("in.txt"));

out = new BufferedOutputStream(new FileOutputStream("out.txt"));

...

while((reallen = in.read(buf, 0, LEN))!=-1){

out.write(buf, 0, reallen);

}

in.close();

out.close();

...

(2)exception

IOException

4. read and write for variable length(depends on a certain character, Ex. '\n')

(1)import & source

import java.io.InputStream;

import java.io.OutputStream;

import java.io.BufferedInputStream;

import java.io.BufferedOutputStream;

import java.io.FileInputStream;

import java.io.FileOutputStream;

import java.lang.Exception;

import java.io.RandomAccessFile;

import java.io.IOException;

...

RandomAccessFile raf = new RandomAccessFile("in.txt", "r");

OutputStream out = new BufferedOutputStream(new FileOutputStream("out.txt"));

...

while((reallen = raf.read(buf, 0, LEN))!=-1){

onelen = filterOneRecord(buf);//see below, stop as first '\n'

onelen = (onelen == -1)?(0):(onelen);

out.write('\t');//add additional process here, now just add a '\t'

out.write(buf, 0, onelen);//0 is offset

startlen += onelen+1;//1 is the char of '\n', otherwise always start from '\n'

raf.seek(startlen);

}

raf.close();

out.close();

(2)exception

IOException

(3)functions

private static int filterOneRecord(byte[] buf)

{

int len=0;

String str = new String(buf);

len = str.indexOf('\n');

return len;

}

Tcl

2009-03-27T21:35:00.006-04:00

Today I see the term "tcl" for twice, therefore I think it's worth to note that what is tcl.

Background, today I restart my travel with Dyninst, after reinstalled my laptop's OS, I download the libdyninst and libdyninst-dev to install, but suddenly, the computer says that the first one needs the denpendency of tcl8.4(what's hell of that?) and the second one says that it needs the dependency of libdyninst(Of course, I didnot install the lib which stucked by tcl8.4). Anyway, after reviewing how to use apitude to search and install the lib of linux, "package installer" installs all the associated dependency automatically, which I do not know why it can not run for the first time.

Actually, it reminds me one Chinese trade mark TCL which was made fun of Chinese people as "Tao Cha Le" that means "aweful" or "very bad".

Here we go with tcl. Tcl (originally from "Tool Command Language", but nonetheless conventionally rendered as "Tcl" rather than "TCL"; pronounced as "tickle" or "tee-cee-ell") is a scripting language created by John Ousterhout. Originally "born out of frustration"—according to the author—with programmers devising their own (poor quality) languages intended to be embedded into applications, Tcl quickly gained wide acceptance on its own and is generally thought to be easy to learn, but powerful in competent hands. It is most commonly used for rapid prototyping, scripted applications, GUIs and testing. Tcl is used extensively on embedded systems platforms, both in its full form and in several other small-footprinted versions. Tcl is also used for CGI scripting and as the scripting language for the Eggdrop bot.
The combination of Tcl and the Tk GUI toolkit is referred to as Tcl/Tk.

Python

2009-03-27T21:32:00.004-04:00

Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are minimalistic, while the standard library is large and comprehensive. Its use of whitespace as block delimiters is unusual among popular programming languages.
Python supports multiple programming paradigms (primarily object oriented, imperative, and functional) and features a fully dynamic type system and automatic memory management, similar to Perl, Ruby, Scheme, and Tcl. Like other dynamic languages, Python is often used as a scripting language.
The language has an open, community-based development model managed by the non-profit Python Software Foundation, which maintains the de facto standard definition of the language in CPython, the reference implementation.

ttf

2009-03-27T20:40:00.003-04:00

Background: yesterday I reinstalled my laptop for a new Linux operating system. Today, I update the language support for Chinese input. During the computer installing the needed package, I wait and see the installation details, finding that there so many libs contain the character of "ttf", what's ttf? Then I search and get the answer:

TTF refers to True Type Font. TrueType is an outline font standard originally developed by Apple Computer in the late 1980s as a competitor to Adobe's Type 1 fonts used in PostScript. The primary strength of TrueType was originally that it offered font developers a high degree of control over precisely how their fonts are displayed, right down to particular pixels, at various font heights. (With widely varying rendering technologies in use today, pixel-level control is no longer certain.)

Linus geek (4): apt-get

2009-03-17T21:26:00.001-04:00

apt-get is the command-line tool for handling packages for Debian Linux which is use to:

Install/manage individual packages
Upgrade packages
Apply security patch(s)
Keep Debian system up to date
Download source .deb files
Front-end to many GUI and other utilities

Data striping & Disk mirroring

2009-03-17T21:22:00.001-04:00

Data Striping

In computer data storage, data striping is the segmentation of logically sequential data, such as a single file, so that segments can be assigned to multiple physical devices (usually disk drives in the case of RAID storage, or network interfaces in the case of Grid-oriented Storage) in a round-robin fashion and thus written concurrently.

Data Mirroring

In data storage, disk mirroring or RAID1 is the replication of logical disk volumes onto separate physical hard disks in real time to ensure continuous availability. A mirrored volume is a complete logical representation of separate volume copies.

Solaris & Safari

2009-03-17T20:41:00.008-04:00

I am a little confused with these two things, since maybe there are similar with start from "S" and both contain "ari". Anyway, after wikiing them, I am clear, Do you?

Solaris is a Unix-based operating system introduced by Sun Microsystems in 1992 as the successor to SunOS.
Solaris is known for its scalability, especially on SPARC systems, and for originating many innovative features such as DTrace and ZFS.[1][2] Solaris supports SPARC-based and x86-based workstations and servers from Sun and other vendors, with efforts underway to port to additional platforms.
Solaris is certified against the Single Unix Specification. Although it was historically developed as proprietary software, it is supported on systems manufactured by all major server vendors, and the majority of its codebase is now open source software via the OpenSolaris project.

Safari is a web browser developed by Apple Inc.. First released as a public beta on January 7, 2003[1] on the company's Mac OS X operating system, it became Apple's default browser beginning with Mac OS X v10.3, commonly known as "OS X Panther." Apple has also made Safari the native browser for the iPhone OS.
The current stable release of the browser is 3.2.1 (Macintosh) and 3.2.2 (Windows), but the Apple website more prominently displays the Safari 4 Beta, a pre-release version, for users to download.
On June 11, 2007, a version of Safari was released for the Microsoft Windows operating system,[2] supporting both Windows XP and Windows Vista.
Safari has a 8.02% market share as of February 2009.

Challenges in XML retrieval

2009-03-13T10:45:00.010-04:00

These challenges are focus on (1) text-centric XML not data-centric XML retrieval and (2)relevant statistic analysis instead of proprocessing and postprocessing by certain constraints:

Structured document retrieval principle：User want to get parts of document in XML retrieval, not like the unstructured retrieval that return the whole document. So, the first problem is which's parts is returned to user. Structured document retrieval principle suggests the system always retrieve the most specific part of a document answering a query.
Indexing Unit: Parallel to the latter challenge, how to index a document? In unstructured retrieval, it is usually clear that the right document unis is files, or emails, or a web pages and so on. In structured retrieval, there are many approach to defining the indexing unit. Here are 4 approach can be used(based on the tree DOM): (1) Group nodes to nonoverlapping pseudodocuments; (2) Select one of the largest elements as the indexing units; (3) Based on searching the most relevant one of all leaves, we can extend them to larger units in postprocessing; (4) The last, the least restrictive approach is to index all elements(It is clear that this araises indexing redundancy and do some kind of ).
Relevant statistics for XML retrieval ranking: we have give some proper solutions on unstructured document retrieval. But XML retrieval has some features that cause difficulties to distinguish different context of a term when we compute term statistic for raning, e.g. how to calculate idf.
Schema Heterogeneity(Schema Diversity): A schema puts constraints on the structure of allowable XML documents for a particular application. However, IR system does retrieval in a large collection with difference XML schemas. This phonomenon is called schema heterogeneity. So, if a user want to do query with an exactly schema from his/her mind, but unfortunately, it is not match the schema in the collection, he/she will get nothing.
Interface design for XML retrieval: As we saw that the failure of IR retrieval is caused by the schema diversity that user doesnot know the schema in the dataset. Therefore, interface design for XML retrieval raised by the latter challenge. If the system gives user a tree structure of the schema of the collection rather than keyword queries like google does, ideally, schema diversity problem can be partially solved.
Extended query: besides the tree interface design for IR system, we can also support the user by interpreting all parent-child relationships in queris as descendant relationships with any number of intervening modes allowed.

Linux geek (3): cc

2009-03-08T14:31:00.003-04:00

About cc

C compiler.

Syntax

cc [ options ]

-c Compiles only; does not attempt to link source files.

-D name[=value] Is passed to C compiler to assign the indicated value to the symbol name when the C preprocessor is run.

-f float

Specifies the floating point options that the compiler and linker use. The following should be supported:

-f - - no floating point required
-f - emulated floating point
-fp hardware floating point (using 80x87 coprocessor)

-Idir Search dir for included files whose names do not begin with a slash (/) prior to searching the usual directories. The directories for multiple -I options are searched in the order specified. The preprocessor first searches for #include files in the directory containing sourcefile, and then in directories named with -I options (if any), then /usr/ucbinclude, and finally, in /usr/include.

-Ldir Add dir to the list of directories searched for libraries by /usr/ccs/bin/ucbcc. This option is passed to /usr/ccs/bin/ld and /usr/lib. Directories specified with this option are searched before /usr/ucblib and /usr/lib.

-l library If linking, adds the indicated library to the list of libraries to be linked.

-M If linking, creates a map file with the same base name as the output executable, but with the suffix .map. This map file contains a list of symbols with their addresses.

-m model

Specifies the memory model that the compiler and linker use. The models may include:

-ms	small model
-mm	medium model
-ml	large model
-mf	flat model (32-bit)
-mc	compact model
-mh	huge model

-o output If linking, places the executable output in the file output.

-S Produces assembler listing with source code.

-Uname Is passed to the C compiler, to undefined the symbol name.

-Y P, dir Change the default directory used for finding libraries.

Examples

cc myfile.c - would compile the file myfile.c.

Linux geek (2): environment variable

2009-03-08T12:47:00.002-04:00

Linux command "export" is used to set an environment variable. Mark each name to be passed to child processes in the environment.

SYNTAX
    export [-fn] [-p] [name[=value]]

OPTIONS
    -f   The names refer to shell functions;
         otherwise the names refer to shell variables
    -n   No longer mark each name for export.
    -p   Display output in a form that may be reused as input.

Linux geek (1): rpm

2009-03-08T12:18:00.004-04:00

In the Linux system, it can not extract *.rpm file initially(at least, my "Linux aura-laptop 2.6.27-11-generic #1 SMP Thu Jan 29 19:24:39 UTC 2009 i686 GNU/Linux"). If we input "rpm" command in terminal, it will tell you to install the rpm by inputting "sudo apt-get install rpm" to install the rpm. At the same time, using the friendly interface like Ubuntu, you can get it by clicking mouse right button to extract it.

RPM Package Manager

2009-03-07T20:48:00.001-05:00

RPM Package Manager is a package management system^[1]. The name RPM refers to two things: a software package file format, and software packaged in this format. RPM was intended primarily for Linux distributions; the file format RPM is the baseline package format of the Linux Standard Base.

Originally developed by Red Hat for Red Hat Linux, RPM is now used by many Linux distributions. It has also been ported to some other operating systems, such as Novell NetWare (as of version 6.5 SP3) and IBM's AIX as of version 4.

The phrase "RPM Package Manager" is a recursive acronym.

XML

2009-03-04T17:20:00.014-05:00

XML, refers to eXtensible Markup Language, is meta markup language that is now widely used.

Before XML, there are many markup languages, GML(Generalized Markup Language), SGML(Standard Generalized Markup Language), HTML(HyperText Markup Language).

SGML found wide acceptance and use in fields with very large-scale documentation requirements. However, it was generally found to be cumbersome and difficult to learn, a side effect of attempting to do too much and be too flexible. XML is a subset of SGML, designed so as to make the parser much easier to implement than a full SGML parser.

Query refinement

2009-03-02T18:13:00.032-05:00

Query refinement refers to users modify query using some return results by the IR system. Basically, users attempt to address this problem by manually refining a query. Actually, IR system can help with query refinement, either fully automatically or with the user in the feedback loop.

The methods for tackling this problem split into two major class: global methods and local methods. Global methods are independent of query and results returned from IR system. Local methods adjust a query relative to the documents that initially appear to match the query.

Local methods, that include user in the feedback loop, gain more attention because is one of the most used and most successful approaches. While global methods mainly refer to "query expansion" in this book that assist user to refine the initial query according to thesaurus.

The idea of relevance feedback(RF) is to involve the user in the IR process, therefore, this is a local method to do query refinement. Rocchio algorithm is the classic algorithm for implementing RF. It gives a method of incorporating relevance feedback information into the vector space model. The underlying theory is to find a revised query that maximizing the similarity with relevance documents and meanwhile minimizing similarity with nonrelevant documents. The optimal query should be the one moved from the initial query towards the centriod of the relevant and as far as possible away from the centroid from the nonrelevant documents.

Anyway, RF seems good for IR system and users. However, there are lots of situations when RF doesn't work. Firstly, RF needs users have prior knowledge that make initial query that is at least somewhere close to the documents they desire. For example, if the user inputs misspelled words, then RF is unlikely to be effective. In addition, RF requires relevant documents to be similar to each other, that is to say, RF works well when relevant documents are highly clustered. That is easy to get an intuition idea the Rocchio RF model treats relevant documents as a single cluster, it's obvious that Rocchio RF will fail if the relevant documents belong to more than one classes. Unfortunately, this could happen if subsets of the documents using different vocabulary, or a query for which the answer set is inherently disjunctive.

As a result, in general, RF has been little used in web search.

----Motivated by reading "Information retrieval".

SIGIR

2009-03-02T10:46:00.003-05:00

SIGIR is the Association for Computing Machinery's Special Interest Group on Information Retrieval. The scope of the group's specialty is the theory and application of computers to the acquisition, organization, storage, retrieval and distribution of information; emphasis is placed on working with non-numeric information, ranging from natural language to highly structured data bases.
The annual international SIGIR conference series, which began in 1978 (there was an initial SIGIR conference in 1971), is considered one of the most important conferences in the field of information retrieval. The 31st SIGIR conference (SIGIR 2008) took place in Singapore, and next SIGIR conference (SIGIR 2009) will be held in Boston MA, USA. SIGIR also sponsors the annual Joint Conference on Digital Libraries JCDL in association with SIGWEB, the Conference on Information and Knowledge Management CIKM, and in 2008 the International Conference on Web Search and Data Mining WSDM in association with SIGKDD, SIGMOD, and SIGWEB.

USPOP2002

2009-03-02T09:13:00.004-05:00

USPOP2002 is one of groud-truth data for comparison between some different acoustic-based similarity measuerments. It contains pre-calculated features for a collection of 706 albums and8764 popular music tracks from 400 artists. Uspop2002 shares the derived feature representations of each song. USPOP2002 also contains the "style" tags from All Music Guide for each of the 400 artists represented inthe collection.