text:
# Datamatching Part 3: Match Scoring

In this post I will share some tips on the final aspect of datamatching that was glossed over in parts 1 and 2 - scoring matches. This is maybe the hardest part of the process, but it also requires the most domain knowledge so it’s hard to give general advice.

### Recap

In the previous posts we started with two datasets “left” and “right”. Using tokenization and the magic of spark we generated for every left record a small bunch of right records that maybe correspond to it. For example this record:

got these two as candidate matches:

And now we need to decide which - if any - is(are) the correct one(s). Last time we dodged this problem by using a heuristic “the more keys were matched, the better the candidate”. In this case the record with Id 'a' was matched on both name and phone number while 'c' was matched on postcode alone, therefore 'a' is the better match. It worked in our simple example but in general it’s not very accurate or robust. Let’s try to do better.

### Similarity functions

The obvious first step is to use some string comparison function to get a continuous measure of similarity for the names rather than the binary match - no match. Levenshtein distance will do, Jaro-Winkler is even better.

and likewise for the phone numbers, a sensible measure of similarity would be the length of the longest common substring:

This makes sense at least if the likely source of phone number discrepancies is area codes or extensions. If we’re more worried about typos than different prefixes/suffixes then Levenshtein would be the way to go.

Next we need to come up with some measure of postcode similarity. E.g. full match = 1, partial match = 0.5 - for UK postcodes. And again the same for any characteristic that can be extracted from the records in both datasets.

With all those comparison functions in place, we can create a better scorer:

This should already work significantly better than our previous approach but it’s still an arbitrary heuristic. Let’s see if we can do better still.

### Scoring as classification

Evaluation of matches is a type of classification. Every candidate match is either true or spurious and we use similarity scores to decide which is the case. This dictates a simple approach:

1. Take a hundred or two of records from the left dataset together with corresponding candidates from the right dataset.
2. Hand label every record-candidate pair as true of false.
3. Calculate similarity scores for every pair.
4. Train a classifier model on the labeled examples.
5. Apply the model to the rest of the left-right candidate pairs. Use probabilistic output from the classifier to get a continuous score that can be compared among candidates.

It shouldn’t have been a surprise to me but it was when I discovered that this actually works and makes a big difference. Even with just 4 features matching accuracy went up from 80% to over 90% on a benchmark dataset just from switching from handpicked weights to weights fitted with logistic regression. Random forest did even better.

One more improvement that can take accuracy to the next level is iterative learning. You train your model, apply it and see in what situations is the classifier least confident (probability ~50%). Then you pick some of those ambiguous examples, hand-label them and add to the training set, rinse and repeat. If everything goes right, now the classifier has learned to crack previously uncrackable cases.

This concludes my tutorial on datamatching but there is one more tip that I want to share.

### Name similarity trick

Levenshtein distance, Yaro-Winkler distnce etc. are great measures of edit distance but not much else. If the variation in the string you’re comparing is due to typos ("Bruce Wayne" -> "Burce Wanye") then Levenshtein is the way to go. Frequently though the variation in names has nothing to do with typos at all, there are just multiple ways people refer to the same entity. If we’re talking about companies "Tesco" is clearly "Tesco PLC" and "Manchester United F.C." is the same as "Manchester United". Even "Nadbor Consulting Company" is very likely at least related to "Nadbor Limited" given how unique the word "Nadbor" is and how "Limited", "Company" and "Consulting" are super common to the point of meaninglessness. No edit distance would ever figure that out because it doesn’t know anything about the nature of the strings it receives or about their frequency in the dataset.

A much better distance measure in the case of company names should look at the words the two names have in common, rather than the characters. It should also discount the words according to their uniqueness. The word "Limited" occurs in a majority of company names so it’s pretty much useless, "Consulting" is more important but still very common and "Nadbor" is completely unique. Let the code speak for itself:

The above can be interpreted as the scalar product of the names in the Bag of Word representation in the idf space except instead of the logarithm usually used in idf I used a square root because it gives more intuitively appealing scores. I have tested this and it works great on UK company names but I suspect it will do a good job at comparing many other types of sequences of tokens (not necessarily words).

# Datamatching Part 2: Spark Pipeline

In the last post I talked about the principles of datamatching, now it’s time to put them into practice. I will present a generic, customisable Spark pipeline for datamatching as well as a specific instance of it that for matching the toy datasets from the last post. TL;DR of the last post:

To match two datasets:

1. Tokenize corresponding fields in both datasets
2. Group records having a token in common (think SQL join)
3. Compare records withing a group and choose the closest match

### Why spark

This datamatching algorithm could easily be implemented in the traditional single-machine, single-threaded way using a collection of hashmaps. In fact this is what I have done on more than one occasion and it worked. The advantage of spark here is built-in scalability. If your datasets get ten times bigger, just invoke spark requesting ten times as many cores. If matching is taking too long - throw some more resources at it again. In the single-threaded model all you can do is up the RAM as your data grows but the computation is taking longer and longer and there is nothing you can do about it.

As an added bonus, I discovered that the abstractions Spark forces on you - maps, joins, reduces - are actually appropriate for this problem and encourage a better design than the naive implementation.

### Example data

In the spirit of TDD, let’s start by creating a test case. It will consist of two RDDs that we are going to match. Spark’s dataframes would be even more natural choice if not for the fact that they are completely fucked up.

### Tokenizers

First step in the algorithm - tokenize the fields. After all this talk in the last post about fancy tokenizers, for our particular toy datasets we will use extremely simplistic ones:

Now we have to specify which tokenizer should be applied to which field. You don’t want to use the phone tokenizer on a person’s name or vice versa. Also, tokens extracted from name shouldn’t mix with tokens from address or phone number. On the other hand, there may be multiple fields that you want to extract e.g. phone numbers from - and these tokens should mix. Here’s minimalistic syntax for specifying these things:

And here’s how they are applied:

The result is a mapping of token -> Id in the form of an RDD. One for each dataset:

### Generating candidate matches

Now comes the time to generate candidate matches. We do that by joining records that have a token in common:

Result:

With every match we have retained the information about what it was joined on for later use. We have 4 candidate matches here - 2 correct and 2 wrong ones. The spurious matches are (1, 'c') - Bruce Wayne and Alfred Pennyworth matched due to shared address; (2, 'a') - Bruce Wayne and Thomas Wayne matched because of the shared last name.

Joining the original records back to the matches, so they can be compared:

### Finding the best match

We’re almost there. Now we need to define a function to evaluate goodness of a match. Take a pair of records and say how similar they are. We will cop out of this by just using the join keys that were retained with every match. The more different types of tokens were matched, the better:

We also need a function that will say: a match must be scored at least this high to qualify.

And now, finally we use those functions to evaluate and filter candidate matches and return the matched dataset:

The result:

Glorious.

### Putting it all together

Now is the time to put “generic” back in the “generic datamatching pipeline in spark”.

To use it, you have to inherit from DataMatcher and override at a minimum the get_left_tokenizers and get_right_tokenizers functions. You will probably want to override score_match and is_good_enough_match as well, but the default should work in simple cases.

Now we can match our toy datasets in a few lines oc code, like this:

Short and sweet.

There are some optimisations that can be done to improve speed of the pipeline, I omitted them here for clarity. More importantly, in any nontrivial usecase you will want to use a more sophisticated evaluation function than the default one. This will be the subject of the next post.

# Datamatching Part 1: Algorithm

In this and the next post I will explain the basics of datamatching and give an implementation of a bare-bones datamatching pipeline in pyspark.

### Datamatching

You have a dataset of - let’s say - names and addresses of some group of people. You want to enrich it with information scraped from e.g. linkedin or wikipedia. How do you figure out which scraped profiles match wich records in your database?

Or you have two datasets of sales leads maintained by different teams and you need to merge them. You know that there is some overlap between the records but there is no unique identifier that you can join the datasets on. You have to look at the the records themselves to decide if they match.

Or you have a dataset that over that years has collected some duplicate records. How do you dedup it, given that the data format is not consistent and there may be errors in the records?

All of the above are specific cases of a problem that can be described as: Finding all the pairs (groups) of records in a dataset(s) that correspond to the same real-world entity.

This is what I will mean by datamatching in this post.

This type of task is very common in data science, and I have done it (badly) many times before finally coming up with a generic, clean and scalable solution. There are already many commercial solutions to specific instances of this problem out there and I know of at least two startups whose main product is datamatching. Nevertheless for many usecases a DIY datamatching pipeline should be just as good and may be easier to build than integration with an external service or application.

### An example

The general problem of datamatching will be easier to discuss with a specific example in mind. Here goes:

You work at a company selling insurance to comic book characters. You have a database of 50.000 potential clients (these are the first 3):

and you just acquired 400.000 new leads:

You need to reconcile the two tables - find which (if any) records from the second table correspond to records in the first. Unfortunately data in both tables is formatted differently and there are some typos in both (“Burce”, “Ogtham”). Nevertheless it is easy for a human being to figure out who is who just by eyeballing the two datasets. $Id = 1$ from the first table and $Id = a$ from the second clearly refer to the same person - Bruce Wayne. And $Id = 3$ matches $Id = b$ - Bruce Banner. The remaining records - Thomas Wayne and Alfred Pennyworth don’t have any matches.

Now, how to do the same automatically and at scale? Comparing every record from one table to every one in the other - $50k \times 400k = 2 \times 10^9$ comparisons - is out of the question.

### The impatient programmer approach

Like any red-blooded programmer, when I see a list of things to be matched to other things, I immediately think: hashmaps. My internal dialogue goes something like this:

• Let’s make a lookup {name -> Id} using the first table and iterate over the second table
• But the names are in a different format, they won’t match
• OK, let’s normalize the names first, strip punctuation, put the words in alphabetical order
• Still won’t match - Bruce Banner is abbreviated to B. Banner in one of the tables
• Fair enough. Let’s have two separate entries in the lookup for ‘Bruce’ and ‘Banner’ both pointing to Id = 3
• but we don’t want to match just any ‘Bruce’ or any ‘Banner’ to this guy
• Yeah, will have to use the remaining attributes to verify if a match is legit. Generate potential matches by looking up every word in the ‘name’ field, and validate by checking if the other fields look similar. This should work
• what if the name is empty or misspeled, but all other fields match up perfectly? Shouldn’t this be still considered a match?
• Now you’re being difficult on purpose! FINE. Let’s have multiple lookups - name -> Id, phone -> Id, etc. A pair of records will be considered a potential match if they have at least one of those in common

This is beginning to sound unwieldy, but it’s basically the correct approach and - I strongly suspect - the only workable approach. At least as long as we’re not taking the hashmaps too literally. But let’s reformulate it in slightly more abstract terms before diving into implementation.

### Generalising

Datamatching must consist of two stages:

1. Generate candidate matches
2. For every record, pick the best match among the candidates

In this post I will assume that we have a good way of evaluating candidate matches (step 2) and concentrate only on step 1. In fact 2 is crucial and usually harder than 1 but it’s very case-specific. More on that topic next time.

#### Generating candidates

When is a pair of records a good candidate for a match? When the records have something in common. What? For example one of the fields - like phone number or name or address. That would definitely suffice but it’s too restrictive. Consider Bruce Wayne from our example. In the first table:

And in the second table:

Not a single field in common between these two records and yet they clearly represent the same person.

It is tempting to try to normalise phone numbers by stripping area extensions, fix misspeled names, normalise order of first-, middle-, last name, etc. And sometimes this may be the way to go. But in general it’s ambiguous and lossy. There will never be a normalisation function that does the right thing for every possible version of the name:

What we can do instead is extract multiple tokens (think: multiple hashes) from the name. A pair of records will be considered a candidate match if they have at least one token in common.

We can for example just split the name on whitespaces:

and have this record be matched with every “Bruce” every “Thomas” and every “Wayne” in the dataset. This may or may not be a good idea depending on how many “Bruces” there are in this specific dataset. But tokens don’t have to be words. We can try bigrams:

Or we can try forming initials:

If we did that, then for instance both “Bruce Wayne” and “Burce T. Wayne” would get “B. Wayne” as one of the tokens and would end up matched as a result.

If we tokenize by removing vowels, that would go a long way toward fixing typos and alternative spellings while introducing few false positives:

There are also algorithms like Soundex that tokenize based on how a word sounds regardless of how it’s spelled. Soundex gives the same result for “Bruce” and “Broose” and “Bruise” or for “John” and “Jon”. Very useful given that a lot data entry is done by marketers who talk to people (and ask their names) over the phone.

Finally, nothing stops us from using all of the above at the same time:

With this, all the different ways of spelling “Bruce Wayne” should get at least one token in common and if we’re lucky few other names will.

This was an overview of name tokenization. Other types of data will require their own tokenization rules. The choice of tokenization logic necessarily depends on the specific data type and dataset but these the general principles:

• tokenization should try to fix ambiguities in the data. If there are multiple ways a real world entity can be represented in the dataset, good tokenizer would give all of them the same token
• tokens should be specific enough records representing different real world entities only rarely get a token in common

One not name-related example: phone numbers. Since people enter phone numbers in databases in one thousand different formats with all kinds of rubbish area codes and extensions you shouldn’t count on raw phone numbers matching perfectly. An example of a sensible tokenizer is one that first strips all non-digit characters from the phone number then returns the last 8 digits.

Or to guard against people putting extensions at the end of phone numbers, we can extract every consecutive 8 digits:

This should catch any reasonable way of writing the number while still having very low likelihood of a collision.

#### TL;DR

To match two datasets:

1. Tokenize corresponding fields in both datasets
2. Group records having a token in common (think SQL join)
3. Compare records withing a group and choose the closest match

Coming up: how to implement this in spark.

# Dear Recruiter

I’ve had a lot of experience with tech interviews and recruiters in the past and I’m likely to have a lot more in the future. A non-negligible fraction of that experience ranged from “mildly annoying” to “exasperating”.

Here’s a list of real examples of irritating recruiter behaviors together with guidlines on how I expect a reasonable person to act instead.

Before we start you must understand where I’m coming from. I’m not constantly looking for new jobs. But when I do, I apply en masse and then I have to deal with many recruiters at once. Each one constantly calling me in the office or at home (what is it with your obsession with phone calls? Why not email?). This in itself can get annoying but on top of that there are other more serious offenses. I am usually extremely agreeable both in person and over the phone. A blog post is my way of expressing complaints that I wouldn’t dare make in a conversation with you. It’s also a form of catharsis so forgive me if I get somewhat snarky and don’t take offense if you personally are not guilty of the sins mentioned here.

### When you contact me about a new role

I have an exciting opportunity with a global company, one of the leaders in its field. When can we arrange a call?

This tells me nothing. Everyone is either a “leader in their field” or an “exciting startup” or a “global brand”. I’m getting 5 of these a day. If I am to commit any time to it I first need to know:

• type of role (data scientist? developer? devops? junior? lead? manager?)
• ballpark salary
• skills they are looking for

Ideally, if possible, also

• what are they trying to build/do

This information is typically enough for me to decide if I’m interested or not. I will let you know if I am. I really don’t need to listen to you talk about their nice offices and what fancy university has the CTO attended. If I’m interested in these things I will look them up myself. This conversation is not going to change my mind one way or the other.

If you want to chat with me because you need to vet me before passing my CV on to the company please say so and indicate clearly what your decision is afterwards. And don’t do this bait-and-switch on me where I express interest in one position and you call me to discuss but only try to peddle another.

In short, this is how it’s going to work:

1. you email me basic details of the role (or multiple roles)
2. I email you back with my latest CV if I’m interested or with questions if I have any
3. you send my details over the company and try to arrange an interview

If you absolutely need to hear my voice and vet me, say so. If I’m interested in the role, we can get it over with once.

#### Before the interview

Let me know what is the best time to call you so that I can talk you through the interview process

Why? It’s a job interview not open heart surgery. There will be a 20 minutes phone call with HR, then an hour with some technical person then 3 hours of technical on-site interviews then a brief chat with some higher-up. Or a homework assignment, then technical phone call, then on-site, then HR. Or some other configuration. Whatever the case, you could’ve explained it in the email and save us both time. Frankly, I don’t care what the format is. All I need from you is the time and place and it is definitely possible to send those by email.

I will call you before the interview to give you a heads up

No.

Are you interviewing with any other companies? Tell me, so we can adjust the schedule so that you don’t miss this opportunity

What you mean is “we can adjust the schedule so that you don’t get the chance to interview with anyone else” (more on that later). Thank you very much. I don’t want to lie to you, so I’m just not going to tell you anything. If I actually need to speed things up because of other interviews, I will let you know. By email.

How it is going to work:

1. you give me time and place
2. I confirm that I will show up

### After the interview

Please call me after the interview to tell me how did it go …

It went well. Probably. Or maybe not. Either way it doesn’t really matter how I think it went, does it?

… what was it like …

It was like every other interview I’ve been to. First they introduced themselves and the company, then we talked about my resume, then about my motivation and finally they gave me some vaguely job-related problems to solve and I solved them. What else did you expect?

… how did you like them

I liked them fine. Or maybe I loved them. Or maybe I thought they were boring. You won’t find out by calling though, because I’m only gonna feed you some enthusiastic sounding platitudes because I want to get to the next stage in this process. There is no upside for me in telling you that I thought the interviewers were boring and dumb even if it was true. So just don’t ask. In the unlikely event that I hated the interview enough to make me want to withdraw my application, I promise to let you know. By - you guessed it - email.

How it’s going to work:

1. if you have any feedback from the interviewers or a decision, you will email it to me
2. if I want to take myself out of the process I will inform you also by email

### The final stretch

So I made it through all the rounds and I’m expecting to hear back from the company. You call me saying you have some positive initial feedback, then we have this conversation:

You: If they come back with an offer of £n are you going to accept?
Me: I don’t know. I’ll need a couple of days to think about it.
You: Why wouldn’t you accept it? What is wrong with the offer?
Me: Nothing is wrong with it. I just need some time to consider my options. Not very long, just the weekend.
You: If there is nothing wrong with the offer then you should take it. I need to get back to them and tell them that you are going to take the offer. Otherwise they will think that you are not really motivated to work with them and they will not make the offer.
Me: What are you talking about?! They know I’m motivated. But this is a serious decision and I will not make it without proper consideration.
You: They have deadlines, you know. They can’t wait forever.
Me: It’s only two days!
You: If I don’t tell them you will accept, they will keep interviewing and they can find someone else. This is a very buyoant market!

This is bullshit and you know it. This is not a heist movie and you’re not looking for a last minute replacement safe cracker. The job ad has been out for months. I think they can wait two more days.

One time this happened to me right after the interview. The recruiter didn’t even wait to hear from the company in question. He based this whole routine on my reporting that the interview went well and that we discussed money at the end. This was also a case of him putting me up for a job that paid 10% less than the one I held at the time even though I explicitly required that my new position pays 10% more. I only found out during the final interview.

Another recruiter upon learning that I’m interviewing with other companies got my final interview cancelled. My first interview was on Monday and the final one was supposed to take place a week later. On Wednesday he asked me about other interviews, then we’ve had the bullshit “you’ve got to accept” conversation. When I didn’t budge, the recruiter got the company to make me an offer that evening, skipping the final interview. The offer came with an expiration date on 12am the following day! 4 days before the planned interview. He even blurted out that the insane timing was because they were afraid they would lose me, before covering up with the deadlines and buyoant markets bs. That they have to resort to this type of tactics is all the proof I need that the market for data scientists isn’t buyoant at all. Obviously they were afraid I would accept another offer. And the only reason they were afraid was that the recruiter tipped them off.

I understand now that we’re not allies. We are not exactly oponents but you’re definitely playing for a different team.

So I am not going to make it easy for your team. I will not get caught up in the false sense of urgency you’re trying to create (one recruiter tried to get me to come to the office and sign the contract on a Sunday) … ever again. I will not fall for scare tactics. I will not reveal any information about other interviews I may be having. Here’s what will happen:

1. you will only contact me when you have an offer
2. I will take my time considering that offer - and I will tell you how long exactly. Shorter if it’s a “start immediately” fixed term contract, longer if it’s a permanent position, but I will never be bullied into committing to a contract I haven’t even seen
3. I will ignore any exploding offer deadlines so don’t even bother. The only exception is if the deadline has been established up front before any interviews

It’s worth noting that I have never experienced anything resembling the “bullshit conversation” when I dealt with a potential employer directly. When applying through recruiters it happened every time.

### Final notes

• no I will not have coffee with you. Why would you even think I’d like that?
• I don’t need you to tell me that “if you like the job you should be flexible about the money” or that “these companies are not going to wait forever, better apply now”
• in general I would appreciate if you keep your obviously-biased career advice to yourself
• any tips regarding my resume or specific interviews are very welcome
• if you can write an email to arrange a call to tell me X, you can just tell me X in the email

If these ground rules seem unreasonable to you, then save us both the trouble and don’t contact me.

Yours Exasperatedly

### P.S.

I didn’t intend to make it read like I’m bragging about all the offers I’m getting like I’m God’s gift to data science who can get any job he wants. It’s just that I’ve interviewed a lot over the years so in addition to dozens of rejections I have had several successes too. I’m only describing here the more successful examples because in case of rejection recruiters tend to mercifully leave me alone.

# Deepwalking With Companies

I have blogged about the wide usefulness of topic models and I have benchmarked word-embedding-assisted classification on Reuter’s benchmark. This time I experiment with these ideas using a real world and decent sized dataset - the graph of UK/Irish companies. I have done this during my “10% time” at DueDil (it’s like google’s “20% time”, except it exists).

### Graph of companies

There are 4 million active companies in the UK and Ireland. DueDil collects all kinds of information about them - financials, legal structures, contact info, company websites, blogs, news appearences etc. All of it is presented to our users and some of it also serves as input to machine learning tasks - like classifying companies into industries.

One very interesting dataset that remains underutilised (AFAIK by anyone, not just DueDil) is the network of connections of companies and directors.

You can tell a lot about a company just by looking at its directors. That is - if you know anything about these people. At DueDil we don’t know much more than just their identities. This would be rather useless in the context of a single company. But there are millions of companies and people who serve as their directors more often then not do it many times in their careers at different companies. Knowing that the director’s name is Jane Brown may be useless, but knowing that the director previously held similar positions at three different tech startups is highly relevant. And this is just one director out of many and one type of relationship.

More generally, one can think about companies as nodes in a graph. Two companies are connected iff there is a person who has served as a director at both of them (not necessarily at the same time). I will call this the company graph. Here’s a part of the graph containing DueDil.

DueDil is connected to Founders For Good Ltd because our CEO Damian Kimmelman is also a director at the other company.

It is intuitive that the position of a company in this graph tells us something about the company. It is however difficult to do anything with this information unless it is somehow encoded into numbers.

### Company2Vec

This is where word embeddings come in. As I mentioned previously, it is possible to apply Word2Vec to a graph to get an embedding of graph nodes as real-valued vectors in a procedure called DeepWalk. The idea is very simple:

1. Construct a bunch of random walks on the graph
2. Feed the random walks into Word2Vec

A random walk is just a sequence of nodes, where the next node is always one of the neighbours of the previous node, chosen at random. Think: Duedil -> Founders For Good Ltd -> Omio Limited.

Word2Vec accepts a collection of documents - where every document is a list of tokens (strings). Here company Id’s play the role of tokens and random walks play the role of documents. It all checks out.

To limit the size of the graph for this proof of concept, I have applied this procedure only to the 2.2 million companies that

1. are active
2. have at least one edge (director in common) to another active company

I generated 10 random walks starting at every company, the length of each walk was 40. Training Word2Vec with gensim on this corpus of $10 \times 40 \times 2200000 = 8.8 \times 10^8$ tokens took over 11h. It also took a machine with 40gb of RAM before it stopped crashing even though the random walks were generated on-line.

Finally I got some vectors out of it - one per company. These vectors themselves were the goal of this project (they can serve as features in ML), but I also made some plots to verify that the algorithm is working as advertised.

### Pretty pictures with t-SNE and Bokeh

The embedding produced by DeepWalk was 100-dimensional in this case, so I had to do some dimensionality reduction before trying to visualize the vectors. t-SNE is perfect for this kind of thing. Here’s a sample of 40000 company vectors embedded in 2D with t-SNE. You can move or zoom in the plot or hover over the dots to see the names of the corresponding companies.

Bokeh Plot

It worked! You can immediately see that there is some structure in the data and t-SNE has picked up on it (and this is only a tiny sample - 2% of all the datapoints). What does this structure mean? After the graph has beed transformed with DeepWalk and then t-SNE, the position of a company in this plot doesn’t have a simple interpretation but it’s clear that groups of highly interconnected companies will correspond to clusters of points in this plot. And it’s easy to verify just by looking at the names of the companies that this is the case.

Take the big blob in the upper left corner - the companies there:

• Edwards Macliammoir Dublin Gate Theatre Productions Limited
• Humanist Association of Ireland Limited
• Kildare Street Management Limited
• Shannon Airport Authority Limited

We have discovered the cluster of irish companies! And if you zoom in on the long, narrow appendage sticking out of this cluster towards bottom left - you’ll see companies like:

• Tempelhof Aircraft Leasing (Ireland) Limited
• Gallic Dragon Aviation Limited
• Aergen Aircraft Ten Limited

… and hundreds more. This is not even cherry-picked. I hereby declare the discoverery of the Irish Aviation Peninsula.

Slightly up and to the right of center there is a smaller scottish cluster recognizable through such companies as

• Caledonian Sausage Company
• Edinburgh Tattoo Productions Limited
• Dundee Ice Arena

There are many other smaller clusters and it’s actually a fun exercise to try to pinpoint exactly what do the companies in a cluster have in common.

#### Now in color!

This was fun if somewhat grim looking. Let’s try to add some color to the plot. The original goal of this project was to get graph-derived features for industry classification. Let’s try using different colors to denote different industries (based on SIC codes). If DeepWalk coordinates are predictive of the industry a company is in, we should expect to see same-colored dots (companies in the same industry) clustering together in the plot. Does this actually happen?

Bokeh Plot

A little bit, yes.

Mostly everything is a big reddish mess (“services” is the most popular category). But there are indeed some clusters. Right of center we can see a medium sized pink blob of insurance companies:

• US Risk (UK) Newco Limited
• Zenith Insurance Management UK Limited
• North Star Underwriting Limited

Below it and to the left lies another, this one green:

• Timeless Films Limited
• Hercules Productions Ltd
• Koninck studios PTE Limited

Clearly this is a cluster of film companies (plus other media). If you look more closely you will discover that this is actually the cluster of London based film companies. Nearby there is a smaller green cluster of media companies from the rest of England and another one for Wales. These are less clearly delimited and partly obscured by the red dots of “Services” companies. There are many others, but they are sometimes so tight, they appear as a single dot in the plot.

This is more noisy than I hoped for but it’s definitely working. Would definitely improve accuracy of industry classification if used with other stronger features. Plus you can learn interesting things from it just by looking at the plot. Like the fact that film production companies are closely connected to each other and relatively unconnected to the rest of the world. Or that London is a different country as far as media companies are concerned.

#### Bonus: keyword based company embedding

Having all this t-SNE and Bokeh niceness in place I couldn’t resist applying it to another interesting dataset - keywords. Keywords are a set of industry related tags that DueDil has for millions of companies. They are things like “fishing” or “management consulting” or “b2b”. A company usually has between a few and a few dozen of them.

A byproduct of the pipeline that extracts keywords for companies is a Word2Vec embedding of the keywords. I used this embedding to create an embedding of companies. This was done simply by averaging all the vectors corresponding to a company’s keywords. I ran the resulting vectors through t-SNE and here’s what it looks like:

Bokeh Plot

I shouldn’t be surprised that keywords - which were picked to be industry related - predict the industry really well. But I was blown away by the level of detail preserved by t-SNE. There are recognizable islands for everything. There is a golden Farmers Archipelago and a narrow blue Dentist Island south from Home Care Island. There is a separate Asian Island in the Restaurant Archipelago - go see for yourself.

This was fun. Long live Word2Vec and t-SNE!

# Data Engineers Will Hate You - One Weird Trick to Fix Your Pyspark Schemas

I will share with you a snippet that took out a lot of misery from my dealing with pyspark dataframes. This is pysparks-specific. Nothing to see here if you’re not a pyspark user. The first two sections consist of me complaining about schemas and the remaining two offer what I think is a neat way of creating a schema from a dict (or a dataframe from an rdd of dicts).

#### The Good, the Bad and the Ugly of dataframes

Dataframes in pyspark are simultaneously pretty great and kind of completely broken.

• they enforce a schema
• you can run SQL queries against them
• faster than rdd
• much smaller than rdd when stored in parquet format

On the other hand:

• dataframe join sometimes gives wrong results
• pyspark dataframe outer join acts as an inner join
• when cached with df.cache() dataframes sometimes start throwing key not found and Spark driver dies. Other times the task succeeds but the the underlying rdd becomes corrupted (field values switched up).
• not really dataframe’s fault but related - parquet is not human readable which sucks - can’t easily inspect your saved dataframes

But the biggest problem is actually transforming the data. It works perfectly on those contrived examples from the tutorials. But I’m not working with flat SQL-table-like datasets. Or if I am, they are already in some SQL database. When I’m using Spark, I’m using it to work with messy multilayered json-like objects. If I had to create a UDF and type out a ginormous schema for every transformation I want to perform on the dataset, I’d be doing nothing else all day, I’m not even joking. UDFs in pyspark are clunky at the best of times but in my typical usecase they are unusable. Take this, relatively tiny record for instance:

the correct schema for this is created like this:

And this is what I would have to type every time I need a udf to return such record - which can be many times in a single spark job.

#### Dataframe from an rdd - how it is

For these reasons (+ legacy json job outputs from hadoop days) I find myself switching back and forth between dataframes and rdds. Read some JSON dataset into an rdd, transform it, join with another, transform some more, convert into a dataframe and save as parquet. Or read some parquet files into a dataframe, convert to rdd, do stuff to it, convert back to dataframe and save as parquet again. This workflow is not so bad - I get the best of both worlds by using rdds and dataframes only for the things they’re good at. How do you go from a dataframe to an rdd of dictionaries? This part is easy:

It’s the other direction that is problematic. You would think that rdd’s method toDF() would do the job but no, it’s broken.

actually returns a dataframe with the following schema (df.printSchema()):

It interpreted the inner dictionary as a map of boolean instead of a struct and silently dropped all the fields in it that are not booleans. But this method is deprecated now anyway. The preferred, official way of creating a dataframe is with an rdd of Row objects. So let’s do that.

prints the same schema as the previous method.

In addition to this, both these methods will fail completely when some field’s type cannot be determined because all the values happen to be null in some run of the job.

Also, quite bizarrely in my opinion, order of columns in a dataframe is significant while the order of keys is not. So if you have a pre-existing schema and you try contort an rdd of dicts into that schema, you’re gonna have a bad time.

#### How it should be

Without further ado, this is how I now create my dataframes:

This doesn’t randomly break, doesn’t drop fields and has the right schema. And I didn’t have to type any of this StructType([StructField(... nonsense, just plain python literal that I got by running

As an added bonus now this prototype is prominently displayed at the top of my job file and I can tell what the output of the job looks like without having to decode parquet files. Self documenting code FTW!

#### How to get there

And here’s how it’s done. First we need to implement our own schema inference - the way it should work:

Using this we can now specify the schema using a regular python object - no more java-esque abominations. But this is not all. We will also need a function that transforms a python dict into a rRw object with the correct schema. You would think that this should be automatic as long as the dict has all the right fields, but no - order of fields in a Row is significant, so we have to do it ourselves.

And finally:

# Text Classification With Word2Vec

In the previous post I talked about usefulness of topic models for non-NLP tasks, it’s back to NLP-land this time. I decided to investigate if word embeddings can help in a classic NLP problem - text categorization. Full code used to generate numbers and plots in this post can be found here: python2 version and python3 version by Marcelo Beckmann (thank you!).

#### Motivation

The basic idea is that semantic vectors (such as the ones provided by Word2Vec) should preserve most of the relevant information about a text while having relatively low dimensionality which allows better machine learning treatment than straight one-hot encoding of words. Another advantage of topic models is that they are unsupervised so they can help when labaled data is scarce. Say you only have one thousand manually classified blog posts but a million unlabeled ones. A high quality topic model can be trained on the full set of one million. If you can use topic modeling-derived features in your classification, you will be benefitting from your entire collection of texts, not just the labeled ones.

#### Getting the embedding

Ok, word embeddings are awesome, how do we use them? Before we do anything we need to get the vectors. We can download one of the great pre-trained models from GloVe:

and use load them up in python:

or we can train a Word2Vec model from scratch with gensim:

#### The (python) meat

We got ourselves a dictionary mapping word -> 100-dimensional vector. Now we can use it to build features. The simplest way to do that is by averaging word vectors for all words in a text. We will build a sklearn-compatible transformer that is initialised with a word -> vector dictionary.

Let’s throw in a version that uses tf-idf weighting scheme for good measure

These vectorizers can now be used almost the same way as CountVectorizer or TfidfVectorizer from sklearn.feature_extraction.text. Almost - because sklearn vectorizers can also do their own tokenization - a feature which we won’t be using anyway because the benchmarks we will be using come already tokenized. In a real application I wouldn’t trust sklearn with tokenization anyway - rather let spaCy do it.

Now we are ready to define the actual models that will take tokenised text, vectorize and learn to classify the vectors with something fancy like Extra Trees. sklearn’s Pipeline is perfect for this:

#### Benchmarks

I benchmarked the models on everyone’s favorite Reuters-21578 datasets. Extra Trees-based word-embedding-utilising models competed against text classification classics - Naive Bayes and SVM. Full list of contestants:

• mult_nb - Multinomial Naive Bayes
• bern_nb - Bernoulli Naive Bayes
• svc - linear kernel SVM
• glove_small - ExtraTrees with 200 trees and vectorizer based on 50-dimensional gloVe embedding trained on 6B tokens
• glove_big - same as above but using 300-dimensional gloVe embedding trained on 840B tokens
• w2v - same but with using 100-dimensional word2vec embedding trained on the benchmark data itself (using both training and test examples [but not labels!])

Each of these came in two varieties - regular and tf-idf weighted.

The results (on 5-fold cv on a the R8 dataset of 7674 texts labeled with 8 categories):

SVM wins, word2vec-based Extra Trees is a close second, Naive Bayes not far behind. Interestingly, embedding trained on this relatively tiny dataset does significantly better than pretrained GloVe - which is otherwise fantastic. Can we do better? Let’s check how do the models compare depending on the number of labeled training examples. Due to its semi-supervised nature w2v should shine when there is little labeled data.

That indeed seems to be the case. w2v_tfidf’s performance degrades most gracefully of the bunch. SVM takes the biggest hit when examples are few. Lets try the other two benchmarks from Reuters-21578. 52-way classification:

Qualitatively similar results.

And 20-way classification:

This time pretrained embeddings do better than Word2Vec and Naive Bayes does really well, otherwise same as before.

#### Conclusions

1. SVM’s are pretty great at text classification tasks
2. Models based on simple averaging of word-vectors can be surprisingly good too (given how much information is lost in taking the average)
3. but they only seem to have a clear advantage when there is ridiculously little labeled training data

At this point I have to note that averaging vectors is only the easiest way of leveraging word embeddings in classification but not the only one. You could also try embedding whole documents directly with Doc2Vec. Or use Multinomial Gaussian Naive Bayes on word vectors. I have tried the latter approach but it was too slow to include in the benchmark.

Update 2017: actually, the best way to utilise the pretrained embeddings would probably be this https://blog.keras.io/using-pre-trained-word-embeddings-in-a-keras-model.html I shall add this approach to the benchmark when I have some time.

1. Sometimes pretrained embeddings give clearly superior results to word2vec trained on the specific benchmark, sometimes it’s the opposite. Not sure what is going on here.

Overall, we won’t be throwing away our SVMs any time soon in favor of word2vec but it has it’s place in text classification. Like when you have a tiny training set or to ensemble it with other models to gain edge in Kaggle.

Plus, can SVM do this:

prints

# DS Toolbox - Topic Models

If you’re not primarily working with NLP you may not have been paying attention to topic modeling and word embeddings. In this post I intend to convince you that you should.

### Topic models

Topic models are a set of models in NLP that discover common themes in a collection of documents. You give it a list of texts and it comes up with a bunch of topics and maps every document to a topic or a mixture of topics. Here you can see a visualization of a topic model applied to wikipedia articles. As you can see, it picks up similar kinds of themes in the texts that a human being would notice. Take topic 5 for instance. Its top relevant words are “war”, “force”, “army”, “attack”, “military” and top articles: “Second Boer War”, “Erwin Rommel”, “Axis powers”, “Vietnam war”. Pretty neat. Most topic models (like the most popular LDA produce a vector of numbers for every text - the distribution of topics and a similar vector for every word - the affinity of the word to every topic.

### Word (and document) embeddings

Word embeddings are related to topic models but instead of mapping a text to a mixture of topics they learn to map words to real valued fixed-size vectors. The mapping is designed to preserve the semantic structure so that the distance between vectors corresponds to distance in meaning of words. An additional property of these embeddings (probably unintended) is that you can do a sort of algebra on words - like this:

- an examples taken from the most famous word embedding algorithm -word2vec. How cool is that? If you want to play with the vectors yourself and discover new fun analogies ($Bush - Iraq + Vietnam \approx Nixon$ !!!) you can download pretrained vectors from word2vec or GloVe.

### Why you should care

Unsupervised algorithms learning about analogies between real-world entities is pretty cool but it obscures the wider applicability of these algorithms. The topic modeling and embedding algorithms were invented in the context of NLP but most of them (including LDA and wor2vec) don’t have any inherent knowledge about natural languages and can be applied just as well to sequences of items from a discrete set of any kind. This is huge. Sequences (or sets) of items are notoriously hard to work with. Most popular ML algorithms expect fixed-size vectors as inputs. If your inputs are sequences you can either:

• do one-hot encoding and then use any old ML algo you want (like a random forest). Unfortunately one-hot discards all information about the order of items. More importantly, as the size of the vocabulary grows beyond thousands (which is still tiny as far as vocabularies go) your random forest will take forever to train and overfit.
• use naive bayes. NB works surprisingly well but only for classification and only when the problem is - well, naive. It also utilizes the item order information to a very limited extent via n-grams.
• use a recurrent neural network This can actually be very effective in some cases but I don’t think it would work well with a vocabulary size in the thousands. Even the character-level language models take days to train properly on a GPU (but what incredible results it produces!). I believe NNs of all kinds will get better and easier to use but as of now this is not a practical solution to our problem at all.

This is where word embeddings come in. Just run word2vec on your sequences of items and you’ll get a reasonably-dimensional representation of every item. You can then take the mean of all vectors in a sequence to get a representation of sequences. Or run doc2vec and you’ll get a vector for each sequence directly. Or if you need them clustered - run LDA. LDA’s word-topic coefficients can also be used as word embedding but they don’t do nearly as good of a job at it as word2vec. Same goes for LDA’s text-topic coefficients as a document to vector mapping.

This is it. This is what topic modeling buys you. It’s a generic clustering and feature extraction technique that works on sequences (or sets) of items from a discrete vocabulary. Does it actually work in practice? I don’t know of a lot of examples of people using it but I know a few.

#### Page jumps

As I have already described in my mini-guide to data science interviews (question “Predicting page jumps”) it can be used to model users jumping between pages of a web application. Here a page plays the role of a word and a user journey is a sentence. You can (and from what I understood from the interview - they [the company I interviewed with] do) use topic modeling to segment users based on their journeys and extract features for them to predict page jumps.

In a similar vein, topic modeling has been used as a feature extraction technique in the prediction of ad clicks. The paper concentrates on the authors’ special brand of topic modeling but the idea is simple and can be used with any topic model for example LDA. They treat hosts (the websites with banners on them) as words and users who visit the websites as documents. Let’s say John visits youtube then google then wikipedia then youtube again then tmz then guardian. This gives us a sequence [“youtube”, “google”, “wikipedia”, “youtube”, “tmz”, “guardian”]. Topic modeling is applied to the set of all users and the result is a set of topics (“media”, “business” and “drive” in the paper) and a decomposition of every user into those topics. So for our John we should expect something like {media: 0.8, business: 0.2, drive: 0}. This is interesting in itself and constitutes a great feature vector that you can feed into a regression predicting clicks - which is exactly what the authors did.

#### DeepWalk

Feature extraction from graphs is even harder than for sequences. Say you want to classify youtube videos. You have a labeled training set and a set of features for every video. But you also know that some videos link to other videos - forming a graph. Information about the position of the video in this graph is bound to be useful for classifiaction (think “oh, I’m in that weird part of youtube again”) but how do you use it. Authors of the DeepWalk paper compared several approaches and the best turned out to be a trick involving word2vec that they invented. This time the role of a word is played by a node in the graph (a youtube video). What plays the role of a sentence? For that a collection of short random walks on the graph is constructed - starting at every node of the graph. Think about what happens when a youtube video ends and another one starts playing, and then another one and another. Do this a few times for every video on youtube and you have a corpus of texts. Authors of the paper applied word2vec to those sequences to get vector embeddings for videos and then used these vectors as features in classification. It worked better then all other approaches - even ones that use global features of the graph. Awesome.

Update July 2016
I have tried this very algorithm on the graph of UK and Irish companies, here are the results

#### Frequent itemsets / collaborative filtering

Update July 2016
Called it. People are totally doing that now here and here. I don’t know why in the above text I fixated on frequent itemsets - which is just a specific, outdated way of doing collaborative filtering.

If you know of any other cool applications of topic modeling to non-NLP problems let me know.

If you want to play with topic models yourself I wholehartedly recommend gensim. I tried also MLLib but its word2vec implementation required 3 times as much RAM (for each of 10 cores I used) and still was about ten times slower than gensim.

# Lead Scoring Without Negative Examples

How do you train a binary classifier when you have only positive-labeled training examples? Impossible? Maybe. But sometimes you can do something just as good. Let’s start from the beginning…

Everyone and their mum in the b2b sector is trying to use machine learning for lead generation. For our purposes lead-gen means selecting from the millions of active companies in your country the ones that are most likely to buy your product once contacted by your sales team. Needless to say lead generation is extremely serious business and constitutes a market sector in its own right - a type of b2b2b if you will.

One popular lead-gen strategy is to look for leads among companies similar the ones that have worked out for you in the past. A machine learning implementation of this strategy is straightforward:

1. collect data on all relevant companies
2. take all the companies your sales have contacted in the past and label every one as either successful (you made money) or failed (you wasted your time) lead. This is your training set.
3. extract good features for every company*
4. train a binary classifier (predicting successful/failed label) on your training set. Ideally this should be a classifier that outputs probabilities.
5. apply the classifier to all the companies outside the training set and hand the results over to sales. The number assigned by the classifier to a given company is (in theory at least) the probability that the lead will be successful. Highest scorers should be prioritized, low scorers should be left alone. So far, so good.

### Forgetting salesman problem

An interesting difficulty frequently arises when you try to apply this approach in real life. Sales teams usually have good records on their clients but often fail to keep track of all the prospects that didn’t work out. As a result, you end up with only positive examples to train your classifier on. It’s not possible in general to train a classifier on a training set with one class amputated this way. But…

### The solution

TL;DR = divide density of “good points” by density of all - this is the lead score

Keep in mind that:

• in addition to the positive examples, you have also the full set of all data points (all companies whether previously contacted or not)
• you are not interested in the absolute probability of success of a given lead per se. You only really need the relative ranking of different leads. All the classifier scores may be off by a factor of 10 but as long as the order is preserved - you’ll still be able to prioritize good leads over rubbish ones.

A solution will present itself once the problem is stated in mathematical terms. Consider the space of all possible company features $X$. Given are:

• a set $C$ of points in $X$ - all companies
• a subset $T_+$ of the above set - companies that were tested and gave positive result Unknown are:

• the probability $f(x)$ that a company $x$ will test positive
• the subset $T$ of all tested companies

This is how it looks in an artificial 1-D dataset.

Notice that the distribution of companies $C$ and the conversion probability $f$ peak at different points and the distribution of positive exmaples $T_+$ peaks somewhere between those two.

It’s useful to think of $C$ as a sample from some probabilty distribution $P(x)$ defined on $X$. Or to express the same in the language of point densities in space:

If the companies tested $T$ were chosen at random from all companies $C$ then they constitute a sample from the same probability distribution $P(x)$

Since a company’s chance of testing positive is $f$, the density of companies that tested positive is simply:

The set $T$ is hidden from us but $C$ and $T_+$ are available so we can use them to find $f(x)$. Combining the first and third equation we get:

This is it. If we can just estimate the densities of $C$ and $T_+$ - we’re golden. Their ratio gives the $f$ function up to a constant, which is all we need to do lead scoring. There are many ways to do density estimation in practice:

• histogram based estimation - lowest on the sophistication scale - divide the space $X$ into sectors and count the number of points in every sector, divide it by volume. Do it for both $C$ and $T_+$ and divide one result by the other
• nearest neighbour estimation - for any interesting point find $k$ (let’s say $k=20$) nearest points in $C$. Count how many of them are also in $T_+$, divide the figures
• kernel based estimation - in a way this is similar to the knn version - except instead of taking k nearest points you take all of them but discount the farthest by a dicreasing function of distance

This is how it looks on our toy dataset:

Unsuprisingly, on a toy model everything works rather well. In reality conversion rates are low, data is sparse, dimensionality is high and even the basic assumption “good lead means similar to what has worked in the past” is questionable. But you have to start somewhere.

This is my first post. pls work pls This is code span (hopefully) def fibo(n): if n < 2: return 1 else: return fibo(n - 1) + fibo(n - 2)


text:
## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Time for action – adding a dedication and an appendix

Our book shall begin with a dedication. The front matter shall consist of the table of contents, lists of tables and figures, and a dedication. All the pages of the front matter shall be numbered with Roman letters. Finally, we add an appendix providing supplementary proofs which we like to present outside the main chapters:

1. Create a file dedication.tex:
\chapter{Dedication}
This book is dedicated to one of the greatest mathematicians of
all time: Carl Friedrich Gauss. Without him, this book wouldn't
have been possible.
2. Create a file proofs.tex:
\chapter{Proofs}
...
3. Extend the main file equation.tex by the highlighted lines:
\documentclass{book}
\input{preamble}
\begin{document}
\frontmatter
\include{dedication} ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required

format: plain


text:
# The Speedup Test

* Auteur correspondant
2 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Numerous code optimisation methods are usually experimented by doing multiple observations of the initial and the optimised executions times in order to declare a speedup. Even with fixed input and execution environment, programs executions times vary in general. So hence different kinds of speedups may be reported: the speedup of the average execution time, the speedup of the minimal execution time, the speedup of the median, etc. Many published speedups in the literature are observations of a set of experiments. In order to improve the reproducibility of the experimental results, this technical report presents a rigorous statistical methodology regarding program performance analysis. We rely on well known statistical tests (Shapiro-wilk's test, Fisher's F-test, Student's t-test, Kolmogorov-Smirnov's test, Wilcoxon-Mann-Whitney's test) to study if the observed speedups are statistically significant or not. By fixing $0<\alpha<1$ a desired risk level, we are able to analyse the statistical significance of the average execution time as well as the median. We can also check if $\prob{X>Y}>\frac{1}{2}$, the probability that an individual execution of the optimised code is faster than the individual execution of the initial code. Our methodology defines a consistent improvement compared to the usual performance analysis method in high performance computing as in \cite{Jain:1991:ACS,lilja:book}. We explain in each situation what are the hypothesis that must be checked to declare a correct risk level for the statistics. The Speedup-Test protocol certifying the observed speedups with rigorous statistics is implemented and distributed as an open source tool based on R software.
Keywords :
Type de document :
Rapport
[Technical Report] 2010, pp.38
Domaine :

https://hal.inria.fr/inria-00443839
Contributeur : Sid Touati <>
Soumis le : mardi 26 janvier 2010 - 08:31:41
Dernière modification le : jeudi 9 février 2017 - 15:53:47
Document(s) archivé(s) le : mercredi 30 novembre 2016 - 11:36:03

### Fichiers

SpeedupTestDocument.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00443839, version 2

### Citation

Sid Touati, Julien Worms, Sébastien Briais. The Speedup Test. [Technical Report] 2010, pp.38. <inria-00443839v2>

Consultations de
la notice

## 1339

Téléchargements du document


text:
## Taiwanese Journal of Mathematics

### ON PERTURBATION OF $\alpha$-TIMES INTEGRATED $C$-SEMIGROUPS

Chung-Cheng Kuo

#### Abstract

Let $\alpha \geq 0$, and $C$ be a bounded linear injection on a complex Banach space $X$. We first show that if $A$ generates an exponentially bounded nondegenerate $\alpha$-times integrated $C$-semigroup $S_{\alpha}(\cdot)$ on $X$, $B$ is a bounded linear operator on $\overline{D(A)}$ such that $BC = CB$ on $\overline{D(A)}$ and $BA \subset AB$, then $A+B$ generates an exponentially bounded nondegenerate $\alpha$-times integrated $C$-semigroup $T_{\alpha}(\cdot)$ on $X$. Moreover, $T_{\alpha}(\cdot)$ is also exponentially Lipschitz continuous or norm continuous if $S_{\alpha}(\cdot)$ is. We show that the exponential boundedness of $T_{\alpha}(\cdot)$ can be deleted and $\alpha$-times integrated $C$-semigroups can be extended to the context of local $\alpha$-times integrated $C$-semigroups when $R(C) \subset \overline{D(A)}$ and $BS_{\alpha}(\cdot) = S_{\alpha}(\cdot)B$ on $\overline{D(A)}$ both are added. Moreover, $T_{\alpha}(\cdot)$ is also locally Lipschitz continuous or norm continuous if $S_{\alpha}(\cdot)$ is. We show that $A+B$ generates a nondegenerate local $\alpha$-times integrated $C$-semigroup $T_{\alpha}(\cdot)$ on $X$ if $A$ generates a nondegenerate local $\alpha$-times integrated $C$-semigroup $S_{\alpha}(\cdot)$ on $X$ and $B$ is a bounded linear operator on $X$ such that either $BC = CB$, $BS_{\alpha} = S_{\alpha}B$ on $X$; or $BC = CB$ on $\overline{D(A)}$ and $BA \subset AB$. Moreover, $T_{\alpha}(\cdot)$ is also locally Lipschitz continuous, (norm continuous, exponentially bounded or exponentially Lipschitz continuous) if $S_{\alpha}(\cdot)$ is.

#### Article information

Source
Taiwanese J. Math., Volume 14, Number 5 (2010), 1979-1992.

Dates
First available in Project Euclid: 18 July 2017

Permanent link to this document
https://projecteuclid.org/euclid.twjm/1500406027

Digital Object Identifier
doi:10.11650/twjm/1500406027

Mathematical Reviews number (MathSciNet)
MR2724144

Zentralblatt MATH identifier
1239.47037

#### Citation

Kuo, Chung-Cheng. ON PERTURBATION OF $\alpha$-TIMES INTEGRATED $C$-SEMIGROUPS. Taiwanese J. Math. 14 (2010), no. 5, 1979--1992. doi:10.11650/twjm/1500406027. https://projecteuclid.org/euclid.twjm/1500406027

#### References

• [1.] W. Arendt, C. J. K. Batty, H. Hieber and F. Neubrander, Vector-Valued Laplace Transformes and Cauchy Problem, Birkhauser Verlag, Basel-Boston-Berlin, 2001, p. 96.
• [2.] R. DeLaubenfuls, Integrated Semigroups, $\tC$-Semigroups and the Abstract Cauchy Problem, Semigroup Forum, 41 (1990), 83-95.
• [3.] M. Hieber, Integrated Semigroups and Differential Operators on $\tL^p$ Spaces, Math. Ann., 291 (1991), 1-16.
• [4.] M. Hieber, Laplace Transforms and $\alpha$-Times Integrated Semigroups, Forum Math., 3 (1991), 595-612.
• [5.] H. Kellerman and M. Hieber, Integrated Semigroups, J. Funct. Anal., 84 (1989), 160-180.
• [6.] C.-C. Kuo and S.-Y. Shaw, On $\alpha$-Times Integrated $\tC$-Semigroups and the Abstract Cauchy Problem, Studia Math., 142 (2000), 201-217.
• [7.] C.-C. Kuo and S.-Y. Shaw, On Strong and Weak Solutions of Abstract Cauchy Problem, J. Concrete and Applicable Math., 2 (2004), 191-212.
• [8.] M. Li and Q. Zheng, $\alpha$-Times Integrated Semigroups: Local and Global, Studia Math., 154 (2003), 243-252.
• [9.] Y.-C. Li and S.-Y. Shaw, N-Times Integrated $\tC$-Semigroups and the Abstract Cauchy Problem, Taiwanese J. Math., 1 (1997), 75-102.
• [10.] Y.-C. Li and S.-Y. Shaw, Perturbation of Non-exponentially-Bounded $\alpha$-Times Integrated $\tC$-Semigroups, J. Math. Soc. Japan, 55 (2003), 1115-1136.
• [11.] Y.-C. Li and S.-Y. Shaw, On Local $\alpha$-Times Integrated C-Semigroups, Abstract and Applied Anal. Vol. 2007, Article ID34890, 18 pages.
• [12.] M. Mijatović and S. Pilipović, $\alpha$-Times Integrated Semigroups ($\alpha\in\Bbb R^+$), J. Math. Anal. Appl., 210 (1997), 790-803.
• [13.] I. Miyadera, M. Okubo and N. Tanaka, On Integrated Semigroups where are not Exponentially Bounded, Proc. Japan Acad., 69 (1993), 199-204.
• [14.] F. Neubrander, Integrated Semigroups and their Applications to the Abstract Cauchy Problem, Pacific J. Math., 135 (1988), 111-155.
• [15.] F. Neubrander, Integrated Semigroups and their Applications to Complete Second Order Cauchy Problems, Semigroup Forum, 38 (1989), 233-251.
• [16.] S. Nicasie, The Hille-Yosida and Trotter-Kato, Theorems for Integrated Semigroups, J. Math. Anal. Appl., 180 (1993), 303-316.
• [17.] S.-Y. Shaw and C.-C. Kuo, Generation of Local $\tC$-Semigroups and Solvability of the Abstract Cauchy Problems, Taiwanese J. Math., 9 (2005), 291-311.
• [18.] N. Tanaka, On Perturbation Theorey for Exponentially Bounded $\tC$-Semigroups, Semigroup Forum, 41 (1990), 215-236.
• [19.] T.-J. Xiao and J. Liang, The Cauchy Problem for Higher-Order Abstract Differential Equations, Lectures Notes in Math. 1701, Springer, 1998.
• [20.] T.-J. Xiao and J. Liang, Approximations of Laplace Transforms and Integrated Semigroups, J. Funct. Anal., 172 (2000), 202-220.
• [21.] Q. Zheng, Perturbations and Approximations of Integrated Semigroups, Acta Math. Sci., 9 (1993), 252-260.


text:
# Is the common formulation for (Ising Model) Monte Carlo simulations a bit off?

A common [Ising Model] Monte Carlo simulation repeats the following algorithm:

1. randomly pick a [flip] event
2. compute change in energy $$\Delta E$$
3. if new energy is lower than old energy, accept the change. Otherwise, accept the change with probability $$\exp(-\Delta E/kT)$$

In this formulation, all “downhill” energy moves are treated the same (occur with equal probability). In a physical system, wouldn’t larger “downhill” events occur more frequently? An easy reformulation that better matches with my expectations about a real system would be:

1. if new energy is lower than old energy, accept the change with probability $$1 - \exp(-|\Delta E|/kT)$$. Otherwise, accept the change with probability $$\exp(-|\Delta E|/kT)$$.

The thinking is that if an event has a probability $$p$$ of going to a higher energy state due to thermal energy, then it should have a probability of $$1-p$$ of staying in a higher energy state due to thermal energy.

• You might be interested in Glauber dynamics, which is a way of simulating the Ising model that's maybe more in line with your intuition. But the real answer is in the comments under Norbert Schuch's answer: the goal of Metropolis-Hastings and most related algorithms is not to simulate the physical dynamics at all, but to create an ersatz system that's known to have the same equilibrium distribution, so that we can sample from it. Traditionally we only care about the equilibrium distribution, so we want it to converge as fast as possible. Apr 4 at 23:27

The goal of any sampling algorithm has to be that it is unbiased -- i.e., the random walk it describes is in a configuration $$\vec s$$ with relative probability $$e^{-E(\vec s)/kT}$$.

This is achieved by the standard Metropolis sampling you describe.

It is also achieved by any other random process where the ratio of probabilities to go from $$\vec s$$ to $$\vec r$$ vs. back satisfies $$\frac{p_{\vec s\to \vec r}}{p_{\vec r\to\vec s}} = \frac{e^{-E(\vec r)/kT}}{e^{-E(\vec s)/kT}}\ , \tag{*}$$ the so-called "detailed balance" condition.

In particular, you could choose the transition probabilities equal to $$e^{-E(\vec r)/kT}$$ and $$e^{-E(\vec s)/kT}$$, respectively. This is not the formula you give (which will not work), but maybe more along the lines of your intuition.

Now why don't we choose the probabilities as above? Well, we want to maximize the probability for a move to be accepted (otherwise, we have to take far more samples), keeping the detailed balance condition (*). Thus, it is best to rescale the transition probabilities as much as possible -- that is, until the larger of them becomes equal to 1. This is precisely what the standard Metropolis update, as you describe it at the beginning of your question, does.

• Thank you for the explanation. There is still the conflict with my intuition that a larger drop in energy would occur more frequently than a smaller one. If my intuition holds, than it would only be appropriate to use the Metropolis update if all energy changes were of equal magnitude. Otherwise, only the largest possible energy drop ought to be assigned a probability of 1, and all others, including those that do reach a lower energy state but with less magnitude than a maximal change, should have an appropriately scaled probability. Can you explain why not? Apr 3 at 20:53
• In other words, can we say anything about $\frac{p_{\vec r\to \vec s}}{p_{\vec r\to\vec t}}$ if $\vec s$ is a lower energy state than $\vec t$? The treatment I outlined in the question says it's $1$ as long as both $\vec s$ and $\vec t$ are lower energy than $\vec r$. Apr 3 at 21:25
• @EricStimpson A larger drop in energy does happen (get sampled) more often than a smaller one. To make the discussion less confusing, let's name some states -- we're in state A now, B is a little lower energy, and C is much lower energy. If I go A -> B, then sometimes I go B -> C next step. But if I go A -> C, I almost never go C -> B next step. So I'm much more likely to be in C than B a little bit from now. Apr 4 at 14:09
• @EricStimpson: It's important to remember that the goal of a Monte Carlo "simulation" is not to accurately simulate the dynamics of a system; it's to generate a Boltzmann-distributed sample of states. Schroeder puts this nicely in his Introduction to Thermal Physics: "It is tempting to imagine that you are watching a simulation of what really happens in the magnet, as the dipoles change their alignments back and forth with the passage of time. ... Apr 4 at 15:11
• "But please remember that we have made no attempt to simulate the real time-dependent behavior of a magnet. Instead we have implemented a 'pseudodynamics,' which flips only one dipole at a time and otherwise ignores the true time-dependent dynamics of the system. The only realistic property of our pseudodynamics is that it generates states with probabilities proportional to their Boltzmann factors, just as the real dynamics of a magnet presumably does." Apr 4 at 15:11


text:
# How do I use cluster analysis in creating a model?

I have a training data set that I've done some cluster analysis on using R's pvclust package. I have a dendrogram of the results and am currently looking for the best way to use the information to create a model(s) of the data. Can anyone recommend a resource to walk me thru the process of going from clustering to predictive model? In other words, how do I read a dendrogram to make the most appropriate model(s).

-
 Some clarification might be helpful. You say want to build a 'predictive model', what is it you want to predict? Also, what constitute the data that went into the CA? A set of explanatory variables, a set of response variables, all the variables you had access to, etc. – gung Nov 18 '11 at 22:09 The training data was missing the variable I wanted to predict (a credit event/failure) and I ran the CA on everything else (age, income, lateness, etc.) The dendrogram normalized the data so that it is on a 0-3 scale. I'm trying to understand what the dendrogram means. I basically want to create a model that better predicts whether a person will have a credit failure. – screechOwl Nov 18 '11 at 22:50


text:
it came, it went! all the old ASMT stuff is here
Kil
Posts: 13
Joined: 13 years ago

UPDATE: All OW music is finally done http://www.youtube.com/watch?v=oVeZ_vDvWyQ

I'm going to update the first post with this list and actually attempt to update it based on people's suggestions. If you do have a suggestion, suggest both where the music could be used, and the music itself. It doesn't really do any good having a bunch of music that we don't know what to do with.

Want custom music in your hack but don't know which to use? Here are some suggestions from other users. Also try checking SMWC's custom music section. In addition, try checking this large list: http://ice.pac.am/music.php

Song suggestions from other users:

Cutscenes
-
General/Unknown
- http://www.youtube.com/watch?v=h-voDR0m9jk (Taiyo School Rooftop, Project Justice)
-
Boss music
- http://www.youtube.com/watch?v=ZqIZ2n5sROk (Through the Fire and Flames)
-
Ghost House Music
- http://www.vgmusic.com/music/console/ni ... At_Sea.mid
-
Grasslands Level Music
-
Beach Level Music
- http://imuse.mixnmojo.com/media/Midi/Monkeys/intro1.mid
-
Forest Level Music
-
Sky Level Music
-
Ice Level Music
Volcano Level Music
-
Cave Music
- http://ice.pac.am/song.php?id=144
-
Castle Level Music
- http://midi.thehylia.com/midifiles/drea ... orders.mid (Holy Orders)
- http://www.youtube.com/watch?v=m-8D4fwxyiw (Gundam Wing: Endless Duel - Heavyarms Stage)
-

If you have a song you'd like to add to your level (and you are actually signed up for the level already on the official signup list), I am willing to try and convert it for you

Songs that are being worked on:
Grasslands OW: prsnth111

Original music we have so far:
Dusty Desert: http://www.youtube.com/watch?v=uDOGIbPt45I (disowned by Kil)
Ice world: http://omohide.com/iceworld.mp3 (by prsnth111)

Music files list:
http://www.sendspace.com/file/ubidw4 (Volcano Area)
http://www.sendspace.com/file/j8ail8 (A thing)
http://www.sendspace.com/file/lki65u (Suishou)

I've seen a couple of people talking about custom music, but found no centralized thread to talk about it in

smwcentral's custom music list:
http://www.smwcentral.net/?p=list&type=music

If you have questions about how to get addmusic to work (it's a giant pain), I can probably answer them

Quick Music Insertion Guide

It's kind of a pain to use addmusic at first. There are some detailed instructions in the first post of this thread, but here are some quick ones off the top of my head, although it's still a lot

1. Make a backup of your ROM in case something goes terribly wrong
3. For convenience extract it to where your rom is located
4. Go to your Start Menu -> Accessories and find Command Prompt
5. Right click it and drag the command prompt into the folder with the rom and addmusic and choose "copy here"
6. Open the command prompt we placed in this folder and type addmusic [your rom name].smc init
7. Now a file called addmusic.ini should have been created in that same directory with everything else
8. Open this addmusic.ini and go down to where it says [LEVEL] and "20=". This is a good place to put your first imported song, so type cirno.txt after 20= (should read 20=cirno.txt) and save addmusic.ini
9. Now, you don't actually have cirno.txt yet. Download the zip attached to this post, take cirno.txt out of the zip, and place it in the folder called LEVEL in the same directory as everything else.

AllSongs.zip
Contains all songs up to cirno.txt

10. Now open command prompt again, this time type "addmusic [your rom name].smc LEVEL". Various data should rush past on the prompt, and at the end it should say that the music was successfully inserted. If not, we messed up somewhere else.
11.Now open your rom with lunar magic and go to your level. Go to the music setting (the music block icon) and scroll down to 20. The word Cirno should be displayed next to 20 if everything went right. Set it to 20, save the rom, and that's it. The music should now work in game.

to insert other songs, just repeat steps 8 through 11 with other files, and use [LEVEL] numbers 21= and onward

Do you make custom music?

1) This list of direct spc commands may be helpful to you. The list part is in English http://d.hatena.ne.jp/GOCHA/20070428/smwmusicspec

2) Here's some info about sound effects. Avoid using these channels if possible, or place unimportant parts on them.

The channels reserved for the sound effects:
$1DF9: channel 5$1DFC: channel 7 (Use this channel last when making overworld music)
\$1DFA: channel 8

Anyway, if you made some music, post it here.
Last edited by Kil 13 years ago, edited 55 times in total.
ShodanWiiReture
Posts: 0
Joined: 13 years ago

I'm good at inserting music into roms. I can help with that if you want. But, I can't create or port. I can insert though. :-)
prsnth1111
Posts: 0
Joined: 13 years ago
Location: Toronto

I've done some original tunes for my levels so far

Here's one...

And I'm working on some for the overworlds rite now.
raekuul
2 Nephi 2:25-27
Posts: 1426
Joined: 13 years ago
First name: Pokota
Pronouns: he/him/his
Location: Melnath's Shoulder
Contact:

Here's a handful of MIDIs that I have on my laptop, if anyone can do anything with them. Please note that I didn't actually make any of these.
Games Beaten In 2020, 2021, 2022
Garlyle
Posts: 163
Joined: 13 years ago

So then, custom music is allowed? Just custom stuff, or can we, ah, borrow?
Help! pawprint
Posts: 152
Joined: 13 years ago
Pronouns: he/him/his
Location: Sweden

No, you don't need to create the music for your level yourself. Using music from SMWC is completely permitted. Though you don't need to worry about that yet, as I won't be collecting the music for insertion until I have all the levels ready.
Kil
Posts: 13
Joined: 13 years ago

prsnth1111 wrote:I've done some original tunes for my levels so far

Here's one...

And I'm working on some for the overworlds rite now.
This is a great tune. Actually when I heard this in the other topic, it motivated me to start this thread.
prsnth1111
Posts: 0
Joined: 13 years ago
Location: Toronto

Why thank you ;)
Kil
Posts: 13
Joined: 13 years ago

raekuul wrote:Here's a handful of MIDIs that I have on my laptop, if anyone can do anything with them. Please note that I didn't actually make any of these.
It is possible is convert midis using tinymml, but it honestly doesn't work too well, and requires tons of work after the fact. Unless there's a song you really really want, I would suggest just taking pre-made music from smwcentral or here. Even then, it'll probably take a good 15-30 minutes just to get the music inserted into your rom...
SeaThief
Posts: 0
Joined: 13 years ago

Kil wrote:If you have questions about how to get addmusic to work (it's a giant pain), I can probably answer them
Tell me about it. I'm trying to figure out how to port songs (I've been meaning to learn for a while but didn't get the inspiration to start until now), but it's tricky. For one, the song I'm trying to port right now as an experiment is looping early at :36 instead of 1:00, and I have no idea if the problem is in addmusic (using Carol's 1.22), in tinymm, or in the midi I started with.

There's also octaves and instruments to be fiddled with, but those I can figure out on my own.
prsnth1111
Posts: 0
Joined: 13 years ago
Location: Toronto

It would be a lot easier if we could, you know, see the code. There is rarely ever a problem with addmusic if used correctly. Problems are pretty much always due to the coding in the .txt file. Converting from midi is already sketchy.
Kil
Posts: 13
Joined: 13 years ago

Yeah the code would help. Early looping could mean one of the channels simply isn't as long as the others. The song will loop as soon as any channel runs out of song data. So if I have a 2 minute song and add a channel of drums that lasts for 5 seconds, the song will end up just being 5 seconds long and looping right as the drum channel runs out of data over and over.

The code probably isn't that big so it should be okay to just paste it in this thread.
SeaThief
Posts: 0
Joined: 13 years ago

Okay then, here you go: (those line breaks were just spaces in the txt file I have, let me know if it's a problem)

http://pastebin.com/d17e45b00

If you're curious, it's supposed to be a port of Axel Almer's theme from Super Robot Wars Advance. Incidentally I checked SMW Central and it doesn't seem to have a single song from Super Robot Wars. Considering how much most SRW fans love the music, that's really surprising.
Kil
Posts: 13
Joined: 13 years ago

I removed all the instruments except #0 and was able to hear the song go on for longer than usual, so yeah, one of the channels is probably ending early. This should be fixable by adding rests to the short channels. I'll fiddle around with it.

--

;title=Dark Knight - Axel Almer
#0 w220 t67

#0 @4 q7f v125 y10
#1 @11 q7f v110 y10
#2 @4 q7f v125 y10
#3 @8 q7f v125 y10
#4 @9 q7f v125 y10
#5 @10 q7f v125 y10
#6 @11 q7f v125 y10
#7 @16 q7f v125 y10

#0
o3r4^8
>c+8f+8a8g+8e8^16
r4^16c+8f+8a8g+8e8
r4^8f+8d8a8g+8d8
r4^8g+8e8b8a8g+8
r4^8c+8f+8a8g+8e8
r4^8c+8f+8a8g+8e8
r4^8f+8d8a8g+8d8
b2r2^4
<f+16^32r32c+16^32r32e16^32r32e32r32f+16^32r32f+32r32f+16^32r32
f+8^16^32r32f+16^32r32e16^32r32e16^32r32f+16^32r32e16^32r32c+2^4^16^32
r32c+16^32r1^4^8^32
f+16^32r32c+16^32r32e16^32r32f+16^32r32a16^32r32f+16^32r32
g+16^32r32g+16^32r32>c+16^32r32c+16^32r32e16^32r32e16^32r32g+16^32r32g+1^2^16^32
r2^4^32
<f+8c+8e8e16f+8f+16a8
f+4f+8e8e8f+8e8c+1
r1^4^8
f+16^32r32c+16^32r32e16^32r32f+16^32r32a16^32r32f+16^32r32
g+16^32r32g+16^32r32>c+16^32r32c+16^32r32e16^32r32e16^32r32g+16^32r32g+1^2^16^32
r2^32
d16^32r32<b16^32r32>d16^32r32<b16^32r32b16^32r32a16^32r32a16^32r32g+4^16^32
r32g+16^32r32>c+4^16^32r32c+16^32r8^32
<a16^32r32a16^32r32a16^32r32a16^32r32a16^32r32g+16^32r32g+16^32r32f+4^8^16^32
r32f+16^32r32d16^32r32d16^32r32f+16^32r32f+16^32r32
f4^16^32r32f16^32r32f16^32r32f+16^32r32g+16^32r32f+4^16^32
r32f+16^32r8^32f+16^32r32g+16^32r32a16^32r32g+4^16^32
r32g+16^32r8^32f+16^32r32g+16^32r32f+16^32r32b4^16^32
r32>e16^32r32c+4^16^32r32f16^32r8^32
c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+16^32r32e8^16^32
r32e16^32r32f+16^32r32e16^32r32g+16^32r32c+16^32r32c+16^32r32e32r16^32
c+32r32<b32r32>c+32r16^32c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+16^32r32f+8^16^32
r32f+16^32r32a16^32r32f+16^32r32f+16^32r32e16^32r32g+16^32r32f+32r16^32
c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32e16^32r32e8^16^32
r32g+16^32r32e16^32r32e16^32r32g+16^32r32c+16^32r32c+16^32r32e16^32r32
<a16^32r32a16^32r32a16^32r32b8^16^32r32b16^32r32b16^32r32a+2^4^8^16^32
r32>f+16^32;

#1o4r4^8
>c+8f+8a8g+8
e4r4^16c+8f+8a8g+8
e8r4^8f+8d8a8g+8
d8r4^8g+8e8b8a8
g+8r4^8c+8f+8a8g+8
e8r4^8c+8f+8a8g+8
e8r4^8f+8d8a8g+8
d8b2r2^4
@4<f+16^32r32c+16^32r32e16^32r32e32r32f+16^32r32f+32r32
f+16^32r32f+8^16^32r32f+16^32r32e16^32r32e16^32r32f+16^32r32e16^32r32
c+2^4^16^32r32c+16^32r1^4^8^32
f+16^32r32c+16^32r32e16^32r32f+16^32r32a16^32r32
f+16^32r32g+16^32r32g+16^32r32>c+16^32r32c+16^32r32e16^32r32e16^32r32g+16^32r32
g+1^2^16^32
r2^4^32
<f+8c+8e8e16f+8f+16
a8f+4f+8e8e8f+8e8
c+1
r1^4^8
f+16^32r32c+16^32r32e16^32r32f+16^32r32a16^32r32
f+16^32r32g+16^32r32g+16^32r32>c+16^32r32c+16^32r32e16^32r32e16^32r32g+16^32r32
g+1^2^16^32
r2^32
d16^32r32<b16^32r32>d16^32r32<b16^32r32b16^32r32a16^32r32a16^32r32
g+4^16^32r32g+16^32r32>c+4^16^32r32c+16^32r8^32
<a16^32r32a16^32r32a16^32r32a16^32r32a16^32r32g+16^32r32g+16^32r32
f+4^8^16^32r32f+16^32r32d16^32r32d16^32r32f+16^32r32
f+16^32r32f4^16^32r32f16^32r32f16^32r32f+16^32r32g+16^32r32
f+4^16^32r32f+16^32r8^32f+16^32r32g+16^32r32a16^32r32
g+4^16^32r32g+16^32r8^32f+16^32r32g+16^32r32f+16^32r32
b4^16^32r32>e16^32r32c+4^16^32r32f16^32r8^32
c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+16^32r32
e8^16^32r32e16^32r32f+16^32r32e16^32r32g+16^32r32c+16^32r32c+16^32r32
e32r16^32c+32r32<b32r32>c+32r16^32c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+16^32r32
f+8^16^32r32f+16^32r32a16^32r32f+16^32r32f+16^32r32e16^32r32g+16^32r32
f+32r16^32c+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32f+32r32<b32r32>c+32r16^32e16^32r32
e8^16^32r32g+16^32r32e16^32r32e16^32r32g+16^32r32c+16^32r32c+16^32r32
e16^32r32<a16^32r32a16^32r32a16^32r32b8^16^32r32b16^32r32b16^32r32
a+2^4^8^16^32 [r1^1]48;

#2o3f+4f+16r16f+8r8f+8r8f+8
f+4f+16r16f+8r8f+8r8f+8
d4d16r16d8r8d8r8d8
e4e16r16e8r8e8r8e8
f+4f+16r16f+8r8f+8r8f+8
f+4f+16r16f+8r8f+8r8f+8
d4d16r16d8r8d8r8d8
e4^8r8>e4^8r8
<f+8r8f+8r8f+8r8f+8d4^8
d16r16e4^8e16r16f+4
f+16r16f+8r8f+8r8f+8f+4
f+16r16f+8r8f+8r8f+8<f+4
f+16r16>f+8r8f+8r8f+8e4
e16r16e8r8e8r8e8c+4
c+16r16c+8r8c+8r8c+8c+4
c+16r16c+8r8>c+8r8c+8r8
<f+8r8f+8r8f+8r8f+8d4^8
d16r16e4^8e16r16f+4
f+16r16f+8r8f+8r8f+8f+4
f+16r16f+8r8f+8r8f+8<f+4
f+16r16>f+8r8f+8r8f+8e4
e16r16e8r8e8r8e8c+4
c+16r16c+8r8c+8r8c+8c+4
c+16r16c+8r8>c+8r8<c+4
g8>g8r8<f+8r8e8r8g+4
g+8>g+8<e4g+8>e8b8
<e8e8r8f8r8f8r8f+4
f+8f+8r8d8r8f+8r8
f8r8f8r8f8r8f8d4
d16r16d8r8d8r8d8d+4
d+16r16d+8r8d+8r8d+8e4
e16r16e8r8<b8>c+4r8
<f+4>c+8f+8a8g+8e16r16d4
d16r16d8e4e8>c+8<e8
<f+4>c+8f+8a8g+8e16r16d4^8
d16r16e4e16r16e4
<f+4>c+8f+8a8g+8e16r16d4^8
d16r16e4e16r16e8>c+8
<d8f+8a8e4e8b8>c+4^8
<f+8r8f+8r8f+8 [r1^1]48;

#3
o3f+4f+16r16f+8r8f+8r8f+8
f+4f+16r16f+8r8f+8r8f+8
d4d16r16d8r8d8r8d8
e4e16r16e8r8e8r8e8
f+4f+16r16f+8r8f+8r8f+8
f+4f+16r16f+8r8f+8r8f+8
d4d16r16d8r8d8r8d8
e4^8r8>e4^8r8
<f+8r8f+8r8f+8r8f+8d4^8
d16r16e4^8e16r16f+4
f+16r16f+8r8f+8r8f+8f+4
f+16r16f+8r8f+8r8f+8<f+4
f+16r16>f+8r8f+8r8f+8e4
e16r16e8r8e8r8e8c+4
c+16r16c+8r8c+8r8c+8c+4
c+16r16c+8r8>c+8r8c+8r8
<f+8r8f+8r8f+8r8f+8d4^8
d16r16e4^8e16r16f+4
f+16r16f+8r8f+8r8f+8f+4
f+16r16f+8r8f+8r8f+8<f+4
f+16r16>f+8r8f+8r8f+8e4
e16r16e8r8e8r8e8c+4
c+16r16c+8r8c+8r8c+8c+4
c+16r16c+8r8>c+8r8<c+4
g8>g8r8<f+8r8e8r8g+4
g+8>g+8<e4g+8>e8b8
<e8e8r8f8r8f8r8f+4
f+8f+8r8d8r8f+8r8
f8r8f8r8f8r8f8d4
d16r16d8r8d8r8d8d+4
d+16r16d+8r8d+8r8d+8e4
e16r16e8r8<b8>c+4r8
<f+4>c+8f+8a8g+8e16r16d4
d16r16d8e4e8>c+8<e8
<f+4>c+8f+8a8g+8e16r16d4^8
d16r16e4e16r16e4
<f+4>c+8f+8a8g+8e16r16d4^8
d16r16e4e16r16e8>c+8
<d8f+8a8e4e8b8>c+4^8
<f+8r8f+8r8f+8 [r1^1]48;

#4
o4f+4^8c+8r2
f+4^8f+8r2
>d4^8d8r2
<b4^8>e8r2
<f+4^8c+8r2
f+4^8f+8r2
>d4^8d8r2
<b4^8>e8r1^1^4^8
o4f+4
c+8f+8>c+8f+8e8c+8<c+4
c+8f+8>c+8f+8e8c+8r1^1
<c+4
c+8f8g+8b8g+8b8>c+4
c+8f8g+8<b8g+8>c+4
r1^2^4^8
o4f+4
c+8f+8>c+8f+8e8c+8<c+4
c+8f+8>c+8f+8e8c+8r1^1
<c+4
c+8f8g+8b8g+8b8>c+4
c+8f8g+8<b8g+8>c+4
o4b16^32r32b16^32r32>d16^32r32<b16^32r32b16^32r32a16^32r32a16^32r32g+4^16^32
r32g+16^32r32>c+4^16^32r32c+16^32r8^32
<a16^32r32a16^32r32a16^32r32a16^32r32a16^32r32g+16^32r32g+16^32r32f+4^8^16^32
r32f+16^32r32d16^32r32d16^32r32f+16^32r32f+16^32r32
f4^16^32r32f16^32r32f16^32r32f+16^32r32g+16^32r32f+4^16^32
r32f+16^32r8^32f+16^32r32g+16^32r32a16^32r32g+4^16^32
r32g+16^32r8^32f+16^32r32g+16^32r32f+16^32r32b4^16^32
r32>e16^32r32c+4^16^32r32f16^32r4^32
f+32r32f+32r32c+32r32c+32r8^32e32r32e32r32a32r32a32r32a32r32a32r32<a8^16^32
r32>d32r32d32r32e32r32e32r32<b8^16^32r32>e32r32e32r32e32r32e32r32f+32r32b32r8^32
c+32r32f+32r32c+32r32c+32r8^32e32r32e32r32a32r32a32r32a32r32a32r32<a8^16^32
r32>d32r32d32r32e32r32e32r32e8^16^32r32g+32r32g+32r32e32r32e32r32b32r32b32r8^32
c+32r32f+32r32c+32r32c+32r8^32e32r32e32r32a32r32a32r32a32r32a32r32<a8^16^32
r32>d32r32d32r32e32r32e32r32e8^16^32r32g+32r32g+32r32e32r32e32r32b32r32b32r32
d4d8<b4a8b8a+4^8
a+16a+8r16a+16r16a+16r16a+16r16>f+16 [r1^1]48;

#5
<f+4^8<c+8>f+8a8g+8e8
<f+4^8f+8>f+8a8g+8e8
d4^8d8d8a8g+8d8
<b4^8>e8e8b8a8g+8
<f+4^8c+8>f+8a8g+8e8
<f+4^8f+8>f+8a8g+8e8
d4^8d8d8a8g+8d8
<b4^8>e8r1^1^4^8
<f+4
f+8>c+8f+8a8g+8e8f+4
f+8>c+8f+8a8g+8e8f+8
r1^2^4^8
c+4
c+8f8g+8b8g+8b8>c+4
c+8f8g+8b8g+8>c+4
r1^2^4^8
o3f+4
f+8>c+8f+8a8g+8e8f+4
f+8>c+8f+8a8g+8e8f+8
r1^2^4^8
c+4
c+8f8g+8b8g+8b8>c+4
c+8f8g+8b8g+8>c+4
r1^1^1^1^1^1^1^4
o5e16r16c+4^8r4
f+4>c+8f+8a8g+8e8d2
e2^8
<f+4>c+8f+8a8g+8e8d2
e2^8
<f+4>c+8f+8a8g+8e8d2
e2^8
<d8f+8a8e4g+8b8>c+2^8
<f+2

[r1^1]48
;

#6
<a4a16r16a16r8^16>c+16r16<a16r16f+16r16
a4a16r16a16r8^16>c+16r16<a16r16f+16r16
f+4f+16r16f+16r8^16f+16r8^16a16r16
b4b16r16b16r8^16>g+16r16<b16r16b16r16
>f+4<a16r16a16r8^16>c+16r16<a16r16f+16r16
a4a16r16a16r8^16>c+16r16<a16r16f+16r16
f+4f+16r16f+16r8^16f+16r8^16a16r16
>e4r8>e16c+16e16c+16<b16g+16e16c+16<b16g+16
e16r16a16r16a16r8^16a8r8f+16r16>d4
<a8>d16r16<g+4<b16r16>e16r16a4
>f+16<a16>c+16r16<a16r16a16r16<a32o4c+32f+32a32>c+32f+32c+32o4a32a4
>f+16r16<a16r8^16a16r8^16>f+8<a4
>f+16r16<a16r8^16a8r8f+16r16g+4
g+16g+16r8>e16<g+16r8g+16r16g+16r16f4
<c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o6g+32f32c+32<g+32f32c+32o4g+32f32c+32<g+32f3

2c+32o3g+32f32c+32<g+32o3c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o6g+32f32

c+32<g+32f32c+32o4g+32f32c+32<g+32f32c+32o3g+32f32c+32
o4e16r16a16r16a16r8^16a8r8f+16r16>d4
<a8>d16r16<g+4<b16r16>e16r16a4
>f+16<a16>c+16r16<a16r16a16r16<a32o4c+32f+32a32>c+32f+32c+32o4a32a4
>f+16r16<a16r8^16a16r8^16>f+8<a4>f+16r16<a16r8^16a8r8f+16r16g+4
g+16g+16r8>e16<g+16r8g+16r16g+16r16f4
<c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c+32<g+32f32c+32o4g+32f32c+32<g+32f3

2c+32o3g+32f32c+32
<g+32o3c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c+32<g+32f32c+32o4

g+32f32c+32<g+32f32c+32o3g+32f32c+32 [r1^1]48
;

#7
r8
f+4<a16r16a16r8^16>c+16r16<a16r16
f+16r16a4a16r16a16r8^16>c+16r16<a16r16
f+16r16f+4f+16r16f+16r8^16f+16r8^16
a16r16b4b16r16b16r8^16>g+16r16<b16r16
b16r16>f+4<a16r16a16r8^16>c+16r16<a16r16
f+16r16a4a16r16a16r8^16>c+16r16<a16r16
f+16r16f+4f+16r16f+16r8^16f+16r8^16
a16r16>e4r8>e16c+16e16c+16<b16g+16e16c+16
<b16g+16e16r16a16r16a16r8^16a8r8f+16r16
>d4<a8>d16r16<g+4<b16r16>e16r16
a4>f+16<a16>c+16r16<a16r16a16r16<a32o4c+32f+32a32>c+32f+32c+32o4a32
a4>f+16r16<a16r8^16a16r8^16>f+8
<a4>f+16r16<a16r8^16a8r8f+16r16
g+4g+16g+16r8>e16<g+16r8g+16r16g+16r16
f4<c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c+32<g+32f32c+32o4g+32f32c+32<g+32

f32
c+32o3g+32f32c+32<g+32o3c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c

+32<g+32f32c+32o4g+32f32c+32<g+32f32
c+32o3g+32f32c+32o4e16r16a16r16a16r8^16a8r8f+16r16
>d4<a8>d16r16<g+4<b16r16>e16r16
a4>f+16<a16>c+16r16<a16r16a16r16<a32o4c+32f+32a32>c+32f+32c+32o4a32
a4>f+16r16<a16r8^16a16r8^16>f+8
<a4>f+16r16<a16r8^16a8r8f+16r16
g+4g+16g+16r8>e16<g+16r8g+16r16g+16r16
f4<c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c+32<g+32f32c+32o4g+32f32c+32<g+32

f32
c+32o3g+32f32c+32<g+32o3c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32f32g+32o4c+32f32g+32>c+32o4g+32f32c

+32<g+32f32c+32o4g+32f32c+32<g+32f32
c+32o3g+32f32c+32 [r1^1]48;

This should work. I added [r1^1]48 to the end of every channel's data except channel 0, meaning whichever channel was short is now filled in with rests at the end. The song doesn't mess up though, because as soon as channel 0 ends, all those extra rests get discarded and the song should loop normally. I also changed some of the instrument numbers around so I could hear and diagnose the problem more easily. Don't forget to change those
SeaThief
Posts: 0
Joined: 13 years ago

Ah, okay, so that's how the length works. I messed around with it some and it looks like #6 and #7 were the culprits. I just set the instruments pretty much at random before, so don't worry about that. Also, wow, everything after ~:36 came out sounding terrible. That's probably because of how I tried to fix octave problems. I'll play around with this for a while longer to see if I can get a version that sounds better.
Dealth0072
Posts: 0
Joined: 13 years ago

Id like to request Cirnos Perfect math class.

Im working on the perfect level for it, with the perfect name.
Kil
Posts: 13
Joined: 13 years ago

I don't mind trying it but do you have a midi file of it? Gonna be impossible otherwise.
Chdata
Posts: 11
Joined: 13 years ago
Location: Computer Chair

Can you insert any type of music in the game as long as it's a midi file? I don't know anything about music hacking but it seems it has to be a midi?

Trouble with a capital COW.

$\tan{A}\sin{N}$
Help! pawprint
Posts: 152
Joined: 13 years ago
Pronouns: he/him/his
Location: Sweden

One thing to remember when porting music: Use loops whenever possible, and use the l command in every channel. Reducing the file size to save space in the ROM is always a good thing.

@chdata: You can't insert midi files directly, but there is a program that converts them (quite badly; they need a whole lot of touching up afterwards) to the .txt format that Addmusic recognizes.
Chdata
Posts: 11
Joined: 13 years ago
Location: Computer Chair

What is the program.
And what do you mean by touching up?

Trouble with a capital COW.

$\tan{A}\sin{N}$
Help! pawprint
Posts: 152
Joined: 13 years ago
Pronouns: he/him/his
Location: Sweden

yoshicookiezeus wrote:To insert music into an SMW hack, it NEEDS to be in a certain .txt format. There is a program that converts MIDI files to that format (called Tinymm, but it does it really badly and the files it outputs needs a lot of fixing (octave changing, looping to reduce file size, adding channel headers, et cetera). SMWC has a rather excellent tutorial on the subject, if anyone would like to try their hands at porting songs. (Just note that the part of the tutorial that is about the actual process of adding music to a ROM is kind of outdated.)
Help! pawprint
Posts: 152
Joined: 13 years ago
Pronouns: he/him/his
Location: Sweden

I kind of got inspired by prsnth1111's musical creations, and made this little remix of the SMW star theme. Is it good enough to use in the collab?

(In case you are unfamiliar with the file format, you need an SPC player such as WinSPC to play the file.)
prsnth1111
Posts: 0
Joined: 13 years ago
Location: Toronto

Is that what plays when you have a star powerup? I like the idea. It's a bit repetitive though, and how about beefing up the harmony? Maybe add some bass or strings, etc.
prsnth1111
Posts: 0
Joined: 13 years ago
Location: Toronto

so I've been working on the overworld music loops. Here's one for the water overworld. Thought it should be pleasant for the first overworld, relatively cheerful.

And for those who cant hear it, heres a recording with my mic, very bad quality
Kristian
Posts: 0
Joined: 13 years ago